OpenCV：二值图像连通区域分析与标记算法实现

http://blog.csdn.net/cooelf/article/details/26581539?utm_source=tuicool&utm_medium=referral

OpenCV：二值图像连通区域分析与标记算法实现

标签： OpenCV连通图两边扫描法种子填充法形成标记算法

2014-05-22 14:30 2058人阅读 评论(0) 收藏 举报

 分类：

OpenCV（6） 

版权声明：本文为博主原创文章，未经博主允许不得转载。

 

目录(?)[+]

 

编译环境：

操作系统：Win8.1  64位

IDE平台：Visual Studio 2013 Ultimate

OpenCV：2.4.8

一、连通域

在图像中，最小的单位是像素，每个像素周围有8个邻接像素，常见的邻接关系有2种：4邻接与8邻接。4邻接一共4个点，即上下左右，如下左图所示。8邻接的点一共有8个，包括了对角线位置的点，如下右图所示。

       

如果像素点A与B邻接，我们称A与B连通，于是我们不加证明的有如下的结论：

如果A与B连通，B与C连通，则A与C连通。

在视觉上看来，彼此连通的点形成了一个区域，而不连通的点形成了不同的区域。这样的一个所有的点彼此连通点构成的集合，我们称为一个连通区域。

下面这符图中，如果考虑4邻接，则有3个连通区域；如果考虑8邻接，则有2个连通区域。（注：图像是被放大的效果，图像正方形实际只有4个像素）。

二、连通区域的标记

1）Two-Pass（两遍扫描法）

下面给出Two-Pass算法的简单步骤：

（1）第一次扫描：

访问当前像素B(x,y)，如果B(x,y) == 1：

a、如果B(x,y)的领域中像素值都为0，则赋予B(x,y)一个新的label：

label += 1， B(x,y) = label；

b、如果B(x,y)的领域中有像素值 > 1的像素Neighbors：

1）将Neighbors中的最小值赋予给B(x,y):

B(x,y) = min{Neighbors}

2）记录Neighbors中各个值（label）之间的相等关系，即这些值（label）同属同一个连通区域；

labelSet[i] = { label_m, .., label_n }，labelSet[i]中的所有label都属于同一个连通区域（注：这里可以有多种实现方式，只要能够记录这些具有相等关系的label之间的关系即可）

（2）第二次扫描：

访问当前像素B(x,y)，如果B(x,y) > 1：

a、找到与label = B(x,y)同属相等关系的一个最小label值，赋予给B(x,y)；

b、完成扫描后，图像中具有相同label值的像素就组成了同一个连通区域。

2）Seed Filling（种子填充法）

种子填充方法来源于计算机图形学，常用于对某个图形进行填充。思路：选取一个前景像素点作为种子，然后根据连通区域的两个基本条件（像素值相同、位置相邻）将与种子相邻的前景像素合并到同一个像素集合中，最后得到的该像素集合则为一个连通区域。

下面给出基于种子填充法的连通区域分析方法：

（1）扫描图像，直到当前像素点B(x,y) == 1：

a、将B(x,y)作为种子（像素位置），并赋予其一个label，然后将该种子相邻的所有前景像素都压入栈中；

b、弹出栈顶像素，赋予其相同的label，然后再将与该栈顶像素相邻的所有前景像素都压入栈中；

c、重复b步骤，直到栈为空；

此时，便找到了图像B中的一个连通区域，该区域内的像素值被标记为label；

（2）重复第（1）步，直到扫描结束；

扫描结束后，就可以得到图像B中所有的连通区域；

三、程序代码

1. #include "stdafx.h"
2. #include<iostream>
3. #include <string>
4. #include <list>
5. #include <vector>
6. #include <map>
7. #include <stack>
8. #include <opencv2/imgproc/imgproc.hpp>
9. #include <opencv2/highgui/highgui.hpp>
10. using namespace std;
11. void Seed_Filling(const cv::Mat& binImg, cv::Mat& lableImg)   //种子填充法
12. {
13. // 4邻接方法
14. if (binImg.empty() ||
15. binImg.type() != CV_8UC1)
16. {
17. return;
18. }
19. lableImg.release();
20. binImg.convertTo(lableImg, CV_32SC1);
21. int label = 1;
22. int rows = binImg.rows - 1;
23. int cols = binImg.cols - 1;
24. for (int i = 1; i < rows-1; i++)
25. {
26. int* data= lableImg.ptr<int>(i);
27. for (int j = 1; j < cols-1; j++)
28. {
29. if (data[j] == 1)
30. {
31. std::stack<std::pair<int,int>> neighborPixels;
32. neighborPixels.push(std::pair<int,int>(i,j));     // 像素位置: <i,j>
33. ++label;  // 没有重复的团，开始新的标签
34. while (!neighborPixels.empty())
35. {
36. std::pair<int,int> curPixel = neighborPixels.top(); //如果与上一行中一个团有重合区域，则将上一行的那个团的标号赋给它
37. int curX = curPixel.first;
38. int curY = curPixel.second;
39. lableImg.at<int>(curX, curY) = label;
40. neighborPixels.pop();
41. if (lableImg.at<int>(curX, curY-1) == 1)
42. {//左边
43. neighborPixels.push(std::pair<int,int>(curX, curY-1));
44. }
45. if (lableImg.at<int>(curX, curY+1) == 1)
46. {// 右边
47. neighborPixels.push(std::pair<int,int>(curX, curY+1));
48. }
49. if (lableImg.at<int>(curX-1, curY) == 1)
50. {// 上边
51. neighborPixels.push(std::pair<int,int>(curX-1, curY));
52. }
53. if (lableImg.at<int>(curX+1, curY) == 1)
54. {// 下边
55. neighborPixels.push(std::pair<int,int>(curX+1, curY));
56. }
57. }
58. }
59. }
60. }
61. }
62. void Two_Pass(const cv::Mat& binImg, cv::Mat& lableImg)    //两遍扫描法
63. {
64. if (binImg.empty() ||
65. binImg.type() != CV_8UC1)
66. {
67. return;
68. }
69. // 第一个通路
70. lableImg.release();
71. binImg.convertTo(lableImg, CV_32SC1);
72. int label = 1;
73. std::vector<int> labelSet;
74. labelSet.push_back(0);
75. labelSet.push_back(1);
76. int rows = binImg.rows - 1;
77. int cols = binImg.cols - 1;
78. for (int i = 1; i < rows; i++)
79. {
80. int* data_preRow = lableImg.ptr<int>(i-1);
81. int* data_curRow = lableImg.ptr<int>(i);
82. for (int j = 1; j < cols; j++)
83. {
84. if (data_curRow[j] == 1)
85. {
86. std::vector<int> neighborLabels;
87. neighborLabels.reserve(2);
88. int leftPixel = data_curRow[j-1];
89. int upPixel = data_preRow[j];
90. if ( leftPixel > 1)
91. {
92. neighborLabels.push_back(leftPixel);
93. }
94. if (upPixel > 1)
95. {
96. neighborLabels.push_back(upPixel);
97. }
98. if (neighborLabels.empty())
99. {
100. labelSet.push_back(++label);  // 不连通，标签+1
101. data_curRow[j] = label;
102. labelSet[label] = label;
103. }
104. else
105. {
106. std::sort(neighborLabels.begin(), neighborLabels.end());
107. int smallestLabel = neighborLabels[0];
108. data_curRow[j] = smallestLabel;
109. // 保存最小等价表
110. for (size_t k = 1; k < neighborLabels.size(); k++)
111. {
112. int tempLabel = neighborLabels[k];
113. int& oldSmallestLabel = labelSet[tempLabel];
114. if (oldSmallestLabel > smallestLabel)
115. {
116. labelSet[oldSmallestLabel] = smallestLabel;
117. oldSmallestLabel = smallestLabel;
118. }
119. else if (oldSmallestLabel < smallestLabel)
120. {
121. labelSet[smallestLabel] = oldSmallestLabel;
122. }
123. }
124. }
125. }
126. }
127. }
128. // 更新等价对列表
129. // 将最小标号给重复区域
130. for (size_t i = 2; i < labelSet.size(); i++)
131. {
132. int curLabel = labelSet[i];
133. int preLabel = labelSet[curLabel];
134. while (preLabel != curLabel)
135. {
136. curLabel = preLabel;
137. preLabel = labelSet[preLabel];
138. }
139. labelSet[i] = curLabel;
140. }  ;
141. for (int i = 0; i < rows; i++)
142. {
143. int* data = lableImg.ptr<int>(i);
144. for (int j = 0; j < cols; j++)
145. {
146. int& pixelLabel = data[j];
147. pixelLabel = labelSet[pixelLabel];
148. }
149. }
150. }
151. //彩色显示
152. cv::Scalar GetRandomColor()
153. {
154. uchar r = 255 * (rand()/(1.0 + RAND_MAX));
155. uchar g = 255 * (rand()/(1.0 + RAND_MAX));
156. uchar b = 255 * (rand()/(1.0 + RAND_MAX));
157. return cv::Scalar(b,g,r);
158. }
159. void LabelColor(const cv::Mat& labelImg, cv::Mat& colorLabelImg)
160. {
161. if (labelImg.empty() ||
162. labelImg.type() != CV_32SC1)
163. {
164. return;
165. }
166. std::map<int, cv::Scalar> colors;
167. int rows = labelImg.rows;
168. int cols = labelImg.cols;
169. colorLabelImg.release();
170. colorLabelImg.create(rows, cols, CV_8UC3);
171. colorLabelImg = cv::Scalar::all(0);
172. for (int i = 0; i < rows; i++)
173. {
174. const int* data_src = (int*)labelImg.ptr<int>(i);
175. uchar* data_dst = colorLabelImg.ptr<uchar>(i);
176. for (int j = 0; j < cols; j++)
177. {
178. int pixelValue = data_src[j];
179. if (pixelValue > 1)
180. {
181. if (colors.count(pixelValue) <= 0)
182. {
183. colors[pixelValue] = GetRandomColor();
184. }
185. cv::Scalar color = colors[pixelValue];
186. *data_dst++   = color[0];
187. *data_dst++ = color[1];
188. *data_dst++ = color[2];
189. }
190. else
191. {
192. data_dst++;
193. data_dst++;
194. data_dst++;
195. }
196. }
197. }
198. }
199. int main()
200. {
201. cv::Mat binImage = cv::imread("test.jpg", 0);
202. cv::threshold(binImage, binImage, 50, 1, CV_THRESH_BINARY_INV);
203. cv::Mat labelImg;
204. Two_Pass(binImage, labelImg, num);
205. //Seed_Filling(binImage, labelImg);
206. //彩色显示
207. cv::Mat colorLabelImg;
208. LabelColor(labelImg, colorLabelImg);
209. cv::imshow("colorImg", colorLabelImg);
210. /*  //灰度显示
211. cv::Mat grayImg;
212. labelImg *= 10;
213. labelImg.convertTo(grayImg, CV_8UC1);
214. cv::imshow("labelImg", grayImg);
215. */
216. cv::waitKey(0);
217. return 0;
218. }

四、演示结果

原图：

效果图：

参考文章：

http://www.cnblogs.com/ronny/p/img_aly_01.html

http://blog.csdn.net/icvpr/article/details/10259577