In this series I'm discussing different ways to compute the connected components of a binary image. Before I get into specific algorithms, though, I need to touch briefly on the notion of connectivity.
For a given pixel p, what is the set of neighbors of p? In other words, what is p's neighborhood? There's no single answer that works best for all applications. One definition is that the neighbors of p are the pixels that share an edge with p. There are four such neighbors:
1 4 p 2 3
This is called a four-connected neighborhood.
Another common neighborhood definition is the set of pixels that share an edge or a corner with p. There are eight:
8 1 2 7 p 3 6 5 4
Here's a binary image that demonstrates the practical difference between these neighborhood definitions:
bw = logical([ ...
0 0 0 0 0 0 0
0 1 1 0 0 0 0
0 1 1 0 0 0 0
0 0 0 1 1 1 0
0 0 0 1 1 1 0
0 0 0 0 0 0 0 ]);
showPixelValues(bw)
If we use a four-connected neighborhood definition, then the image above has two connected components: an upper-left 2-by-2 component, and a lower-right 2-by-3 component. With an eight-connected neighborhood definition, there's just one connected component.
Many Image Processing Toolbox functions support other kinds of neighborhood definitions as well, via an optional input argument called CONN (for connectivity). For two-dimensional processing, CONN is a 3-by-3 matrix of 0s and 1s. The matrix has to be symmetric about its central element. The 1s define the neighbors. For example, here are the CONN matrices for four-connected and eight-connected neighborhoods:
conn4 = [0 1 0; 1 1 1; 0 1 0]
conn4 =
0 1 0
1 1 1
0 1 0
conn8 = [1 1 1; 1 1 1; 1 1 1]
conn8 =
1 1 1
1 1 1
1 1 1
In my next post in this series, I'll talk about representing the collection of neighbor relationships among foreground pixels as a graph.
Get
the MATLAB code
Published with MATLAB® 7.4



Steve, Please give us some insight in to resolving equivalences using the union find algorithm/ some detail on the equivalence table structure.
Thanks
Karthick - yes, I plan to give more information on that topic later in this series of postings yet. It’s not written yet. :-)
Steve, your blog is great and I would like to browse old postings, but the uncategorized link only goes back so far. How do I access older entries?
Raymond - click on the “Archives” link in the sidebar, just above “Categories.”
Steve
Looking forward for it. Thanks