Connected component labeling

Hello Dear Experts,

Consider I have a binary image and I need to find and label the components. Without using the matlab function that does it.

I am stuck and I need to send it tomorrow morning. Please help me.

[Geoff]

Steve, I'm happy to help via this forum so that others can comment, but emailing me and asking for a Skype session is not going to be useful for you. I post on MatLab Answers while at work. I pick things up when I have spare brain time for it, but I am not employed by MatLab Answers to help you with your homework, and my employer would not be happy about me reserving a block of my morning to guide you through your assignment.

Your need may be urgent, but I'm quite certain that you would have been given more than one day to complete this, and I can't help you with time management. It would be most beneficial if you are very specific about what you need help with, while showing what code you have written, what errors or behaviour you observe, and descibing exactly what you expect to achieve. Others in the community may wish to pitch in and help, and you will get the greatest benefit that way. You have surely asked enough questions in the past to understand this.

Answer 1

[Geoff]

Is this an assignment for a course you are doing? If so, what algorithms have you discussed in lectures? Surely you would not be asked to do something with absolutely no theoretical preparation.

Exactly where are you stuck, and what have you done so far?

The way to find connected components is to use the Union Find algorithm. You run it over each non-zero pixel and do a union with its immediate neighbours. You can represent the pixel location as a single number (its linear index) if you want, to make things easier.

Then after doing all your unions, you go through the image again and find the root node of its set. You can create an image based on that, thereby colouring each connected blob of pixels with a unique value. I assume that's what you mean by "labeling".

[Steve]

Yes, but I am stuck here:

I have created a function :

function res = neighbour(x,y,img)

res = 0;

if y-1>0 && x-1>0

if img(x-1,y) == img(x,y)

...

I mean I want to check that I am not exceeding the matrix, but again I am stuck here, please help me.

[Steve]

I need to 2 pass algorithm on matlab to do this...

1st pass to label and the second one to put equivalent labels..

[Geoff]

Well, that looks okay, except I would not do the subtractions... What is wrong with "if x > 1"?

Now, think for a minute. For that test you are doing, you need only "x >1", because "y" will be in range. You need a different test for each neighbour, depending on whether you are using a different "x", "y" or both.

To test for out-of-range-by-one on the other side, you go: "x < size(img,1)" or "y < size(img,2)".

[Note 1] Later on if you are concerned about efficiency you can nest the tests for neighbours that have something in common.

[Note 2] You don't need to do a union on every neighbour. Only half of the neighbours (eg just those on the left and above). This is because the union between two pixels is symmetric - ie, you don't need to do a union on the right if you are going to later do a union on that pixel's left.

[Note 3] By the way, the usual way to index an image in MatLab is "img(y,x)", because "y" denotes the row.