Graphs and subgraphs (connected components)

Posted by BenTupper on Apr 29, 2010; 1:46pm
URL: http://imagej.273.s1.nabble.com/Graphs-and-subgraphs-connected-components-tp3688463.html

Hello,

I have a collection of foreground objects (blobs) and I want to  
associate some of them based upon separation distance.  So I create a  
distance matrix just like a distance table on a map for driving  
distances between cities.  Using my threshold distance I can create an  
adjacency matrix.  Here is an example for a 13 blob problem(best  
viewed with a fixed width font)...

           1   2   3   4   5   6   7   8   9  10  11  12  13


   1       1   0   3   0   5   0   0   0   0   0   0   0   0
   2       0   2   0   4   0   0   0   0   0   0   0   0   0
   3       1   0   3   0   5   0   0   0   0   0   0   0   0
   4       0   2   0   4   0   0   0   0   0   0   0   0   0
   5       1   0   3   0   5   6   0   0   0   0   0   0   0
   6       0   0   0   0   5   6   0   8   0   0   0   0   0
   7       0   0   0   0   0   0   7   0   0   0   0   0   0
   8       0   0   0   0   0   6   0   8   9   0  11   0   0
   9       0   0   0   0   0   0   0   8   9   0  11   0   0
  10       0   0   0   0   0   0   0   0   0  10   0  12   0
  11       0   0   0   0   0   0   0   8   9   0  11   0  13
  12       0   0   0   0   0   0   0   0   0  10   0  12   0
  13       0   0   0   0   0   0   0   0   0   0  11   0  13



Reading across row one, blob 1 is within the threshold distance of  
blobs 3 and 5.  You can see that blob 3 (row three) is "adjacent to 1  
and 5 while blob 5 (row five) is adjacent to 1,3 and 6.  And so the  
chase begins... It is possible to have anywhere from 1 to 13 adjacency  
lists where the former means they are all "connected" and the latter  
means they all "disconnected" or independent of each other. If I have  
done my figuring correctly, in the example above there are 4 connected-
component lists.

List1: 1,3,5,6,8,9,11,13
List2: 2,4
List3: 7
List4: 10,12


I plan to use this adjacency matrix to build adjacency lists (using a  
either a breadth-first-search or a depth-first-search).  I plan to  
model the search after the Flood Filling routines described in chapter  
11 of "Digital Image Processing" (Burger and Burge), but I am open to  
using other tricks.

Before I leap into to it, I thought it worth asking here if this is  
already available in ImageJ.  I have scoured the ImageJ website, but I  
think the task of searching (no pun intended) for this graph stuff is  
that the vocabulary of the science is so large and squishy.

Thanks!
Ben Tupper