[Insight-users] [vtkusers] How to store a binary image skeleton as a tree or graph?

[Roman Grothausmann]

Dear Jeff,


Many thanks for Your reply. You have given me some nice tips, I'll look 
into. So far I thought only ITK offers an iterator with a neighborhood, 
but I did not know about boost's dfs/bfs traversal algorithms.
The AnalyzeSkeleton imagej plug-in cuts open loops and definitely 
results in a tree, but I'd be happy if I got the skeleton into a graph. 
Because of possible loops in graphs, I thought that directly starting 
with a tree might be easier. Let's see how far I get with Your tips.

Many thanks again for looking into this.
Roman


On 26.07.2012 17:53, Jeff Baumes wrote:
> I don't know of anything that does this type of traversal and tracking of
> branches out of the box, at least in VTK. It sounds like you want vtkGraph
> (which you create with vtkMutableUndirectedGraph/vtkMutableDirectedGraph)
> instead of vtkTree since you may have back edges. You can give the vertices
> positions with graph->SetPoint(i, x, y, z), and add other properties by
> calling graph->Get[Vertex|Edge]Data()->AddArray(arr). As for traversal, the
> most flexible way would be to use boost's dfs/bfs traversal algorithms,
> which is possible if you build VTK with vtkInfovisBoost and
> vtkInfovisBoostGraphAlgorithms modules enabled. A vtkGraph instance can be
> used directly with boost's algorithms if you include
> vtkBoostGraphAdapter.h. See
> Infovis/BoostGraphAlgorithms/vtkBoostBreadthFirstSearch.cxx for an example
> of how to implement a bfs_visitor.
>
> BTW, you can view the graph with vtkGraphLayoutView. Make sure to set the
> layout strategy to PassThrough and turn on 3D interaction if you set your
> own 3D coordinates.
>
> Jeff
>
> On Thu, Jul 26, 2012 at 9:56 AM, Roman Grothausmann <
> roman.grothausmann at helmholtz-berlin.de> wrote:
>
>> Dear mailing list members,
>>
>>
>> My aim is to store the result of AnalyzeSkeleton imagej plug-in (
>> http://fiji.sc/wiki/index.**php/AnalyzeSkeleton#Loop_**
>> detection_and_pruning<http://fiji.sc/wiki/index.php/AnalyzeSkeleton#Loop_detection_and_pruning>)
>> as an itk or vtk tree. Or if easier, the result of Skeletonize3D, i.e. a
>> not analysed skeleton, into a vtkGraph (there seems to be no itkGraph
>> strucutre).
>> Each tree or graph node should also store its voxel position it originated
>> from. Therefore, the vtk structures might be better, since they already
>> offer to store extra data, which itkTree does not (if I'm not mistaken).
>>
>> What would be the best way to do this?
>>
>> At the moment my plan is to use a ConstNeighborhoodIterator starting at
>> the root of the tree, which is supplied by the user. I'd add each
>> CenterPixel as a node to the tree and check its 26 neighbors for other
>> foreground pixels. If there is at least one, take that as the next center
>> pixel and so iterate on. However, I'd need to keep track of branching
>> points (i.e. nodes with more than one child). Therefore, it might be best
>> to recursively traverse through the tree up to its leafs, adding branches
>> from the leafs. This would need, I think, separate
>> ConstNeighborhoodIterators for each branch.
>>
>> Before I start implementing this, I wonder, is there perhaps already a
>> filter/tree-generator that does this? Can the KdTreeGenerator be used for
>> my purpose some how?
>>
>> Any help or hints are very much appreciated
>> Roman
>>
>>
>>
>> --
>> Roman Grothausmann
>>
>> Helmholtz-Zentrum Berlin für Materialien und Energie GmbH
>> Bereich Funktionale Materialien
>> Institut für angewandte Materialforschung
>> Hahn-Meitner-Platz 1
>> D-14109 Berlin
>>
>> (früher Hahn-Meitner-Institut und BESSY)
>>
>>
>> Tel.: +49-(0)30-8062-42816
>> Fax.: +49-(0)30-8062-43059
>>
>> Vorsitzender des Aufsichtsrats: Prof. Dr. Dr. h.c. mult. Joachim Treusch
>> Stellvertretende Vorsitzende: Dr. Beatrix Vierkorn-Rudolph
>> Geschäftsführer: Prof. Dr. Anke Rita Kaysser-Pyzalla, Dr. Ulrich Breuer
>> Sitz der Gesellschaft: Berlin
>> Handelsregister: AG Charlottenburg, 89 HRB 5583
>>
>>
>> ______________________________**_________________
>> Powered by www.kitware.com
>>
>> Visit other Kitware open-source projects at http://www.kitware.com/**
>> opensource/opensource.html<http://www.kitware.com/opensource/opensource.html>
>>
>> Please keep messages on-topic and check the VTK FAQ at:
>> http://www.vtk.org/Wiki/VTK_**FAQ <http://www.vtk.org/Wiki/VTK_FAQ>
>>
>> Follow this link to subscribe/unsubscribe:
>> http://www.vtk.org/mailman/**listinfo/vtkusers<http://www.vtk.org/mailman/listinfo/vtkusers>
>>
>

-- 
Roman Grothausmann

Helmholtz-Zentrum Berlin für Materialien und Energie GmbH
Bereich Funktionale Materialien
Institut für angewandte Materialforschung
Hahn-Meitner-Platz 1
D-14109 Berlin	

(früher Hahn-Meitner-Institut und BESSY)


Tel.: +49-(0)30-8062-42816
Fax.: +49-(0)30-8062-43059

Vorsitzender des Aufsichtsrats: Prof. Dr. Dr. h.c. mult. Joachim Treusch
Stellvertretende Vorsitzende: Dr. Beatrix Vierkorn-Rudolph
Geschäftsführer: Prof. Dr. Anke Rita Kaysser-Pyzalla, Dr. Ulrich Breuer
Sitz der Gesellschaft: Berlin
Handelsregister: AG Charlottenburg, 89 HRB 5583