Disconnected component labeling: part 1
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.
评论
要发表评论,请点击 此处 登录到您的 MathWorks 帐户或创建一个新帐户。