Posted by
Michael Miller on
Feb 27, 2007; 1:16pm
URL: http://imagej.273.s1.nabble.com/skeleton-length-tp3700229p3700232.html
Gabriel,
Good catch. My basis for the algorithm was from work by Niemisto, et al.
"Robust Quantification of In Vitro Angiogenesis Through Image Analysis"
published in IEEE Transactions on Medical Imaging Vol24, No.4, April 2005,
regarding the publication of the Angioquant tool. They do not detail their
method for counting Nd, so restricting Nd as I now do below is likely an
oversight on my part in the description of the algorithm.
x4 | x3 | x2
------------
x5 | p | x1
------------
x6 | x7 | x8
One quick fix for the problem you described is to not count diagonals in the
presence of one 4-connected pixel in that direction (ie. suppose x4 is
skeletal, do not count the diagonal connection to x4 if either x3 or x5 is
also skeletal). Using this modified method in your example, C would prevent
AB and AD from being counted.
To illustrate that there are many methods; I also have a paper by Fabrizio
Lamberti; Andrea Gamba; and Bartolomeo Montrucchio "Computer-assisted
analysis of in-vitro vasculogenesis and angiogenesis processes" in the
Journal of WSCG 237-244, Vol.12, No1-3, that appears to use the centers of
straight line segments to attempt to approximate a more continuous skeleton;
(the details in my version of the paper were damaged by my printer
misinterpretting the latex). They state they plan to evaluate the accuracy
of various length algorithms, but I have been unable to find any recent
published work to that end. (If this is interesting to anyone, be careful in
your implementation that your algorithm properly mesaures a square.)
Thanks for catching my mistake!
-Mike
----- Original Message -----
From: "Gabriel Landini" <
[hidden email]>
To: <
[hidden email]>
Sent: Tuesday, February 27, 2007 6:00 AM
Subject: Re: skeleton length
> On Tuesday 27 February 2007 08:07:50 Michael Miller wrote:
>> I've been working on using ImageJ to compute lengths via skeletons for
>> some
>> time. My solution is below.
>>
>> Parse the entire skeleton (loop over every pixel). Once you find a part
>> of
>> the skeleton:
>> -count up the number of horizontal Nh, vertical Nv, and diagonal Nd
>> connections separately
>> Once you're done with this loop, you will have counted every pair of
>> pixels
>> exactly twice; divide each Nd, Nv, Nh by 2.
>
> A problem arises when you have a "T" configuration of pixels which can
> easily
> happen when skeletonizing:
>
> (you need a fixed font to see this):
>
> A
> BCD
>
> In this configuration your method will find the distances CB, CD, CA, but
> also
> the unnecessary AB and AD (since the skeleton is already connected from A
> to
> C.
> This will over-estimage the length of the skeletons.
> In reality each corner (above A-C-D) will be overestimated by sqrt(2)
> pixels.
> This can account for quite a bit in some skeletons.
>
> I would be happy to try some other ideas.
>
> Cheers,
>
> Gabriel