种子填充算法描述及C++代码实现

时间:2023-12-10 13:22:32

项目需要看了种子填充算法,改进了算法主要去除面积小的部分。种子填充算法分为两种,简单的和基于扫描线的方法,简单的算法如下描述(笔者针对的是二值图像):

(1)从上到下,从左到有,依次扫描每个像素;

(2)遇到一个非零数值压栈,并置原图像像素点值为0,面积初始化为1;否则,处理完毕。

(3)对栈非空查找,如果非空弹出栈顶,检测4领域或8领域,如果非空压栈,并置原图像像素点为0,标示不在处理此点,面积加1;如果为空,停止;

(4)判断面积是否大于给定阈值,小于的删掉,大于的把得到的所有像素点保存到目标图像上去,继续扫描像素,转2。

这里我用c++实现,开始用的stl栈,运行一段时间会有中断,之后换成链表可以了,代码共享如下,可以运行,图片使用二值,有需要的可以留下邮箱,一起研究:

 //视频处理测试算法,种子填充算法,扫描线算法,二值图像
//用栈会保存,这里把栈换成链表了,下面有栈注释掉代码
//
#include <iostream>
#include "cv.h"
#include "highgui.h"
#include <stack>
#include <list>
#include <string> using namespace std;
int ScanLine_SeedFillingAlgo(IplImage *src,IplImage *dst,int MinCutNumb);//原图像和目标图像不要是同一副图像
int main()
{
IplImage *ipl_origin;
IplImage *ipl_target;
string fname = "D:/无腐蚀膨胀/Fight1save";
cvNamedWindow("原始图片");
cvNamedWindow("处理后图片");
for (int k=;k<;k++)
{
string filename="";
char tmp[];
_itoa_s(k,tmp,,);
filename+=tmp;
filename+=".bmp";
filename=fname+filename;
ipl_origin=cvLoadImage(filename.c_str(),-);
ipl_target=cvCreateImage(cvGetSize(ipl_origin),,);//cvCloneImage(ipl_origin); cvZero(ipl_target);
cvShowImage("原始图片",ipl_origin);
int s=clock();
ScanLine_SeedFillingAlgo(ipl_origin,ipl_target,);
int e=clock();
std::cout<<"\n"<<e-s;
cvShowImage("处理后图片",ipl_target);
cvWaitKey();
cvReleaseImage(&ipl_origin);
cvReleaseImage(&ipl_target);
} cvWaitKey(); cvDestroyWindow("原始图片");
cvDestroyWindow("处理后图片"); }
//MinCutNumb代表剔除面积小于MinCutNumb的值;
//返回找到目标数
int ScanLine_SeedFillingAlgo(IplImage *src,IplImage *dst,int MinCutNumb)
{
int i, j, k;
for ( i = ; i < ; i++ ) //上下两行
{
unsigned char * t_pPos = (unsigned char *) ( &src->imageData[ i * src->widthStep ] ); for ( j = ; j < src->widthStep; j++ )
{
* t_pPos = (unsigned char);
t_pPos++;
}
} for ( i = ( src->height - ); i < src->height; i++ ) //上下两行
{
unsigned char * t_pPos = (unsigned char *) ( &src->imageData[ i * src->widthStep ] ); for ( j = ; j < src->widthStep; j++ )
{
* t_pPos = (unsigned char);
t_pPos++;
}
} for ( i = ; i < src->height; i++ ) //左右两边
{
unsigned char * t_pPos = (unsigned char *) ( &src->imageData[ i * src->widthStep ] ); for ( j = ; j < ; j++ )
{
* t_pPos = (unsigned char);
t_pPos++;
} t_pPos = (unsigned char *) ( &src->imageData[ i * src->widthStep + src->widthStep - ] ); for ( j = ( src->widthStep - ); j < src->widthStep; j++ )
{
* t_pPos = (unsigned char);
t_pPos++;
}
}
int width = src->width;
int height = src->height;
int targetSumNumb=;
int area;
CvPoint direction_4[]={{-, }, {, }, {, }, {, -}};//上右下左
//CvPoint direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };//顺时针
int n_Count=sizeof(direction_4)/sizeof(CvPoint);//遍历方向个数
std::list<CvPoint> stk;//stl栈
std::list<CvPoint> lst;//stl链表
cvZero(dst);
//IplImage *tempimage=cvCreateImage(cvGetSize(src),8,1);//创建一个临时数据,保存源图像数据到目标过度数据
int t_i;//每次种子的位置
int t_j;
//cvZero(tempimage);//临时数据初始化,清0
for (int i=;i<height-;i++)
{
for (int j=;j<width-;j++)
{
//int s=clock(); //
if (src->imageData[i*width+j])
{
targetSumNumb++;
stk.push_back(cvPoint(i,j));//栈换成链表
lst.push_back(cvPoint(i,j));
src->imageData[i*width+j]=;//二值图像
//tempimage->imageData[i*width+j]=255;
area=;
while (!stk.empty())
{
CvPoint seed=stk.back();//弹出头部
stk.pop_back();
t_i=seed.x;
t_j=seed.y;
if (t_i<=||t_i>=height||t_j<=||t_j>=width)
continue;
for (int ii=;ii<n_Count;ii++)//扫描各个方向
{
if (src->imageData[(t_i+direction_4[ii].x)*width+t_j+direction_4[ii].y])
{
area++;
stk.push_back(cvPoint(t_i+direction_4[ii].x,t_j+direction_4[ii].y));
lst.push_back(cvPoint(t_i+direction_4[ii].x,t_j+direction_4[ii].y));
src->imageData[(t_i+direction_4[ii].x)*width+t_j+direction_4[ii].y]=;//二值图像
//tempimage->imageData[(t_i+direction_4[ii].x)*width+t_j+direction_4[ii].y]=255;
}
}
}
//int e=clock();
//std::cout<<e-s;
if (area>MinCutNumb)
{
//cvOr(dst,tempimage,dst);
while (!lst.empty())
{
CvPoint tmpPt=lst.front();
lst.pop_front();
dst->imageData[tmpPt.x*width+tmpPt.y]=;
}
}
else
{
//std::list<CvPoint>().swap(lst);
//while (!lst.empty()) lst.pop_back();
//lst.resize(0);
//lst.
lst.clear();
} }//判断是否入栈
//CvPoint }
}
//cvReleaseImage(&tempimage);
return targetSumNumb;
}

图片处理效果:种子填充算法描述及C++代码实现

基于扫描线的算法,描述如下(也是针对二值图像编程的):

(1) 初始化一个空的栈用于存放种子点,将种子点(x, y)入栈;

(2) 判断栈是否为空,如果栈为空则结束算法,否则取出栈顶元素作为当前扫描线的种子点(x, y),y是当前的扫描线;

(3) 从种子点(x, y)出发,沿当前扫描线向左、右两个方向填充,直到边界。分别标记区段的左、右端点坐标为xLeft和xRight;

(4) 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素,从xLeft开始向xRight方向搜索,若存在非边界且未填充的像素点,则找出这些相邻的像素点中最右边的一个,并将其作为种子点压入栈中,然后返回第(2)步。

也是用的c++实现,代码如下:

 //视频处理测试算法,种子填充算法,扫描线算法,二值图像
#include <iostream>
#include "cv.h"
#include "highgui.h"
#include <stack>
#include <list>
#include <string> using namespace std;
int ScanLine_SeedFillingAlgoE(IplImage *src,IplImage *dst,int MinCutNumb);//原图像和目标图像不要是同一副图像
int main()
{
IplImage *ipl_origin;
IplImage *ipl_target;
string fname = "C:/Users/zcx/Desktop/打架斗殴测试图片/第四次无腐蚀膨胀/Fight1save";
cvNamedWindow("原始图片");
cvNamedWindow("处理后图片");
for (int k=;k<;k++)
{
string filename="";
char tmp[];
_itoa_s(k,tmp,,);
filename+=tmp;
filename+=".bmp";
filename=fname+filename;
ipl_origin=cvLoadImage(filename.c_str(),-);
//ipl_target=cvCreateImage(cvGetSize(ipl_origin),8,1);//cvCloneImage(ipl_origin); //cvZero(ipl_target);
cvShowImage("原始图片",ipl_origin);
int s=clock();
ScanLine_SeedFillingAlgoE(ipl_origin,ipl_origin,);
int e=clock();
std::cout<<"\n"<<e-s;
cvShowImage("处理后图片",ipl_origin);
cvWaitKey(); } cvWaitKey();
cvReleaseImage(&ipl_origin);
//cvReleaseImage(&ipl_target);
cvDestroyWindow("原始图片");
cvDestroyWindow("处理后图片"); }
//MinCutNumb代表剔除面积小于MinCutNumb的值;
//返回找到目标数
int ScanLine_SeedFillingAlgoE(IplImage *src,IplImage *dst,int MinCutNumb)
{
int width = src->width;
int height = src->height;
int targetSumNumb=;//目标数
int area;//区域面积
int rcount=,lcount=;//向左向右计算像素个数
int yLeft,yRight;//左右像素坐标
//IplImage *src=cvCreateImage(cvGetSize(p_src),8,1);//cvCloneImage(p_src);
//cvCopy(p_src,src);
CvPoint direction_4[]={{-, }, {, }, {, }, {, -}};//上右下左
//CvPoint direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} };//顺时针
int n_Count=sizeof(direction_4)/sizeof(CvPoint);//遍历方向个数
std::list<CvPoint> stk;//stl栈
std::list<CvPoint> lst;//stl链表 IplImage *tempimage=cvCreateImage(cvGetSize(src),,);//创建一个临时数据,保存源图像数据到目标过度数据
int t_i,t_j;//每次种子的位置
int rt_j,lt_j;//左右搜索
cvZero(tempimage);//临时数据初始化,清0
for (int i=;i<height-;i++)
{
for (int j=;j<width-;j++)
{
//int s=clock(); //
if (src->imageData[i*width+j])
{
targetSumNumb++;
stk.push_back(cvPoint(i,j));//栈换成链表
lst.push_back(cvPoint(i,j));
src->imageData[i*width+j]=;//二值图像
//tempimage->imageData[i*width+j]=255;
area=;
while (!stk.empty())
{
CvPoint seed=stk.back();//弹出头部
stk.pop_back();
t_i=seed.x;
rt_j=lt_j=t_j=seed.y;
if (t_i<=||t_i>=height)//上下扫描界限
continue;
//向右扫描
rcount=,lcount=;
while (rt_j<width)
{
//++t_j;
if (src->imageData[t_i*width+(++rt_j)])
{
rcount++;
lst.push_back(cvPoint(t_i,rt_j));
src->imageData[t_i*width+rt_j]=;//二值图像
}
else
{
break;
}
}
area+=rcount;
yRight=t_j+rcount;//右边坐标
//向左扫描
while (lt_j>)
{
//++t_j;
if (src->imageData[t_i*width+(--lt_j)])
{
lcount++;
lst.push_back(cvPoint(t_i,lt_j)); src->imageData[t_i*width+lt_j]=;//二值图像
}
else
{
break;
}
}
area+=lcount;
yLeft=t_j-lcount;//左边坐标
//上一行搜索入栈点
int up_yLeft=yLeft,up_yRight=yRight;
bool up_findNewSeed = false;//判断是否找到种子点
while(up_yLeft<=up_yRight)
{
up_findNewSeed = false;
while(src->imageData[(t_i-)*width+up_yLeft]&&up_yLeft<width)
{
up_findNewSeed=true;
up_yLeft++;
} if (up_findNewSeed)
{
if (up_yLeft==up_yRight)
{
stk.push_back(cvPoint(t_i-,up_yLeft));
lst.push_back(cvPoint(t_i-,up_yLeft));
src->imageData[(t_i-)*width+up_yLeft]=;//二值图像
}
else
{
stk.push_back(cvPoint(t_i-,up_yLeft-));
lst.push_back(cvPoint(t_i-,up_yLeft-));
src->imageData[(t_i-)*width+up_yLeft-]=;//二值图像
}
up_findNewSeed=false;
}
int itemp=up_yLeft;
while (!src->imageData[(t_i-)*width+up_yLeft]&&up_yLeft<up_yRight)
{
up_yLeft++;
}
if (itemp==up_yLeft)
{
up_yLeft++;
}
} //下一行搜索入栈点
int down_yLeft=yLeft,down_yRight=yRight;
bool down_findNewSeed = false;//判断是否找到种子点
while(down_yLeft<=down_yRight)
{
down_findNewSeed = false;
while(src->imageData[(t_i+)*width+down_yLeft]&&down_yLeft<width)
{
down_findNewSeed=true;
down_yLeft++;
} if (down_findNewSeed)
{
if (down_yLeft==down_yRight)
{
++area;
stk.push_back(cvPoint(t_i+,down_yLeft));
lst.push_back(cvPoint(t_i+,down_yLeft));
src->imageData[(t_i+)*width+down_yLeft]=;//二值图像
}
else
{
++area;
stk.push_back(cvPoint(t_i+,down_yLeft-));
lst.push_back(cvPoint(t_i+,down_yLeft-));
src->imageData[(t_i+)*width+down_yLeft-]=;//二值图像
}
down_findNewSeed=false;
}
int itemp=down_yLeft;
while (!src->imageData[(t_i+)*width+down_yLeft]&&down_yLeft<down_yRight)
{
down_yLeft++;
}
if (itemp==down_yLeft)
{
down_yLeft++;
} } }
//int e=clock();
//std::cout<<e-s;
if (area>MinCutNumb)
{
//cvOr(dst,tempimage,dst);
while (!lst.empty())
{
CvPoint tmpPt=lst.front();
lst.pop_front();
tempimage->imageData[tmpPt.x*width+tmpPt.y]=;
}
}
else
{
//std::list<CvPoint>().swap(lst);
//while (!lst.empty()) lst.pop_back();
//lst.resize(0);
//lst.
lst.clear();
} }//判断是否入栈
//CvPoint }
}
//cvZero(dst);
cvCopy(tempimage,dst);
cvReleaseImage(&tempimage);
return targetSumNumb;
}

效果如下图:

种子填充算法描述及C++代码实现

小结:去除小面积效果还好,这里实现两种算法的时间优化并不是很明显,自己编程实现效率并不是很高,仅供参考,有园友写的比较好的代码可以分享一下,大家互相学习。