Algorithms for the Medial Axis
CG Week Workshop, Brisbane, July 7, 2017

Organizers: Erin Chambers, Tao Ju, and David Letscher

Description: Skeletons are a fundamental construct in many areas which seek to model shapes. In particular, the medial axis has seen broad success as a shape descriptor in a variety of settings including graphics, image detection, and biomedical imaging, including many new results and growing interest in tools. There has also historically been considerable work on algo- rithms and theoretical results for the medial axis and related skeletons in the computational geometry community. Our aim with this workshop is to bring together a group of people, both in the computational geometry community and in related areas such as graphics and computer vision, to present and discuss current issues and trends in this area.

The workshop is part of CG Week 2017. It takes place on Friday, July 7, from 14:30 - 17:30 in the afternoon (with a break for coffee in the middle). See the CG Week 2017 main page for information about the venue and about other CG Week events.

Tentative Program

Session I: 14:30–16:00

14:30–15:15
Tamal Dey, Computing medial axis and curve skeleton with Voronoi diagrams

Voronoi diagrams of a set of points in 3D can be thought of as the singularity of the distance function defined with respect to the points. When a sufficiently dense set of points is sampled from a smoothly embedded surface in 3D, this distance function approximates the distance with respect to the surface that is sampled. Consequently, a subcomplex of the Voronoi diagram approximates the medial axis of the surface which is the singularity of this surface distance function. The curve skeleton, a cousin of the medial axis, is intended to capture the `middle' of the shape with only one (curves) and zero (vertices) dimensional elements. We gave a definition of the curve skeleton as the singularity of a distance function called medial geodesic function (MGF) defined on the medial axis. We also showed how one can compute an approximation of this singularity using Voronoi diagrams. In this talk we go over these developments that we proposed more than a decade back.

15:15–16:00
Mathijs Wintraecken, Manifolds with positive reach: metric distortion, tangent space variation and geodesic convexity

We discuss three results, for two different classes of embedded manifolds: The first class of manifolds consists of closed $C^2$ manifolds $\M$ embedded in $\mathbb{R}^d$. For these we first provide a tight bound on difference between the Euclidean distance and geodesic distance between two points $p$ and $q$ on $\M$. Secondly, we give tight bounds on the angles between the tangent spaces of two points on the $C^2$ manifold $\M$. In both cases we assume that $p$ and $q$ are not too far from each other, where far can be quantified in terms of the reach of the manifold. Thirdly we give a proof that the intersection of a ball in the ambient space $\mathbb{R}^n$ of radius smaller than the reach with the manifold is geodesically convex, in particular it is a topological ball. Our first exposition of the first two results is based on differential geometry and is a consequence of combining (and sometimes simplifying) the work of Niyogi, Smale, and Weinberger, and the two dimensional analysis of Attali, Edelsbrunner, and Mileyko with the work of Federer. The result on convexity is new, and generalizes the pseudo-ball property of Boissonnat and Oudot. We then give elementary proofs of slightly weaker versions of the previous results, with the exception of convexity (we can prove a weaker result, namely that the intersection is a topological ball). The proofs are elementary in the sense that no differential geometry is required, although some topology is used. Our elementary approach goes through with some modification for $C^{1,1}$ manifolds.

Session II: 16:30–18:00

16:30–17:15
David Letcher, On the Stability of the Medial Axis of a Union of Balls in the Plane

We examine the stability of a the medial axis for a union of disks in the plane as the centers and radii of the disks vary continuously. If extra restrictions are place on the disks then the medial axis is stable. Without these conditions we show that if the medial axis is pruned by one of four significance measures (circumradius, erosion thickness, object angle or potential residue) then it is stable under motions of the disks. We will briefly discuss conjectures about the stability of the pruned medial axis in a 3-dimensional union of balls.

17:15–18:00
Tao Ju, Erosion Thickness on the Medial Axes of 3D Shapes

In this talk, I will present our recent work on creating robust and descriptive skeleton descriptors of 3D shapes. Our work extends the Erosion Thickness (ET), a classical significance measure on the medial axes of 2D shapes, to 3D. On the theoretical side, we introduce a consistent definition of ET in both 2D and 3D, from which we are able to formalize lower-dimensional medial forms (e.g., medial points of 2D shapes, medial curves and medial points of 3D shapes). On the algorithmic side, we present robust and efficient algorithms to compute these functions and structures on triangulated medial axis of 3D shapes.