# two Pass方法连通域检测

## 原理：

Two-Pass方法检测连通域的原理可参见这篇博客：http://blog.csdn.net/lichengyu/article/details/13986521

# 代码：

```  1 #include "opencv2/imgproc/imgproc.hpp"
2 #include "opencv2/highgui/highgui.hpp"
3 #include <map>
4 #include <cassert>
5 #include <iostream>
6
7 using namespace std;
8
9 const int max_size = 1000;
10 int parent[max_size] = { 0 };
11
12 // 找到label x的根节点
13 int Find(int x, int parent[])
14 {
15     assert(x < max_size);
16     int i = x;
17     while (0 != parent[i])
18         i = parent[i];
19     return i;
20 }
21
22 // 将label x 和 label y合并到同一个连通域
23 void Union(int x, int y, int parent[])
24 {
25     assert(x < max_size && y < max_size);
26     int i = x;
27     int j = y;
28     while (0 != parent[i])
29         i = parent[i];
30     while (0 != parent[j])
31         j = parent[j];
32     if (i != j)
33         parent[i] = j;
34 }
35
36 cv::Mat twoPassConnectComponent(cv::Mat &binaryImg)
37 {
38     int imgW = binaryImg.cols;
39     int imgH = binaryImg.rows;
40     int channel = binaryImg.channels();
41     int type = binaryImg.type();
42     // first pass
43     int label = 0;
44
45     cv::Mat dst = cv::Mat::zeros(cv::Size(imgW, imgH), CV_32SC1);
46     for (int y = 0; y < imgH; y++)
47     {
48         for (int x = 0; x < imgW; x++)
49         {
50             if (binaryImg.at<uchar>(y, x) != 0)
51             {
52                 int left = (x - 1 < 0) ? 0 : dst.at<int>(y, x - 1);
53                 int up = (y - 1 < 0) ? 0 : dst.at<int>(y - 1, x);
54
55                 if (left != 0 || up != 0)
56                 {
57                     if (left != 0 && up != 0)
58                     {
59                         dst.at<int>(y, x) = min(left, up);
60                         if (left <= up)
61                             Union(up, left, parent);
62                         else if (up<left)
63                             Union(left, up, parent);
64                     }
65                     else
66                         dst.at<int>(y, x) = max(left, up);
67                 }
68                 else
69                 {
70                     dst.at<int>(y, x) = ++label;
71                 }
72             }
73         }
74     }
75
76     //second pass
77     for (int y = 0; y < imgH; y++)
78     {
79         for (int x = 0; x < imgW; x++)
80         {
81             if (binaryImg.at<uchar>(y, x) != 0)
82                 dst.at<int>(y, x) = Find(dst.at<int>(y, x), parent);
83         }
84     }
85
86     return dst;
87 }
88
89 cv::Scalar getRandomColor()
90 {
91     uchar r = 255 * (rand() / (1.0 + RAND_MAX));
92     uchar g = 255 * (rand() / (1.0 + RAND_MAX));
93     uchar b = 255 * (rand() / (1.0 + RAND_MAX));
94     return cv::Scalar(b, g, r);
95 }
96
97 cv::Mat showColorLabel(cv::Mat label)
98 {
99     int imgW = label.cols;
100     int imgH = label.rows;
101     std::map<int, cv::Scalar> colors;
102
103     cv::Mat colorLabel = cv::Mat::zeros(imgH, imgW, CV_8UC3);
104     int *pLabel = (int*)label.data;
105     uchar *pColorLabel = colorLabel.data;
106     for (int i = 0; i < imgH; i++)
107     {
108         for (int j = 0; j < imgW; j++)
109         {
110             int idx = (i*imgW + j) * 3;
111             int pixelValue = pLabel[i*imgW + j];
112             if (pixelValue > 0)
113             {
114                 if (colors.count(pixelValue) <= 0)
115                 {
116                     colors[pixelValue] = getRandomColor();
117                 }
118                 cv::Scalar color = colors[pixelValue];
119                 pColorLabel[idx + 0] = color[0];
120                 pColorLabel[idx + 1] = color[1];
121                 pColorLabel[idx + 2] = color[2];
122             }
123         }
124     }
125
126     return colorLabel;
127 }
128
129 int main()
130 {
131     // 加载图像
132     string imageName = "data/source_images/logo.png";
133     cv::Mat image = cv::imread(imageName, 1);
134     if (!image.data)
135     {
136         cout << "No image data" << endl;
137         getchar();
138         return -1;
139     }
140     //转为灰度图
141     cv::cvtColor(image, image, CV_RGB2GRAY);
142     //阈值化，情景为255，背景为0
143     cv::Mat threshImg;
144     cv::threshold(image, threshImg, 200, 255, cv::THRESH_BINARY);
145     cv::bitwise_not(threshImg, threshImg);
146
147     //连通域检测 two Pass方法标记图像
148     cv::Mat labelImg = twoPassConnectComponent(threshImg);
149
150     //不同连通区域用不同颜色表示
151     cv::Mat colorLabelImg=showColorLabel(labelImg);
152
153     //显示
154     cv::imshow("thresh", threshImg);
155     cv::imshow("label", labelImg*20);
156     cv::imshow("colorLabel", colorLabelImg);
157     cv::waitKey(0);
158 }```

# 结果：

（1）转为灰度图然后阈值化

（2）寻找连通域

（3）不同连通区域不同颜色显示

0 条评论

• ### 直方图实现快速中值滤波

中值滤波能够有效去除图像中的异常点，具有去除图像噪声的作用。传统中值滤波的算法一般都是在图像中建立窗口，然后对窗口内的所有像素值进行排序，选择排序后的中间值作为...

• ### OpenCV3.4两种立体匹配算法效果对比

以OpenCV自带的Aloe图像对为例： ? ? ? 1.BM算法（Block Matching） 参数设置如下： int numberOfDispa...

• ### 洛谷P2045 方格取数加强版(费用流)

对于拆出来的每个点，在其中连两条边，一条为费用为点权，流量为1，另一条费用为0，流量为INF

• ### LeetCode 215. Kth Largest Element in an Array分析

显然最简单的思想就是排序，然后取出倒数第k个元素就可以了，我们可以直接调用内部的排序函数。

• ### 图论建图

图论建图无外乎邻接表建图和链式前向星建图,不要问我是怎么知道的,要是你的学校逼你打图论位的话你就知道了。

• ### 1062. 昂贵的聘礼

思路： 实际上是一个图模型，采用递归，物品之间的交换有一条关系边，比如国王需要物品2，那么可以用8000来交换，此时子问题就变成了从物品2出发，所需要的最少...

• ### POJ 刷题系列：2002. Squares

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### Antenna Placement

思路： 看了discuss，咋有那么多人纠结无向图和有向图的区别。而且我也并没有理解所谓的答案： 顶点数 - 最大匹配数 / 2，说说我的思路吧。首先在二维...