简介
所谓漫水填充,简单来说,就是自动选中了和种子点相连的区域,接着将该区域替换成指定的颜色,这是个非常有用的功能,经常用来标记或者分离图像的一部分进行处理或分析.漫水填充也可以用来从输入图像获取掩码区域,掩码会加速处理过程,或者只处理掩码指定的像素点.
有这个填充算法为基础,类似photoshop的魔术棒选择工具就很容易实现了。漫水填充(FloodFill)是查找和种子点联通的颜色相同的点,魔术棒选择工具则是查找和种子点联通的颜色相近的点,将和初始种子点颜色相近的点压进栈作为新种子
本人认为该算法还能用于相对理想情况下的道路识别,实现汽车的无人驾驶.
部分代码
FloodFill
用指定颜色填充一个连接域 ,此处用了对比鲜明的红色和绿色作为填充色
void cvFloodFill( CvArr* image, CvPoint seed_point, CvScalar new_val,
CvScalar lo_diff=cvScalarAll(0), CvScalar up_diff=cvScalarAll(0),
CvConnectedComp* comp=NULL, int flags=4, CvArr* mask=NULL );
#define CV_FLOODFILL_FIXED_RANGE (1 << 16)
#define CV_FLOODFILL_MASK_ONLY (1 << 17)
image
输入的 1- 或 3-通道, 8-比特或浮点数图像。输入的图像将被函数的操作所改变,除非你选择 CV_FLOODFILL_MASK_ONLY 选项 (见下面).
seed_point
开始的种子点.
new_val
新的重新绘制的象素值
lo_diff
当前观察象素值与其部件领域象素或者待加入该部件的种子象素之负差(Lower difference)的最大值。对 8-比特 彩色图像,它是一个 packed value.
up_diff
当前观察象素值与其部件领域象素或者待加入该部件的种子象素之正差(upper difference)的最大值。 对 8-比特 彩色图像,它是一个 packed
value.
comp
指向部件结构体的指针,该结构体的内容由函数用重绘区域的信息填充。
flags
操作选项. 低位比特包含连通值, 4 (缺省) 或 8, 在函数执行连通过程中确定使用哪种邻域方式。高位比特可以是 0 或下面的开关选项的组合:
CV_FLOODFILL_FIXED_RANGE - 如果设置,则考虑当前象素与种子象素之间的差,否则考虑当前象素与其相邻象素的差。(范围是浮点数).
CV_FLOODFILL_MASK_ONLY - 如果设置,函数不填充原始图像 (忽略 new_val), 但填充掩模图像 (这种情况下 MASK 必须是非空的).
mask
运算掩模, 应该是单通道、8-比特图像, 长和宽上都比输入图像 image 大两个象素点。若非空,则函数使用且更新掩模, 所以使用者需对 mask 内容的初始化负责。填充不会经过 MASK 的非零象素, 例如,一个边缘检测子的输出可以用来作为 MASK 来阻止填充边缘。或者有可能在多次的函数调用中使用同一个 MASK,以保证填充的区域不会重叠。注意: 因为 MASK 比欲填充图像大,所以 mask 中与输入图像(x,y)像素点相对应的点具有(x+1,y+1)坐标。
函数 cvFloodFill 用指定颜色,从种子点开始填充一个连通域。连通性由象素值的接近程度来衡量。在点 (x, y) 的象素被认为是属于重新绘制的区域,如果:
src(x',y')-lo_diff<=src(x,y)<=src(x',y')+up_diff, 灰度图像,浮动范围
src(seed.x,seed.y)-lo<=src(x,y)<=src(seed.x,seed.y)+up_diff, 灰度图像,固定范围
src(x',y')r-lo_diffr<=src(x,y)r<=src(x',y')r+up_diffr 和
src(x',y')g-lo_diffg<=src(x,y)g<=src(x',y')g+up_diffg 和
src(x',y')b-lo_diffb<=src(x,y)b<=src(x',y')b+up_diffb, 彩色图像,浮动范围
src(seed.x,seed.y)r-lo_diffr<=src(x,y)r<=src(seed.x,seed.y)r+up_diffr 和
src(seed.x,seed.y)g-lo_diffg<=src(x,y)g<=src(seed.x,seed.y)g+up_diffg 和
src(seed.x,seed.y)b-lo_diffb<=src(x,y)b<=src(seed.x,seed.y)b+up_diffb, 彩色图像,固定范围
其中 src(x',y') 是象素邻域点的值。也就是说,为了被加入到连通域中,一个象素的彩色/亮度应该足够接近于:
它的邻域象素的彩色/亮度值,当该邻域点已经被认为属于浮动范围情况下的连通域。
固定范围情况下的种子点的彩色/亮度值
[cpp] view plaincopyprint?
/ // 漫水法填充标定
//像素值
unsigned char pixel;
//种子堆栈及指针
Seed *Seeds;
int StackPoint;
//当前像素位置
int iCurrentPixelx,iCurrentPixely;
//分配种子空间
Seeds = new Seed[iWidth*iLength];
//计算每个标定值的像素个数
int count[251];
for(i=1;i<252;i++)
{ count[i]=0; } //初始化为0
//滤波的阈值
int yuzhi = 700;
for (i=0;i<iWidth;i++)
{
for (j=0;j<iLength;j++)
{
if (grey_liantong.GetPixel(i,j)==0) //当前像素为黑,对它进行漫水法标定
{
//初始化种子
Seeds[1].x = i;
Seeds[1].y = j;
StackPoint = 1;
while( StackPoint != 0)
{
//取出种子
iCurrentPixelx = Seeds[StackPoint].x;
iCurrentPixely = Seeds[StackPoint].y;
StackPoint--;
//取得当前指针处的像素值,注意要转换为unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx,iCurrentPixely);
//将当前点标定
grey_liantong.SetPixel(iCurrentPixelx,iCurrentPixely,flag);
count[flag]++; //标定像素计数
//判断左面的点,如果为黑,则压入堆栈
//注意防止越界
if(iCurrentPixelx > 1)
{
//取得当前指针处的像素值,注意要转换为unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx-1,iCurrentPixely);
if (pixel == 0)
{
StackPoint++;
Seeds[StackPoint].y = iCurrentPixely;
Seeds[StackPoint].x = iCurrentPixelx - 1;
}
}
//判断上面的点,如果为黑,则压入堆栈
//注意防止越界
if(iCurrentPixely < iLength - 1)
{
//取得当前指针处的像素值,注意要转换为unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx,iCurrentPixely+1);
if (pixel == 0)
{
StackPoint++;
Seeds[StackPoint].y = iCurrentPixely + 1;
Seeds[StackPoint].x = iCurrentPixelx;
}
}
//判断右面的点,如果为黑,则压入堆栈
//注意防止越界
if(iCurrentPixelx < iWidth - 1)
{
//取得当前指针处的像素值,注意要转换为unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx+1,iCurrentPixely);
if (pixel == 0)
{
StackPoint++;
Seeds[StackPoint].y = iCurrentPixely;
Seeds[StackPoint].x = iCurrentPixelx + 1;
}
}
//判断下面的点,如果为黑,则压入堆栈
//注意防止越界
if(iCurrentPixely > 1)
{
//取得当前指针处的像素值,注意要转换为unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx,iCurrentPixely-1);
if (pixel == 0)
{
StackPoint++;
Seeds[StackPoint].y = iCurrentPixely - 1;
Seeds[StackPoint].x = iCurrentPixelx;
}
}
}//end while( StackPoint != 0)
flag = (flag + 7)%251+1; //当前点连通区域标定后,改变标定值
}//end if
}//end for(i
}//end for(j
//释放堆栈
delete Seeds;
grey_res.Clone(grey_liantong);
//=====漫水法标定结束==========
在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)并将邻域内联通的上下行中的一行最右边的点作为种子点入栈;
}
此算法的缺点是会造成很多点的重复访问。