如何在二進制圖像中查找連接的組件？

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) 

我已經看過了two pass labelling算法在維基百科上，但我不相信它返回我的實際組成部分 - 它只是標籤的不同的組件。 （或者這是一樣的嗎？）

如果可能，這應該能夠實時對視頻流運行。

Answer 1

下面是使用簡單dfs標記不同組件的簡單代碼（C++），您可以試試。

例如，如果你的stdin的輸入是

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; 
}