# Almost-connected-component labeling14

Posted by Steve Eddins,

In a recent post I demonstrated the use of bwdist (binary image Euclidean distance transform) to perform isotropic dilation. This was inspired by something that Brett asked me about.

Last night Brett posted a comment explaining a little bit more about what he was doing. I'm going to coin a term for what Brett described: almost-connected-component labeling.

I'll illustrate with a simple synthetic image containing a number of circular blobs.

url = 'http://blogs.mathworks.com/images/steve/2010/blobs_in_clumps.png';
imshow(bw)

Now let's label the connected components in bw.

cc = bwconncomp(bw)
cc =

Connectivity: 8
ImageSize: [337 313]
NumObjects: 23
PixelIdxList: {1x23 cell}



You can see that there are 23 distinct objects detected. The function label2rgb is useful for visualizing connected components. You use it by converting the output of bwconncomp to a label matrix using labelmatrix and then passing the result to label2rgb.

L = labelmatrix(cc);
rgb = label2rgb(L, 'jet', [.7 .7 .7], 'shuffle');
imshow(rgb)

Brett's question was this: How can we label and measure the three clumps instead of the smaller circles? (The clumps were cell clusters in Brett's problem.) The answer is to combine an isotropic dilation step with connected component labeling.

Let's say that two circles are "almost connected" if they are within 25 pixel units of distance from each other. So start with an isotropic dilation step:

bw2 = bwdist(bw) <= 12.5;
imshow(bw2)

Now we can perform connected component labeling on bw2:

L2 = labelmatrix(bwconncomp(bw2));
rgb2 = label2rgb(L2, 'jet', [.7 .7 .7], 'shuffle');
imshow(rgb2)

We have the three clumps now, but they are too "fat." That is, they have too many pixels in them because of the isotropic dilation step. So if, for example, we measure the area of each clump using regionprops:

s = regionprops(L2, 'Area');
[s.Area]
ans =

14418       11023        6341



we get a distorted area measurement. What if we want to perform measurements only on the pixels in the original clumps?

A nice application of logical indexing will modify L2 to get rid of the added pixels. The following line sets to 0 all elements of L2 corresponding to background pixels in bw.

L2(~bw) = 0;
imshow(label2rgb(L2, 'jet', [.7 .7 .7], 'shuffle'))
s = regionprops(L2, 'Area');
[s.Area]
ans =

4827        3510        2208



Do you have an application for "almost-connected-component labeling"? Post your comment here.

PS. Hey, in case you didn't notice, the R2010b release is out. I'll post something about it soon.

Get the MATLAB code

Published with MATLAB® 7.10

### Note

Siddharth replied on : 1 of 14

This is off topic, but, regarding R2010b : It would be great if you could address the ImageAdapter class. It seems to be getting integrated into more and more functions in the Image Processing Toolbox and I’ve found it to be a very handy enhancement. I currently use it with blockproc, but I’m interested in certain use cases that may not be very common.

Steve replied on : 2 of 14

Siddharth—Thanks for the suggestion.

Matthew Miller replied on : 3 of 14

This is a pretty slick application combining connected component labeling and dilation. Now that I’ve seen this I’m going to expand a library of functions I’ve built to identify and track contiguous areas of precipitation in radar and satellite data. I’m going to experiment with identifying, quantifying, and tracking groups or “families” of convective cells embedded in areas of otherwise stratiform precipitation.

Oliver Woodford replied on : 4 of 14

I once had a need to connect pixels which satisfied max(abs(dx), abs(dy)) < 5. I used the same technique – dilating with ones(4), then using bwconncomp. However, sometimes you might have different connection criteria, which cannot be solved using dilation, e.g. the nhood [1 0 1]. It would be great to see bwconncomp support arbitrary connection nhoods, to get round this problem.

Steve replied on : 5 of 14

Oliver—Can you say more about this? What constraint on the form of connectivity do you want to relax, and can you give an example of an application?

Oliver Woodford replied on : 6 of 14

I’d like to be able to specify a connection nhood, e.g. [1 0 0; 0 1 0; 0 0 1], of any size, though with the criterion isequal(nhood, fliplr(flipud(nhood))). An example application is where you have an MRF (each image pixel being a variable) with some odd-shaped cliques, some variables are known and some are not, and you want to compute the independent regions of unknown variables in the MRF. This could crop up in computer vision applications which use such cliques, such as image denoising, texture/image synthesis, stereo, optic flow etc.

Steve replied on : 7 of 14

Oliver—How does dilation fail in such cases?

Oliver Woodford replied on : 8 of 14

It’s not necessarily the dilation which fails. If I had the nhood [1 0 1] and the image [1 1 1] I would want the output of bwconncomp to be [1 2 1].

Steve replied on : 9 of 14

Oliver—I know how this can be done using the existing toolbox functions. I’ll post something on it.

Oliver Woodford replied on : 10 of 14

Joel MacAuslan replied on : 11 of 14

Nice work.

A somewhat different solution would use the Minimal Spanning Tree (which you can look up under user-contributed MATLAB software). The MST of a set of discrete points is the collection of straight-line paths, “bonds”, of shortest total length that pass through every point in the set just once; in general, this is a tree-structured object.

[Technical aside: Most MST algorithms run on lists of points of arbitrary coordinates; however, it is trivial to extract such points from the regularly spaced pixels of an image — MATLAB’s FIND function does just this — and it is even easy to optimize an MST algorithm for this case. End aside]

The MST would have one significant advantage: You can look through the bond lengths AFTER determining the tree. Thus, you could decide what length to use as a criterion for “almost connected” vs. “distant enough to be separated”: a length that could be suggested by the data, instead of necessarily imposed in advance. (This is analogous to using Principle Components Analysis on some data set to determine, in a data-suggested fashion, which linear components to keep and which ones describe irrelevantly small features of the data set.)

In trade, the MST may be slower on some architectures, because dilation permits a massively-parallel algorithm, as well as a fast sequential (conventional) one; MST might not, depending on the number of points or the total number of pixels being analyzed.

Also, for this problem, it would be helpful to pre-process the image to determine its skeleton (central pixels of the dots). Otherwise, MST would spend some pointless time connecting all the pixels of each dot into a cluster, i.e., a subtree of very short total length and no particular structure. After all, it is only the bonds between the dots, and especially the longer bonds between the clusters of dots, that are interesting here.

Steve replied on : 12 of 14

Joel—Thanks very much for the ideas.

Gulcan replied on : 13 of 14

Hello Steve,
I have a kinda-similar problem. I am trying to detect buildings and obtain a labeled image after segmentation. I have also binary mask of buildings and I want to train my system for each building object. Thus, I have a labeled image and a binary mask for the desired objects. However, there are several labels in the region of corresponding component in binary mask and I want to merge these regions in labeled image and give them a single label for each object. I mean, I want to merge building segment labels which I know they are part of a building object indeed. I guess traversing all the pixels of objects in the binary mask is the most cumbersome way, but I can’t think of any other thing. Any suggestions will be appreciated. Thanks a lot.

Steve replied on : 14 of 14

Gulcan—Can you send me sample images and a more detailed description of the operation you want to perform? My contact information is on my MATLAB Central author page.