Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1995 | Buch

Edge Detection and Segmentation Kapitel lesen Erstes Kapitel lesen

Variational Methods in Image Segmentation

with seven image processing experiments

verfasst von: Jean Michel Morel, Sergio Solimini

Verlag: Birkhäuser Boston

Buchreihe : Progress in Nonlinear Differential Equations and Their Applications

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

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").

Inhaltsverzeichnis

Frontmatter

Modelization

Frontmatter
Chapter 1. Edge Detection and Segmentation
Abstract
In this chapter, we shall give a short survey of the segmentation problem as it appears in the research in Computer Vision and introduce the main ideas which lead to the choice of a variational approach. The terms like edge, segmentation, region and boundary will not receive a single definition since several theories and algorithms for defining them will be compared. These terms will be therefore assumed, in the beginning of this chapter, in their heuristic meaning
Jean Michel Morel, Sergio Solimini
Chapter 2. Linear and Nonlinear Multiscale Filtering
Abstract
In this chapter, we analyse the main theories of image multiscale filtering (and subsequent multiscale edge detection). The main point of the doctrine is that “edge detection” is a kind of differentiation; now, the image must be filtered (and smoothed) before differentiation. Thus “edge detection” becomes multiscale, like the filtering, and any edge detection theory is directly deduced from a multiscale filtering theory. We show how variational formulations are naturally associated with the main multiscale filtering theories.
Jean Michel Morel, Sergio Solimini
Chapter 3. Region and Edge Growing
Abstract
The general idea of the region growing methods is to create a partition of the picture into homogeneous regions by any kind of process which starts with small regions and then grows them according to some homogeneity criterion. The general idea of edge growing methods is to create an initial set of (“fine scale”) edges (e.g., by one of the above-mentioned theories) and to connect the edges iteratively, according to some criterion based on proximity and orientation. Both methods are “dual” and can be made to interact in “hybrid growing methods”. In this chapter, we shall review and formalize the three above-mentioned kinds of growing methods and we shall, as in the last section, associate with them a variational formulation. This formulation is obtained by identifying for each method an energy for which the growing process appears as a steepest descent algorithm.
Jean Michel Morel, Sergio Solimini
Chapter 4. Variational Theories of Segmentation
Abstract
We have given in the preceding chapter a generic formula for the segmentation problem. This formula was deduced from the algorithmic methods proposed in Computer Vision. We shall now analyse several classical segmentation methods which have been directly defined by a variational formulation. This will give a final confirmation of the well-foundedness of the energy functionals which are discussed in this book.
Jean Michel Morel, Sergio Solimini
Chapter 5. The Piecewise Constant Mumford and Shah Model: Mathematical Analysis
Abstract
In this chapter, we start with the mathematical proofs and show that the minimizing of the “simplest” segmentation energy discussed in the first chapters, the Mumford and Shah piecewise constant model, yields properties sought by most segmentation devices. Indeed, the most primitive segmentation tool, the “merging”, applied to this variational model, is enough to ensure a small (compact) set of possible segmentations, with no small regions and no thin regions. Uniform a priori estimates for the size and number of the regions can be given for all segmentations obtained by exhaustive “merging”.
In Section 5.1, we state the main existence theorem. In Section 5.2, we give some notation and define the “2-normal segmentations” as a formalization of the segmentations obtained by exhaustive “merging”. We list some useful topological properties of these segmentations. In Section 5.3, we prove several compactness, existence and regularity results for 2-normal and optimal segmentations and obtain a proof of Theorem 5.1. Section 5.4 is devoted to the definition of an algorithm computing 2-normal segmentations and to some numerical experiments on real images.
Jean Michel Morel, Sergio Solimini

Elements of Geometric Measure Theory

Frontmatter
Chapter 6. Hausdorff Measure
Abstract
From now on, we abandon the heuristic style which was used in Part I. We shall give a rigorous definition of one of the terms used previously: the length. In this chapter, we define the Hausdorff outer measure of dimension a in a metric space E. We shall see that when E = ℝ N and a is an integer, this definition is a generalization of length (α = 1), area (α = 2), volume (α = 3). Those quantities can be easily defined for smooth curves, surfaces, etc. The main difficulty of a more general definition, suitable for objects like the “edges” in an image, is maintaining the basic properties which are expected from such a measure, particularly the additivity. It must be emphasized that, in the very general framework of outer measures, the additivity is not ensured. In the following, we shall define the main formal properties of outer measures and give a characterization of the sets on which an outer measure becomes additive (measurable sets) when it is defined on a topological space (Section 2). Then, we shall apply this theory to the Hausdorff outer measure. Sections 3 and 4 are devoted to two basic examples of sets with finite Hausdorff length: the path connected sets on the one side which will be a paradigm for “edge sets”. The second example, somehow orthogonal to the first, is the classical two-dimensional Cantor set. This set shows all characteristics of what we shall later call “fully irregular” or “fully unrectifiable” sets.
Jean Michel Morel, Sergio Solimini
Chapter 7. Covering Lemmas in a Metric Space
Abstract
Of course, we only have access to the Hausdorff measure of a given set A by looking at its coverings. Clearly, the definition (6.1) is very abstract and gives no indication about how a covering of A should be to give an accurate account of the Hausdorff measure. This section is devoted to several criteria which will tell us when a covering is a “good” covering, correctly approximating the Hausdorff measure. As we shall see, and this is rather surprising, the first criterion simply is that the covering is made of sets with diameter small enough. We shall also focus on additional properties that we would like to require from a covering. The main property is that the sets of the covering should be disjoint. Indeed, if they are, we may add inequalities concerning A obtained on each one of the sets of the covering and obtain global estimates on A. Thus, we may pass from local estimates on a covering of A to global estimates on the set A itself. The Vitali Covering Lemma is an essential tool to do that and we shall use it constantly in the next chapters. This chapter ends with a classical application of the Vitali Covering Lemma: Lebesgue measure and the N- dimensional Hausdorff measure agree on ℝ N .
Jean Michel Morel, Sergio Solimini
Chapter 8. Density Properties
Abstract
In this chapter and the following, we shall be concerned with properties which are true for all points of a given set A, except a set of points with zero Hausdorff measure. In this situation, we say that the considered property is true almost everywhere (a.e.) in K. We call α-set any \({{\cal H}^\alpha }(K)\, < \, + \infty .\)- measurable subset of a metric space E such that \(\lim {\inf _{r \to 0}}{{{{\cal H}^1}(K \cap B(x,r))} \over {2r}}\). We shall begin to develop the Besicovitch theory of sets with finite Hausdorff measure.
In order to explain the relevance of the results proved below, let us take as an (important) example, the case a = 1. Then obvious examples of 1-sets are the differentiable Jordan curves with finite length. It is easily seen that for such sets A, the length contained in a ball B(x,r) centered at a point x of A is equivalent to 2r as r tends to zero. This relation is true for all points of A except for the endpoints of the curve. Let us take an example of quite different structure: the “planar Cantor set” defined in Section 4 of Chapter 4. Let us denote this set by K. It is easily seen (and we prove at the end of the present chapter) that the “spherical lower density” lim inf \({{\cal H}^\alpha } - \) is not 1. So we observe a quite different spatial repartition for K and for smooth curves. It is expected that a general 1-set will have points where “curve-like” behaviour occurs (the spherical density is 1) and points where “Cantor- like” behaviour occurs. The first kind of point will be called “regular” and the other one “irregular”. One of the most remarkable results of the Besicovitch theory is that this classication is stable when one cuts a set into measurable pieces: The set of the regular points of an α-set K which are contained in a measurable subset J is essentially the same as the set of regular points of J!
The same thing happens for irregular points. So the properties of “regularity” and “irregularity” are intrinsic, local, stable properties. Every set will be divided by the Besicovitch theory into its regular part (which we will later prove to be contained in a bunch of rectifiable curves) and its irregular part (which will be, under many aspects, similar to the planar Cantor set). Those parts clearly behave like two nonmiscible fluids, and the Besicovitch theory yields clear computational criteria (the local spherical densities) to decide whether a point is regular or irregular. From the Image Processing viewpoint, we can say that the Besicovitch theory yields an absolute definition of which points in an “edge map” are really points of an edge and which are not (the irregular points).
Jean Michel Morel, Sergio Solimini
Chapter 9. Tangency Properties of Regular Subsets of ℝ N
Abstract
In this chapter, we shall be concerned with some tangency properties of regular α-sets of ℝN. We shall prove that a is necessarily an integer and that a regular set admits a tangent affine space almost everywhere and therefore “looks like” an α-dimensional manifold almost everywhere. The proof is essentially based on a remarkable reflection lemma due to Marstrand. Roughly speaking, this lemma, which is not difficult to prove once the right ideas are at hand, says that given two points x and y in a regular set A, the reflected point 2x-y lies close to A. This argument can be iterated by successive reflections and therefore yields nets of points which are contained in an affine sub space V and close to A. Of course, the whole argument is a little bit more technical than this abstract. We shall need precise estimates on how a net of points obtained by reflection spreads out and on how close to A the reflected point 2x-y is. This will be done in the first section. The second section is devoted to the existence proof, for any r > 0, of “approximate tangent affine spaces”, V(x,r), at most points x ∈ A. The third section analyses accurately how close A is to its approximate tangent spaces. It is proved that the orthogonal projection of A onto V(x, r) has a density inside B(x,r) tending to 1. This fact easily implies convergence of the sets V(x, r) towards an (almost everywhere) unique tangent space V(x).
Jean Michel Morel, Sergio Solimini
Chapter 10. Semicontinuity Properties of the Hausdorff Measure
Abstract
In this chapter, we first define a natural metric on the set of the closed sets of a metric space E: the Hausdorff distance. For this distance, we prove that the set of closed subsets of a compact set is compact. It would be extremely convenient to have the following continuity property: If a sequence of sets An converges for the Hausdorff distance towards a set A, then the Hausdorff measures of the An also converge to the Hausdorff measure of A. We give examples which show that this is in general not true. However, simple and useful conditions can be given on the sequence An in order that the Hausdorff measure is lower semicontinuous, that is,
$${{\cal H}^\alpha }(A)\, \le \,\mathop {\lim }\limits_{\,\,\,\,\,\,\,\,\,\,\,\,\,n} \inf \,\,\,\,{{\cal H}^\alpha }({A_n}).$$
(1)
We show that this last property is true when the sets An are “uniformly concentrated” (a property which we shall show to be true in Chapter 15 of this book for minimizing sequences of segmentations.
Jean Michel Morel, Sergio Solimini
Chapter 11. Rectifiable Sets
Abstract
In this chapter, we introduce the notion of rectifiable sets and mainly show that rectifiable sets are regular. The converse implication will be proved in the next chapter. We then discuss with some more details the case of rectifiable curves, which was already considered in Chapter 5.
Jean Michel Morel, Sergio Solimini
Chapter 12. Properties of Regular and Rectifiable Sets
Abstract
The full equivalence between the notions of rectifiability and regularity is developed in this chapter, as well as two very remarkable geometric properties of unrectifiable sets. It is first proved that there is a universal constant c(α) such that at almost every point of a fully unrectifiable set, the lower conic density is larger that c(α). This is a local and clear cut computational criterion for distinguishing rectifiable points from unrectifiable points in a given α-set. From this property, and from the existence almost everywhere of a tangent space for regular sets, it is immediately deduced that fully unrectifiable sets are fully irregular and that regular sets are rectifiable. We also know from Chapter 11 that rectifiable sets are regular. Thus the equivalence between regularity and rectifiability will be complete and, as a by product, the equivalence of simple rectifiability and rectifiability. We end the chapter with the surprising property of (N - 1)-fully irregular (or unrectifiable) sets of ℝN to have a negligible projection on almost every hyperplane.
Jean Michel Morel, Sergio Solimini

Existence and Structural Properties of the Minimal Segmentations for the Mumford-Shah Model

Frontmatter
Chapter 13. Properties of the Approximating Image in the Mumford-Shah Model
Abstract
In this chapter, we assume that a closed 1-set K with finite ℋ1 -measure has been associated with an image g as a possible ”edge set“. We shall not assume that K is minimal with respect to the Mumford-Shah functional because we wish to focus on the following question: Given K, what is to be said of u =uK, where u is assumed to be the minimum point of the two-dimensional part of the Mumford-Shah energy,
$$I(u) = \int_{\Omega \backslash K} {(|\nabla u{|^2} + {{(u - g)}^2}?} $$
(1)
In Section 13.1, we explain some elementary properties satisfied by u, namely the elliptic equation -Δu + u = g and we answer the following question: If Kn “tends to” K (in a sense which will be discussed), what can be said about the convergence of UKn, associated with Kn, towards u = uk ?
In Section 13.2, we look for the effect on the energy of u of a certain kind of modification of K: when some part of K has been erased. Then the new approximating function v satisfies I(v) ≥ I(u), and we give precise estimates on I(v) — I(u) which relate this “jump of energy” to the geometry of K. Section 13.3 is devoted to an accurate estimate of the gradient of u, Vu, as a function of the distance to K. When coupled with the “jump of energy” estimates of Section 13.2, this estimate will prove a basic tool to understand the geometry of minimal edge sets K.
Jean Michel Morel, Sergio Solimini
Chapter 14. Small Oscillation Coverings and the Excision Method
Abstract
In this chapter, we develop the main general tool used for proving regularity properties of the minimizers of the Mumford-Shah functional. It will be called Excision Method and consists in showing that, whenever the set K is too “ragged” inside some disk D, and whenever u is smooth enough around each piece of K, then the excision operation, consisting of removing from the edge set K the points contained in D, decreases the value of the functional E(K).
This kind of information will have a straightforward use: since the functional E(K) cannot decrease when the edge set K is a minimum, we shall conclude that K is not too “ragged”, whatever the disk D is, and regularity properties for K will follow. Let us now see roughly which kind of raggedness condition we shall consider. We shall assume that the edge set can be covered by a family of sets Di on whose boundary, ∂Di, the function u = u k does not oscillate much. Such coverings will be called small oscillation coverings. We shall prove that when one can cover the edge set K with a small oscillation covering made of sets Di whose size is small enough with respect to the diameter of D, then the excision operation works successfully and decreases the Mumford-Shah energy.
Several applications of this general excision principle will be done in the next two chapters. The “concrete properties” of the minimizers which will be proved therein will in fact be straightforward applications of the excision method.
Jean Michel Morel, Sergio Solimini
Chapter 15. Density Properties and Existence Theory for the Mumford-Shah Minimizers
Abstract
In this chapter, we shall find a first application of the elimination techniques which we have introduced in the preceding chapter. We shall prove more and more precise density properties for minimal segmentations and, more generally, for segmentations satisfying the minimality property (M). Recall that this property essentially states that no excision of a disk can decrease the Mumford-Shah energy of the segmentation. To make a long story short, let us say that we shall prove (in this order):
  • The Essentiality Property: Around every point x of K one has that ℋ1(K ∩ D(R)) > 0, where D(R) denotes the disk B(x,R). In other terms, no point of K is “isolated”.
  • The Uniform Density Property: There is a universal constant β such that at every point x ∈ K, ℋ1(K∩D(R)) > βR. This clearly is a stronger nonsparseness property for K.
  • The Concentration Property: For every ε > 0, there is α > 0 such that every disk D(R) centered on the edge set K contains a subdisk D′ with radius larger than αR inside which K is “concentrated”, that is ℋ1(K ∩ D′) ≥ (1 - ε)diam(D′). This property clearly implies the Uniform Density Property.
  • The First Projection Property: There is a universal constant β1 such that ∀x ∈ K, ℋ1(p1(K ∩ D(R))) + ℋ1(p2(K ∩ D(R))) ≥ βR, where p1 and p2 denote the projectors in two orthogonal directions.
We shall also prove a Second Projection Property, which is in the same relation to the first as the Concentration Property is to the Uniform Density Property. We could have directly stated and proved the two last density properties, which are stronger, but this would have made the exposition tedious and technical. As a matter of fact, each one of the above-mentioned properties will be used in the proof of existence of minimizers for the Mumford-Shah energy. To be more precise, we shall make in the second part of this chapter the following deductions.
  • From the Uniform Projection Property we deduce, by using the results of Chapter 12 about projections of 1-sets, that the Mumford-Shah minima and quasiminima (in the sense of Property (M)) must be rectifiable.
  • From the Uniform Projection Property, we deduce that any minimal or quasiminimal (in the sense of property (M)) rectifiable segmentation can be approximated by a finite set of curves.
  • From both the Projection Property and the Uniform Concentration Property, we deduce, by using the results of Chapter 10, that the set of segmentations satisfying (M) is compact and that the minimum of the Mumford-Shah energy is attained for some uniformly rectifiable segmentation.
We end the chapter by showing that the minimal segmentation may be nonunique, which somehow matches the computer scientist’s intuition tha t more than one segmentation can be “good” for a given image.
Jean Michel Morel, Sergio Solimini
Chapter 16. Further Properties of Minimizers: Covering the Edge Set with a Single Curve
Abstract
In this final chapter we shall consider further properties of the optimal segmentations. The main new information which we shall obtain is that the whole segmentation K is contained in a single rectifiable curve γ whose length is proportional (with a ratio depending on Ω) to the length of K and which is Ahlfors regular. More precisely, there is a universal constant C such that on every disk D(r), r ≤ 1 one has l(c∩D(r)) ≤ Cr. The existence of such a curve will be obtained as a counterpart to a uniform rectifiability property, stronger than any considered in the last chapter. We shall prove that in every disk centered on K there is a rectifiable curve which is almost equal to a “big piece” of K. This property, which we call “Concentrated Rectifiability Property” will be proved in Sections 1 and 2 by using the “small oscillation covering” technique of Chapters 14 and 15. Section 3 is devoted to the proof that we can somehow join the curves given by this Rectifiability Property and obtain a curve containing all of K. In Section 4, we show by a simple minimality argument that such a curve can be imposed to be Ahlfors regular, with a universal constant only depending on the diameter of Ω.
Jean Michel Morel, Sergio Solimini
Backmatter
Metadaten
Titel
Variational Methods in Image Segmentation
verfasst von
Jean Michel Morel
Sergio Solimini
Copyright-Jahr
1995
Verlag
Birkhäuser Boston
Electronic ISBN
978-1-4684-0567-5
Print ISBN
978-1-4684-0569-9
DOI
https://doi.org/10.1007/978-1-4684-0567-5