{"id":137,"date":"2007-05-25T12:02:13","date_gmt":"2007-05-25T16:02:13","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/05\/25\/connected-component-labeling-part-6\/"},"modified":"2019-10-23T12:56:09","modified_gmt":"2019-10-23T16:56:09","slug":"connected-component-labeling-part-6","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/05\/25\/connected-component-labeling-part-6\/","title":{"rendered":"Connected component labeling – Part 6"},"content":{"rendered":"
\r\n \r\n

In this part of the connected component labeling series<\/a>, I'll finally get to one of the algorithms actually used in the Image Processing Toolbox. It's based on a technique called\r\n union-find<\/i>, as described in Sedgewick's Algorithms in C<\/i>, Addison-Wesley, 1998, pp. 11-20. This algorithm is designed to be able to quickly form the union of two sets, and also\r\n to be able to quickly find which set contains a given element.\r\n <\/p>\r\n

Here's the example I'll use to illustrate the method. On the left is a small binary image containing a single eight-connected\r\n component. We start by making each nonzero pixel a node in a graph. The nodes are numbered as shown on the right.\r\n <\/p>\r\n

<\/p>\r\n <\/introduction>\r\n

In its initial state, the graph contains 7 unconnected nodes, one for each nonzero pixel:<\/p>\r\n

<\/p>\r\n

We can represent this graph in MATLAB by a vector:<\/p>

nodes = 1:7<\/pre>
\r\nnodes =\r\n\r\n     1     2     3     4     5     6     7\r\n\r\n<\/pre>
In this representation, nodes(k)<\/tt> gives the parent of node k<\/i>.  A node that is its own parent (that is, nodes(k)<\/tt> equals k<\/i>) is a root node.\r\n   <\/p>\r\n   
As we scan the image columnwise, we encounter pairs of pixels that are connected to each other.  The first such pair is that\r\n      pixel 2 is connected to pixel 1.  We find the root node for the set containing pixel 2 (node 2) and the root node for the\r\n      set containing pixel 1 (node 1).  Since they are different, we form the union of those two sets simply by making the root\r\n      node of one of the sets point to the root node of the other.\r\n   <\/p>
nodes(2) = 1<\/pre>
\r\nnodes =\r\n\r\n     1     1     3     4     5     6     7\r\n\r\n<\/pre>
 <\/p>\r\n   
The second connection encountered in the scan is that pixel 3 is connected to pixel 2.  The root node for the set containing\r\n      pixel 3 is node 3; the root node for the set containing pixel 2 is node 1. So we connect node 3 to node 1.\r\n   <\/p>
nodes(3) = 1<\/pre>
\r\nnodes =\r\n\r\n     1     1     1     4     5     6     7\r\n\r\n<\/pre>
 <\/p>\r\n   
Now continue to process connections.  Pixel 4 is connected to pixel 3, so connect node 4 to node 1:<\/p>
nodes(4) = 1<\/pre>
\r\nnodes =\r\n\r\n     1     1     1     1     5     6     7\r\n\r\n<\/pre>
 <\/p>\r\n   
Pixel 6 is connected to pixel 5, so connect node 6 to node 5:<\/p>
nodes(6) = 5<\/pre>
\r\nnodes =\r\n\r\n     1     1     1     1     5     5     7\r\n\r\n<\/pre>
 <\/p>\r\n   
Pixel 7 is connected to pixel 6, so connect node 7 to node 5:<\/p>
nodes(7) = 5<\/pre>
\r\nnodes =\r\n\r\n     1     1     1     1     5     5     5\r\n\r\n<\/pre>
 <\/p>\r\n   
Now for the moment of truth.  So far our graph still contains two sets (trees). But now we see that pixel 7 is connected to\r\n      pixel 4.  When we connect their corresponding roots (5 to 1), we are finally left with a single set:\r\n   <\/p>
nodes(5) = 1<\/pre>
\r\nnodes =\r\n\r\n     1     1     1     1     1     5     5\r\n\r\n<\/pre>
 <\/p>\r\n   
According to Sedgewick, there are two important things to do to the graph while processing pairs:<\/p>\r\n   
\r\n      
    \r\n         
  • When forming a union by connecting two trees in the graph, always connect the smaller of the two trees to the larger one.\r\n             This prevents the growth of long paths in the trees.\r\n         <\/li>\r\n         
  • When \"walking\" up a chain of nodes to find the root node, \"flatten out\" the tree using a technique called path compression<\/i>.  Here's an example showing path compression by halving<\/i>.  The tree on the left has a long path from node 7 up to node 1.  As you follow the path, take two nodes at a time and make\r\n            the bottom node point to the same parent as the top node. That give you the tree on the right.\r\n         <\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   
     <\/p>\r\n   
    If you keep doing this, then over time the trees in the graph stay almost completely flat.  The flat tree is what makes the\r\n      \"find\" operation as quick as the \"union\" operation.\r\n   <\/p>\r\n   
    The Image Processing Toolbox function bwlabeln<\/tt>, which performs connected component labeling for arbitrary dimension and arbitrary connectivity, uses the union-find technique.\r\n       If you have the product, you can see the key parts of the implementation in the source files bwlabelnmex.cpp and unionfind.c,\r\n      which are in toolbox\\images\\images\\private.\r\n   <\/p>\r\n   
    I'll try to wrap this series up with one more post, which will be about the two-dimensional algorithm used by the function\r\n      bwlabel<\/tt>.\r\n   <\/p>