关于Two-Pass标记连通域个数

关于Two-Pass标记连通域个数

背景

在完成图像的一系列处理后，得到二值图，一般会统计目标数量，即是获取连通域个数，这里采用TwoPass的方法。

基本思想

在Two-pass连通域标记中，第一次标记(first pass)时从左向右，从上向下扫描，会将各个有效像素置一个label值，判断规则如下(以4邻域为例)：

1. 当该像素的左邻像素和上邻像素为无效值时，给该像素置一个新的label值，label ++;
2. 该像素的左邻像素或者上邻像素有一个为有效值时，将有效值像素的label赋给该像素的label值；
3. 当该像素的左邻像素和上邻像素都为有效值时，选取其中较小的label值赋给该像素的label值。

此时，还需维护一个关系表，记录哪些label值属于同一个连通域。这个关系表通常用union-find数据结构来实现。

原文在这

还有个图：

原文说用union-find结构保存连通域，没仔细看，于是自己用了个数组保存，类似于hash...实现起来也并不是很麻烦，大概这样，在开始建立一个map数组固定大小，一般而言应该与用于标记的最大数一致（注意，这里是标记数，是小于连通域数的），这里取uint16最大值，65535，这样也就意味着连通域数不能太大，估计最大能达到万把个吧，因为不同的图标记数和连通域数关系是不一样的。

在FirstPass时，取周围点的标记最小值，map[标记]=min,这样就构成了map数组，然后根据map数据进行第二次标记。

实现

int ImageAlgorithm::TwoPassConnetedDomin(Mat image) {
Mat imageFlag;
imageFlag.create(image.rows, image.cols, CV_16UC1);
for (int k = 0; k < image.rows; ++k) {
for (int i = 0; i < image.cols; ++i) {
imageFlag.at<ushort>(k, i) = UINT16_MAX;
}
}
uint16_t mapp[UINT16_MAX];
memset(mapp, UINT16_MAX, sizeof(uint16_t));
//第一次扫描，完成ImageFlag中的标记
int num = 0;
for (int i = 0; i < image.rows; ++i) {
for (int j = 0; j < image.cols; ++j) {
auto &cu = image.at<Vec3b>(i, j);
if (cu[0] == 255) {
uint16_t pos[4];
auto &up = pos[0];
auto &left = pos[1];
auto &ul = pos[2];
if (i > 0)
up = imageFlag.at<ushort>(i - 1, j);
if (j > 0)
left = imageFlag.at<ushort>(i, j - 1);
if (i > 0 && j > 0)
ul = imageFlag.at<ushort>(i - 1, j - 1); uint16_t min = pos[0];
for (int m = 1; m < 3; m++)
if (min > pos[m])
min = pos[m];
for (int m = 0; m < 3; m++) {
if (mapp[pos[m]] > min)
mapp[pos[m]] = min;
}
if (min == UINT16_MAX) {
imageFlag.at<ushort>(i, j) = num;
mapp[num] = num;
num++;
if(num>=UINT16_MAX)
return -1;
} else {
imageFlag.at<ushort>(i, j) = min;
} }
}
}
//第二次扫描，进行标记，以及修改map
map<ushort, uint32_t> colorMap;
int total = 0;
for (int n = 0; n < num; ++n) {
if (mapp[n] == n) {
total++;
uint32_t t = 0;
for (int i = 0; i < 3; ++i) {
t += (uint32_t) (rand() / (RAND_MAX + 0.0) * 255) << (i * 8);
}
colorMap[n] = t;
} else
mapp[n] = mapp[mapp[n]];
} for (int i = 0; i < imageFlag.rows; ++i) {
for (int j = 0; j < imageFlag.cols; ++j) {
auto t = imageFlag.at<ushort>(i, j);
if (t != UINT16_MAX) {
uint32_t c = colorMap[mapp[t]];
image.at<Vec3b>(i, j)[0] = (uchar) c;
image.at<Vec3b>(i, j)[1] = (uchar) (c >> 8);
image.at<Vec3b>(i, j)[2] = (uchar) (c >> 16);
}
}
}
return total;
}