连通成分（连通域）标记算法（⼀）bwlabel算法的C++实现
（基于opencv）
在图像处理过程中，我们经常需要对图像进⾏连通成分（连通域）的提取操作，提取连通成分的算法也就成了我们⼀直在研究的⼀个算法。近期图像处理⽼师给了我们⼀个标记⼀张图中连通成分的任务，不同连通成分⽤不同的标签标记，要求算法效率⾼。我对其进⾏了简单思考，现在把我觉得我所想出来的⼏种算法中的最优的⼀个算法进⾏讲解。
⾸先我们拿到⼀张图，假设是下⾯这张：
图中⿊⾊表⽰符合我们要求的值，从图中可以看出，图中有三个相互独⽴的⿊⾊团，可以称之为三个独⽴的连通成分，⽽我们要做的就是把这三个连通成分在图中找出来并按照⼀定顺序给他们标上不同的标签，在⼀个连通成分中的像素点标签相同。
那么我们可以怎么做呢？我是这么想的。
1. 逐⾏扫描，将每⼀⾏中的连通成分标记起来；
2. 扫描下⼀⾏时，判定是否与上⼀⾏的连通成分有相连。若有相连，则标记为上以⾏连通成分的标签。若与多个上⼀⾏的连通成分相
连，则把这些标签保存到⼀个数组中，以⽅便建⽴⼀个标签等价表。
3. 将等价的标签都转换为其等价表中最⼩的那个标签。（如1,2,3标签等价，则将标签为3的像素点的标签转换为2，再将标签为2的像素
点的标签转换为1，最后实现连通成分中的各像点标签相同）。
4. 将标签映射到⼀个从1开始的连续区域。
可能这么说还是有些同学不懂，没关系，我们对照上⾯的图来分析⼀下：喜欢你粤语谐音
⾸先，我们可以逐⾏扫描，把每⼀⾏中的连通成分标记起来。如上⾯第⼆⾏就⼀个我们所需的像素值，那么给它标上标签1。
然后再扫描下⾯⼀⾏，把这⼀⾏中连在⼀起的符合要求的像素点⼜附上⼀样的标签，但是我们发现，第三⾏中的两个⿊⾊像素点与第⼆⾏中的那个已经标记的像素点是连在⼀起的，是同⼀个连通成分，应该附上相同的标签。所以我们在扫描后⾯的⾏的时候，就应该判断⽬前⾏中存在的连通域是否和上⼀⾏的某些连通域相连，如果相连，就赋予上⼀⾏的标签，说明它们是同⼀个连通域。
当扫描到第四⾏时，我们发现这⼀⾏前两个⿊⾊像素点是相连的，并且与上⼀⾏的两个⿊⾊点相连，所以赋予上⼀⾏的标签1，但第三个⿊⾊像素点是独⽴的，也没有与上⼀⾏的像素点相连，这时候就应该赋予它⼀个新的标签，标签1，我们已经⽤过，所以赋予它新的标签2，说明它是⼀个新的连通成分中的元素。当然，也可能它会通过下⾯⾏的⼀些连通成分和连通成分1连接起来，这些我们就后⾯再做处理。
再往下扫描的时候，我们可能会发现某⼀⾏把上⾯两个标签不⼀样的连通成分连接起来了，那么它们应该属于同⼀个连通成分（上⾯这张图中没有这种情况），这个时候这⼀个连接两个不同标签的连通成分到底该赋予哪个标签呢？不要急，我们随便给它⼀个标签，就暂且给最先与它所连接的上⼀⾏连通成分的标签（如果是从左边扫描，则是左上连通成分的标签），那么右边与它连接的那个标签怎么处理呢？我们可以先判断⼀下⽬前扫描的这⼀⾏是否已经赋予了上⼀⾏的标签，如果已经赋予，并且⽬前按道理来说⼜要赋予另⼀个标签（即与它连接的第⼆个连通成分），那么我们就把第⼆个甚⾄第三个要赋予的标签和已经赋予给它的这个标签存储到⼀起，作为等价标签，后⾯再对这些标签进⾏处
理。
这样扫描⼀遍之后，基本所有连通成分都有⼀个标签了。当然也可能属于同⼀个连通成分的不同元素标签并不同，这时候我们就要把这些同⼀个连通成分中的不同标签进⾏处理了。怎么处理呢？还记得我们刚刚建⽴的等价标签表吗？我们只需要判断它们是不是等价标签，然后把它们合并起来就⾏了，把⼤的标签更好为更⼩的标签。为了节省时间，对每个连通成分其实只需要读取它的第⼀个像素点的标签就⾏了，所以并不需要对其中的所有像素点都进⾏标签更换。
做到这⾥我们⼯作差不多就完成了，但是当时题⽬要求的是连续标签，所以这⾥再把之前的标签映射到⼀个从1开始的连续区域。这⾥停⼀下，有些同学可能会问，标签为什么不连续呢？我们可以看到刚刚标签合并的时候，我们只是把相对⼤的标签更换为了更⼩的标签，那么刚刚那个⼤的标签就为空了，⽐如本来是1 2 3 4，但是1和3等价，那么3变成了1，就成了 1 2 4 ，这样就不连续了。
那么怎么做呢？不要急，先想⼀想。有些同学会说，把空缺标签的后⼀个依次往前移不就⾏了？这样确实能完成任务，但是当图中独⽴的连通成分较多的时候，需要移动的标签就较多，时间就变长了。这⾥我采⽤的是，⼀个变量从前⾯遍历寻找空缺标签，⼀个从后⾯遍历寻找不为空的标签，寻找到第⼀个的时候就停⽌，然后交换这两个连通成分，并把刚从后⾯交换过来的标签更换为⽬前空缺的标签。这⾥有点快速排序算法的思想。还不理解的同学可以再好好理解⼀下快速排序。最后当两个变量相遇，就说明所有空缺标签都填满了。
这样我们的任务就完成了，可以把每个连通成分在另⼀张图上打印出来，观察⼀下效果。
以下就是我的实现代码了，连通成分的标记⽤了⼀个结构体来实现。⽐如⾏连通成分，只需要记住这个连通成分所在的⾏，起始位置和末了位置即可，这样就⽅便后⾯的操作。
话不多说，附上我的代码：
#include <iostream>
#include <opencv2\highgui\highgui.hpp>
#include <opencv2\imgproc\imgproc.hpp>
#include <vector>
对党支部的意见和建议//连通区域结构体
struct RowGroups{
int begin_pos; //区域的y轴起始值
long end_pos; //区域的y轴结束值
int row; //区域所在的⾏
除臭鞋柜int block_flag; //区域的标记
int change_times; //区域标记改变的次数
// std::vector<int> other_flags; //该区域所连接的还未进⾏融合其他区域的标记⽤于连接了多个区域时
};
//两个连通成分相加保留第⼀个参数的标签合并连通成分时⽤
std::vector<RowGroups> add_Groups(std::vector<RowGroups>& v1, std::vector<RowGroups>& v2)
{
std::vector<RowGroups> r;
for (auto i = 0; i < v1.size(); ++i) {
r.push_back(v1[i]);
}
for (auto j = 0; j < v2.size(); ++j){
// v2[j].block_flag = v1[0].block_flag; //更换标签但是在该程序中输出标签时直接读取每个连通成分第⼀个像素点的标签即可
r.push_back(v2[j]);
}
return r;
}
//获取图像中的连通成分并进⾏标记
void getConnectedDomain(cv::Mat &inputImg, cv::Mat &outputImg)
{
if (inputImg.channels() > 1) //⾮单通道图像退出程序
{
std::cout << "getConnecteDomain input error , inputImage's channels > 1 " << std::endl;
return;
}
std::vector<std::vector<RowGroups>> row_groupsAll; //所有⾏连通区域的集合
std::vector<std::vector<RowGroups>> connectedDomain; //⽤来存储连通成分的容器
//std::vector<RowGroups> temp_run; //中间变量
// std::vector<RowGroups> bridge_group; //连接了多个⾏连通域的⾏连通域
std::vector<int> equal_1, equal_2; //等价标签
int block_flag = 0;
int new_label = 1;
int rows = ws;
int cols = ls;
//outputImg = cv::Mat::zeros(inputImg.size(), pe());
outputImg = cv::Mat::zeros(cv::Size(cols, rows), CV_8UC1);
std::cout << "rows*cols: " << rows << cols << std::endl;
//遍历图像找出⾏连通成分
for (int i = 0; i < rows; i++)
{
int flagGroup = 0;
std::vector<RowGroups> row_group; //⾏连通区域
uchar *input_img = inputImg.ptr<uchar>(i);
for (int j = 0; j < cols; j++)
{
if ((int)input_img[j] == 0)
std::cout << "0 ";
el
std::cout << "1 ";
// std::cout << (int)input_img[j] << " ";
if ((int)input_img[j] > 0 && flagGroup == 0)
{
flagGroup = 1;
// block_flag++;
RowGroups tempGroups;
销售渠道tempGroups.begin_pos = j;
tempGroups.change_times = 0;
// tempGroups.block_flag = block_flag;
row_group.push_back(tempGroups);
}
el if ((int)input_img[j] == 0 && flagGroup == 1 || flagGroup==1 && j==cols-1)
{
flagGroup = 0;
int vect_size = row_group.size();
row_group[vect_size - 1].end_pos = j - 1;
if (i > 0)
{
for (int m = 0; m < row_groupsAll[i - 1].size(); m++)
{
//判断是否与上⼀⾏的某些⾏连通域相连，并更新新的标签
if (row_groupsAll[i - 1][m].begin_pos >= 0 && //保证该⾏所保存的连通域不为空 row_groupsAll[i - 1][m].begin_pos <= row_group[vect_size - 1].end_pos &&
高中报名row_groupsAll[i - 1][m].end_pos >= row_group[vect_size - 1].begin_pos)
{
if (row_group[vect_size - 1].change_times == 0)
{
row_group[vect_size - 1].block_flag = row_groupsAll[i - 1][m].block_flag;
if (connectedDomain.size() < row_groupsAll[i - 1][m].block_flag)
{
std::vector<RowGroups> temp_connect;
temp_connect.push_back(row_group[vect_size - 1]);
connectedDomain.push_back(temp_connect);
}
el
connectedDomain[row_groupsAll[i - 1][m].block_flag - 1].push_back(row_group[vect_size - 1]); // row_groupsAll[i][k].other_flags.push_back(row_groupsAll[i][k].block_flag);
}
el
{
{
equal_1.push_back(row_group[vect_size - 1].block_flag); //保存等价标签
equal_2.push_back(row_groupsAll[i - 1][m].block_flag);
// row_groupsAll[i][k].other_flags.push_back(row_groupsAll[i - 1][j].block_flag);
// bridge_group.push_back(row_groupsAll[i][k]);
}
row_group[vect_size - 1].change_times++;
冬至谚语大全
}
}
}
if (row_group[vect_size - 1].change_times == 0)
{
row_group[vect_size - 1].block_flag = new_label;
if (connectedDomain.size() < new_label)
{
std::vector<RowGroups> temp_connect;
temp_connect.push_back(row_group[vect_size - 1]);
connectedDomain.push_back(temp_connect);
}
el
connectedDomain[new_label - 1].push_back(row_group[vect_size - 1]);
new_label++;
}
}
}
std::cout << std::endl;
if (row_group.size() == 0)
{
RowGroups nonGroups; //⽤来表⽰这⼀⾏没有值为1的像素点
nonGroups.begin_pos = -1; //赋值为⼀个不存在的位置-1 ⽅便后续判断
row_group.push_back(nonGroups);
}
if (row_group.size() > 0)
row_groupsAll.push_back(row_group); //每⼀⾏保存⼀次
}
if (row_groupsAll.size() == 0)
{
std::cout << "There is no connected domain in this image!" << std::endl;
}
el
{
//根据连接了多个⾏连通成分的⾏连通成分来找出可以继续合并的区域
if (equal_1.size() > 0)
{
还少胶囊的功效与作用for (int i = equal_1.size() - 1; i >= 0; i--)
{
int max_label = equal_1[i] > equal_2[i] ? equal_1[i] : equal_2[i];
int min_label = equal_1[i] < equal_2[i] ? equal_1[i] : equal_2[i];
std::cout << "equal_labels: "; //输出等价标签
std::cout << min_label << max_label << std::endl;
std::vector<RowGroups> temp;
temp = add_Groups(connectedDomain[min_label - 1], connectedDomain[max_label - 1]); connectedDomain[min_label - 1].clear();
connectedDomain[max_label - 1].clear(); //合并之后相关的区域清零
connectedDomain[min_label - 1] = temp;
}
}
//equal_1.clear();
//equal_2.clear();
//将标签范围映射到连续的标签
//将标签范围映射到连续的标签
int domain_size = connectedDomain.size();
for (int i = 0; i < domain_size; i++)
{
int flag_meet = 0;
if (connectedDomain[i].size() == 0)
{
for (int j = domain_size - 1; j > i; j--)
{
if (connectedDomain[j].size() > 0)
{
connectedDomain[i] = connectedDomain[j];
connectedDomain[i][0].block_flag = i;
domain_size--;
flag_meet = 1;
break;
地球上的水资源}
}
if (flag_meet == 0) //如果该flag仍为0，则说明后⾯都没有不为空的连通成分，可以直接退出循环
break;
}
}
// uchar *output_img = outputImg.data;
std::cout << std::endl;
//写标签
for (int i = 0; i < connectedDomain.size(); i++)
{
for (int j = 0; j < connectedDomain[i].size(); j++)
{
int rows = connectedDomain[i][j].row;
uchar *output_img = outputImg.ptr<uchar>(rows);
std::cout << connectedDomain[i][i].begin_pos << " " << connectedDomain[i][j].end_pos << std::endl; for (int k = connectedDomain[i][j].begin_pos; k <= connectedDomain[i][j].end_pos; k++)
{
// outputArray[connectedDomain[i][j].row][k] = i + 1;
// output_img[k] = i + 1;
// output_img[k] = 255;
output_img[k] = connectedDomain[i][0].block_flag;
// std::cout << connectedDomain[i][j].block_flag << " ";
}
}
std::cout << std::endl;
}
}
std::cout << "output_img data : " << std::endl;
for (int i = 0; i < ws; i++)
{
uchar *opt_img = outputImg.ptr<uchar>(i);
for (int j = 0; j < ls; j++)
{
std::cout << (int)opt_img[j] << " ";
}
std::cout << std::endl;
}
}
//主函数
int main()
{
cv::Mat flag_img;
cv::Mat src = cv::imread("test.png"); //输⼊图像
