FloodFill(漫水填充)算法

  在OpenCV里有一个函数,为cvFloodFill(IplImage* img, CvPoint seedPoint, CvScalar newVal,

cvScalar loDiff=cvScalarAll(0), cvScalar upDiff=cvScalarAll(0), CvConnectedComp* com=NULL,

int flags=4, CvArr* mask = NULL)

其中各参数的意义为:img指输入图像, seedPoint指种子像素坐标,newVal指用来填充区域的新颜色,loDiff和upDiff分别指与种子像素的值的上下差值。而com指填充的联通域信息指针,其成员变量包括面积大小和平均颜色等信息。flags是关键参数,它包含了填充的几种方式选择,如邻哉是4联通还是8联通,是否只填充掩码矩阵,以及掩码矩阵的掩码值(默认为1)

mask为掩码矩阵,它是即是一个输入参数也是一个输出参数。mask作为输入时只有掩码值为0的像素点有效,而输出时有填充的像素的坐标点上也相应的被掩码(掩码值由flags决定,默认为1)

  对于此函数所用的算法,并没有仔细去分析它的代码。而是认识了两种比较简单的算法。分别如下:
算法一:递归算法

void floodFill(int x, int y, int fill, int old)
{
  if ((x < 0) || (x >= width)) return;
  if ((y < 0) || (y >= height)) return;
  if (getPixel(x, y) == old)

  {
    setPixel(fill, x, y);
    floodFill(x+1, y, fill, old);
    floodFill(x, y+1, fill, old);
    floodFill(x-1, y, fill, old);
    floodFill(x, y-1, fill, old);
  }
}

8邻域的填充过种也是一样,此算法的过程简单易懂,效率也较高,但由于函数的反复调用会使操作系统的栈溢出。

算法二:基于行一致性的算法

(1)将种子点入栈;

while(栈非空)

{

(2)将种子点出栈;

(3)填充联通的此行;

(4)并将邻域内联通的上下行中的一行最右边的点作为种子点入栈;

}

此算法的缺点是会造成很多点的重复访问。

 

 

 

原文地址:https://www.cnblogs.com/seacode/p/1821574.html