7

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.

sdasdadas
  • 23,917
  • 20
  • 63
  • 148
  • 1
    Two-pass is fine. Once you have them all labeled, simply iterate over them and add them to separate lists by label. In essence, make it three-pass :) – Geobits Feb 26 '14 at 19:21
  • Look up [flood fill algorithm](http://en.wikipedia.org/wiki/Flood_fill) – Jim Mischel Feb 26 '14 at 21:40
  • My thought is Connnected-component labeling(CCL) is fine, @Geobits is right, once you got the label of those components, the post-processing is not a problem (in terms of complexity). What I am thinking is that, actually it seems CCL is a bit overkilling.. isn't it a simple DFS can mark all the components with same complexity? – shole Feb 27 '14 at 18:12
  • @shole By DFS, you mean depth first search? How do I get the image into a graph to perform a DFS? – sdasdadas Feb 27 '14 at 20:48
  • @JimMischel How do I perform flood fill for multiple components? – sdasdadas Feb 27 '14 at 20:49
  • Maintain a boolean array that's the size of your array, and set it initially to all false. As you scan the array and flood fill, set the corresponding values in the boolean array to true, meaning that you've already matched them. Whenever you find a non-background pixel whose corresponding value in the boolean array is false, you have to flood fill. Each call to flood fill is a different component. You're done when you scan the last item in the array. – Jim Mischel Feb 27 '14 at 22:26
  • @sdasdadas Yes DFS it's depth first search. I don't get your question, what you mean by "get the image into a graph"? I think somehow in your question / situation, you are already able to get the 0-1 matrix of the image? So I thought no matter I use CCL or DFS, the input is a 2D bit array..Am I missing anything? – shole Feb 28 '14 at 00:42
  • @shole It's just that DFS is for graphs? The image must be converted to a graph in some way. Am I using the bit array for the edges of the graph? – sdasdadas Feb 28 '14 at 02:41
  • @sdasdadas not only graph, or should I say, even for graphs (in graph theory), the implementation is using array as well..let me write a few lines of codes and reply as an example maybe – shole Feb 28 '14 at 02:57
  • I just reply a simple code sample, you may compile and play around with [this](http://www.compileonline.com/compile_cpp11_online.php) – shole Feb 28 '14 at 03:39
  • Do you want a single pass algorithm? They do exist. – Rethunk Mar 01 '14 at 06:16

1 Answers1

12

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

The same number represent that cell belongs to the same component.

I am assuming all 8-directions belongs to the same component, if you only want 4-directions, change dx[] and dy[]

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;
}
shole
  • 4,046
  • 2
  • 29
  • 69