A new look for connected component labeling in R2009a – Part 2

Posted by Steve Eddins, July 13, 2009

1 views (last 30 days) | 0 Likes | 23 comments

Last week I wrote about our desire to reduce the memory used by bwlabel. I also wrote about other issues we hoped to address:

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

With so much code out there using bwlabel and regionprops, though, we did not want to introduce any compatibility problems.

Our solution was to introduce two new functions in R2009a, bwconncomp and labelmatrix, as well as a couple of new syntaxes for the existing function regionprops.

The new function bwconncomp finds the connected components of a binary image, just as bwlabel does. But it does not return the result as a label matrix.

BW = [1     1     1     0     0     0     0     0
      1     1     1     0     1     1     0     0
      1     1     1     0     1     1     0     0
      0     0     0     0     0     0     1     0
      0     0     0     0     0     0     1     0
      0     0     0     0     0     0     1     0
      0     1     1     0     0     1     1     0
      0     1     1     0     0     0     0     0];

s = bwconncomp(BW)

s = 

    Connectivity: 8
       ImageSize: [8 8]
      NumObjects: 3
    PixelIdxList: {[9x1 double]  [4x1 double]  [9x1 double]}

As you can see, bwconncomp produces a structure. The critical information for subsequent processing is the PixelIdxList field, which contains the linear indices of the pixels belonging to each object. For example, the 2nd object found comprises four pixels with the following linear indices:

s.PixelIdxList{2}

A key aspect of this design is that the amount of memory required is proportional to the number of object pixels, not the number of image pixels. For a 1000-by-1000 image containing a single foreground pixel, the output data structure is nicely compact:

BW2 = false(1000, 1000);
BW2(500, 500) = true;
s2 = bwconncomp(BW2)

s2 = 

    Connectivity: 8
       ImageSize: [1000 1000]
      NumObjects: 1
    PixelIdxList: {[499500]}

whos s2

  Name      Size            Bytes  Class     Attributes

  s2        1x1               596  struct

You can compute the label matrix, if you really need it, using the new function labelmatrix.

L2 = labelmatrix(s2);
whos L2

  Name         Size                Bytes  Class    Attributes

  L2        1000x1000            1000000  uint8

Notice that L2 is a uint8 matrix. Unlike bwlabel, labelmatrix does adjust the output data type based on the number of objects.

The last related change was to regionprops. As I mentioned before, we've noticed that this is a very common coding pattern:

  L = bwlabel(bw);
  s = regionprops(L, ...);

We've modified the syntax for regionprops so that you can now do this in a one step:

  s = regionprops(bw, ...);

For example:

bw = imread('text.png');
s = regionprops(bw, 'Centroid');

These several new and modified functions, working together, nicely solve several design problems:

Reducing memory use
Increasing speed (in many cases) by eliminating duplicate computation
Converting a two-step workflow to a one-step workflow

We had one last concern, though. It takes code changes to benefit from these enhancements. Users who aren't aware of the new features and don't change their code will never benefit. So what could we do to help users discover the new features?

I'll comment about that next time.

Published with MATLAB® 7.8