{"id":123,"date":"2007-03-20T07:00:46","date_gmt":"2007-03-20T11:00:46","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/20\/connected-component-labeling-part-3\/"},"modified":"2019-10-23T08:47:06","modified_gmt":"2019-10-23T12:47:06","slug":"connected-component-labeling-part-3","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2007\/03\/20\/connected-component-labeling-part-3\/","title":{"rendered":"Connected component labeling – Part 3"},"content":{"rendered":"
\r\n

Let's start looking at connected component labeling algorithms. In this post I want to explain how you can think of pixel\r\n neighborhood relationships in terms of a graph. We'll look at how to represent and visualize a graph in MATLAB, as well as\r\n how to compute the connected components of a graph.\r\n <\/p>\r\n

Here's our sample binary image:<\/p>

bw = logical([ ...<\/span>\r\n    0 0 0 0 0 0 0\r\n    0 1 1 0 0 0 0\r\n    0 1 1 0 0 0 0\r\n    0 0 0 1 1 1 0\r\n    0 0 0 1 1 1 0\r\n    0 0 0 0 0 0 0 ])<\/pre>
\r\nbw =\r\n\r\n     0     0     0     0     0     0     0\r\n     0     1     1     0     0     0     0\r\n     0     1     1     0     0     0     0\r\n     0     0     0     1     1     1     0\r\n     0     0     0     1     1     1     0\r\n     0     0     0     0     0     0     0\r\n\r\n<\/pre>
Each foreground pixel becomes a node in the graph.  Let's number the nodes.  Theoretically, the node ordering doesn't matter\r\n      very much, but for us it's convenient to use the same order as the find<\/tt> function:\r\n   <\/p>
0  0  0  0  0  0  0\r\n0  1  3  0  0  0  0\r\n0  2  4  0  0  0  0\r\n0  0  0  5  7  9  0\r\n0  0  0  6  8 10  0<\/pre>
Next, make a list of which nodes in the graph are connected to each other.  Two nodes are connected if the corresponding pixels\r\n      are neighbors.  Using 4-connectivity, for example, node 1 is connected to nodes 2 and 3.  Node 4 is connected to nodes 2 and\r\n      3. Let's capture these pairwise connections in a matrix:\r\n   <\/p>
pairs = [...<\/span>\r\n    1 3; 1 2;\r\n    2 1; 2 4;\r\n    3 1; 3 4;\r\n    4 2; 4 3;\r\n    5 6; 5 7;\r\n    6 5; 6 8;\r\n    7 5; 7 8; 7 9;\r\n    8 6; 8 7; 8 10;\r\n    9 7; 9 10;\r\n    10 8; 10 9]<\/pre>
\r\npairs =\r\n\r\n     1     3\r\n     1     2\r\n     2     1\r\n     2     4\r\n     3     1\r\n     3     4\r\n     4     2\r\n     4     3\r\n     5     6\r\n     5     7\r\n     6     5\r\n     6     8\r\n     7     5\r\n     7     8\r\n     7     9\r\n     8     6\r\n     8     7\r\n     8    10\r\n     9     7\r\n     9    10\r\n    10     8\r\n    10     9\r\n\r\n<\/pre>
From these pairs you can build up a graph representation called an adjacency matrix<\/i>.  An adjacency matrix has one row and column for each graph node.  A nonzero element (p,q) means that there is a connection\r\n      between nodes p and q.  In other words, nodes p and q are adjacent.  You can build up an adjacency matrix from the list of\r\n      pairs by using accumarray<\/tt>, like this:\r\n   <\/p>
A = accumarray(pairs, 1)<\/pre>
\r\nA =\r\n\r\n     0     1     1     0     0     0     0     0     0     0\r\n     1     0     0     1     0     0     0     0     0     0\r\n     1     0     0     1     0     0     0     0     0     0\r\n     0     1     1     0     0     0     0     0     0     0\r\n     0     0     0     0     0     1     1     0     0     0\r\n     0     0     0     0     1     0     0     1     0     0\r\n     0     0     0     0     1     0     0     1     1     0\r\n     0     0     0     0     0     1     1     0     0     1\r\n     0     0     0     0     0     0     1     0     0     1\r\n     0     0     0     0     0     0     0     1     1     0\r\n\r\n<\/pre>
For graphs containing many nodes, you are better off constructing a sparse adjacency matrix, like this:<\/p>
A = sparse(pairs(:,1), pairs(:,2), 1);\r\nspy(A)\r\ntitle('Spy plot of sparse adjacency matrix'<\/span>)<\/pre> 
MATLAB has a function called dmperm<\/tt>, which computes the Dulmage-Mendelsohn decomposition of a matrix. If the matrix is an adjacency matrix, dmperm<\/tt> can be used to compute the connected components of the corresponding graph. Here's how to do it.\r\n   <\/p>\r\n   
First, you have to put 1s on the diagonal of A<\/tt>:\r\n   <\/p>
A(1:11:end) = 1;<\/pre>\r\n\r\n
[Note added June 29, 2007: Tim Davis pointed out this the above line is an inefficient way to get ones onto the diagonal of a sparse matrix.  Please see his comments<\/a> for an explanation and for better ways to do it.]<\/em><\/p>\r\n
Next, call dmperm<\/tt>:\r\n   <\/p>\r\n\r\n
[p,q,r,s] = dmperm(A);<\/pre>
The output p<\/tt> contains a permuted list of nodes:\r\n   <\/p>
p<\/pre>
\r\np =\r\n\r\n     3     4     2     1    10     9     7     8     6     5\r\n\r\n<\/pre>
And the output r<\/tt> tells you which nodes of p<\/tt> belong to the same connected component:\r\n   <\/p>
r<\/pre>
\r\nr =\r\n\r\n     1     5    11\r\n\r\n<\/pre>
Specifically, the first connected component contains these nodes:<\/p>
p(r(1):r(2)-1)<\/pre>
\r\nans =\r\n\r\n     3     4     2     1\r\n\r\n<\/pre>
The second connected component contains these nodes:<\/p>
p(r(2):r(3)-1)<\/pre>
\r\nans =\r\n\r\n    10     9     7     8     6     5\r\n\r\n<\/pre>
These two sets of nodes are the connected components of our original binary image.<\/p>\r\n   
Let's finish this example by using 8-connectivity instead of 4-connectivity.  Our list of pairs becomes:<\/p>
pairs = [...<\/span>\r\n    1 2; 1 3; 1 4;\r\n    2 1; 2 3; 2 4;\r\n    3 1; 3 2; 3 4;\r\n    4 1; 4 2; 4 3; 4 5;\r\n    5 4; 5 6; 5 7; 5 8;\r\n    6 5; 6 7; 6 8;\r\n    7 5; 7 6; 7 8; 7 9; 7 10;\r\n    8 5; 8 6; 8 7; 8 9; 8 10;\r\n    9 7; 9 8; 9 10;\r\n    10 7; 10 8; 10 9];<\/pre>
Now repeat the steps of building the sparse adjacency matrix and calling dmperm<\/tt>:\r\n   <\/p>
A = sparse(pairs(:,1), pairs(:,2), 1);\r\nA(1:11:end) = 1;\r\n[p,q,r,s] = dmperm(A);\r\nr<\/pre>
\r\nr =\r\n\r\n     1    11\r\n\r\n<\/pre>\r\n\r\n
\r\n[Note added June 29, 2007: See Tim's comment<\/a> about A(1:11:end) = 1.]<\/em>\r\n<\/p>\r\n\r\n
Now there's only one connected component:<\/p>
p(r(1):r(2)-1)<\/pre>
\r\nans =\r\n\r\n    10     9     8     7     6     5     4     3     2     1\r\n\r\n<\/pre>
Next time we'll look at computing connected components using a kind of \"flood fill\" approach.<\/p>