{"id":134,"date":"2007-05-11T12:12:59","date_gmt":"2007-05-11T16:12:59","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/05\/11\/connected-component-labeling-part-5\/"},"modified":"2019-10-23T12:54:06","modified_gmt":"2019-10-23T16:54:06","slug":"connected-component-labeling-part-5","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/05\/11\/connected-component-labeling-part-5\/","title":{"rendered":"Connected component labeling – Part 5"},"content":{"rendered":"
\r\n

OK, I've learned an important lesson about this blog: I really shouldn't start up two topics series at the same time. It's\r\n too hard to find the time to compose posts on both topics each week, and so the frequency of my posts drops off.\r\n <\/p>\r\n

Anyway, let's get into the third algorithm for labeling connected components in a binary image. It involves two passes over\r\n the image, with an in-between step called equivalence class resolution<\/i>. I first learned about this idea from Haralick and Shapiro, Computer and Robot Vision<\/i>, vol. I, Addison-Wesley, 1992.\r\n <\/p>\r\n

The first pass assigns temporary labels to each foreground pixel. Here's a graphical illustration of that procedure, using\r\n this small sample image:\r\n <\/p>\r\n

<\/p>\r\n

Now scan the image, processing one pixel at a time. Because of the way MATLAB stores matrix elements in memory, we'll scan\r\n along columns. When the scan encounters a foreground pixel, look at that pixel's neighbors that have already been encountered in the scan<\/b>. Here's the first foregound pixel encountered, shown with its already-scanned neighbors highlighted in color:\r\n <\/p>\r\n

<\/p>\r\n

For the pixel shown above, none of the highlighted neighbors have been assigned a temporary label yet, so a new label value\r\n (1) is assigned to the corresponding pixel in the output.\r\n <\/p>\r\n

Here's the second foregound pixel encountered:<\/p>\r\n

<\/p>\r\n

Note that one of this pixel's neighbors has already received a label (1), so this pixel is also assigned a temporary label\r\n of 1 in the output image.\r\n <\/p>\r\n

When the scan gets to row 2, column 4 pixel, none of that pixel's scanned neighbors have been labeled, so that pixel gets\r\n assigned a new temporary label of 2.\r\n <\/p>\r\n

<\/p>\r\n

The very next pixel, on row 3, column 4, is where things start to get more interesting:<\/p>\r\n

<\/p>\r\n

One of this pixel's scanned neighbors has already been assigned a label of 1, but another of the neighbors has been assigned\r\n a label of 2. So the algorithm picks one of the labels arbitrarily, and then records the fact that temporary label 1 and temporary\r\n label 2 actually refer to the same object.\r\n <\/p>\r\n

This situation happens again on row 4, column 8:<\/p>\r\n

<\/p>\r\n

So the pair of labels 3 and 4 is an equivalence<\/i> and goes into the equivalence table<\/i>.\r\n <\/p>\r\n

When the first pass is done, you have this matrix of labels:<\/p>\r\n

<\/p>\r\n

And you have an equivalence table containing these pairs:<\/p>

 1 <--> 2\r\n 3 <--> 4<\/pre>
Equivalence class resolution<\/i> is the process of determining which subsets of the temporary labels really refer to the same object.  You can do that in\r\n      MATLAB using the technique I showed previously<\/a> that was based adjacency matrix and dmperm<\/tt>.  From this you would compute that temporary labels 1 and 2 map to final label 1, and temporary labels 3 and 4 map to final\r\n      label 2.  Then you make a second pass over the output matrix to relabel the pixels according to this mapping:\r\n   <\/p>\r\n   
 <\/p>\r\n   
The Image Processing Toolbox function bwlabeln<\/tt> uses a variation of this technique, where the equivalence class resolution is actually performed during the first pass, using\r\n      an algorithm called union find<\/i>.  I'll explain that next time.\r\n   <\/p>