Disconnected component labeling: part 1

著者 Steve Eddins, October 1, 2010

1 ビュー (過去 30 日間) | 0 いいね | 10 コメント

A blog reader asked me recently for an enhancement related to connectivity. I found the request a bit surprising, and I want to explore it with you in the this post and the next.

Many Image Processing Toolbox functions rely on some notion of connectivity between a pixel and its neighbors. In two-dimensional processing, the most common connectivities are usually called "4-connected" and "8-connected."

In the 4-connected definition, a pixel is connected to its north, east, south, and west neighbors. In the matrix below, the 1-valued elements indicate the connected neighbors of the center pixel.

 0 1 0
 1 1 1
 0 1 0

In the 8-connected definition, a pixel is connected to all 8 of its touching neighbors:

 1 1 1
 1 1 1
 1 1 1

Most toolbox functions that take a connectivity input argument will accept other, more unusual connectivities, such as this one:

 0 1 0
 0 1 0
 0 1 0

The connectivity matrix above means that a pixel is connected only to its north and south neighbors.

Let's see what this does with a simple connected component labeling problem. Here's a small test 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
    1     1     1     0     0     0     1     0
    1     1     1     0     0     0     1     0
    1     1     1     0     0     0     1     0
    1     1     1     0     0     1     1     0
    1     1     1     0     0     0     0     0]

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
     1     1     1     0     0     0     1     0
     1     1     1     0     0     0     1     0
     1     1     1     0     0     0     1     0
     1     1     1     0     0     1     1     0
     1     1     1     0     0     0     0     0

With a connectivity of 8, here are the connected components:

cc = bwconncomp(bw, 8);
L8 = labelmatrix(cc)

L8 =

    1    1    1    0    0    0    0    0
    1    1    1    0    2    2    0    0
    1    1    1    0    2    2    0    0
    1    1    1    0    0    0    2    0
    1    1    1    0    0    0    2    0
    1    1    1    0    0    0    2    0
    1    1    1    0    0    2    2    0
    1    1    1    0    0    0    0    0

You can see that there are just two connected components.

Here's what you get if you specify a north-south connectivity using a connectivity matrix:

conn = [0 1 0; 0 1 0; 0 1 0]

conn =

     0     1     0
     0     1     0
     0     1     0

cc_ns = bwconncomp(bw, conn);
L_ns = labelmatrix(cc_ns)

L_ns =

    1    2    3    0    0    0    0    0
    1    2    3    0    4    5    0    0
    1    2    3    0    4    5    0    0
    1    2    3    0    0    0    7    0
    1    2    3    0    0    0    7    0
    1    2    3    0    0    0    7    0
    1    2    3    0    0    6    7    0
    1    2    3    0    0    0    0    0

Now there are seven connected components, each of which lies entirely within a single column.

A valid connectivity matrix has to be 3-by-3 (or 3-by-3-by- ... -by-3) for higher dimensions); the center pixel has to be 1; and the matrix has to be symmetric about the center pixel. (This last rule means that pixel p is connected to pixel q if and only if pixel q is connected to pixel p.)

Blog reader Oliver recently asked me if we could relax one of these constraints on connectivity matrices in order to allow a connectivity definition such as this:

 1 0 1 0 1

With this connectivity, a pixel is not considered be connected to any of its touching neighbors. Instead, a pixel is connected only to the pixels two over to the east and west.

Since I've been making up new terms related to connected component labeling recently (see almost-connected-component labeling), here's your new term for the day: disconnected component labeling.

Toolbox functions currently do not allow this.

In part 2 I will show how to work around this restriction. In the meantime, I'm giving you homework: think about whether you know of applications that could benefit from allowing this looser definition of connectivity.

Published with MATLAB® 7.11