pruning

[Aryeh Weiss]

Is there a plugin which will prune a skeleton such that the longest
nonbranched distance remains?

The skeleton analyzer will provide endpoints and triple points, so what
I need is to remove the shortest branch coming off of each triple point.
Before I do this, I am wondering if it is already done (and I welcome
any comments on the best way to do it).

--aryeh
--
Aryeh Weiss
School of Engineering
Bar Ilan University
Ramat Gan 52900 Israel

Ph:  972-3-5317638
FAX: [phone]

[Gabriel Landini]

On Sunday 22 August 2010, you wrote:
> Is there a plugin which will prune a skeleton such that the longest
> nonbranched distance remains?
> The skeleton analyzer will provide endpoints and triple points, so what
> I need is to remove the shortest branch coming off of each triple point.
> Before I do this, I am wondering if it is already done (and I welcome
> any comments on the best way to do it).

Here I assume that the object is 8 connected and the image has been
skeletonised (there are no filled areas).

For the branches you need the endpoints and all the 2-neighbour points.

The binary connectivity plugin gives you an image labelled according to the
number of pixels connected to the centre pixels in a 3x3 kernel.
If you threshold this result for the values 1 and 2, then you could use the
Lines8 plugin to measure the lengths of the thresholded segments and either
use the magic wand or Binary Reconstruction to keep the largest one.

For the latter scan throught the Results table, find the longest segment, get
its XStart YStart coordinates, then create an empty image (same dimensions)
and set those corrdinates in the image. That is your seed, while the
thresholded image is the mask and then reconstruct.

Note that the Lines8 plugin gives 2 different estimates of the segment
lengths.

Both plugins are in the Morphology zip file in my page.
http://www.dentistry.bham.ac.uk/landinig/software/software.html

I fgorgot to say that this is all for 2D. For 3D I assume that one can appply
a similar approach but the plugins above work for 2D only.

Cheers
G.

[Michael Doube]

On 22/08/10 08:14, Aryeh Weiss wrote:
> Is there a plugin which will prune a skeleton such that the longest
> nonbranched distance remains?
>
> The skeleton analyzer will provide endpoints and triple points, so what
> I need is to remove the shortest branch coming off of each triple point.
> Before I do this, I am wondering if it is already done (and I welcome
> any comments on the best way to do it).
>
> --aryeh

Hi Aryeh

I added some code to Ignacio's AnalyzeSkeleton plugin that does
something like this.  I think it's only in my version of
AnalyzeSkeleton, in BoneJ:

http://bonej.org/analyseskeleton

The graph classes in AnalyzeSkeleton (Edge, Graph, Point and Vertex) are
helpful to do pruning; you can quickly identify and remove branches.  I
think your case is a bit different to mine, but take a look at
pruneEndBranches(), here:
http://github.com/mdoube/BoneJ/blob/master/src/org/doube/skeleton/AnalyzeSkeleton.java#L1674


Michael

[gerrit]

Aryeh,


we did an implementation of the Warshall algorithm (<a href="http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm">http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm)
in the analyse skelleton plugin. We contacted Ignatio already about adding the code to his plugin, but we are
currently busy to add some final enhancements to the code.
If you like I can send you the current version.

BTW I will present this work on the ImageJ conference in October.

kindly,
Gerrit.

[David Webster]

Gerrit,

Can this do "longest" path problems as well? If you modify the path weights
so that

newWeight = maxOldWeight-oldWeight

will the shortest path algorithm give you the longest path?

david

On Mon, Aug 23, 2010 at 2:40 AM, Gerrit Polder <[hidden email]> wrote:

> Aryeh,
>
>
> we did an implementation of the Warshall algorithm (
> http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm<http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm>
> )
> in the analyse skelleton plugin. We contacted Ignatio already about adding
> the code to his plugin, but we are
> currently busy to add some final enhancements to the code.
> If you like I can send you the current version.
>
> BTW I will present this work on the ImageJ conference in October.
>
> kindly,
> Gerrit.
>

[gerrit]

David,

What our algorithm actually gives is the longest shortest path.

According to http://en.wikipedia.org/wiki/Longest_path_problem the longest path problem can be solved by negating the branch weights, but this only works for acyclic graphs.

The Warchall algorithm we implemented can cope with negative weights, in contrast with the Dijkstra algorithm.
Please let me know wether this works for you.

Gerrit.

>Gerrit,
>
>Can this do "longest" path problems as well? If you modify the path weights
>so that
>
>newWeight = maxOldWeight-oldWeight
>
>will the shortest path algorithm give you the longest path?
>
>david