{"id":343,"date":"2010-10-07T12:54:39","date_gmt":"2010-10-07T16:54:39","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2010\/10\/07\/disconnected-component-labeling-part-2\/"},"modified":"2019-10-29T13:36:11","modified_gmt":"2019-10-29T17:36:11","slug":"disconnected-component-labeling-part-2","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2010\/10\/07\/disconnected-component-labeling-part-2\/","title":{"rendered":"Disconnected component labeling: part 2"},"content":{"rendered":"
\r\n

Last week I wrote<\/a> about a user's request to perform connected-component labeling with an unusual connectivity definition:\r\n <\/p>

  [1 0 1 0 1]<\/pre>
This definition, which is not supported by Image Processing Toolbox functions, has the effect of dividing an image into two\r\n      noninteracting subimages, one containing the even columns and one containing the odd columns.\r\n   <\/p>\r\n   
That description gives us our needed clue about how to implement such a thing. We split the image up into the two subimages,\r\n      find the connected components in each subimage, and then merge the results.\r\n   <\/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>
bw1 = bw(:,1:2:end)<\/pre>
\r\nbw1 =\r\n\r\n     1     1     0     0\r\n     1     1     1     0\r\n     1     1     1     0\r\n     1     1     0     1\r\n     1     1     0     1\r\n     1     1     0     1\r\n     1     1     0     1\r\n     1     1     0     0\r\n\r\n<\/pre>
bw2 = bw(:,2:2:end)<\/pre>
\r\nbw2 =\r\n\r\n     1     0     0     0\r\n     1     0     1     0\r\n     1     0     1     0\r\n     1     0     0     0\r\n     1     0     0     0\r\n     1     0     0     0\r\n     1     0     1     0\r\n     1     0     0     0\r\n\r\n<\/pre>
Find connected components in each subimage assuming that each pixel is connected only to its east and west neighbors.<\/p>
cc1 = bwconncomp(bw1, [0 0 0; 1 1 1; 0 0 0])<\/pre>
\r\ncc1 = \r\n\r\n    Connectivity: [3x3 double]\r\n       ImageSize: [8 4]\r\n      NumObjects: 12\r\n    PixelIdxList: {1x12 cell}\r\n\r\n<\/pre>
cc2 = bwconncomp(bw2, [0 0 0; 1 1 1; 0 0 0])<\/pre>
\r\ncc2 = \r\n\r\n    Connectivity: [3x3 double]\r\n       ImageSize: [8 4]\r\n      NumObjects: 11\r\n    PixelIdxList: {[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [18]  [19]  [23]}\r\n\r\n<\/pre>
Now we have to go through a bit of work to modify the PixelIdxList for each connected component.<\/p>
size_bw1 = size(bw1);\r\nsize_bw = size(bw);\r\nfor<\/span> k = 1:numel(cc1.PixelIdxList)\r\n    idx = cc1.PixelIdxList{k};\r\n    [r,c] = ind2sub(size_bw1, idx);\r\n    new_idx = sub2ind(size_bw, r, 2*c-1);\r\n    cc1.PixelIdxList{k} = new_idx;\r\nend<\/span>\r\n\r\nsize_bw2 = size(bw2);\r\nfor<\/span> k = 1:numel(cc2.PixelIdxList)\r\n    idx = cc2.PixelIdxList{k};\r\n    [r,c] = ind2sub(size_bw2, idx);\r\n    new_idx = sub2ind(size_bw, r, 2*c);\r\n    cc2.PixelIdxList{k} = new_idx;\r\nend<\/span><\/pre>
Now the pixel index lists for each connected component have been corrected to refer to pixel locations in the original image.\r\n      Next we make a new connected component struct containing both sets of components.\r\n   <\/p>
cc = cc1;\r\ncc.ImageSize = size_bw;\r\ncc.NumObjects = cc1.NumObjects + cc2.NumObjects;\r\ncc.PixelIdxList = [cc1.PixelIdxList, cc2.PixelIdxList]<\/pre>
\r\ncc = \r\n\r\n    Connectivity: [3x3 double]\r\n       ImageSize: [8 8]\r\n      NumObjects: 23\r\n    PixelIdxList: {1x23 cell}\r\n\r\n<\/pre>
Finally, let's visualize what we ended up with by converting to a label matrix:<\/p>
L = labelmatrix(cc)<\/pre>
\r\nL =\r\n\r\n    1   13    1    0    0    0    0    0\r\n    2   14    2    0    2   21    0    0\r\n    3   15    3    0    3   22    0    0\r\n    4   16    4    0    0    0    9    0\r\n    5   17    5    0    0    0   10    0\r\n    6   18    6    0    0    0   11    0\r\n    7   19    7    0    0   23   12    0\r\n    8   20    8    0    0    0    0    0\r\n\r\n<\/pre>
So it can be done, although it takes some extra coding. I confess, though, that I'm still not exactly sure why one might want\r\n      to do connected component labeling this way.\r\n   <\/p>\r\n   
Anyone have any inspiration about this? Creative ideas you'd like to share? Post your comments here.<\/p>