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

[Dan Mueller]

Hi Roman,

Instead of converting a skeleton (a set of undirected points) into a
directed graph, you could consider a method which generates a directed
graph from the beginning.

The minimal path extraction method does this:
    http://www.insight-journal.org/browse/publication/213

Unfortunately there are a number of drawbacks:
* Requires you to define some sort of speed function (which can be tricky)
* Requires start and end points for each path

You may also be interested in some of the methods in VMTK (which is
for tubular centrelines (vessels), but skeletons are related):
    http://www.vmtk.org

HTH

Cheers, Dan

On 27 July 2012 17:46, Roman Grothausmann
<roman.grothausmann at helmholtz-berlin.de> wrote:
> 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
>
>
>
> _____________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Kitware offers ITK Training Courses, for more information visit:
> http://www.kitware.com/products/protraining.php
>
> Please keep messages on-topic and check the ITK FAQ at:
> http://www.itk.org/Wiki/ITK_FAQ
>
> Follow this link to subscribe/unsubscribe:
> http://www.itk.org/mailman/listinfo/insight-users