二值图像处理连通区域分析

OpenCV提供了专门的函数标记连通区域connectedComponents，它有四种形式：

1. int connectedComponents(InputArray image, OutputArray labels, int connectivity, int ltype, int ccltype);

参数说明：

image : 输入原始图像，8bit单通道，二值图像

labels : 输出标记图像

connectivity : 邻域类型，4连通或8连通，所以这个值通常为两个值（4或8）

ltype : 输出标记的类型，只支持 CV_32S和CV_16U

ccltype : 连通标记的算法，这个值有三个选择CCL_WU（8连通和4连通均用SAUF算法），CCL_DEFAULT（8连通用BBDT算法，4连通用SAUF算法）和CCL_GRANA（8连通用BBDT算法，4连通用SAUF算法）。（后两种方法是一样的，这里有疑问）

2. int connectedComponents(InputArray image, OutputArray labels, int connectivity = 8, int ltype = CV_32S);

这个函数实际上就是第一个的简化版

这两个函数的返回值是标记的个数[0，N－1]，0表示背景区域

3. int connectedComponentsWithStats(InputArray image, OutputArray labels, OutputArray stats, OutputArray centroids,  int connectivity, int ltype, int ccltype);

参数说明：

image : 输入原始图像，8bit单通道，二值图像

labels : 输出标记图像

stats : 每个标记的统计输出，类型为CV_32S，使用格式为stats(label, COLUMN)，其中COLUMN为连通类型，包括CC_STAT_LEFT、CC_STAT_TOP、CC_STAT_WIDTH、CC_STAT_HEIGHT、CC_STAT_AREA

centroids : 每个标记区域的质心，类型为CV_64F，使用方法为x = centroids(label,0), y = centroids(label, 1)

connectivity : 邻域类型，4连通或8连通，所以这个值通常为两个值（4或8）

ltype : 输出标记的类型，只支持 CV_32S和CV_16U

4. int connectedComponentsWithStats(InputArray image, OutputArray labels, OutputArray stats, OutputArray centroids,  int connectivity = 8, int ltype = CV_32S);

第三个函数的简化版

－－－－－－－－－－－－－－－－－－－－－－华丽的分界线－－－－－－－－－－－－－－－－－－－－－－－－

以下转自：https://blog.csdn.net/icvpr/article/details/10259577

OpenCV_连通区域分析（Connected Component Analysis/Labeling）

【摘要】

本文主要介绍在CVPR和图像处理领域中较为常用的一种图像区域（Blob）提取的方法——连通性分析法（连通区域标记法）。文中介绍了两种常见的连通性分析的算法：1）Two-pass；2）Seed-Filling种子填充，并给出了两个算法的基于OpenCV的C++实现代码。

一、连通区域分析

连通区域（Connected Component）一般是指图像中具有相同像素值且位置相邻的前景像素点组成的图像区域（Region，Blob）。连通区域分析（Connected Component Analysis,Connected Component Labeling）是指将图像中的各个连通区域找出并标记。

连通区域分析是一种在CVPR和图像分析处理的众多应用领域中较为常用和基本的方法。例如：OCR识别中字符分割提取（车牌识别、文本识别、字幕识别等）、视觉跟踪中的运动前景目标分割与提取（行人入侵检测、遗留物体检测、基于视觉的车辆检测与跟踪等）、医学图像处理（感兴趣目标区域提取）、等等。也就是说，在需要将前景目标提取出来以便后续进行处理的应用场景中都能够用到连通区域分析方法，通常连通区域分析处理的对象是一张二值化后的图像。

二、连通区域分析的算法

从连通区域的定义可以知道，一个连通区域是由具有相同像素值的相邻像素组成像素集合，因此，我们就可以通过这两个条件在图像中寻找连通区域，对于找到的每个连通区域，我们赋予其一个唯一的标识（Label），以区别其他连通区域。

连通区域分析有基本的算法，也有其改进算法，本文介绍其中的两种常见算法：

1）Two-Pass法；2）Seed-Filling种子填充法；

Note：

a、这里的扫描指的是按行或按列访问以便图像的所有像素，本文算法采用的是按行扫描方式；

b、图像记为B，为二值图像：前景像素（pixel value = 1），背景像素（pixel value = 0）

c、label从2开始计数；

d、像素相邻关系：4-领域、8-领域，本文算法采用4-邻域；

                                     

4—领域图例                                                     8—领域图例

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

两遍扫描法，正如其名，指的就是通过扫描两遍图像，就可以将图像中存在的所有连通区域找出并标记。思路：第一遍扫描时赋予每个像素位置一个label，扫描过程中同一个连通区域内的像素集合中可能会被赋予一个或多个不同label，因此需要将这些属于同一个连通区域但具有不同值的label合并，也就是记录它们之间的相等关系；第二遍扫描就是将具有相等关系的equal_labels所标记的像素归为一个连通区域并赋予一个相同的label（通常这个label是equal_labels中的最小值）。

下面给出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)；

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

下面这张图动态地演示了Two-pass算法：

2）Seed Filling（种子填充法）

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

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

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

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

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

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

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

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

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

下面这张图动态地演示了Seed-Filling算法：

三、实验演示

1）前景二值图像

2）连通区域分析方法标记后得到的label图像

Two-pass算法：

Seed-filling算法：

注：为了显示方便，将像素值乘以了一个整数进行放大。

3）color后的label图像

Two-pass算法：

Seed-filling算法：

注：颜色是随机生成的。

四、代码

1）Two-pass算法的一种实现

说明：

基于OpenCV和C++实现，领域：4-领域。实现与算法描述稍有差别（具体为记录具有相等关系的label方法实现上）。

[cpp]  view plain  copy

1. //  Connected Component Analysis/Labeling By Two-Pass Algorithm   
2. //  Author:  www.icvpr.com    
3. //  Blog  :  http://blog.csdn.net/icvpr   
4. #include <iostream>  
5. #include <string>  
6. #include <list>  
7. #include <vector>  
8. #include <map>  
9.   
10. #include <opencv2/imgproc/imgproc.hpp>  
11. #include <opencv2/highgui/highgui.hpp>  
12.   
13.   
14. void icvprCcaByTwoPass(const cv::Mat& _binImg, cv::Mat& _lableImg)  
15. {  
16.     // connected component analysis (4-component)  
17.     // use two-pass algorithm  
18.     // 1. first pass: label each foreground pixel with a label  
19.     // 2. second pass: visit each labeled pixel and merge neighbor labels  
20.     //   
21.     // foreground pixel: _binImg(x,y) = 1  
22.     // background pixel: _binImg(x,y) = 0  
23.   
24.   
25.     if (_binImg.empty() ||  
26.         _binImg.type() != CV_8UC1)  
27.     {  
28.         return ;  
29.     }  
30.   
31.     // 1. first pass  
32.   
33.     _lableImg.release() ;  
34.     _binImg.convertTo(_lableImg, CV_32SC1) ;  
35.   
36.     int label = 1 ;  // start by 2  
37.     std::vector<int> labelSet ;  
38.     labelSet.push_back(0) ;   // background: 0  
39.     labelSet.push_back(1) ;   // foreground: 1  
40.   
41.     int rows = _binImg.rows - 1 ;  
42.     int cols = _binImg.cols - 1 ;  
43.     for (int i = 1; i < rows; i++)  
44.     {  
45.         int* data_preRow = _lableImg.ptr<int>(i-1) ;  
46.         int* data_curRow = _lableImg.ptr<int>(i) ;  
47.         for (int j = 1; j < cols; j++)  
48.         {  
49.             if (data_curRow[j] == 1)  
50.             {  
51.                 std::vector<int> neighborLabels ;  
52.                 neighborLabels.reserve(2) ;  
53.                 int leftPixel = data_curRow[j-1] ;  
54.                 int upPixel = data_preRow[j] ;  
55.                 if ( leftPixel > 1)  
56.                 {  
57.                     neighborLabels.push_back(leftPixel) ;  
58.                 }  
59.                 if (upPixel > 1)  
60.                 {  
61.                     neighborLabels.push_back(upPixel) ;  
62.                 }  
63.   
64.                 if (neighborLabels.empty())  
65.                 {  
66.                     labelSet.push_back(++label) ;  // assign to a new label  
67.                     data_curRow[j] = label ;  
68.                     labelSet[label] = label ;  
69.                 }  
70.                 else  
71.                 {  
72.                     std::sort(neighborLabels.begin(), neighborLabels.end()) ;  
73.                     int smallestLabel = neighborLabels[0] ;    
74.                     data_curRow[j] = smallestLabel ;  
75.   
76.                     // save equivalence  
77.                     for (size_t k = 1; k < neighborLabels.size(); k++)  
78.                     {  
79.                         int tempLabel = neighborLabels[k] ;  
80.                         int& oldSmallestLabel = labelSet[tempLabel] ;  
81.                         if (oldSmallestLabel > smallestLabel)  
82.                         {                             
83.                             labelSet[oldSmallestLabel] = smallestLabel ;  
84.                             oldSmallestLabel = smallestLabel ;  
85.                         }                         
86.                         else if (oldSmallestLabel < smallestLabel)  
87.                         {  
88.                             labelSet[smallestLabel] = oldSmallestLabel ;  
89.                         }  
90.                     }  
91.                 }                 
92.             }  
93.         }  
94.     }  
95.   
96.     // update equivalent labels  
97.     // assigned with the smallest label in each equivalent label set  
98.     for (size_t i = 2; i < labelSet.size(); i++)  
99.     {  
100.         int curLabel = labelSet[i] ;  
101.         int preLabel = labelSet[curLabel] ;  
102.         while (preLabel != curLabel)  
103.         {  
104.             curLabel = preLabel ;  
105.             preLabel = labelSet[preLabel] ;  
106.         }  
107.         labelSet[i] = curLabel ;  
108.     }  
109.   
110.   
111.     // 2. second pass  
112.     for (int i = 0; i < rows; i++)  
113.     {  
114.         int* data = _lableImg.ptr<int>(i) ;  
115.         for (int j = 0; j < cols; j++)  
116.         {  
117.             int& pixelLabel = data[j] ;  
118.             pixelLabel = labelSet[pixelLabel] ;   
119.         }  
120.     }  
121. }

2）Seed-Filling种子填充方法

说明：

基于OpenCV和C++实现；领域：4-领域。

[cpp]  view plain  copy

1. //  Connected Component Analysis/Labeling By Seed-Filling Algorithm   
2. //  Author:  www.icvpr.com    
3. //  Blog  :  http://blog.csdn.net/icvpr   
4. #include <iostream>  
5. #include <string>  
6. #include <list>  
7. #include <vector>  
8. #include <map>  
9. #include <stack>  
10.   
11. #include <opencv2/imgproc/imgproc.hpp>  
12. #include <opencv2/highgui/highgui.hpp>  
13.   
14.   
15. void icvprCcaBySeedFill(const cv::Mat& _binImg, cv::Mat& _lableImg)  
16. {  
17.     // connected component analysis (4-component)  
18.     // use seed filling algorithm  
19.     // 1. begin with a foreground pixel and push its foreground neighbors into a stack;  
20.     // 2. pop the top pixel on the stack and label it with the same label until the stack is empty  
21.     //   
22.     // foreground pixel: _binImg(x,y) = 1  
23.     // background pixel: _binImg(x,y) = 0  
24.   
25.   
26.     if (_binImg.empty() ||  
27.         _binImg.type() != CV_8UC1)  
28.     {  
29.         return ;  
30.     }  
31.   
32.     _lableImg.release() ;  
33.     _binImg.convertTo(_lableImg, CV_32SC1) ;  
34.   
35.     int label = 1 ;  // start by 2  
36.   
37.     int rows = _binImg.rows - 1 ;  
38.     int cols = _binImg.cols - 1 ;  
39.     for (int i = 1; i < rows-1; i++)  
40.     {  
41.         int* data= _lableImg.ptr<int>(i) ;  
42.         for (int j = 1; j < cols-1; j++)  
43.         {  
44.             if (data[j] == 1)  
45.             {  
46.                 std::stack<std::pair<int,int>> neighborPixels ;     
47.                 neighborPixels.push(std::pair<int,int>(i,j)) ;     // pixel position: <i,j>  
48.                 ++label ;  // begin with a new label  
49.                 while (!neighborPixels.empty())  
50.                 {  
51.                     // get the top pixel on the stack and label it with the same label  
52.                     std::pair<int,int> curPixel = neighborPixels.top() ;  
53.                     int curX = curPixel.first ;  
54.                     int curY = curPixel.second ;  
55.                     _lableImg.at<int>(curX, curY) = label ;  
56.   
57.                     // pop the top pixel  
58.                     neighborPixels.pop() ;  
59.   
60.                     // push the 4-neighbors (foreground pixels)  
61.                     if (_lableImg.at<int>(curX, curY-1) == 1)  
62.                     {// left pixel  
63.                         neighborPixels.push(std::pair<int,int>(curX, curY-1)) ;  
64.                     }  
65.                     if (_lableImg.at<int>(curX, curY+1) == 1)  
66.                     {// right pixel  
67.                         neighborPixels.push(std::pair<int,int>(curX, curY+1)) ;  
68.                     }  
69.                     if (_lableImg.at<int>(curX-1, curY) == 1)  
70.                     {// up pixel  
71.                         neighborPixels.push(std::pair<int,int>(curX-1, curY)) ;  
72.                     }  
73.                     if (_lableImg.at<int>(curX+1, curY) == 1)  
74.                     {// down pixel  
75.                         neighborPixels.push(std::pair<int,int>(curX+1, curY)) ;  
76.                     }  
77.                 }         
78.             }  
79.         }  
80.     }  
81. }

3）颜色标记（用于显示）

[cpp]  view plain  copy

1. //  Connected Component Analysis/Labeling -- Color Labeling   
2. //  Author:  www.icvpr.com    
3. //  Blog  :  http://blog.csdn.net/icvpr   
4. #include <iostream>  
5. #include <string>  
6. #include <list>  
7. #include <vector>  
8. #include <map>  
9. #include <stack>  
10.   
11. #include <opencv2/imgproc/imgproc.hpp>  
12. #include <opencv2/highgui/highgui.hpp>  
13.   
14. cv::Scalar icvprGetRandomColor()  
15. {  
16.     uchar r = 255 * (rand()/(1.0 + RAND_MAX));  
17.     uchar g = 255 * (rand()/(1.0 + RAND_MAX));  
18.     uchar b = 255 * (rand()/(1.0 + RAND_MAX));  
19.     return cv::Scalar(b,g,r) ;  
20. }  
21.   
22.   
23. void icvprLabelColor(const cv::Mat& _labelImg, cv::Mat& _colorLabelImg)   
24. {  
25.     if (_labelImg.empty() ||  
26.         _labelImg.type() != CV_32SC1)  
27.     {  
28.         return ;  
29.     }  
30.   
31.     std::map<int, cv::Scalar> colors ;  
32.   
33.     int rows = _labelImg.rows ;  
34.     int cols = _labelImg.cols ;  
35.   
36.     _colorLabelImg.release() ;  
37.     _colorLabelImg.create(rows, cols, CV_8UC3) ;  
38.     _colorLabelImg = cv::Scalar::all(0) ;  
39.   
40.     for (int i = 0; i < rows; i++)  
41.     {  
42.         const int* data_src = (int*)_labelImg.ptr<int>(i) ;  
43.         uchar* data_dst = _colorLabelImg.ptr<uchar>(i) ;  
44.         for (int j = 0; j < cols; j++)  
45.         {  
46.             int pixelValue = data_src[j] ;  
47.             if (pixelValue > 1)  
48.             {  
49.                 if (colors.count(pixelValue) <= 0)  
50.                 {  
51.                     colors[pixelValue] = icvprGetRandomColor() ;  
52.                 }  
53.                 cv::Scalar color = colors[pixelValue] ;  
54.                 *data_dst++   = color[0] ;  
55.                 *data_dst++ = color[1] ;  
56.                 *data_dst++ = color[2] ;  
57.             }  
58.             else  
59.             {  
60.                 data_dst++ ;  
61.                 data_dst++ ;  
62.                 data_dst++ ;  
63.             }  
64.         }  
65.     }  
66. }  

4）测试程序

[cpp]  view plain  copy

1. //  Connected Component Analysis/Labeling -- Test code  
2. //  Author:  www.icvpr.com    
3. //  Blog  :  http://blog.csdn.net/icvpr   
4. #include <iostream>  
5. #include <string>  
6. #include <list>  
7. #include <vector>  
8. #include <map>  
9. #include <stack>  
10.   
11. #include <opencv2/imgproc/imgproc.hpp>  
12. #include <opencv2/highgui/highgui.hpp>  
13.   
14. int main(int argc, char** argv)  
15. {  
16.     cv::Mat binImage = cv::imread("../icvpr.com.jpg", 0) ;  
17.     cv::threshold(binImage, binImage, 50, 1, CV_THRESH_BINARY_INV) ;  
18.   
19.     // connected component labeling  
20.     cv::Mat labelImg ;  
21.     icvprCcaByTwoPass(binImage, labelImg) ;  
22.     //icvprCcaBySeedFill(binImage, labelImg) ;  
23.   
24.     // show result  
25.     cv::Mat grayImg ;  
26.     labelImg *= 10 ;  
27.     labelImg.convertTo(grayImg, CV_8UC1) ;  
28.     cv::imshow("labelImg", grayImg) ;  
29.   
30.     cv::Mat colorLabelImg ;  
31.     icvprLabelColor(labelImg, colorLabelImg) ;  
32.     cv::imshow("colorImg", colorLabelImg) ;  
33.     cv::waitKey(0) ;  
34.   
35.     return 0 ;  
36. }