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
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_f...
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...
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.
On Wed, Nov 18, 2015 at 2:22 PM, Arctic_python ejsaiet@alaska.edu wrote:
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
-- 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+unsubscribe@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
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.
On Wednesday, November 18, 2015 at 8:52:05 AM UTC+5:30, Arctic_python wrote:
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
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.
On 18 November 2015 at 06:43, Pratap Vardhan pratapgr8@gmail.com wrote:
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.
- 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.
On Wednesday, November 18, 2015 at 8:52:05 AM UTC+5:30, Arctic_python wrote:
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
-- 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+unsubscribe@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
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.
On Tue, Nov 17, 2015 at 9:43 PM, Pratap Vardhan pratapgr8@gmail.com wrote:
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.
- 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.
On Wednesday, November 18, 2015 at 8:52:05 AM UTC+5:30, Arctic_python wrote:
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
-- 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+unsubscribe@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
-
Arctic_python -
Eyal Saiet
-
Juan Nunez-Iglesias -
Julius Bier Kirkegaard -
Pratap Vardhan