A skeleton that ignores small teeth

The skeleton inside a shape described the medial axis: the points inside a shape that have two or more nearest points on its outline. It is the Voronoi diagram of the outline itself, it is where fires lit all round the edge would meet, and with the distance to the edge recorded at each point it rebuilds the shape exactly. It is also violently unstable. A tooth three hundredths of the height of a rectangle, sticking out of one side, grew a whole new branch running from the tooth deep into the interior, several times longer than the tooth was tall.

That instability is not a curiosity. Any shape measured from the world — a scanned outline, a region segmented from an image, a coastline — has an edge that wobbles at the scale of the measurement, and every wobble grows a branch. The skeleton of a scanned shape is mostly noise. The previous essay ended by naming the compromise that has been proposed: the λ-medial axis of Frédéric Chazal and André Lieutier, which keeps only part of the axis, chosen by one number. This essay computes it, measures how stable it is, and measures what it costs.

A branch for every wobble #

The rectangle in the figure has sides that wobble by up to two per cent of its height. The axis of a true rectangle is a segment along its middle with four arms running into the corners. The axis of the wobbly one has those, and also a branch reaching towards nearly every wobble: each little convex bump on the outline is a corner, and every corner sends a branch of the axis towards itself, as the previous essay showed for a single tooth. The branches are not short. A branch to a bump runs from the bump inwards until it meets the part of the axis governed by the opposite side, so on a rectangle of height 1 many of them are nearly half a unit long.

The axis here is computed in the standard way for a sampled outline. Sample the boundary densely, take the Voronoi diagram of the samples, and keep the Voronoi vertices that fall inside the shape: each is the centre of a circle passing through three samples with no sample inside it, so it is equidistant from three boundary points and closer to them than to any other — a circle touching three things, with the three things shrunk to points, and a point with several nearest points on the outline, which is what an axis point is. Equivalently, these are the circumcentres of the Delaunay triangles of the boundary samples that lie inside the shape — the same triangulation that contains the shortest network joining the samples, put here to a different use. As the samples become denser, the vertices converge to the true medial axis of the sampled outline, wobbles and all.

Sampling sets a floor of its own. On the clean rectangle sampled every hundredth, the axis points with the smallest enclosing radii are the tips of the four arms, within a few hundredths of the corners, where the two sides that meet are only a sampling step or two apart: their radii run down to about six thousandths. Along a straight side the samples add no branches, because the Delaunay triangles of samples in a row reach across to the far side of the shape rather than between neighbours. But no sampling can resolve the axis closer to a corner than a step, and a wobble smaller than the step cannot be seen at all. A sampled outline determines its skeleton only down to the scale at which it was sampled, so a λ comfortably larger than the sampling step is not an afterthought to the computation; it is the honest statement of what the samples can say.

What λ measures #

Every point of the axis has a set of nearest points on the outline, at least two of them. The difference between a point on the rectangle’s trunk and a point on a branch to a wobble lies in where those nearest points are.

For a point on the trunk the nearest points are on opposite sides of the rectangle, nearly a whole height apart, and the smallest circle enclosing them has radius 0.491. For a point on a corner arm they are on the two sides that meet at the corner, and the circle has radius 0.169, shrinking towards nought as the arm approaches the corner. For a point on a branch to a wobble they are two points of the same wobble, a whisker apart, and the circle has radius 0.036. The radius of that enclosing circle — at most the distance to the boundary, and much smaller when the nearest points are bunched together — measures how much of the shape a point of the axis is really responding to.

The λ-medial axis keeps the points of the axis whose enclosing radius is at least λ. Chazal and Lieutier defined it in 2005, for any closed set and any λ. It is a subset of the medial axis — it adds nothing — and it removes exactly the parts of the axis that are responding to small features: branches running to bumps narrower than about $2\lambda$, and the tips of arms running into corners sharper than λ allows. The smallest enclosing circle is determined by two or three of the nearest points, by the same reasoning that makes any point in the hull of many points lie in the hull of three, so for a Voronoi vertex it is the circle through its triangle’s corners when the triangle is acute, and the circle on its longest side when it is obtuse.

Stable against small wobbles, and only those #

The point of the λ-medial axis is stability: a small change in the outline should make a small change in the skeleton. The way to measure that is to compare the axis of the wobbly rectangle with the axis of the clean rectangle using the Hausdorff distance — the furthest any point of either set is from the other set.

The whole medial axis fails at once. At a wobble of ±0.0025, a quarter of a per cent of the rectangle’s height, it is already 0.42 from the clean axis, because a branch to the smallest bump reaches far into the shape; by ±0.04 it is 0.52 away. There is no wobble small enough to leave it nearly unchanged.

Each λ-medial axis behaves differently. At λ = 0.2 the distance grows slowly and steadily with the wobble, reaching only 0.10 at ±0.04. At λ = 0.1 it stays under 0.1 while the wobble is ±0.01 or less, then jumps to 0.26 at ±0.02. At λ = 0.05 it jumps already at ±0.01. The rule the figure shows is that a λ-medial axis barely moves while the wobble stays below about a tenth of λ, and jumps once the wobble passes about a fifth of it. Below the threshold the bumps are too narrow to produce nearest points spread as widely as λ; above it, the larger wobbles make bumps wide enough that their branches survive the cut.

That is the content of Chazal and Lieutier’s theorem, in a form a figure can show. They proved that, for values of λ that are not themselves critical for the shape, the λ-medial axis depends continuously on the shape: as the Hausdorff distance between two outlines goes to nought, so does the distance between their λ-medial axes, with an explicit bound. The bound needs the perturbation to be small compared with λ, and the figure shows why it must: stability is a statement about wobbles smaller than the scale λ names, and about nothing else.

The trade λ makes #

A larger λ tolerates larger wobbles. It also removes more of the true skeleton.

At λ = 0 nothing true is lost, but branches reach 0.50 from the true axis. As λ rises the spurious branches disappear — by λ = 0.15 the furthest point kept is within 0.016 of the true axis — but the corner arms shorten, because near a corner the two nearest sides are close together and the enclosing radius is small. By λ = 0.25 most of each arm is gone; by 0.49 only the trunk is left, and the furthest point of the true axis, a corner, is 0.71 from anything kept. The worse of the two errors is smallest at about λ = 0.1, where both are around a quarter of the rectangle’s height.

So there is no λ that gives the true skeleton. The λ-medial axis is a stable approximation to the skeleton of a shape at scale λ: features smaller than λ, real or not, are removed, and those larger are kept. The corners of the rectangle are real features, but a corner looks small near its tip, and the λ-medial axis treats the tip as it treats a wobble.

The size below which a bump is not a feature #

The same trade can be measured on a single feature, cleanly.

The λ needed to remove the tooth’s branch is exactly half the tooth’s height, at every size: 0.005 for a tooth of height 0.01, 0.06 for a tooth of 0.12. The whole medial axis grows a branch to a tooth of any size, and the branch’s length does not shrink with the tooth; the λ-medial axis removes it once λ passes half its height and keeps every larger tooth’s branch. Choosing λ is choosing the size below which a bump is not a feature, and the relation between the two is as simple as it could be.

The half has a short explanation, and it also explains why the whole axis’s branch is so long. The tooth sticks out of the rectangle, so its tip is a convex corner and the two corners where it meets the side are concave ones. The branch starts at the tip and runs straight up the middle of the tooth. Inside the tooth, a point’s nearest boundary points are on the tooth’s two sloping sides, close together near the tip and further apart higher up, so the enclosing radius grows from nought. Once the branch passes the base of the tooth and enters the rectangle, the nearest boundary points are the two concave corners themselves, the tooth’s width apart, and the enclosing circle is the one on that width: its radius is half the width, which for this tooth is half the height, and it stays exactly that all the way up the branch. Nothing about those two corners changes as the point rises; the point is simply equidistant from them, and remains so until the far side of the rectangle comes closer, near the middle.

So the branch is long because the two concave corners keep producing points equidistant from them for as far as nothing else is nearer, and the λ that removes it is half the tooth’s width because that is the spread of the only two boundary points the branch is responding to. A tooth twice as wide needs twice the λ. The whole medial axis treats the tooth’s two corners as being as significant as the rectangle’s opposite sides; the λ-medial axis measures how far apart the things a point is responding to are, and so can tell a tooth from a rectangle.

That simplicity is what makes λ usable. A shape scanned with an accuracy of a millimetre has wobbles of about a millimetre, and a λ of several millimetres removes them; any genuine feature smaller than that is removed too, and the scan could not have distinguished it from a wobble anyway. The method states its assumption as a length, which is the right currency for it.

A skeleton that comes apart #

Removing small features from a skeleton sounds like simplifying it. It can also change what the skeleton says about the shape’s structure.

The medial axis of the two rooms is one connected piece: the diagonals of each room, joined through the middle of the corridor. In the corridor every point’s nearest boundary points are on its two walls, 0.16 apart, so its enclosing radius is 0.08, the corridor’s half-width. Once λ passes 0.08 the corridor’s axis is removed and the λ-medial axis is two separate pieces, one in each room. Past 0.35, the rooms’ own half-width, nothing is left at all.

A skeleton is often used precisely to read off a shape’s structure — how many parts it has, how they connect — and here the λ-medial axis reports one part or two depending on λ. Neither answer is wrong. At scales below the corridor’s width the shape is one connected space; at scales above it, it is two rooms with a slit between them. The λ-medial axis does not let the user avoid deciding which of those descriptions is wanted. Chazal and Lieutier proved that for λ small enough — below a quantity they call the weak feature size — the λ-medial axis has the same shape, up to continuous deformation, as the region itself; the corridor is a weak feature, and λ above its half-width is above that size.

The same compromise elsewhere #

The λ-medial axis is one instance of a pattern that appears whenever a topological description meets measured data. Counting targets when the sensors make mistakes met it in a different form: the Euler characteristic of a field of sensor readings counts every speck of noise as a piece or a hole, and the repair — smoothing, then counting each feature by how long it survives — works only once a size is chosen below which features are noise. There the size was a smoothing width; here it is λ. In both, the unrepaired method needs no assumption about size and is useless on real data, and the repaired one is robust and needs exactly one length to be specified.

The analogy can be made exact. The radius function on the medial axis is closely related to the distance from the boundary, and the λ-medial axis is defined by a threshold on a function, as the level sets of persistence are. Chazal, Cohen-Steiner and Lieutier developed this into a theory of how well a sampled shape’s topology and geometry can be recovered, in terms of the shape’s critical points at each scale, which underlies much of the later work on reconstructing shapes from point clouds.

The Voronoi construction underneath is the one the plane divided by whoever is nearest began with, applied to points that happen to lie along an outline. Its vertices know nothing about which samples are noise; the enclosing radius is the one extra number per vertex that lets the noise be told apart, and it is computed from the vertex’s own triangle.

Still open: choosing λ, and three dimensions #

The λ-medial axis is stable for each fixed λ that is not critical for the shape, but it changes abruptly as λ passes a critical value, as the corridor shows, and nothing in the definition says which λ to use. Methods that look at all values of λ at once — keeping, for each branch, the range of λ over which it survives, in the manner of persistence — have been proposed, and they turn the choice of λ into a choice of how long a branch must survive to count, which is a choice of the same kind. Whether some way of reading the whole family is canonical is not settled.

In three dimensions the medial axis of a solid is a collection of surfaces rather than curves, and the Voronoi vertices of samples on a solid’s surface do not converge to it: some lie far from the true axis however densely the surface is sampled, a phenomenon that does not happen in the plane. Approximations that are both stable and provably close to the true axis of a scanned solid exist only under assumptions on the sampling, and computing a medial axis of a solid from a real scan, with guarantees, remains an active problem.