skeleton length

[Martin du Saire]

Hi,

I am thinking about estimating root length based on a
non-intersecting skeleton of a root scan.  The idea is to tally the
number of 4-connected and 8-connected (diagonals only) pixels, and
assign a length of 1 to each pair of 4-connected pixels and 1.414 to
each pair of 8-connected pixels.  Has someone already done this?  Or
is this a bad idea?

Thanks.

M

[karo03]

... perhaps the perimeter of the skeleton divided by two is not such  
a bad estimate for skeleton or fibre length?
Karsten

Am 23.02.2007 um 20:14 schrieb Martin du Saire:

> Hi,
>
> I am thinking about estimating root length based on a non-
> intersecting skeleton of a root scan.  The idea is to tally the  
> number of 4-connected and 8-connected (diagonals only) pixels, and  
> assign a length of 1 to each pair of 4-connected pixels and 1.414  
> to each pair of 8-connected pixels.  Has someone already done  
> this?  Or is this a bad idea?
>
> Thanks.
>
> M

[Martin du Saire]

Thanks, that's perfect!.

M
At 03:41 PM 2/23/2007, you wrote:

>... perhaps the perimeter of the skeleton divided by two is not such
>a bad estimate for skeleton or fibre length?
>Karsten
>
>Am 23.02.2007 um 20:14 schrieb Martin du Saire:
>
>>Hi,
>>
>>I am thinking about estimating root length based on a non-
>>intersecting skeleton of a root scan.  The idea is to tally the
>>number of 4-connected and 8-connected (diagonals only) pixels, and
>>assign a length of 1 to each pair of 4-connected pixels and 1.414
>>to each pair of 8-connected pixels.  Has someone already done
>>this?  Or is this a bad idea?
>>
>>Thanks.
>>
>>M

[Gabriel Landini]

>... perhaps the perimeter of the skeleton divided by two is not such
>a bad estimate for skeleton or fibre length?

Yes, but only if there are no closed loops in the skeleton (i.e. the original
shape does not have holes).

Just imagine the skeleton of a doughnut (a circle). In this case its perimeter
should be the skeleton length (and by dividing by two one will underestimate
it by half). Of course this is an extreme situation, but better be aware of
it beforehand.

I have a semi-working version of Particles8_Plus that measures lines lengths.
If anybody wants to test/validate it (with skeletons of known sizes?) let me
know.

Cheers,

Gabriel

[Michael Miller]

Hello,

I've been working on using ImageJ to compute lengths via skeletons for some
time. My solution is below.

Essentially, use a single-pixel-wide skeletonization from your segmentation
[Binary -> Skeletonize is horrible but its still the only functioning
algorithm I can find at this time despite help from the community] (the
ridge of the distance map isn't always 2 pixels wide, your answer will be
off by half a pixel because of this).

Here a single pixel has no length; measurement is from between the centers
of every pixel, ie 3 horizontal pixels will be length 2.

Feedback is welcome.

-Mike

Details:

pixelWidth = 1;  // this is the true width and height of a pixel connection
pixelHeight = imageAspectRatio; // height / width
pixelDiagonal = Math.sqrt(pixelWidth+pixelHeight); // if the aspectratio was
1, you get 1.414..

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.

L = Nd*pixelDiagonal + Nh*pixelWidth + Nv*pixelHeight;  // this computes the
raw pixel length of the skeleton
L *= distanceInUnitsPerPixel; // you can use info from Set Scale... to
extract units from the image
Your final length L is now in real-world units.

----- Original Message -----
From: "Martin du Saire" <[hidden email]>
To: <[hidden email]>
Sent: Friday, February 23, 2007 1:14 PM
Subject: skeleton length

> Hi,
>
> I am thinking about estimating root length based on a non-intersecting
> skeleton of a root scan.  The idea is to tally the number of 4-connected
> and 8-connected (diagonals only) pixels, and assign a length of 1 to each
> pair of 4-connected pixels and 1.414 to each pair of 8-connected pixels.
> Has someone already done this?  Or is this a bad idea?
>
> Thanks.
>
> M

[Gabriel Landini]

On Tuesday 27 February 2007 08:07:50 Michael Miller wrote:
> Here a single pixel has no length; measurement is from between the centers
> of every pixel, ie 3 horizontal pixels will be length 2.
>
> Feedback is welcome.

I have just realised that if the skeleton has closed loops with more structure
inside (let's say like the mercedes benz logo), then perimeter-based methods
do not see the pixels inside, but your method will.

Cheers,

Gabriel

[Gabriel Landini]

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

[Michael Miller]

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

[Gabriel Landini]

On Tuesday 27 February 2007 13:16:57 Michael Miller wrote:
> 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).

Yes, that seems to work fine.
Thanks,

Gabriel