Steve on Image Processing

June 12th, 2007

Connected component labeling - Part 7

I described in my previous connected component labeling post the algorithm used by bwlabeln. This time I'll talk about the variation used by bwlabel. This variation uses run-length encoding as the first step.

Here's what I mean by run-length encoding. Consider this small binary image matrix:

Such a binary image can be represented as a collection of runs, or sequences of 1s. Working columnwise, this image contains 9 runs:

Each run can be represented by its starting pixel and by the number of pixels in the run, which is called the run length. Hence the term run-length encoding.

For a larger binary image containing larger objects, the number of runs can be much smaller than the number of foreground pixels. But the connectivity analysis can be completely determined based on the runs. In our small example:

  • Run #3 is connected to run #1
  • Run #4 is connected to run #2
  • Run #6 is connected to run #4
  • Run #7 is connected to run #5
  • Run #8 is connected to run #6
  • Run #9 is connected to run #7
  • Run #9 is connected to run #8

This set of connectivity pairs can be resolved into equivalence classes using the technique I described earlier based on dmperm. In this example there are only two equivalence classes, corresponding to the two connected components.

The function bwlabel calls computes a run-length encoding first. As it finds each run, it also determines which runs on the previous column are connected, if any. Then it constructs a sparse adjacency matrix and calls dmperm to compute the equivalence classes. Then it labels each run in the output label matrix according to the equivalence class it belongs to.

This is a very efficient method because it scans each pixel in the input image only once, and also because the adjacency matrix is usually relatively small. It is R-by-R, where R is the number of runs.

You can find this method described in Haralick and Shapiro, Computer and Robot Vision Volume 1, Addison-Wesley, 1992, pp. 40-48. (Note that the equivalence class resolution method used by bwlabel is different than the one described in the book.)


Get the MATLAB code

Published with MATLAB® 7.4

6 Responses to “Connected component labeling - Part 7”

  1. Emanuele Rodolà replied on :

    Just finished reading through your seven-parts tour. Thanks a lot, found it very useful!

  2. Steve replied on :

    Emanuele—I’m glad you liked it. Thanks for taking the time to comment.

  3. jxwht replied on :

    Hi Steve,
    As you mentioned before, we can find the 4- or 8- connected “pairs” by using linear indexing and linear neighbor index offsets, is there a similar algorithm to find the 4- or 8- connected “pairs” RUNs?
    Thank you!

  4. Steve replied on :

    Jxwht—Not directly by using indexing offsets, but it can be programmed in MATLAB. I have done it in the past, but a long time ago. I don’t have code for it anymore.

  5. Ashwati replied on :

    Dear Steve,
    I am currently doing a project in Digital Image Processing. I just wanted to say that I have followed your book, DIP with Matlab, and have found it a very satisfying experience, especially the section of Frequency Domain processing, cleared a lot of cobwebs. Thank you very much.
    Ashwati

  6. Steve replied on :

    Ashwati—Thanks! I forwarded your comment to Dr. Gonzalez, who wrote the frequency domain processing chapter.

Leave a Reply

Wrap code fragments inside <pre> tags, like this:

<pre class="code">
a = magic(3);
sum(a)
</pre>

If you have a "<" character in your code, either follow it with a space or replace it with "&lt;" (including the semicolon).


Steve Eddins manages the Image & Geospatial development team at The MathWorks and coauthored Digital Image Processing Using MATLAB. He writes here about image processing concepts, algorithm implementations, and MATLAB.

  • murat: Hi Steve, I have an rgb image of a kind of cream and it contains some small black particles (black dots). In...
  • Steve: Ernest—Look at setting the FaceColor property. The code for setting that is shown on the page you asked...
  • Ernest Miller: Hi Steve, Understood. However, can you explain how to change the colors? Thanks, Ernest
  • Jan: Hi Steve Very useful code, yet what if I parts of my rotated+translated object are outside the original...
  • Steve: MoHDa—It might be possible. You’ll need to use one of the options that produces closed edge...
  • MoHDa: I have one question about the ROIPOLY: I have an image with stripes, I use the “edge” command for...
  • Steve: Shahn—My November 17, 2006 post shows you how to do it.
  • Steve: Kay-Uwe—Thanks for following up. I am planning to make it easier to use test directories in a package....
  • shahn: Hello Steve Instead of superimposing a star on the image to show the centroide. How would you superimpose a...
  • Kay-Uwe: Having TestSuite.fromPackag e() would be nice to have, but so far using simple “test” subdirs...

These postings are the author's and don't necessarily represent the opinions of The MathWorks.