In the previous post in this series I talked about forming a graph based on pixel neighbor relationships, and then finding the connected components of the graph. Another approach starts by finding a foreground pixel and then iteratively searching that pixel's neighbors to find the connected component. Sometimes this technique is called the flood fill approach. I'll demonstrate the basic idea using a small sample image and a series of diagrams.
The matrix below and on the left is our binary image. Using 4-connected neighbors, the image has two connected components. The matrix on the right is going to become our label matrix when we're done. It is initialized to contain all zeros.
Step 1: Find a foreground pixel. Set the corresponding label matrix pixel to 1, which is the first label.
Step 2: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Set the corresponding pixels in the label matrix to 1.
Step 3: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Set the corresponding pixels in the label matrix to 1. (This step should seem familiar.)
Step 4: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Oops, there aren't any!
Step 5: We have finished labeling object 1. Now search for the next nonzero pixel. Set the corresponding pixel in the label matrix to 2, which is the next object label.
Step 6: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Set the corresponding pixels in the label matrix to 2.
Step 7: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Set the corresponding pixels in the label matrix to 2.
Step 8: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Since there aren't any, we know we have finished labeling object 2. Furthermore, since there are no nonzero pixels left in the image, we know we have completed the labeling operation.
Now let's talk about how you might program this in MATLAB. I'd use the neighbor indexing technique that I wrote about a couple of weeks ago. Start from this point:
Call the matrix on the left bw, and call the matrix on the right L.
bw = logical([0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 1 1 1 0
0 1 0 0 1 0 0
0 0 0 0 0 0 0]);
L = [0 0 0 0 0 0 0
0 1 1 0 0 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0];The linear indices of the pixels that were just labeled are 8 and 12:
idx = [8; 12];
Here are the neighbor offsets for a four-connected neighborhood:
offsets = [-1; 5; 1; -5];
"Set the pixels that were just labeled to 0".
bw(idx) = 0;
"Find all the nonzero 4-connected neighbors." Do this by adding all neighbor offsets to all pixels in the current set.
neighbors = bsxfun(@plus, idx, offsets')
neighbors =
7 13 9 3
11 17 13 7
Remove duplicates.
neighbors = unique(neighbors(:))
neighbors =
3
7
9
11
13
17
Keep only the neighbors that are nonzero.
idx = neighbors(bw(neighbors))
idx =
13
"Set the corresponding pixels in the label matrix to 1."
L(idx) = 1;
You'd repeat these operations in a loop until idx was empty, indicating that a connected component has been completely labeled.
I've covered two connected components methods in this series so far. In my next post I'll start to explain a third method - the one used by the Image Processing Toolbox functions bwlabel and bwlabeln.
PS. Good luck to everyone running in the Boston Marathon tomorrow!
Get
the MATLAB code
Published with MATLAB® 7.4
Hi,Steve,it has a small mistake,the sentence:
idx = neighbors(bw(neigbhors))
should be
idx = neighbors(bw(neighbors))
Jxwht—Thanks. I fixed the problem.
Hi Steve,
the flood-fill algorithm you described here depends on the initial point you pick in each component. sometimes, it fails to detect all white pixels in the area.
Khosrow
Khosrow—I don’t believe it does, but if you care to give an example I’ll take a look at it.
Steve, I don’t use MATHLAB. I just implemented this approach in Yorick. My program works fine for simple geometries. Even for complicated patterns, sometimes it is successful, but not always, depending on which initial pixel you pick in each region. My guess is that some sort of closed black bands form around a pixels blocking the algorithm to access the pixels beyond.
anyways, I can send you a sample image, if you want. please, let me know your email.
Khosrow—The algorithm described here is for finding connected components. If a “closed black band forms around pixels blocking [access to] the pixels beyond,” then you don’t have a single connected component. I don’t know what you were trying to accomplish in your own implementation, but apparently the goal was something other than finding connected components.
Steve – True. I have several white foreground areas embedded in black background, and I want to index all the pixels in the first white region by 1, then all the pixels in the second region by 2, and etc. so that, later I can assign a property, let say color, to each region. I thought, this is what the flood-fill approach is supposed to do! even in the example given here, you have two separated areas. if there is only a single white area surrounded by black background all around, then what is the point of indexing at the first place? I can just say that all white pixels have index 1.
Khosrow—This post only sketches out the idea of one particular connected-component algorithm; it doesn’t provide the details. (The Image Processing Toolbox already provides this capability, after all.) In particular, once a particular region is marked, you have to continue scanning the image to find a pixel in the next region and then start the flood-filling process again from there.
Steve- OK. thanks a lot for sharing your expertise with us.
hi steve, why do you put ” offsets = [-1; 5; 1; -5];” ? I dont understand that .
Stefano—See my neighbor indexing post.
the last idx you put was idx=13… mmm i think that your last idx must be = 9 ; because of the step3 (figure) .
Stefano—Looks like that might be right, thanks.
Steve your post is great!!
How can I programatically find the foreground pixel?. Is there any function in Matlab that can do this for us?
Jorge—Take a look at graythresh and im2bw.
Hi Steve.
I am brazilian so i don´t write very well in english, sorry about this.
This algorithm that you write here has a name? And where i can find an explanation about this algorithm?
I am thinking in using this algorithm in a study of college.
Thanks fou your attention.
Domenico—There are a couple of key terms mentioned in this post: “connected-component labeling” and “flood fill.”
Steve where i can find theoretical definition about this algorithm? For example, what books i can find an explanation of the algorithm?
Thanks again.
Domenico—These are pretty widely used terms. I think you can use some basic Internet searches to find a lot of information about them.
Steve I’ve searched a more formal explanation of “connected-component labeling” and “flood fill” algorithm in a book or paper and I haven’t found nothing good on the internet. you know some material that explains this algorithm formally?
Thanks.
Domenico—Seriously? The first link I see when I Google for “connected component labeling” is for a lengthy Wikipedia article with detailed descriptions of several algorithms, a number of diagrams, relevant cross references, and external reference links.
Yes it’s seriously. I need to get this information from websites, books, or anywhere else where there is a recognition by the scientific community.
But tahnks for your attention.
Domenico—Well, then, you could start with the search I suggested in my previous comment.
Hi Steve,
Can you advice me how can I use this approach to assign index for the object which are separate and may be very closely placed in an image, such as image of a section of plant stem image showing closely placed cells. What if I want to assign a number in index for each of the cells even if they are very close to each other? The only distinction is the boundary of each cell separating them and shape is quite variable for each of the cells?
Thanks
Ethan—You might want to look at my 07-Sep-2011 post, “almost-connected-component labeling.”