skeletonize - alternative method

[Peter Stierlen]

Hi,

I used skeletonize to find the centerline of a laser line. It works fine
but there are sometimes unwanted short artifacts connected with the
centerline. I found a very interesting article about another
skeletonization process (
www.cmis.csiro.au/Hugues.Talbot/dicta2003/cdrom/pdf/0283.pdf).
Has anybody realized this as a Java plugin? Any suggestions?

Best regards

Peter

[Michael Miller]

Hello,

I wrote this big long e-mail, and I realize what you may be looking for is a
pruning algorithm. I've got a very nice one working, and I will be
publishing my work within the week. But, regarding skeletonization...

I have been working for the past year on a better skeletonization process.
To my understanding, it all traces back to work done by Blum and his medial
axis.

The ImageJ brushfire skeletonization is very poor and directional dependent:
e.g. skeletonize a rectangle and you will get a single line segment, but
then rotate it an angle not divisible by 90 degrees and you will get the
true medial axis of the rectangle with five line segments. Also, the
skeletonization of large objects creates very rigid skeletonizations which
do not fit the true curves of the Euclidean Distance Map ridges.

I have been casually working on the problem in the past year in my studies
and work towards creating a network analysis tool for ImageJ. I have written
Java code that attempts to find the ridge in the EDM (but the concept of a
discrete gradient has caused discontinuities in my skeletons).

I have also tried looking at properties of the 8-neighbors of the EDM to
determine if it's a skeletal point, but this has proven impossible because
EDMs on rectangles with even widths or heights produces a ridge 2 pixels
thick. Experiments on 5x5 neighborhoods, (the 24-neighbors?) have produced
either discontinuous skeletons, or end up identifying ridges in circular
gradient formations.

Another approach was to use edge sampling and inputting the set into a
Voronoi/Delaunay class, and while it produces a continuous skeletonization
as expected there are many branching artifacts which are not biologically
representative. I suspect with my newer pruning routines this may actually
be a viable skeletonization routine, and I will investigate this shortly.

I've even tried to trace along the EDM to find maximal circles that are
tangent to at least two points, but small discrete circles at small angles
can produce unusual artifacts. It's mathematically perhaps equivalent to the
EDM ridge tracing, but has proven equally difficult.

I've spoken with many people on the topic, and everyone seems to know
theoretically how to do it, but I have yet to find functional code in any
language. In all the papers I've read on the subject, they're always very
fuzzy on the implementation.

So this whole process has been very frustrating for me, I've got a
half-dozen algorithms that are all insufficient in contrasting ways. I'd
love to get this problem looked at in more detail.

-Mike

----- Original Message -----
From: "Peter Stierlen" <[hidden email]>
To: <[hidden email]>
Sent: Monday, January 08, 2007 8:06 PM
Subject: skeletonize - alternative method

> Hi,
>
> I used skeletonize to find the centerline of a laser line. It works fine
> but there are sometimes unwanted short artifacts connected with the
> centerline. I found a very interesting article about another
> skeletonization process (
> www.cmis.csiro.au/Hugues.Talbot/dicta2003/cdrom/pdf/0283.pdf).
> Has anybody realized this as a Java plugin? Any suggestions?
>
> Best regards
>
> Peter

[Gabriel Landini]

Hi,
The morphology collection has a number of different skeletonising and pruning
macros based on binary thinning. Maybe some of this would be of some help.

http://www.dentistry.bham.ac.uk/landinig/software/software.html

Cheers,

G.


On Tuesday 09 January 2007 04:17, Michael Miller wrote:
> I wrote this big long e-mail, and I realize what you may be looking for is
> a pruning algorithm.

> ----- Original Message -----
> From: "Peter Stierlen" <[hidden email]>
> > I used skeletonize to find the centerline of a laser line. It works fine
> > but there are sometimes unwanted short artifacts connected with the
> > centerline.

[Peter Stierlen]

@ Mike

Dear Mike,

thanks for the very helpful info. I also agree about what you said about the
papers with all the theories about different algorithms without any codes.
I tried to find an easy way for my homebuilt 3d-laser scanner application.
The reduction of the artifacts is one of the last points on my todo list.
But looking on your notes I feel affirmed to realize an own filter to delete
all artifacts after the skeletonizaton.
The laser projection plane is orientated in vertical direction. so the
intersection between the laser plane and the scanned object can not include
any loops. I think it should be possible to analyse all segments in
y-direction. Testing all the neighbour elements of a crossing if they are
running backwards in -y direction, if they are connected to other elements
if they are parallel to other elements may help reducing the artifacts
resulting from the insufficient skeletonization.

1. skeletonize
2. binary options > Iterations 1 & count 6
3. binary erode "to get the crossings"
4. subtract result 3. from result 1.  
5. analyse the neighbour elements if they are running in -y & delete them
6. analyse neighbour elements if they are horizontal (y const) and if there
is another neighbour in y-direction > delete horizontal element
7. analyse elements if they have the same y-coordinate of endpoint > ...

and so on.

A lot of different "Ifs" to handle.



@Gabriel
Dear Gabriel,

thanks for the link. Very nice collection of different filters. I installed
the package yesterday evening and did some tests with some of my scans. in
the short time of testing I could not find parameters for skeletonisation
without artifacts. But I will make more tests on sunday.



If one have any ideas and suggestions ... I do not want to reinvent the
wheel. I will be pleased for any idea.

Thanks in advance

Peter