欢迎来到我的主页!
0%

经典算法：基于行程的连通域标记算法

发表于 更新于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

引言：本文介绍一种用于二值图像或者占空图的聚类算法，并给出c++实现。

介绍

Two-Pass算法是一种基于行程的二值图像连通域标记算法，matlab中连通区域标记函数bwlabel中使用的就是该算法，其算法流程如下：

1，逐行扫描图像，我们把每一行中连续的白色像素组成一个序列称为一个团(run)，并记下它的起点start、它的终点end以及它所在的行号。

2，对于除了第一行外的所有行里的团，如果它与前一行中的所有团都没有重合区域，则给它一个新的标号；如果它仅与上一行中一个团有重合区域，则将上一行的那个团的标号赋给它；如果它与上一行的2个以上的团有重叠区域，则给当前团赋一个相连团的最小标号，并将上一行的这几个团的标记写入等价对，说明它们属于一类。

3，将等价对转换为等价序列，每一个序列需要给一相同的标号，因为它们都是等价的。从1开始，给每个等价序列一个标号。

4，遍历开始团的标记，查找等价序列，给予它们新的标记。

5，将每个团的标号填入标记图像中。

6，结束。

实现

下面给出其c++实现，主要分四步进行：

第一步：查找所有团并记录，需要记录团所在的行号、团开始的位置、结束的位置，当然还有一个表征团总数的变量。需要注意的就是团开始位置和结束位置在行首和行末的情况要单独拿出来考虑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void fillRunVectors(const std::vector<std::vector<int>>& bimage, int& NumberOfRuns, std::vector<int>& stRun, std::vector<int>& enRun, std::vector<int>& rowRun, const int& rows, const int& cols, std::vector<int>& label_map) {
    for (int i = 0; i < rows; ++i) {
        auto& rowData = bimage[i];
        if (rowData[0] == 1) {
            NumberOfRuns++;
            stRun.emplace_back(0);
            rowRun.emplace_back(i);
            label_map[i * cols] = NumberOfRuns;
        }
        for (int j = 1; j < cols; ++j) {
            int cur_idx = i * cols + j;
            if (rowData[j-1] == 0 && rowData[j] == 1) {
                NumberOfRuns++;
                stRun.emplace_back(j);
                rowRun.emplace_back(i);
                label_map[cur_idx] = NumberOfRuns;
            } else if (rowData[j-1] == 1 && rowData[j] == 0) {
                enRun.emplace_back(j-1);
            } else if (rowData[j] == 1) {
                label_map[cur_idx] = NumberOfRuns;
            }
        }
        if (rowData[cols - 1] == 1) {
            enRun.emplace_back(cols - 1);
        }
    }
}

第二步：遍历所有的团，完成团的标记与等价对列表的生成。这里判断团是否相邻的关键条件是：一个团的开始位置小于另一个团的结束位置，且结束位置大于另一个团的开始位置。 这里的equivalences 用于存储等价对，offset：0对应四连通，1对应八连通。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void markArea(vector<int>& stRun, vector<int>& enRun, vector<int>& rowRun, int NumberOfRuns, vector<int>& runLabels, vector<pair<int, int>>& equivalences, int offset) {
    int idxLabel = 1;    // 标记编号
    int curRowIdx = 0;    // 当前所在行   
    int firstRunOnCur = 0;    // 当前行的第一个团索引
    int firstRunOnPre = 0;    // 前一行的第一个团索引
    int lastRunOnPre = -1;    // 前一行的最后一个团索引
    // 初始化每个团的标签都为0
    runLabels.assign(NumberOfRuns, 0);
    
    for(int i = 0; i < NumberOfRuns; ++i) {
        if (rowRun[i] != curRowIdx) {
            // 换行后更新状态变量
            curRowIdx = rowRun[i];
            firstRunOnPre = firstRunOnCur;
            lastRunOnPre = i - 1;
            firstRunOnCur = i;
        }
        // 相邻行不存在团
        if（curRowIdx != rowRun[lastRunOnPre] + 1） {
            runLabels[i] = idxLabel++;
            continue;
        }
        // 对前一行进行遍历，检查是否有相邻的团
        for (int j = firstRunOnPre; j <= lastRunOnPre; ++j) {
            if (stRun[i] <= enRun[j] + offset && enRun[i] >= stRun[j] - offset) {
                // 之前没有被标记过，即j是上一行第一个与当前团相邻的
                if (runLabels[i] == 0) {
                    runLabels[i] = runLabels[j];
                } else if (runLabels[i] != runLabels[j]) {
                    equalLabels.emplace_back(std::make_pair(runLabels[i], runLabels[j]));
                }
            }
        }
        // 没有与前一列如何run重合
        if (runLabels[i] == 0) {
            runLabels[i] = idxLabel++;
        }
    }
}

第三步：将等价对处理成等价序列，比如有如下等价对：(1,2),(1,6),(3,7),(9-3),(8,1),(8,10),(11,5),(11,8),(11,12),(11,13),(11,14),(15,11)，得到的最终序列是：

list1：1-2-5-6-8-10-11-12-13-14-15

list2：3-7-9

list3：4

这里还是采用DFS思想，c++实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void replaceSameLabel(std::vector<int> runLabels, std::vector<pair<int, int>>& equivalence) {
    int maxLabel = *std::max_element(runLabels.begin(), runLabels.end());
    // 等价标签矩阵，值为true表示这两个标签等价
    std::vector<std::vector<bool>> eqTab(maxLabel, std::vector<bool>(maxLabel, false));
    // 将等价对信息转移到矩阵上
    std::vector<pair<int, int>>::iterator vecPairIt = equivalence.begin();
    while (vecPairIt != equivalence.end()) {
        eqTab[vecPairIt->first - 1][vecPairIt->second - 1] = true;
        eqTab[vecPairIt->second - 1][vecPairIt->first - 1] = true;
        vecPairIt++;
    }
    // 标签映射，会将上一步团的标号映射到序列的标号，也是这一步的关键结果。
    std::vector<int> labelFlag(maxLabel, 0);
    // 等价标签队列
    std::vector<int> tempList;
    // 当前使用的标签
    int curLabel = 1；
    
    for (int i = 1; i <= maxLabel; i++) {
        // 如果该标签已被映射，直接跳过
        if (labelFlag[i - 1] != 0) {
            continue;
        }
        labelFlag[i - 1] = curLabel;
        tempList.emplace_back(i);
        // 在所有标签中寻找与当前标签等价的标签(这里可以换成栈操作，和floodfill类似) 
        for (int j = 0; j < tempList.size(); ++j) {
            for (int k = 1; k <= maxLabel; ++k) {
                // 等价且未访问
                if (eqTab[tempList[j] - 1][k - 1] && labelFlag[k] == 0) {
                   labelFlag[k - 1] = curLabel;
                   tempList.emplace_back(k);
                }
            }
        }
        curLabel++;
        tempList.clear();
    }    
    
    // 根据映射修改标签
    for (auto itr = runLabels.begin(); itr != runLabels.end(); ++iter) {
        *itr = labelFlag[*itr - 1];
    }
}

第四步：填充二值图中每个栅格的标签。

1
2
3
4
5
6
7
8
void fillLabel(const std::vector<int>& runLabels, std::vector<int>& label_map) {
    for (size_t i = 0; i < label_map.size(); ++i) {
        if (label_map[i] == 0) {
            continue;
        }
        label_map[i] = runLabels[label_map[i]];
    }
}

总结

该算法本质上和floodFill算法是一样的，区别在于floodFill是对每个栅格进行深度优先搜索，而这个是对团进行深度优先搜索。另外，在算法的第三步在对等价对进行合并时，可以用并查集进行优化，也可以用稀疏矩阵与Dulmage-Mendelsohn分解算法用来消除等价对（matlab中的做法），比较复杂。