如何找到二进制图像中的连接组件? [英] How do I find the connected components in a binary image?
问题描述
我在寻找一种算法来找到所有连接的组件在我的二进制图像。
I am looking for an algorithm to find all connected components in my binary image.
如果我们认为像一个矩阵的形象,它看起来像:
If we think of the image like a matrix, it looks like:
[ 0 0 0 0 ...
0 0 0 0 ...
0 1 1 1 ...
0 1 0 1 ...
0 1 0 0 ...
...
]
我想找到所有正在接触的人(对角,以及)。在这个例子中,只有一个构件 - 但可能有数百个独特的构成部分中的图像
I would like to find the all the ones that are touching (diagonally, as well). In this example, there is only one component - but there may be hundreds of unique components in an image.
Image => ALGORITHM => [ [(x,y)], ... ]
# list of lists of coordinates (each shape is a list)
我已经看了看二传的标签算法,但我不'不敢相信它返回我的实际组成部分 - 它只是标注了不同的组件。 (或者这是同一个?)
I have looked at the two pass labelling algorithm on Wikipedia, but I don't believe it returns me the actual components - it just labels the distinct components. (Or is this one and the same?)
如果可能的话,这应该是能在对一个视频流的实时运行。
If possible, this should be able to run in real-time against a video stream.
推荐答案
下面是一个简单的code。使用简单的DFS来标记不同的组件(C ++),你可以尝试一下。
Below are a simple code (C++) using simple dfs to mark different component, you may try it out.
例如,如果你的标准输入输入
For example, if your stdin input is
4 5
0 0 0 0 1
0 1 1 0 1
0 0 1 0 0
1 0 0 0 1
那么输出应该是
Then the output should be
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
相同数量重新present该小区属于相同的组件。
The same number represent that cell belongs to the same component.
我假设所有8个方向上属于同一个组件,如果你只是想4方向, 变化DX []和dy []
I am assuming all 8-directions belongs to the same component, if you only want 4-directions, change dx[] and dy[]
另外,我假设输入最多为200 * 200的,我做了一件以避免处理那些烦人的阵列出境的问题,您可以检查出来:)
Also I am assuming the input is at most 200*200, and I did something to avoid handling those annoying array outbound issues, you may check it out :)
#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;
}
这篇关于如何找到二进制图像中的连接组件?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!