Variational Methods in Image Segmentation

This book contains both a synthesis and mathematical analysis of a wide set of algorithms and theories whose aim is the automatic segmen­ tation of digital images as well as the understanding of visual perception. A common formalism for these theories and algorithms is obtained in a variational form. Thank to this formalization, mathematical questions about the soundness of algorithms can be raised and answered. Perception theory has to deal with the complex interaction between regions and "edges" (or boundaries) in an image: in the variational seg­ mentation energies, "edge" terms compete with "region" terms in a way which is supposed to impose regularity on both regions and boundaries. This fact was an experimental guess in perception phenomenology and computer vision until it was proposed as a mathematical conjecture by Mumford and Shah. The third part of the book presents a unified presentation of the evi­ dences in favour of the conjecture. It is proved that the competition of one-dimensional and two-dimensional energy terms in a variational for­ mulation cannot create fractal-like behaviour for the edges. The proof of regularity for the edges of a segmentation constantly involves con­ cepts from geometric measure theory, which proves to be central in im­ age processing theory. The second part of the book provides a fast and self-contained presentation of the classical theory of rectifiable sets (the "edges") and unrectifiable sets ("fractals").

Contenu

I. Modelisation.- 1. Edge detection and segmentation.- 1. Is there a general theory for segmentation?.- 2. Principles of multiscale analysis.- 2. Linear and nonlinear multiscale filtering.- 1. The linear model (Hildreth, Marr, Witkin, Koenderink,...).- 2. The Perona and Malik theory.- 3. Anisotropic diffusion and "mean curvature motion".- 4. Image restoration by mean curvature motion.- 3. Region and edge growing methods.- 1. Formalization of region growing methods. (Brice and Fennema, Pavlidis, ...).- 2. Edge growing methods.- 3. Hybrid methods.- 4. How to translate a heuristic algorithm into a variational theory.- 4. Variational theories of segmentation.- 1. The Nitzberg and Mumford 2.1-D sketch.- 2. The "structural saliency" of Sha'ashua and Ullman.- 3. The "minimum description length" method of Yvon Leclerc.- 4. Algorithms for minimizing the general Mumford and Shah energy.- 5. Affine invariant segmentation.- 5. The piecewise constant Mumford-Shah model: mathematical analysis.- 1. Main theorem.- 2. Definition and elementary properties of segmentations.- 3. Properties of segmentations obtained by merging. Proof of the main theorem.- 4. A pyramidal algorithm computing 2-normal segmentations.- 5. Examples.- II. Elements Of Geometric Measure Theory.- 6. Hausdorff measure.- 1. Hausdorff outer measure.- 2. Outer measures in topological spaces.- 3. Connected sets of finite 1-dimensional Hausdorff measure.- 4. A suggesting example of Hausdorff measurable set with finite length.- 7. Covering lemmas in a metric space.- 1. Elementary properties of generic coverings.- 2. Vitali coverings.- 3. Hausdorff and Lebesgue measure.- 8. Density properties.- 1. Upper and lower density.- 2. Regular sets.- 9. Tangency properties of regular subsets of ?N.- 1. Reflection lemmas.- 2. Approximate tangent space.- 3. Existence of a tangent space.- 10. Semicontinuity properties of Hausdorff measure.- 1. Hausdorff distance.- 2. Counterexamples to the semicontinuity of the Hausdorff measure for the Hausdorff metric.- 3. Upper semicontinuity in [0,1].- 4. Lower semicontinuity of the Hausdorff measure on uniformly concentrated sets.- 5. Sequences of compact connected 1-sets.- 11. Rectiflable sets.- 1. Rectifiable surfaces and rectifiable sets.- 2. Regularity of rectifiable sets.- 3. Rectifiable curves.- 12. Properties of regular and rectifiable sets.- 1. Geometric lemmas.- 2. Equivalence of the notions of regularity and rectifiability.- 3. Projection properties of irregular sets.- III. Existence and Structural Properties of the Minimal Segmentations ror the Mumford-Shah Model.- 13. Properties of the approximating image&in the Mumford-Shah model.- 1. Notation and preliminary lemmas.- 2. Green Formulas.- 3. Interior regularity estimates.- 14. Small oscillation coverings&and the excision method.- 1. The excision method.- 2. Small oscillation coverings.- 3. The excision lemmas.- 4. The Interpolation Lemma.- 5. Energy jump estimates.- 6. Proof of the excision lemmas.- 15. Density properties and existence theory&for the Mumford-Shah minimizers.- 1. The Essentiality Property.- 2. The Uniform Density Property.- 3. The Concentration Property.- 4. The Projection Properties.- 5. Existence theory for the Mumford-Shah minimizers.- 6. Nonuniqueness of the Mumford-Shah minimizers.- 16. Further properties of the minimizers:&covering the edge set with a single curve.- 1. The David-Semmes Concentrated Rectifiability Property.- 2. Dual curve lemmas.- 3. Existence of a rectifiable curve containing the edge set.- 4. Existence of a regular curve containing the edge set.- Bibliographical notes.- References References of Part I.- I-A) Image segmentation and edge detection, surveys and monographs..- I-B) Articles proposing algorithms for edge detection and image segmentation..- I-C) Scale space theory..- I-D) Mathematical analysis related to scale space theory..- I-E) Monographs in Image Processing..- I-F) Articles on texture analysis and segmentation..- I-G) Wavelets, theory and relation to image processing and scale space..- I-H) Related topics in psychophysics, neurobiology and gestalt theory..- References of Part II 232.- II-A) References on geometric measure theory and rectifiability.- II-B) Monographs on mathematics and geometric measure theory..- References of Part III:Mathematical analysis of the Mumford-Shah model.- Index of segmentation algorithms.- Notation.