The skeleton inside a shape

The Voronoi diagram divides the plane among a finite set of sites, each point going to whichever site is nearest. Its edges are the places where two sites tie. Every earlier construction of this kind has started from finitely many points — sites, weighted sites, centroids — and the last of them closed a loop by turning the diagram into a way of finding a tree.

The question that was left open is what happens when the sites are not a finite set at all but a curve: the whole outline of a shape. Every point of the outline is a site. Inside the shape, most points have a single nearest point on the outline; the ones with two or more nearest points form the edges of this continuous Voronoi diagram. That set has a name, the medial axis, and it turns out to be one of the most useful and most treacherous objects in the geometry of shape.

The Voronoi diagram of a boundary #

The opening figure approaches the medial axis the way a computer does, from finitely many sites. Sample the outline at fifty points and draw their ordinary Voronoi diagram. Two kinds of edge appear inside the shape. Between two samples next to each other on the outline, the bisector is a short edge running straight in from the boundary, perpendicular to it — a hair, one for each gap between samples. Between two samples far apart on the outline, on opposite walls of the shape, the bisector runs along the middle of the shape.

The hairs are an artefact of sampling: they shorten and multiply as the samples get denser, and in the limit they vanish into the outline. The other edges converge to something. Their corners — the points equidistant from three samples, dotted in the figure — crowd along a thin branching curve, and as the sampling gets finer they crowd closer to it.

That limit is the medial axis. It can be defined directly: the set of points inside the shape with at least two nearest points on the boundary. The finite Voronoi diagram approximates it for the same reason a fine polygon approximates a curve, and in two dimensions the approximation converges. In three dimensions it does not, quite, and the repair — keeping only the Voronoi vertices farthest from each sample, called poles — is how Nina Amenta and Marshall Bern turned the medial axis into a method for reconstructing surfaces from scanned points in 1998.

A rectangle, and the discs that define it #

For a rectangle the axis can be worked out by hand, and the answer shows its character.

A point in the middle band of the rectangle is equally far from the two long sides, so it has two nearest boundary points, one directly above and one directly below: the middle segment. A point near a corner is nearest to the two sides meeting there when it lies on the line bisecting the corner’s angle — the diagonal branches. The segment and the branches meet where a point is equidistant from three sides, and the five pieces together form the skeleton.

The circles in the figure are the key to what the axis is for. Centre a disc at a point of the axis and make it as large as possible while staying inside the shape. Because the point has two nearest boundary points, the disc touches the boundary in two places, and it cannot be moved or enlarged without leaving the shape. These are the maximal discs — discs inside the shape not contained in any larger disc inside the shape — and the medial axis is exactly the set of their centres.

That gives the second definition, and the one Harry Blum had in mind when he introduced the axis in 1967 as a way of describing biological shapes. Record each point of the axis together with the radius of its maximal disc. From that record alone the shape can be rebuilt: it is the union of all the discs. The medial axis transform — skeleton plus radius — is a complete description of the shape, and a very economical one: a two-dimensional region reduced to a one-dimensional tree with a number on it.

Corners, reflex corners, and curves #

Different kinds of boundary produce different kinds of axis, and the L-shape shows all three at once.

A convex corner — one pointing outward — always sends a branch of the axis straight into it, along the bisector of its angle, because points near the corner are nearest to the two sides that meet there. A reflex corner — pointing inward — never does. Points near it are nearest to the corner point itself, and a point equidistant from a line and from a single point lies on a parabola; so near a reflex corner the axis is curved, even though every piece of the boundary is straight. The medial axis of a polygon is made of straight segments and parabolic arcs, and the arcs come only from reflex corners.

A smooth boundary behaves differently again. The axis of an oval is a single straight segment between two points inside it, and it stops short of the boundary: it ends at the centres of curvature of the two ends, where the circle that best fits the boundary is itself a maximal disc, touching at one point rather than two. A smooth convex shape has a skeleton that never reaches its own edge.

Where the branches meet: a circle touching three things #

The axis of a polygon has a small number of special points — the places where three branches meet — and they have a classical description. At a branch point the maximal disc touches the boundary in three places, not two: it is a circle tangent to three sides of the shape, or to two sides and a reflex corner, or to one side and two corners. Finding such a circle is the problem of Apollonius, which asks for the circles touching three given circles, lines or points, and which has up to eight solutions in general. Inside a shape only one of them is the maximal disc, and the branch point is its centre.

So the medial axis of a polygon is determined by finitely many Apollonius problems — one for each branch point — joined by the curves along which a disc touches two things at once: straight segments when the two things are sides, parabolic arcs when one is a side and one a corner, and straight segments again, on the perpendicular bisector, when both are corners. The algorithms that compute the axis exactly are careful ways of deciding which triples of boundary pieces produce a branch point and in what order the branches meet. For a polygon with $n$ vertices there are only a linear number of them, which is why the exact axis can be computed in time proportional to $n$.

The same structure appears in the ordinary Voronoi diagram, where a vertex is the centre of a circle through three sites — the empty circle that makes a triangle Delaunay. The medial axis is that picture with the sites smeared out into curves, and the Delaunay triangles become the maximal discs that touch three pieces of the boundary.

The grassfire #

There is a third way to see the axis, and it explains its name in image processing, where it is called the skeleton of a shape.

Light a fire all the way round the edge of a field of dry grass at the same moment, and let it burn inward at a constant speed. At each moment the burning front is the set of points at one distance from the edge — one of the bands in the figure. Where two parts of the front, which started on different parts of the edge, arrive at the same place at the same moment, they meet and go out. The set of places where fronts meet is exactly the set of points with two nearest boundary points, and the moment they meet is the radius of the maximal disc there.

This picture is Blum’s, and it is why the axis is computed, in practice, from the distance function of a shape — the distance from each point to the nearest edge. The distance function is smooth almost everywhere, and the axis is where it has a crease: a ridge, like the ridge of a roof. The bands in the figure show the creases as the places where a band bends sharply rather than smoothly, and a closely related construction, the straight skeleton, literally builds a roof over a polygon by raising every edge at the same slope.

The tooth that grows a branch #

The medial axis has one property that every application has to fight. It is unstable: a tiny change to the shape can produce a large change to the axis.

The reason is visible in the maximal discs. The tooth adds a convex corner to the outline — its tip — and every convex corner sends a branch of the axis into itself, along the bisector of its angle, however small the corner is. That branch runs from the tip of the tooth up into the rectangle until it meets the axis coming from the rest of the outline: as far as there are points whose nearest boundary points include one on each side of the tooth. The tooth is tiny; the region of points that can see both of its sides at the same distance is not.

This is why skeletons of real images — scanned letters, cells under a microscope, the outline of a hand — are full of spurious branches, one for every tooth in the outline, and why a large part of the practical literature is about pruning: deciding which branches are features of the shape and which are noise. Measures of a branch’s importance by the size of the discs along it, or by how much of the shape would be lost without it, give stable approximations such as the λ-medial axis of Frédéric Chazal and André Lieutier, at the cost of no longer being the exact axis. The exact axis is a precise definition with an imprecise dependence on its input.

Discs instead of points #

The medial axis transform describes a shape as a union of discs, and that connects it to another object met earlier. When the sites are not the same size, each site is a disc with a radius, and the plane is divided by the power diagram, in which a point belongs to the disc whose tangent length from the point is shortest. Take the maximal discs of a shape as weighted sites: their power diagram, restricted to the union of the discs, divides the shape into pieces, one per disc, and the boundaries between pieces run along the lines where neighbouring maximal discs cross.

This is how the transform is used in practice, with finitely many discs rather than a continuum. Approximate the shape by a union of a few hundred discs centred on its axis — a representation used in simulation and collision detection, because testing whether two unions of discs overlap is quick — and the power diagram organises them. The union of discs is a slightly rounded version of the shape, and the fewer discs are kept, the rounder it becomes; the discs worth keeping are those with the largest radii, which is exactly the pruning rule that tames the axis’s instability. The two problems, choosing which branches of the skeleton are real and choosing which discs to keep, turn out to be the same problem.

It is also a small instance of the centroidal idea met earlier, in which sites move until each sits at the centre of its own cell: a shape covered by discs whose centres lie on its axis is, roughly, a covering in which every disc sits in the middle of the part of the shape it is responsible for.

What a skeleton describes #

For shapes without noise, the skeleton is a good description, and it is why Blum proposed it.

A skeleton’s topology — how many branches, where they join — is a summary of a shape’s parts: a trunk and an appendage, a star with five arms, a ring. The extreme case is a disc, whose axis is a single point, its centre, carrying one radius — the shape that encloses the most area for its boundary is also the one with the simplest possible skeleton, and every departure from roundness shows up as axis. Two shapes with the same skeleton topology and similar radius functions look alike, and that makes the axis a tool for recognising shapes and for comparing them, used for classifying the forms of leaves and bones and for animating characters by bending their skeletons. The same object turns up in robot motion planning, where the axis of the free space is the path that keeps a robot as far as possible from every obstacle, and in the design of the paths that machine tools follow when they clear a pocket of material.

And the tree structure connects back to the earlier essays. The minimum spanning tree inside the Delaunay triangulation was a tree extracted from the Voronoi diagram of points; the medial axis is a tree extracted from the Voronoi diagram of a boundary. For a shape without holes the axis is always a tree — it has no loops, because a loop in the axis would enclose a region of the shape with no boundary inside it.

What the pictures cannot show #

The figures compute the axis on a grid of points spaced a small fraction of the shape’s size apart, and mark a grid point as on the axis when two of its nearest boundary points lie far apart along the outline. That is an approximation with a resolution: branches thinner than the grid are invisible, the ends of the oval’s axis are blurred, and the curve round the L-shape’s reflex corner comes out as a staircase. The exact axis of a polygon is a finite collection of segments and parabolic arcs, computable exactly and quickly — in time proportional to the number of vertices, for a simple polygon — but the figures do not compute it that way.

The pictures also show only planar shapes. In three dimensions the medial axis of a solid is not a curve but a collection of surfaces, meeting along curves, and it is far harder to compute and to stabilise; that is where the sampled-Voronoi method needs its repair. And the maximal discs drawn are a handful chosen by size, not the continuum whose union is the shape.

Still open: stable skeletons with guarantees #

The exact medial axis is completely understood for polygons and for smooth shapes, and its instability is completely understood too. What remains open is the compromise between them: a skeleton that is stable under small changes to the shape, faithful to its genuine features, and backed by a guarantee about how far it is from the true axis.

Several constructions come close in one respect or another — the λ-medial axis keeps its topology under small perturbations for suitable λ, scale-space methods smooth the boundary before taking the axis — but each depends on a parameter whose right value is a judgement about what counts as noise, and none is known to be optimal. For three-dimensional shapes even the question of what the right stable approximation is remains unsettled, and computing a medial axis of a solid from a scan with provable accuracy is an active problem in computational geometry. The difficulty is not computing power but definition: the true axis of a scanned solid is dominated by branches from the noise, and any method that ignores them is choosing, somewhere, a scale below which features are declared not to exist.