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

作者：网络转载发布时间：[ 2014/10/14 13:30:21 ] 推荐标签：软件开发 C++

　　基于扫描线的算法，描述如下（也是针对二值图像编程的）：
　　(1) 初始化一个空的栈用于存放种子点，将种子点(x， y)入栈；
　　(2) 判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x， y)，y是当前的扫描线；
　　(3) 从种子点(x， y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight；
　　(4) 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft， xRight]中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中右边的一个，并将其作为种子点压入栈中，然后返回第（2）步。
　　也是用的c++实现，代码如下：
1 //视频处理测试算法，种子填充算法，扫描线算法，二值图像
2 #include <iostream>
3 #include "cv.h"
4 #include "highgui.h"
5 #include <stack>
6 #include <list>
7 #include <string>
8
9 using namespace std;
10 int ScanLine_SeedFillingAlgoE(IplImage *src，IplImage *dst，int MinCutNumb);//原图像和目标图像不要是同一副图像
11 int main()
12 {
13     IplImage *ipl_origin;
14     IplImage *ipl_target;
15     string fname = "C:/Users/zcx/Desktop/打架斗殴测试图片/第四次无腐蚀膨胀/Fight1save";
16     cvNamedWindow("原始图片");
17     cvNamedWindow("处理后图片");
18     for (int k=0;k<246;k++)
19     {
20         string filename="";
21         char tmp[20];
22         _itoa_s(k，tmp，20，10);
23         filename+=tmp;
24         filename+=".bmp";
25         filename=fname+filename;
26         ipl_origin=cvLoadImage(filename.c_str()，-1);
27         //ipl_target=cvCreateImage(cvGetSize(ipl_origin)，8，1);//cvCloneImage(ipl_origin);
28
29         //cvZero(ipl_target);
30         cvShowImage("原始图片"，ipl_origin);
31         int s=clock();
32         ScanLine_SeedFillingAlgoE(ipl_origin，ipl_origin，125);
33         int e=clock();
34         std::cout<<" "<<e-s;
35         cvShowImage("处理后图片"，ipl_origin);
36         cvWaitKey(1);
37
38     }
39
40
41
42
43
44
45     cvWaitKey(0);
46     cvReleaseImage(&ipl_origin);
47     //cvReleaseImage(&ipl_target);
48     cvDestroyWindow("原始图片");
49     cvDestroyWindow("处理后图片");
50
51 }
52 //MinCutNumb代表剔除面积小于MinCutNumb的值；
53 //返回找到目标数
54 int ScanLine_SeedFillingAlgoE(IplImage *src，IplImage *dst，int MinCutNumb)
55 {
56     int width = src->width;
57     int height = src->height;
58     int targetSumNumb=0;//目标数
59     int area;//区域面积
60     int rcount=0，lcount=0;//向左向右计算像素个数
61     int yLeft，yRight;//左右像素坐标
62     //IplImage *src=cvCreateImage(cvGetSize(p_src)，8，1);//cvCloneImage(p_src);
63     //cvCopy(p_src，src);
64     CvPoint direction_4[]={{-1， 0}， {0， 1}， {1， 0}， {0， -1}};//上右下左
65     //CvPoint direction_8[] = { {-1， 0}， {-1， 1}， {0， 1}， {1， 1}， {1， 0}， {1， -1}， {0， -1}， {-1， -1} };//顺时针
66     int n_Count=sizeof(direction_4)/sizeof(CvPoint);//遍历方向个数
67     std::list<CvPoint> stk;//stl栈
68     std::list<CvPoint> lst;//stl链表
69
70     IplImage *tempimage=cvCreateImage(cvGetSize(src)，8，1);//创建一个临时数据，保存源图像数据到目标过度数据
71     int t_i，t_j;//每次种子的位置
72     int rt_j，lt_j;//左右搜索
73     cvZero(tempimage);//临时数据初始化，清0
74     for (int i=1;i<height-1;i++)
75     {
76         for (int j=1;j<width-1;j++)
77         {
78             //int s=clock();
79
80             //
81             if (src->imageData[i*width+j])
82             {
83                 targetSumNumb++;
84                 stk.push_back(cvPoint(i，j));//栈换成链表
85                 lst.push_back(cvPoint(i，j));
86                 src->imageData[i*width+j]=0;//二值图像
87                 //tempimage->imageData[i*width+j]=255;
88                 area=1;
89                 while (!stk.empty())
90                 {
91                     CvPoint seed=stk.back();//弹出头部
92                     stk.pop_back();
93                     t_i=seed.x;
94                     rt_j=lt_j=t_j=seed.y;
95                     if (t_i<=0||t_i>=height)//上下扫描界限
96                         continue;
97                     //向右扫描
98                     rcount=0，lcount=0;
99                     while (rt_j<width)
100                     {
101                         //++t_j;
102                         if (src->imageData[t_i*width+(++rt_j)])
103                         {
104                             rcount++;
105                             lst.push_back(cvPoint(t_i，rt_j));
106                             src->imageData[t_i*width+rt_j]=0;//二值图像
107                         }
108                         else
109                         {
110                             break;
111                         }
112                     }
113                     area+=rcount;
114                     yRight=t_j+rcount;//右边坐标
115                     //向左扫描
116                     while (lt_j>0)
117                     {
118                         //++t_j;
119                         if (src->imageData[t_i*width+(--lt_j)])
120                         {
121                             lcount++;
122                             lst.push_back(cvPoint(t_i，lt_j));
123
124                             src->imageData[t_i*width+lt_j]=0;//二值图像
125                         }
126                         else
127                         {
128                             break;
129                         }
130                     }
131                     area+=lcount;
132                     yLeft=t_j-lcount;//左边坐标
133                     //上一行搜索入栈点
134                     int up_yLeft=yLeft，up_yRight=yRight;
135                     bool up_findNewSeed = false;//判断是否找到种子点
136                     while(up_yLeft<=up_yRight)
137                     {
138                         up_findNewSeed = false;
139                         while(src->imageData[(t_i-1)*width+up_yLeft]&&up_yLeft<width)
140                         {
141                             up_findNewSeed=true;
142                             up_yLeft++;
143                         }
144
145                         if (up_findNewSeed)
146                         {
147                             if (up_yLeft==up_yRight)
148                             {
149                                 stk.push_back(cvPoint(t_i-1，up_yLeft));
150                                 lst.push_back(cvPoint(t_i-1，up_yLeft));
151                                 src->imageData[(t_i-1)*width+up_yLeft]=0;//二值图像
152                             }
153                             else
154                             {
155                                 stk.push_back(cvPoint(t_i-1，up_yLeft-1));
156                                 lst.push_back(cvPoint(t_i-1，up_yLeft-1));
157                                 src->imageData[(t_i-1)*width+up_yLeft-1]=0;//二值图像
158                             }
159                             up_findNewSeed=false;
160                         }
161                         int itemp=up_yLeft;
162                         while (!src->imageData[(t_i-1)*width+up_yLeft]&&up_yLeft<up_yRight)
163                         {
164                             up_yLeft++;
165                         }
166                         if (itemp==up_yLeft)
167                         {
168                             up_yLeft++;
169                         }
170                     }
171
172                     //下一行搜索入栈点
173                     int down_yLeft=yLeft，down_yRight=yRight;
174                     bool down_findNewSeed = false;//判断是否找到种子点
175                     while(down_yLeft<=down_yRight)
176                     {
177                         down_findNewSeed = false;
178                         while(src->imageData[(t_i+1)*width+down_yLeft]&&down_yLeft<width)
179                         {
180                             down_findNewSeed=true;
181                             down_yLeft++;
182                         }
183
184                         if (down_findNewSeed)
185                         {
186                             if (down_yLeft==down_yRight)
187                             {
188                                 ++area;
189                                 stk.push_back(cvPoint(t_i+1，down_yLeft));
190                                 lst.push_back(cvPoint(t_i+1，down_yLeft));
191                                 src->imageData[(t_i+1)*width+down_yLeft]=0;//二值图像
192                             }
193                             else
194                             {
195                                 ++area;
196                                 stk.push_back(cvPoint(t_i+1，down_yLeft-1));
197                                 lst.push_back(cvPoint(t_i+1，down_yLeft-1));
198                                 src->imageData[(t_i+1)*width+down_yLeft-1]=0;//二值图像
199                             }
200                             down_findNewSeed=false;
201                         }
202                         int itemp=down_yLeft;
203                         while (!src->imageData[(t_i+1)*width+down_yLeft]&&down_yLeft<down_yRight)
204                         {
205                             down_yLeft++;
206                         }
207                         if (itemp==down_yLeft)
208                         {
209                             down_yLeft++;
210                         }
211
212                     }
213
214
215
216
217
218
219
220                 }
221                 //int e=clock();
222                 //std::cout<<e-s;
223                 if (area>MinCutNumb)
224                 {
225                     //cvOr(dst，tempimage，dst);
226                     while (!lst.empty())
227                     {
228                         CvPoint tmpPt=lst.front();
229                         lst.pop_front();
230                         tempimage->imageData[tmpPt.x*width+tmpPt.y]=255;
231                     }
232                 }
233                 else
234                 {
235                     //std::list<CvPoint>().swap(lst);
236                     //while (!lst.empty()) lst.pop_back();
237                     //lst.resize(0);
238                     //lst.
239                     lst.clear();
240                 }
241
242             }//判断是否入栈
243             //CvPoint
244
245         }
246     }
247     //cvZero(dst);
248     cvCopy(tempimage，dst);
249     cvReleaseImage(&tempimage);
250     return targetSumNumb;
251 }
　　效果如下图：