{"id":2537,"date":"2017-04-06T15:35:08","date_gmt":"2017-04-06T19:35:08","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=2537"},"modified":"2019-11-01T17:08:12","modified_gmt":"2019-11-01T21:08:12","slug":"variation-on-connected-objects-using-graphs","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2017\/04\/06\/variation-on-connected-objects-using-graphs\/","title":{"rendered":"Variation on Connected Objects – Using Graphs"},"content":{"rendered":"

Reader Uri Pe'er found an old post from 2011<\/a> about shortest paths in binary images, and he asked this follow-up question (paraphrased):<\/p>

How can I determine if there is a path from one row to another in a binary image? And can I constrain the direction of movement along the path?<\/i><\/p>

Last week<\/a> I showed how to tackle this problem using imfill<\/tt><\/a>. Today I'm going to use a graph<\/tt>.<\/p>

In December 2015 I wrote about how to create graphs based on the connectivity of image pixels, and I submitted some functions to the File Exchange<\/a> to make it easy.<\/p>

One of those functions is binaryImageGraph<\/tt>. Let's try it using one of the same images from my last post.<\/p>

bw1 = imread('https:\/\/blogs.mathworks.com\/steve\/files\/path-shapes-1.png'<\/span>);\r\nimshow(bw1)\r\n<\/pre>\"\" 
g = binaryImageGraph(bw1)\r\n<\/pre>
\r\ng = \r\n\r\n  graph with properties:\r\n\r\n    Edges: [180444×2 table]\r\n    Nodes: [45880×3 table]\r\n\r\n<\/pre>
Each foreground pixel in the binary image corresponds to a graph node, so the total number of graph nodes is the same as the number of foreground pixels.<\/p>
nnz(bw1)\r\n<\/pre>
\r\nans =\r\n\r\n       45880\r\n\r\n<\/pre>
The function plotImageGraph<\/tt> (from the same File Exchange submission<\/a>) can be used to visualize the image graph.<\/p>
plotImageGraph(g)\r\n<\/pre>\"\" 
Zoom in to see the graph details in a small portion of the image.<\/p>
axis([275 300 125 140])\r\n<\/pre>\"\" 
Now let's figure out whether there are any graph paths connecting a row-100 pixels to a row-300 pixel. Note that binaryImageGraph<\/tt> stores the original foreground pixel locations in the graph's node table for purposes just like this. Here's what the node table looks like.<\/p>
head(g.Nodes)\r\n<\/pre>
\r\nans =\r\n\r\n  8×3 table\r\n\r\n     x     y     PixelIndex\r\n    ___    __    __________\r\n\r\n    121    76    57676     \r\n    121    77    57677     \r\n    121    78    57678     \r\n    121    79    57679     \r\n    121    80    57680     \r\n    121    81    57681     \r\n    121    82    57682     \r\n    121    83    57683     \r\n\r\n<\/pre>
row_100_nodes = find(g.Nodes.y == 100);\r\nrow_300_nodes = find(g.Nodes.y == 300);\r\n<\/pre>
Next, use conncomp<\/tt> to find the connected components of the graph.<\/p>
bins = conncomp(g);\r\n<\/pre>
For one of the graph nodes, bins(node)<\/tt> tells you which connected component that node belongs to.<\/p>
unique(bins(row_100_nodes))\r\n<\/pre>
\r\nans =\r\n\r\n     1\r\n\r\n<\/pre>
So the foreground pixels on row 100 all belong to the same connected component.<\/p>
unique(bins(row_300_nodes))\r\n<\/pre>
\r\nans =\r\n\r\n     1     2\r\n\r\n<\/pre>
The foreground pixels on row 300 belong to two different connected components. Since one of those the components is the same as for the row 100 pixels, that means there is path from row 100 to row 300.<\/p>
Just like imfill<\/tt>, binaryImageGraph<\/tt> can take a custom connectivity matrix. We can use that to constrain the allowed paths. Let's try that with one of the other images I used last time.<\/p>
bw3 = imread('https:\/\/blogs.mathworks.com\/steve\/files\/path-shapes-3.png'<\/span>);\r\nimshow(bw3)\r\n<\/pre>\"\" 
conn = [\r\n    1 0 0\r\n    0 1 0\r\n    0 0 1 ];\r\ng = binaryImageGraph(bw3,conn);\r\nplotImageGraph(g)\r\naxis([275 300 125 140])\r\n<\/pre>\"\" 
Is there a constrained path from row 180 to row 250?<\/p>
row_180_nodes = find(g.Nodes.y == 180);\r\nrow_250_nodes = find(g.Nodes.y == 250);\r\nbins = conncomp(g);\r\n~isempty(intersect(bins(row_180_nodes),bins(row_250_nodes)))\r\n<\/pre>
\r\nans =\r\n\r\n  logical\r\n\r\n   0\r\n\r\n<\/pre>
No.<\/p>
But what if we reverse the path constraint?<\/p>
conn = [\r\n    0 0 1\r\n    0 1 0\r\n    1 0 0 ];\r\ng = binaryImageGraph(bw3,conn);\r\nplotImageGraph(g)\r\naxis([275 300 125 140])\r\n<\/pre>\"\" 
row_180_nodes = find(g.Nodes.y == 180);\r\nrow_250_nodes = find(g.Nodes.y == 250);\r\nbins = conncomp(g);\r\n~isempty(intersect(bins(row_180_nodes),bins(row_250_nodes)))\r\n<\/pre>
\r\nans =\r\n\r\n  logical\r\n\r\n   1\r\n\r\n<\/pre>
Yes, rows 180 and 250 are connected via a paths constrained to lie along the upper-right to lower-left diagonal.<\/p>