Posted by
Kenneth Sloan-2 on
Mar 24, 2009; 4:42pm
URL: http://imagej.273.s1.nabble.com/Concave-Hull-tp3693191p3693193.html
This looks like the kind of problem that Alpha-Shapes can solve (of
course,
I think Gamma-Shapes - a minor tweak to handle non-uniform density - is
better).
The link provided pretty pictures, but at first glance I couldn't find
a description
of the algorithm. Can someone familiar with it please summarize the
method?
I'll offer a quick overview of Alpha-Shapes - just to get things
started.
Alpha-Shapes is a method based on generalizing the convex hull. The
convex hull
uses supporting LINES. Consider a supporting line as being a
supporting BALL with infinite radius. Alpha-Shapes allows the radius
of the supporting BALLS to be finite. The usual analogy is a
spherical cutting tool carving away soft material but being blocked by
hard material (the data points). The finite spherical cutting tool
can make it's way into concavities (and, if it's small enough, can
separate the data points into several blobs).
The essential building block of Alpha-Shapes is the Voronoi Diagram/
Delaunayt Triangulation. If you have a good
implementation of the DT, adding the extra processing to get Alpha-
Shapes is relatively easy.
One nice property is that you only have to do the DT once - then there
is a control knob (the radius of the cutting tool) that can be
modified interactively - new Alpha-Shapes can be computed quickly as a
function of the
cutting ball radius.
Beware - one flaw in Alpha-Shapes is the inability to handle non-
uniform sampling density. This flaw is
repaired in Gamma Shapes.
Both Alpha- and Gamma-Shapes can operate in either 2D or 3D. I'm not
aware of any ImageJ plugin for either. Again, the essential
foundation is the Delaunay Triangulation of the data points.
IF your data points all lie on the BOUNDARY of the object, and you
want a shape that interpolates ALL of the data points, there are other
methods available.
As previously noted, the CONVEX HULL has a well-accepted definition.
The so-called CONCAVE HULL is
not so well defined, and is probably domain specific. That said, I
think Alpha-(Gamma-)Shapes are the best
candidates.
On Mar 24, 2009, at 5:54 AM, Gabriel Landini wrote:
> On Tuesday 24 March 2009 10:25:44 Mathias Zech wrote:
>> does anyone know of an ImageJ plugin which calculates and draws the
>> concave hull of an image? I could only find plugins for the convex
>> hull.
>> If there is no such plugin, can anyone point me to the algorithm to
>> use
>> then I will implement it myself.
>
> That is because there is no single concave hull.
> A few proposed algorithms make assumptions on what should be on and
> inside the
> hull and produce something that satisfies the assumptions. So you
> end up with
> a parametric procedure.
>
http://ubicomp.algoritmi.uminho.pt/local/concavehull.html>
> Cheers,
>
> G.