引言：本文介绍简化的漫水填充算法，用于二值图像聚类或者点云栅格聚类，并给出了c++实现。
介绍
floodFill，又叫seedfill，译作漫水填充算法，或者泛洪算法，其在opencv中进行了实现，参考这里。
漫水填充法是一种用特定的颜色填充联通区域，通过设置可连通像素的上下限以及连通方式来达到不同的填充效果的方法。漫水填充经常被用来标记或分离图像的一部分以便对其进行进一步处理或分析，简而言之，漫水填充就是查找和种子点联通的颜色相同或者相近的点，ps的魔棒工具就是以该算法为基础的。
对于点云栅格化后的二值占空图，也可以采用该算法查找出与种子栅格联通的栅格，遍历所有种子点（非空点），就可以得到不同的簇。
实现
下面给出该算法对二值图进行聚类的c++实现，其实质是一个DFS，优先地寻找一个完整连通域，在找的同时把他们都标记一下，找完一个完整连通域， 再去找下一个连通域：
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
45
46
47
48
49
| int cols = 2048, rows = 1024;
std::vector<int> seed_map(cols * rows, 0);
std::vector<int> label_map;
label_map.resize(cols * rows, 0);
int tot_num_obj = 0;
for (int row = 0; i < rows; ++i) {
for (int col = 0; j < cols; ++j) {
int idx = row * cols + col;
if (seed_map[idx] == 0) {
continue;
}
if (label_map[idx] != 0) {
continue;
}
std::stack<Eigen::Vector2i> neighbor_grids;
Eigen::Vector2i tmp_grid;
tmp_grid << col, row;
neighbor_grids.push(tmp_grid);
tot_num_obj++;
label_map[idx] = tot_num_obj;
while(!neighbor_grids.empty()) {
Eigen::Vector2i cur_grid = neighbor_grids.top();
neighbor_grids.pop();
for(int i = cur_grid.x - 1; i <= cur_grid.x + 1; ++i) {
if (i < 0 || i >= cols) {
continue;
}
for (int j = cur_grid.y - 1; j <= cur_grid.y + 1; ++j) {
if (j < 0 || j >= rows) {
continue;
}
int tmp_idx = j * cols + i;
if (seed_map[tmp_idx] == 0) {
continue;
}
if (label_map[tmp_idx] != 0) {
continue;
}
label_map[tmp_idx] = tot_num_obj;
tmp_grid << i, j;
neighbor_grids.push(tmp_grid);
}
}
}
}
}
|
这样就对二值占空图的每个栅格进行了标记，得到了多个簇。