Graphs and subgraphs (connected components)

[BenTupper]

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

[Mario Guarracino]

BFS is implemented in yawi3d (http://yawi3d.sourceforge.net). There
are many algorithms for graph partitioning. I think it is also worth
give a try to spectral clustering.
Mario

-----Messaggio originale-----
Da: ImageJ Interest Group [mailto:[hidden email]] Per conto di Ben
Tupper
Inviato: giovedì 29 aprile 2010 15.47
A: [hidden email]
Oggetto: Graphs and subgraphs (connected components)

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



----- Fine del messaggio inoltrato -----



----- Fine del messaggio inoltrato -----