{"id":275,"date":"2009-07-13T12:48:45","date_gmt":"2009-07-13T16:48:45","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2009\/07\/13\/a-new-look-for-connected-component-labeling-in-r2009a-part-2\/"},"modified":"2019-10-28T15:38:36","modified_gmt":"2019-10-28T19:38:36","slug":"a-new-look-for-connected-component-labeling-in-r2009a-part-2","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2009\/07\/13\/a-new-look-for-connected-component-labeling-in-r2009a-part-2\/","title":{"rendered":"A new look for connected component labeling in R2009a – Part 2"},"content":{"rendered":"
\r\n

Last week<\/a> I wrote about our desire to reduce the memory used by bwlabel<\/tt>. I also wrote about other issues we hoped to address:\r\n <\/p>\r\n

\r\n
    \r\n
  • The label matrix uses memory proportional to the total number of image pixels. This seems unreasonable when you're working\r\n with an image containing only a few object pixels.\r\n <\/li>\r\n
  • When bwlabel<\/tt> was used with regionprops<\/tt> (a frequent combination), some computational work was duplicated in both functions.\r\n <\/li>\r\n
  • Many users never use the label matrix directly. They only compute it in order to pass it to regionprops<\/tt>. That implies there may be a simpler, more usable interface design.\r\n <\/li>\r\n <\/ul>\r\n <\/div>\r\n

    With so much code out there using bwlabel<\/tt> and regionprops<\/tt>, though, we did not want to introduce any compatibility problems.\r\n <\/p>\r\n

    Our solution was to introduce two new functions in R2009a, bwconncomp<\/tt> and labelmatrix<\/tt>, as well as a couple of new syntaxes for the existing function regionprops<\/tt>.\r\n <\/p>\r\n

    The new function bwconncomp<\/tt> finds the connected components of a binary image, just as bwlabel<\/tt> does. But it does not return the result as a label matrix.\r\n <\/p>

    BW = [1     1     1     0     0     0     0     0\r\n      1     1     1     0     1     1     0     0\r\n      1     1     1     0     1     1     0     0\r\n      0     0     0     0     0     0     1     0\r\n      0     0     0     0     0     0     1     0\r\n      0     0     0     0     0     0     1     0\r\n      0     1     1     0     0     1     1     0\r\n      0     1     1     0     0     0     0     0];\r\n\r\ns = bwconncomp(BW)<\/pre>
    \r\ns = \r\n\r\n    Connectivity: 8\r\n       ImageSize: [8 8]\r\n      NumObjects: 3\r\n    PixelIdxList: {[9x1 double]  [4x1 double]  [9x1 double]}\r\n\r\n<\/pre>
    As you can see, bwconncomp<\/tt> produces a structure.  The critical information for subsequent processing is the PixelIdxList<\/tt> field, which contains the linear indices of the pixels belonging to each object. For example, the 2nd object found comprises\r\n      four pixels with the following linear indices:\r\n   <\/p>
    s.PixelIdxList{2}<\/pre>
    \r\nans =\r\n\r\n    15\r\n    16\r\n    23\r\n    24\r\n\r\n<\/pre>
    A key aspect of this design is that the amount of memory required is proportional to the number of object pixels, not the\r\n      number of image pixels. For a 1000-by-1000 image containing a single foreground pixel, the output data structure is nicely\r\n      compact:\r\n   <\/p>
    BW2 = false(1000, 1000);\r\nBW2(500, 500) = true;\r\ns2 = bwconncomp(BW2)<\/pre>
    \r\ns2 = \r\n\r\n    Connectivity: 8\r\n       ImageSize: [1000 1000]\r\n      NumObjects: 1\r\n    PixelIdxList: {[499500]}\r\n\r\n<\/pre>
    whos s2<\/span><\/pre>
      Name      Size            Bytes  Class     Attributes\r\n\r\n  s2        1x1               596  struct              \r\n\r\n<\/pre>
    You can compute the label matrix, if you really need it, using the new function labelmatrix<\/tt>.\r\n   <\/p>
    L2 = labelmatrix(s2);\r\nwhos L2<\/span><\/pre>
      Name         Size                Bytes  Class    Attributes\r\n\r\n  L2        1000x1000            1000000  uint8              \r\n\r\n<\/pre>
    Notice that L2<\/tt> is a uint8<\/tt> matrix.  Unlike bwlabel<\/tt>, labelmatrix<\/tt> does<\/b> adjust the output data type based on the number of objects.\r\n   <\/p>\r\n   
    The last related change was to regionprops<\/tt>. As I mentioned before, we've noticed that this is a very common coding pattern:\r\n   <\/p>
      L = bwlabel(bw);\r\n  s = regionprops(L, ...);<\/pre>
    We've modified the syntax for regionprops<\/tt> so that you can now do this in a one step:\r\n   <\/p>
      s = regionprops(bw, ...);<\/pre>
    For example:<\/p>
    bw = imread('text.png'<\/span>);\r\ns = regionprops(bw, 'Centroid'<\/span>);<\/pre>
    These several new and modified functions, working together, nicely solve several design problems:<\/p>\r\n   
    \r\n      
      \r\n         
    • Reducing memory use<\/li>\r\n         
    • Increasing speed (in many cases) by eliminating duplicate computation<\/li>\r\n         
    • Converting a two-step workflow to a one-step workflow<\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   
      We had one last concern, though. It takes code changes to benefit from these enhancements.  Users who aren't aware of the\r\n      new features and don't change their code will never benefit.  So what could we do to help users discover the new features?\r\n   <\/p>\r\n   
      I'll comment about that next time.<\/p>