Posted by
Mario Guarracino on
Apr 29, 2010; 7:42pm
URL: http://imagej.273.s1.nabble.com/Graphs-and-subgraphs-connected-components-tp3688463p3688464.html
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 -----