measuring the longest thread of a skeleton

[Arctic_python]

Hello,
Anyone has suggestions for an algorithm to measure the length of a skeleton line/thread(e.g http://scikit-image.org/docs/dev/auto_examples/plot_skeleton.html)?
The context- I skeletonize a shape to infer its length.
Thanks

[Juan Nunez-Iglesias]

Hey Arctic! =)

This is probably overkill, but you could build a networkx graph of the pixels of the skeleton using a variation of this recipe:

http://ilovesymposia.com/2014/06/24/a-clever-use-of-scipys-ndimage-generic_filter-for-n-dimensional-image-processing/

You will need every pixel of the skeleton to be its own label. You can get this by using the np.arange function and setting to zero every pixel not in the skeleton.

and then use networkx's diameter function to find the length of the longest path in the graph:

https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.distance_measures.diameter.html

I hope that's a good enough outline to get you where you want to go! But post back to the list if you need more detail... Just a bit stretched for time right now.

Juan.

--
You received this message because you are subscribed to the Google Groups "scikit-image" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Pratap Vardhan]

My first thought was what Juan suggested and seemed logical to do that.

As an alternative, you could also (this may be an overfill and could be slower than network approach) try.

1. From every endpoints of skeleton compute the distance transform (using flood-fill or neighbourhood methods).

2. Now the maximum distance for above all distances will give you the longest path in skeleton.

This way you can have the trace path of the longest thread in skeleton in image form itself.

[Eyal Saiet]

Thanks I will look into the network approach.

I guess I was naive to assume there is a common algorithm, built in scikit-image to measure the length of the skeleton.

--
You received this message because you are subscribed to a topic in the Google Groups "scikit-image" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/scikit-image/wM-zMGL9dVI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to scikit-image...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Eyal Saiet

Project manager

Remote sensing and in-situ measurements

Geophysical Institute 

University of Alaska Fairbanks

Fairbanks, AK 99775

(907) 750 6555 (cell)

ejs...@alaska.edu

[Julius Bier Kirkegaard]

I have some code lying around that will do this. It's not the most efficient way though, but if you just need a quick solution:

def floyd_warshall(x,y):
dist = np.sqrt((x[:,np.newaxis]-x[np.newaxis,:])**2 + (y[:,np.newaxis]-y[np.newaxis,:])**2)
d = np.array(dist)
d[dist>1.5] = np.inf # sqrt(2) < 1.5 < 2
n = len(x)
for k in xrange(n):
kd = d[:,k,np.newaxis] + d[k,:]
d = np.minimum(d,kd)
return d 
skel = np.argwhere(skel)
x, y = skel[:,0], skel[:,1]
d = np.max(floyd_warshall(x,y))

(if you have many seperated skeletons it's worth doing each label independently)

A better method is to find the two end points and use Dijkstra's algorithm on those.

--

You received this message because you are subscribed to the Google Groups "scikit-image" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.

[Juan Nunez-Iglesias]

Eyal, not naive at all, it's a reasonable expectation! Skeletonization and related algorithms are a place where the library needs improving. If you come up with a good solution, we can help you get it into the library. See http://scikit-image.org/docs/stable/contribute.html .

Thanks!

Juan.

--

You received this message because you are subscribed to the Google Groups "scikit-image" group.

To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.