{"id":274,"date":"2009-07-06T13:26:02","date_gmt":"2009-07-06T17:26:02","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2009\/07\/06\/a-new-look-for-connected-component-labeling-in-r2009a\/"},"modified":"2019-10-28T15:37:54","modified_gmt":"2019-10-28T19:37:54","slug":"a-new-look-for-connected-component-labeling-in-r2009a","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2009\/07\/06\/a-new-look-for-connected-component-labeling-in-r2009a\/","title":{"rendered":"A new look for connected component labeling in R2009a"},"content":{"rendered":"
\r\n

One of the changes we made to the Image Processing Toolbox for R2009a was partially inspired by comments received on this\r\n blog. Specifically, several blog readers complained about the memory required by the function bwlabel<\/tt>.\r\n <\/p>\r\n

The function bwlabel<\/tt> labels connected components (or objects, or blobs) in a binary image. (I wrote a series of posts<\/a> a couple of years ago about connected component labeling algorithms.)\r\n <\/p>\r\n

I'll illustrate what bwlabel<\/tt> does using a very small binary image.\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]<\/pre>
\r\nBW =\r\n\r\n     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\n<\/pre>
L = bwlabel(BW)<\/pre>
\r\nL =\r\n\r\n     1     1     1     0     0     0     0     0\r\n     1     1     1     0     3     3     0     0\r\n     1     1     1     0     3     3     0     0\r\n     0     0     0     0     0     0     3     0\r\n     0     0     0     0     0     0     3     0\r\n     0     0     0     0     0     0     3     0\r\n     0     2     2     0     0     3     3     0\r\n     0     2     2     0     0     0     0     0\r\n\r\n<\/pre>
The output, L<\/tt>, of bwlabel<\/tt> is called a label matrix.<\/i> A label matrix contains nonnegative integer values.  0s correspond to background pixels in the binary image, and positive\r\n      values identify each labeled object.  For example, the elements of L<\/tt> that equal 2 correspond to the second object found by bwlabel<\/tt>.\r\n   <\/p>
L == 2<\/pre>
\r\nans =\r\n\r\n     0     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     0\r\n     0     0     0     0     0     0     0     0\r\n     0     1     1     0     0     0     0     0\r\n     0     1     1     0     0     0     0     0\r\n\r\n<\/pre>
Very often, the output of bwlabel<\/tt> is used as the input to regionprops<\/tt>, a function that measures geometric properties of regions. For example, we can compute the area of each labeled object:\r\n   <\/p>
s = regionprops(L, 'Area'<\/span>)<\/pre>
\r\ns = \r\n\r\n3x1 struct array with fields:\r\n    Area\r\n\r\n<\/pre>
[s.Area]   % comma-separated list syntax for structures<\/span><\/pre>
\r\nans =\r\n\r\n     9     4     9\r\n\r\n<\/pre>
As I mentioned in the first paragraph above, we occasionally hear complaints about the amount of memory required by bwlabel<\/tt>.  Because bwlabel<\/tt> always returns L<\/tt> as a double-precision matrix, the memory required is 8 bytes per image pixel.\r\n   <\/p>\r\n   
Why is L<\/tt> double-precision?  Because bwlabel<\/tt> was introduced to the Image Processing Toolbox at a time when support for integer matrices was just getting off the ground.\r\n       In 1998 or so, the only non-double data type supported by the Image Processing Toolbox was uint8<\/tt>.  It did not seem reasonable to limit label matrices to 255 objects, and we were uncomfortable with a design that called\r\n      for the data type of L<\/tt> to vary according to the number of objects detected.\r\n   <\/p>\r\n   
If there had been more than minimal support at the time for uint32<\/tt> or single<\/tt> matrices, we might have chosen one of those types. But there wasn't, so we went with double<\/tt>, and that's what it's been ever since.\r\n   <\/p>\r\n   
The memory complaints have persisted, though, particularly with users who are doing multidimensional image processing. 8 bytes\r\n      per image pixel seemed to be a high price to pay, especially when there were relatively few foreground pixels.\r\n   <\/p>\r\n   
The usual request was to change the data type L<\/tt> to be uint8<\/tt> when there were only a few objects.  We thought about doing that, but there were other issues we wanted to fix:\r\n   <\/p>\r\n   
1. The memory requirement was proportional to the total number of image pixels instead of the number of object pixels.  This\r\n      would still be the case even we used uint8<\/tt> in some cases.\r\n   <\/p>\r\n   
2. We knew that an early step inside the implementation of regionprops<\/tt> was to compute a list of all the pixel indices corresponding to each object.  This information is known inside the bwlabel<\/tt> computation, but it gets lost the label matrix doesn't represent it directly. Recomputing the pixel indices causes a speed\r\n      penalty.\r\n   <\/p>\r\n   
3. We knew that most users didn't use the label matrix directly.  Often, the only reason for computing it was to hand it off\r\n      to regionprops<\/tt>.\r\n   <\/p>\r\n   
So we looked for a new design that would address all these issues and that would not cause compatibility problems.<\/p>\r\n   
Next time I'll show you what we did.<\/p>