{"id":132,"date":"2007-04-15T12:28:00","date_gmt":"2007-04-15T16:28:00","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/04\/15\/connected-component-labeling-part-4\/"},"modified":"2019-10-23T12:50:36","modified_gmt":"2019-10-23T16:50:36","slug":"connected-component-labeling-part-4","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/04\/15\/connected-component-labeling-part-4\/","title":{"rendered":"Connected component labeling – Part 4"},"content":{"rendered":"
\r\n

In the previous post in this series<\/a> I talked about forming a graph based on pixel neighbor relationships, and then finding the connected components of the graph.\r\n Another approach starts by finding a foreground pixel and then iteratively searching that pixel's neighbors to find the connected\r\n component. Sometimes this technique is called the flood fill<\/i> approach. I'll demonstrate the basic idea using a small sample image and a series of diagrams.\r\n <\/p>\r\n

The matrix below and on the left is our binary image. Using 4-connected neighbors, the image has two connected components.\r\n The matrix on the right is going to become our label matrix when we're done. It is initialized to contain all zeros.\r\n <\/p>\r\n

<\/p>\r\n

Step 1: Find a foreground pixel. Set the corresponding label matrix pixel to 1, which is the first label.<\/p>\r\n

<\/p>\r\n

Step 2: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Set the corresponding\r\n pixels in the label matrix to 1.\r\n <\/p>\r\n

<\/p>\r\n

Step 3: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Set the corresponding\r\n pixels in the label matrix to 1. (This step should seem familiar.)\r\n <\/p>\r\n

<\/p>\r\n

Step 4: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Oops, there aren't\r\n any!\r\n <\/p>\r\n

<\/p>\r\n

Step 5: We have finished labeling object 1. Now search for the next nonzero pixel. Set the corresponding pixel in the label\r\n matrix to 2, which is the next object label.\r\n <\/p>\r\n

<\/p>\r\n

Step 6: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Set the corresponding\r\n pixels in the label matrix to 2.\r\n <\/p>\r\n

<\/p>\r\n

Step 7: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Set the corresponding\r\n pixels in the label matrix to 2.\r\n <\/p>\r\n

<\/p>\r\n

Step 8: Set the pixels that were just labeled to 0, and then find all the nonzero 4-connected neighbors. Since there aren't\r\n any, we know we have finished labeling object 2. Furthermore, since there are no nonzero pixels left in the image, we know\r\n we have completed the labeling operation.\r\n <\/p>\r\n

<\/p>\r\n

Now let's talk about how you might program this in MATLAB. I'd use the neighbor indexing technique<\/a> that I wrote about a couple of weeks ago. Start from this point:\r\n <\/p>\r\n

<\/p>\r\n

Call the matrix on the left bw<\/tt>, and call the matrix on the right L<\/tt>.\r\n <\/p>

bw = logical([0 0 0 0 0 0 0\r\n    0 0 1 0 0 0 0\r\n    0 1 0 1 1 1 0\r\n    0 1 0 0 1 0 0\r\n    0 0 0 0 0 0 0]);\r\n\r\nL = [0 0 0 0 0 0 0\r\n    0 1 1 0 0 0 0\r\n    0 1 0 0 0 0 0\r\n    0 0 0 0 0 0 0\r\n    0 0 0 0 0 0 0];<\/pre>
The linear indices of the pixels that were just labeled are 8 and 12:<\/p>
idx = [8; 12];<\/pre>
Here are the neighbor offsets for a four-connected neighborhood:<\/p>
offsets = [-1; 5; 1; -5];<\/pre>
\"Set the pixels that were just labeled to 0\".<\/p>
bw(idx) = 0;<\/pre>
\"Find all the nonzero 4-connected neighbors.\" Do this by adding all neighbor offsets to all pixels in the current set.<\/p>
neighbors = bsxfun(@plus, idx, offsets')<\/pre>
\r\nneighbors =\r\n\r\n     7    13     9     3\r\n    11    17    13     7\r\n\r\n<\/pre>
Remove duplicates.<\/p>
neighbors = unique(neighbors(:))<\/pre>
\r\nneighbors =\r\n\r\n     3\r\n     7\r\n     9\r\n    11\r\n    13\r\n    17\r\n\r\n<\/pre>
Keep only the neighbors that are nonzero.<\/p>
idx = neighbors(bw(neighbors))<\/pre>
\r\nidx =\r\n\r\n    13\r\n\r\n<\/pre>
\"Set the corresponding pixels in the label matrix to 1.\"<\/p>
L(idx) = 1;<\/pre>
You'd repeat these operations in a loop until idx<\/tt> was empty, indicating that a connected component has been completely labeled.\r\n   <\/p>\r\n   
I've covered two connected components methods in this series so far. In my next post I'll start to explain a third method\r\n      - the one used by the Image Processing Toolbox functions bwlabel<\/tt> and bwlabeln<\/tt>.\r\n   <\/p>\r\n\r\n
\r\nPS. Good luck to everyone running in the Boston Marathon tomorrow!\r\n<\/p>\r\n\r\n