Steve on Image Processing

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