{"id":342,"date":"2010-10-01T14:31:37","date_gmt":"2010-10-01T18:31:37","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2010\/10\/01\/disconnected-component-labeling-part-1\/"},"modified":"2019-10-29T13:35:27","modified_gmt":"2019-10-29T17:35:27","slug":"disconnected-component-labeling-part-1","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2010\/10\/01\/disconnected-component-labeling-part-1\/","title":{"rendered":"Disconnected component labeling: part 1"},"content":{"rendered":"
\r\n

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

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

In the 4-connected definition, a pixel is connected to its north, east, south, and west neighbors. In the matrix below, the\r\n 1-valued elements indicate the connected neighbors of the center pixel.\r\n <\/p>

 0 1 0\r\n 1 1 1\r\n 0 1 0<\/pre>
In the 8-connected definition, a pixel is connected to all 8 of its touching neighbors:<\/p>
 1 1 1\r\n 1 1 1\r\n 1 1 1<\/pre>
Most toolbox functions that take a connectivity input argument will accept other, more unusual connectivities, such as this\r\n      one:\r\n   <\/p>
 0 1 0\r\n 0 1 0\r\n 0 1 0<\/pre>
The connectivity matrix above means that a pixel is connected only to its north and south neighbors.<\/p>\r\n   
Let's see what this does with a simple connected component labeling problem. Here's a small test matrix:<\/p>
bw = [1     1     1     0     0     0     0     0\r\n    1     1     1     0     1     1     0     0\r\n    1     1     1     0     1     1     0     0\r\n    1     1     1     0     0     0     1     0\r\n    1     1     1     0     0     0     1     0\r\n    1     1     1     0     0     0     1     0\r\n    1     1     1     0     0     1     1     0\r\n    1     1     1     0     0     0     0     0]<\/pre>
\r\nbw =\r\n\r\n     1     1     1     0     0     0     0     0\r\n     1     1     1     0     1     1     0     0\r\n     1     1     1     0     1     1     0     0\r\n     1     1     1     0     0     0     1     0\r\n     1     1     1     0     0     0     1     0\r\n     1     1     1     0     0     0     1     0\r\n     1     1     1     0     0     1     1     0\r\n     1     1     1     0     0     0     0     0\r\n\r\n<\/pre>
With a connectivity of 8, here are the connected components:<\/p>
cc = bwconncomp(bw, 8);\r\nL8 = labelmatrix(cc)<\/pre>
\r\nL8 =\r\n\r\n    1    1    1    0    0    0    0    0\r\n    1    1    1    0    2    2    0    0\r\n    1    1    1    0    2    2    0    0\r\n    1    1    1    0    0    0    2    0\r\n    1    1    1    0    0    0    2    0\r\n    1    1    1    0    0    0    2    0\r\n    1    1    1    0    0    2    2    0\r\n    1    1    1    0    0    0    0    0\r\n\r\n<\/pre>
You can see that there are just two connected components.<\/p>\r\n   
Here's what you get if you specify a north-south connectivity using a connectivity matrix:<\/p>
conn = [0 1 0; 0 1 0; 0 1 0]<\/pre>
\r\nconn =\r\n\r\n     0     1     0\r\n     0     1     0\r\n     0     1     0\r\n\r\n<\/pre>
cc_ns = bwconncomp(bw, conn);\r\nL_ns = labelmatrix(cc_ns)<\/pre>
\r\nL_ns =\r\n\r\n    1    2    3    0    0    0    0    0\r\n    1    2    3    0    4    5    0    0\r\n    1    2    3    0    4    5    0    0\r\n    1    2    3    0    0    0    7    0\r\n    1    2    3    0    0    0    7    0\r\n    1    2    3    0    0    0    7    0\r\n    1    2    3    0    0    6    7    0\r\n    1    2    3    0    0    0    0    0\r\n\r\n<\/pre>
Now there are seven connected components, each of which lies entirely within a single column.<\/p>\r\n   
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\r\n      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\r\n      and only if pixel q is connected to pixel p.)\r\n   <\/p>\r\n   
Blog reader Oliver recently asked me<\/a> if we could relax one of these constraints on connectivity matrices in order to allow a connectivity definition such as this:\r\n   <\/p>
 1 0 1 0 1<\/pre>
With this connectivity, a pixel is not considered be connected to any<\/b> of its touching neighbors. Instead, a pixel is connected only to the pixels two over to the east and west.\r\n   <\/p>\r\n   
Since I've been making up new terms related to connected component labeling recently (see almost-connected-component labeling<\/a>), here's your new term for the day: disconnected component labeling<\/i>.\r\n   <\/p>\r\n   
Toolbox functions currently do not allow this.<\/p>\r\n   
In part 2 I will show how to work around this restriction. In the meantime, I'm giving you homework: think about whether you\r\n      know of applications that could benefit from allowing this looser definition of connectivity.\r\n   <\/p>