> 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.
>