Concave Hull

[Mathias Zech]

Hi,

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.

Thanks a lot!
Mathias Zech

[Gabriel Landini]

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.

[Kenneth Sloan-2]

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.

[_-3]

Hi list,
are Alpha-(Gamma-)Shapes already  implemented in imagej or exists a java
class ?
Thank you


Kenneth Sloan schrieb:

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