G13 Image Segmentation: the Mumford–Shah Functional

The reference for this lecture is David Mumford and Jayant Shah, Optimal approximations by piecewise smooth functions and associated variational problems (Commun. Pure Applied Math. 1989).

Images

• A three-dimensional scene is observed by an eye or a camera: at a point , light of intensity comes from the direction .
• A lens at focuses the light on a retina (a surface). The intensity of the light signal received by at the point with coordinates is obtained from through some transformation that depends on the functioning of the optical system.
• The resulting function is “an image”.

The slide’s illustration (from Mumford–Shah) shows two objects, a pyramid with a striped face and a small box , whose light passes through a lens at and forms an inverted image on a screen.

There will be discontinuities in the function along boundaries: an object in front of another, objects with a common boundary, discontinuities in illumination, in the object albedo, and so on. Additional complications:

• textured objects, fragmented objects (for example a canopy of leaves);
• shadows, penumbra;
• surface markings;
• partially transparent objects;
• noisy measurements of .

The segmentation problem

The goal is to compute a decomposition of the domain of such that

1. the function is smooth within each domain ;
2. the function varies discontinuously (and/or very rapidly) across most of the boundary between different .

Equivalently, this is the problem of computing optimal approximations of a function by piecewise smooth functions.

Mathematical approach

What constitutes an optimal segmentation? We look for a functional measuring the degree of match between a function and a segmentation, to be optimized. Let the be connected open subsets of a given planar domain , each with piecewise smooth boundary , and set We discuss three different action functionals whose minimization gives an optimal image segmentation: a functional that depends on two parameters and , and two limiting cases and , each depending on a parameter.

The Mumford–Shah functional

• The first term measures how good is as an approximation of .
• The second term asks that not vary too much within each .
• The third term asks that the boundary achieving the decomposition be as short as possible.

Heuristic interpretation: a solution of the minimization of is a “cartoon” version of the image , in which contours are drawn sharply and the scene is simplified.

The functional

Restrict to piecewise constant functions, . Then As a function of the , this is minimized by the averages where is the area of .

Relation to the Ising model

The relation is the one between continuous and discrete segmentation:

• Suppose is locally constant with only the values .
• Assume and are “discretized”, that is, defined on a lattice.
• Let be a path made of segments of horizontal and vertical lines between pairs of adjacent lattice sites where changes sign.
• Then the functional , seen as a function of , becomes the Ising model energy where the first sum is over lattice sites and the second over pairs of neighboring sites. (A neighboring pair separated by contributes and every other pair contributes , so the second sum is times the length of in lattice units; the factor only rescales .)

The functional

Minimizing means finding so that

• the length of is as short as possible;
• the variation of in the direction normal to is as large as possible.

Relation of to

So one can think of as a limit of .

The variational equation for : summary

• For fixed , is a positive definite quadratic functional in , with a unique minimum, the solution of the elliptic boundary value problem on each
• With the solution of this elliptic problem, becomes a function of , , to be minimized over .
• Consider an infinitesimal variation of by a normal vector field , vanishing in a neighbourhood of the singular points of .

(On the normal derivative of vanishes, so there; compare the energy density below.) Then is minimized by a that satisfies the variational equation

Complications due to singular points of

The minimizing function is bounded pointwise, but its gradient need not be bounded near the singular points of . If is made of -arcs joined at endpoints, one can use the theory of elliptic boundary value problems in domains with corners to handle this problem.

A further complication: a minimizer may have worse singularities than meetings of arcs; cusp singularities at the end of arcs may also occur.

A more detailed discussion of the variational problem for

Hölder spaces

Start by assuming that is a union of curves joined at endpoints, and that on ; initially assume also that the first derivatives are continuous up to the boundary points (this will be weakened later).

Variation of for fixed

Fix and consider the variational problem for , with variation : The last step uses integration by parts and Green’s theorem, with the whole boundary of , given by and the two sides of each arc of .

Imposing the vanishing of the variation for all test functions gives the variational equation

The operator is positive-definite and self-adjoint. It has a Green function that is outside the diagonal , with singularity

The unique solution on each is constructed by convolution with the Green function:

Variation of

Now vary with respect to .

• Move near a simple point (not a point where several arcs meet). The point lies on one arc .
• The regularity of ensures that it can be written locally as the graph of a function, either or (implicit function theorem). One can then deform the path by deforming the function, with the variation outside a small neighborhood of the point, so that the new curve does not meet the other arcs outside the endpoints.

Varying forces to vary too, because is on and discontinuous across . Let and ; extend both to all of by extensions , and set Then compute explicitly the variation , where : This gives the variational equation for the path variation :

Since , its curvature is well defined almost everywhere: Integrating by parts in the last term of the variational equation, so along each

In these terms the equation reads which, for fixed , is a second order ODE for .

Special points of

At special points of the analysis of the variational problem is more complicated: the stationarity condition for the functional imposes restrictions at these points. The cases are

1. points where meets ;
2. corners, where two arcs meet;
3. vertices, where three or more arcs meet;
4. crack-tips, where an arc ends without meeting another arc.

Corners

The problem with corners is that one can have a function with in an open region and on the boundary, with a singularity at a corner point.

Minimizers have no kinks, and other local results

One uses this to show that Mumford–Shah minimizers cannot have kinks (corners between two arcs with angle ). Divide a neighborhood of the corner into the sectors with angle larger and smaller than , and take a smooth cutoff function on a ball near the corner.

Cut the corner at a small distance, shrinking and enlarging :

• The new on the smaller is defined by restriction; the new on the larger is extended using the cutoff function, as .
• Measuring the corresponding change in , one finds that if the functional decreases when the corner is cut as above, so the original kinked path cannot be a minimizer.
• A similar argument shows that a minimizer meets orthogonally.
• A similar argument also shows that triple points must have angles : otherwise one can cut a sector and lower the value of .

• If has points where four or more arcs meet, it is not a minimizer: one can separate such a point into triple points and lower the value of .

• One can also eliminate cusp corners and lower the value of .

Summary of further results

• For minimizing with fixed, one estimates its proximity to the locally constant average of on each .
• The relevant quantity is the isoperimetric constant, which measures the smallest necks in each component .

For the dumbbell in the figure, the curve across the neck has length about , so is at most about . The slides also show a domain with isoperimetric constant : a chain of bulges joined by necks, shrinking towards one end.

Existence of -minimizers

Method of proof: geometric measure theory. The main idea is first to show the existence of a “weak solution” with a “very singular” , and then to show that the weak solution must in fact be sufficiently regular, as required by the original problem. Weak solutions are given by Caccioppoli sets (measurable sets whose characteristic function has bounded variation). The topological boundary of such a set may have infinite 1-dimensional Hausdorff measure, but a “reduced boundary” is 1-rectifiable.

What is geometric measure theory?

• It is the use of measure theory methods to study geometric objects (curves, surfaces) that are highly non-smooth.
• It was historically developed to study the Plateau problem: the geometry of soap bubble films, that is, area-minimizing surfaces with given boundary curves. (The slides show photographs of clusters of soap bubbles.)
• Introductions to geometric measure theory: Frank Morgan, Geometric measure theory: A beginner’s guide; Frederick J. Almgren, Jr., Plateau’s Problem: An Invitation to Varifold Geometry; Herbert Federer, Colloquium lectures on geometric measure theory (see the references).

The large case

When , the effect of on the energy is localized in a narrow strip around . First one uses Green’s theorem to reduce to an integral along only, in terms of the solutions and of

• The first variation of converges, for large , to the first variation of .
• One computes explicitly the vanishing of the first variation of , which gives a second order differential equation for .

Let be the matrix of second derivatives of , and , the unit tangent and normal vectors to . The variational equation for is This equation can be interpreted as the geodesic equation in a Lorentzian metric (an indefinite metric, of signature ): space-like solutions locally minimize and time-like solutions locally maximize it; general solutions flip between these two types through cusp singularities at the transitions.

Further reading

There are many more recent results on Mumford–Shah minimizers and segmentation: this is a rich current area of research, with a large number of papers on the topic. Suggested references are the papers of Younes–Michor–Shah–Mumford, Mumford–Kosslyn–Hillger–Herrnstein, and the survey of Leah Bar et al. listed below.

References

• David Mumford, Jayant Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Commun. Pure Applied Math. Vol. XLII (1989) 577–685.
• Frank Morgan, Geometric measure theory: A beginner’s guide (Fourth ed.), Academic Press, 2009.
• Frederick J. Almgren, Jr., Plateau’s Problem: An Invitation to Varifold Geometry, Revised Edition, American Mathematical Society, 2001.
• Herbert Federer, Colloquium lectures on geometric measure theory, Bull. Amer. Math. Soc. 84 (1978), 291–338.
• Laurent Younes, Peter W. Michor, Jayant Shah, David Mumford, A metric on shape space with explicit geodesics, Rend. Lincei Mat. Appl. 19 (2008) 25–57.
• D. Mumford, S. M. Kosslyn, L. A. Hillger, R. J. Herrnstein, Discriminating figure from ground: the role of edge detection and region growing, Proc. Nat. Acad. Sci. U.S.A. 84 (1987), no. 20, 7354–7358.
• Leah Bar et al., Mumford and Shah model and its applications to image segmentation and image restoration, in “Handbook of Mathematical Methods in Imaging”, Springer 2011, 1095–1157.