如何在二进制图像中找到连通组件？

Question

我需要寻找一个算法来查找二进制图像中的所有连通分量。

如果我们把图像看成一个矩阵，它会像这样：

[ 0 0 0 0 ...
  0 0 0 0 ...
  0 1 1 1 ...
  0 1 0 1 ...
  0 1 0 0 ...
  ...
]

我想找到所有相邻的元素（包括对角线方向）。在这个例子中，只有一个组件 - 但在一张图片中可能会有数百个独立的组件。

Image => ALGORITHM => [ [(x,y)], ... ] 
                      # list of lists of coordinates (each shape is a list)

我查看了维基百科上的双遍标记算法，但我不认为它会返回实际的组件 - 它只是对不同的组件进行标记。(或者这是一样的吗？)

如果可能的话，这应该能够实时运行在视频流上。

- sdasdadas

---

两遍过程就可以了。一旦你给它们都贴上标签，只需遍历它们并按照标签将它们添加到不同的列表中。本质上，这就是三遍过程 :) - Geobits

请查阅泛洪算法。 - Jim Mischel

@shole 你说的 DFS 是指深度优先搜索吗？我该如何将图像转换为图形以执行 DFS？ - sdasdadas

@shole 只是DFS是用于图形的吗？这个图像必须以某种方式转换为图形。我是否使用位数组来表示图形的边缘？ - sdasdadas

我刚刚回复了一个简单的代码示例，你可以在这里编译并进行测试。 - shole

Answer 1

以下是一段简单的代码（使用简单的深度优先搜索）来标记不同的组件，您可以尝试它。

例如，如果您的标准输入为

4 5
0 0 0 0 1
0 1 1 0 1
0 0 1 0 0
1 0 0 0 1

那么输出结果应该是

Graph:
0 0 0 0 1 
0 1 1 0 1 
0 0 1 0 0 
1 0 0 0 1 

Output:
0 0 0 0 1 
0 2 2 0 1 
0 0 2 0 0 
3 0 0 0 4

相同的数字表示该单元格属于同一个组件。

我假设所有8个方向都属于同一个组件，如果你只想要4个方向，请更改dx []和dy []

此外，我假设输入最多为200 * 200，并且我做了一些事情来避免处理那些烦人的数组越界问题，你可以检查一下 :)

#include<cstdio>
#include<cstdlib>
#include<cstring>

int g[202][202] = {0};
int w[202][202] = {0};

int dx[8] = {-1,0,1,1,1,0,-1,-1};
int dy[8] = {1,1,1,0,-1,-1,-1,0};

void dfs(int x,int y,int c){
    w[x][y] = c;
    for(int i=0; i<8;i++){
        int nx = x+dx[i], ny = y+dy[i];
        if(g[nx][ny] && !w[nx][ny]) dfs(nx,ny,c);
    }
}

int main(){
    int row, col, set = 1;
    scanf("%d%d", &row, &col);

    for(int i=1; i<=row; i++) for(int j=1; j<=col; j++) scanf("%d", &g[i][j]);

    for(int i=1; i<=row;i++)
        for(int j=1; j<=col; j++)
            if(g[i][j] && !w[i][j])
                dfs(i,j,set++);

    printf("Graph:\n");
    for(int i=1; i<=row;i++){
        for(int j=1; j<=col;j++)
            printf("%d ", g[i][j]);
        puts("");
    }
    puts("");
    printf("Output:\n");
    for(int i=1; i<=row;i++){
        for(int j=1; j<=col;j++)
            printf("%d ", w[i][j]);
        puts("");
    }

    return 0;
}

- shole