OpenCV 漫水填充
漫水填充：也就是用一定颜色填充联通区域，通过设置可连通像素的上下限以及连通方式来达到不同的填充效果;漫水填充经常被用来标记或分离图像的一部分以便对其进行进一步处理或分析，也可以用来从输入图像获取掩码区域，掩码会加速处理过程，或只处理掩码指定的像素点，操作的结果总是某个连续的区域。
种子填充算法
种子填充算法是从多边形区域内部的一点开始，由此出发找到区域内的所有像素。
种子填充算法采用的边界定义是区域边界上所有像素具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色，而边界外的像素则可具有与边界相同的颜色值。
具体算法步骤：
- 标记种子（x,y）的像素点 ;
- 检测该点的颜色，若他与边界色和填充色均不同，就用填充色填 充该点，否则不填充 ;
- 检测相邻位置，继续 2。这个过程延续到已经检测区域边界范围内的所有像素为止。
当然在搜索的时候有两种检测相邻像素：四向连通和八向连通。四向连通即从区域上一点出发，通过四个方向上、下、左、右来检索。而八向连通加上了左上、左下、右上、右下四个方向。这种算法的有点是算法简单，易于实现，也可以填充带有内孔的平面区域。但是此算法需要更大的存储空间以实现栈结构，同一个像素多次入栈和出栈，效率低，运算量大。
扫描线种子填充算法
该算法属于种子填充算法，它是以扫描线上的区段为单位操作。所谓区段，就是一条扫描线上相连着的若干内部象素的集合。扫描线种子填充算法思想：首先填充当前扫描线上的位于给定区域的一区段，然后确定于这一区段相邻的上下两条线上位于该区域内是否存在需要填充的新区段，如果存在，则依次把他们保存起来，反复这个过程，直到所保存的各区段都填充完毕。
借助于堆栈，上述算法实现步骤如下：
初始化堆栈。
种子压入堆栈。
while（堆栈非空）{
从堆栈弹出种子象素。
如果种子象素尚未填充，则：
求出种子区段：xleft、xright;
填充整个区段。
检查相邻的上扫描线的xleft <= x <= xright区间内,是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleft <= x <= xright范围内的最右边的象素，作为新的种子象素依次压入堆栈。
检查相邻的下扫描线的xleft <= x <= xright区间内，是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleft <= x <= xright范围内的最右边的象素，作为新的种子象素依次压入堆栈。
}
更进一步算法
原算法中, 种子虽然代表一个区段, 但种子实质上仍是一个象素, 我们必须在种子出栈的时候计算种子区段, 而这里有很大一部分计算是重复的. 而且, 原算法的扫描过程如果不用mask的话, 每次都会重复扫描父种子区段所在的扫描线, 而用mask的话又会额外增加开销。所以, 对原算法的一个改进就是让种子携带更多的信息, 让种子不再是一个象素, 而是一个结构体. 该结构体包含以下信息: 种子区段的y坐标值, 区段的x开始与结束坐标, 父种子区段的方向(上或者下), 父种子区段的x开始与结束坐标.
struct seed{
int y,
int xleft,
int xright,
int parent_xleft,
int parent_xright,
bool is_parent_up
};
这样算法的具体实现变动如下
初始化堆栈.
将种子象素扩充成为种子区段(y, xleft, xright, xright+1, xrihgt, true), 填充种子区段, 并压入堆栈. (这里有一个构造父种子区段的技巧)
while（堆栈非空）{
从堆栈弹出种子区段。
检查父种子区段所在的扫描线的xleft <= x <= parent_xleft和parent_xright <= x <= xright两个区间, 如果存在需要填充的新区段, 则将其填充并压入堆栈.
检查非父种子区段所在的扫描线的xleft <= x <= xright区间, 如果存在需要填充的新区段, 则将其填充并压入堆栈.
}
另外, opencv里的种子填充算法跟以上方法大致相同, 不同的地方是opencv用了队列不是堆栈, 而且是由固定长度的数组来实现的循环队列, 其固定长度为 max(img_width, img_height)*2. 并且push与pop均使用宏来实现而没有使用函数. 用固定长度的数组来实现队列(或堆栈)意义是显然的, 能大大减少构造结构, 复制结构等操作, 可以大大提高效率.
c语言实现
//漫水法填充标定实现
//像素值
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);
推荐阅读：