Steve on Image Processing

Disconnected component labeling: part 2 3

Posted by Steve Eddins,

Last week I wrote about a user's request to perform connected-component labeling with an unusual connectivity definition:

  [1 0 1 0 1]

This definition, which is not supported by Image Processing Toolbox functions, has the effect of dividing an image into two noninteracting subimages, one containing the even columns and one containing the odd columns.

That description gives us our needed clue about how to implement such a thing. We split the image up into the two subimages, find the connected components in each subimage, and then merge the results.

bw = [1     1     1     0     0     0     0     0
    1     1     1     0     1     1     0     0
    1     1     1     0     1     1     0     0
    1     1     1     0     0     0     1     0
    1     1     1     0     0     0     1     0
    1     1     1     0     0     0     1     0
    1     1     1     0     0     1     1     0
    1     1     1     0     0     0     0     0]
bw =

     1     1     1     0     0     0     0     0
     1     1     1     0     1     1     0     0
     1     1     1     0     1     1     0     0
     1     1     1     0     0     0     1     0
     1     1     1     0     0     0     1     0
     1     1     1     0     0     0     1     0
     1     1     1     0     0     1     1     0
     1     1     1     0     0     0     0     0

bw1 = bw(:,1:2:end)
bw1 =

     1     1     0     0
     1     1     1     0
     1     1     1     0
     1     1     0     1
     1     1     0     1
     1     1     0     1
     1     1     0     1
     1     1     0     0

bw2 = bw(:,2:2:end)
bw2 =

     1     0     0     0
     1     0     1     0
     1     0     1     0
     1     0     0     0
     1     0     0     0
     1     0     0     0
     1     0     1     0
     1     0     0     0

Find connected components in each subimage assuming that each pixel is connected only to its east and west neighbors.

cc1 = bwconncomp(bw1, [0 0 0; 1 1 1; 0 0 0])
cc1 = 

    Connectivity: [3x3 double]
       ImageSize: [8 4]
      NumObjects: 12
    PixelIdxList: {1x12 cell}

cc2 = bwconncomp(bw2, [0 0 0; 1 1 1; 0 0 0])
cc2 = 

    Connectivity: [3x3 double]
       ImageSize: [8 4]
      NumObjects: 11
    PixelIdxList: {[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [18]  [19]  [23]}

Now we have to go through a bit of work to modify the PixelIdxList for each connected component.

size_bw1 = size(bw1);
size_bw = size(bw);
for k = 1:numel(cc1.PixelIdxList)
    idx = cc1.PixelIdxList{k};
    [r,c] = ind2sub(size_bw1, idx);
    new_idx = sub2ind(size_bw, r, 2*c-1);
    cc1.PixelIdxList{k} = new_idx;
end

size_bw2 = size(bw2);
for k = 1:numel(cc2.PixelIdxList)
    idx = cc2.PixelIdxList{k};
    [r,c] = ind2sub(size_bw2, idx);
    new_idx = sub2ind(size_bw, r, 2*c);
    cc2.PixelIdxList{k} = new_idx;
end

Now the pixel index lists for each connected component have been corrected to refer to pixel locations in the original image. Next we make a new connected component struct containing both sets of components.

cc = cc1;
cc.ImageSize = size_bw;
cc.NumObjects = cc1.NumObjects + cc2.NumObjects;
cc.PixelIdxList = [cc1.PixelIdxList, cc2.PixelIdxList]
cc = 

    Connectivity: [3x3 double]
       ImageSize: [8 8]
      NumObjects: 23
    PixelIdxList: {1x23 cell}

Finally, let's visualize what we ended up with by converting to a label matrix:

L = labelmatrix(cc)
L =

    1   13    1    0    0    0    0    0
    2   14    2    0    2   21    0    0
    3   15    3    0    3   22    0    0
    4   16    4    0    0    0    9    0
    5   17    5    0    0    0   10    0
    6   18    6    0    0    0   11    0
    7   19    7    0    0   23   12    0
    8   20    8    0    0    0    0    0

So it can be done, although it takes some extra coding. I confess, though, that I'm still not exactly sure why one might want to do connected component labeling this way.

Anyone have any inspiration about this? Creative ideas you'd like to share? Post your comments here.


Get the MATLAB code

Published with MATLAB® 7.11

3 CommentsOldest to Newest

Hi Steve.
Thanks for the solution. However, while your method works for the particular neighbourhood I gave, I was expressing a more general problem which this approach doesn’t solve. Consider nhood = [0 0 0 0 1; 0 1 0 0 0; 0 1 1 1 0; 0 0 0 1 0; 1 0 0 0 0]. Interestingly, the code to find connected components given such an arbitrary nhood already comes with MATLAB. Using the private function bwlabelnmex, I can do:
A = bwlabelnmex(rand(100) < 0.1, nhood);
and I believe I get the right answer, at least for this example. I think it’s a shame that this functionality isn’t (easily) available to the user. I acknowledge that it’s rare that people need to do this sort of thing, but it has cropped up for me when dealing with sparsely connected cliques in MRFs over images. Such cliques occur in algorithms such as the one presented here:
http://cns.bu.edu/~lgrady/cremers2006learning_final.pdf
Oliver

@Oliver: Thanks for your tip! I have arrays where I’d like to run bwlabel on columns only (i.e. with a neighborhood of ones(3,1), since the array contains different realizations of a process and I need a good way to identify runs of ones.

These postings are the author's and don't necessarily represent the opinions of MathWorks.