Mathematical Morphology E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 855

Veröffentlichungsjahr: 2013

Beschreibung

Mathematical Morphology allows for the analysis and processing of geometrical structures using techniques based on the fields of set theory, lattice theory, topology, and random functions. It is the basis of morphological image processing, and finds applications in fields including digital image processing (DSP), as well as areas for graphs, surface meshes, solids, and other spatial structures. This book presents an up-to-date treatment of mathematical morphology, based on the three pillars that made it an important field of theoretical work and practical application: a solid theoretical foundation, a large body of applications and an efficient implementation.

The book is divided into five parts and includes 20 chapters. The five parts are structured as follows:

• Part I sets out the fundamental aspects of the discipline, starting with a general introduction, followed by two more theory-focused chapters, one addressing its mathematical structure and including an updated formalism, which is the result of several decades of work.
• Part II extends this formalism to some non-deterministic aspects of the theory, in particular detailing links with other disciplines such as stereology, geostatistics and fuzzy logic.
• Part III addresses the theory of morphological filtering and segmentation, featuring modern connected approaches, from both theoretical and practical aspects.
• Part IV features practical aspects of mathematical morphology, in particular how to deal with color and multivariate data, links to discrete geometry and topology, and some algorithmic aspects; without which applications would be impossible.
• Part V showcases all the previously noted fields of work through a sample of interesting, representative and varied applications.

Leseprobe

Contents

Preface

Part I. Foundations

Chapter 1. Introduction to Mathematical Morphology

1.1. First steps with mathematical morphology: dilations and erosions

1.2. Morphological filtering

1.3. Residues

1.4. Distance transform, skeletons and granulometric curves

1.5. Hierarchies and the watershed transform

1.6. Some concluding thoughts

Chapter 2. Algebraic Foundations of Morphology

2.1. Introduction

2.2. Complete lattices

2.3. Examples of lattices

2.4. Closings and openings

2.5. Adjunctions

2.6. Connections and connective segmentation

2.7. Morphological filtering and hierarchies

Chapter 3. Watersheds in Discrete Spaces

3.1. Watersheds on the vertices of a graph

3.2. Watershed cuts: watershed on the edges of a graph

3.3. Watersheds in complexes

Part II. Evaluating and Deciding

Chapter 4. An Introduction to Measurement Theory for Image Analysis

4.1. Introduction

4.2. General requirements

4.3. Convex ring and Minkowski functionals

4.4. Stereology and Minkowski functionals

4.5. Change in scale and stationarity

4.6. Individual objects and granulometries

4.7. Gray-level extension

4.8. As a conclusion

Chapter 5. Stochastic Methods

5.1. Introduction

5.2. Random transformation

5.3. Random image

Chapter 6. Fuzzy Sets and Mathematical Morphology

6.1. Introduction

6.2. Background to fuzzy sets

6.3. Fuzzy dilations and erosions from duality principle

6.4. Fuzzy dilations and erosions from adjunction principle

6.5. Links between approaches

6.6. Application to the definition of spatial relations

6.7. Conclusion

Part III. Filtering and Connectivity

Chapter 7. Connected Operators based on Tree Pruning Strategies

7.1. Introduction

7.2. Connected operators

7.3. Tree representation and connected operator

7.4. Tree pruning

7.5. Conclusions

Chapter 8. Levelings

8.1. Introduction

8.2. Set-theoretical leveling

8.3. Numerical levelings

8.4. Discrete levelings

8.5. Bibliographical comment

Chapter 9. Segmentation, Minimum Spanning Tree and Hierarchies

9.1. Introduction

9.2. Preamble: watersheds, floodings and plateaus

9.3. Hierarchies of segmentations

9.4. Computing contours saliency maps

9.5. Using hierarchies for segmentation

9.6. Lattice of hierarchies

Part IV. Links and Extensions

Chapter 10. Distance, Granulometry and Skeleton

10.1. Skeletons

10.2. Skeletons in discrete spaces

10.3. Granulometric families and skeletons

10.4. Discrete distances

10.5. Bisector function

10.6. Homotopic transformations

10.7. Conclusion

Chapter 11. Color and Multivariate Images

11.1. Introduction

11.2. Basic notions and notation

11.3. Morphological operators for color filtering

11.4. Mathematical morphology and color segmentation

11.5. Conclusion

Chapter 12. Algorithms for Mathematical Morphology

12.1. Introduction

12.2. Translation of definitions and algorithms

12.3. Taxonomy of algorithms

12.4. Geodesic reconstruction example

12.5. Historical perspectives and bibliography notes

12.6. Conclusions

Part V. Applications

Chapter 13. Diatom Identification with Mathematical Morphology

13.1. Introduction

13.2. Morphological curvature scale space

13.3. Scale-space feature extraction

13.4. 2D size-shape pattern spectra

13.5. Datasets

13.6. Results

13.7. Conclusions

Chapter 14. Spatio-temporal Cardiac Segmentation

14.1. Which objects of interest?

14.2. How do we segment?

14.3. Results, conclusions and perspectives

Chapter 15. 3D Angiographic Image Segmentation

15.1. Context

15.2. Anatomical knowledge modeling

15.3. Hit-or-miss transform

15.4. Application: two vessel segmentation examples

15.5. Conclusion

Chapter 16. Compression

16.1. Introduction

16.2. Morphological multiscale decomposition

16.3. Region-based decomposition

16.4. Conclusions

Chapter 17. Satellite Imagery and Digital Elevation Models

17.1. Introduction

17.2. On the specificity of satellite images

17.3. Mosaicing of satellite images

17.4. Applications to digital elevation models

17.5. Conclusion and perspectives

Chapter 18. Document Image Applications

18.1. Introduction

18.2. Applications

Chapter 19. Analysis and Modeling of 3D Microstructures

19.1. Introduction

19.2. 3D morphological analysis

19.3. Models of random multiscale structures

19.4. Digital materials

19.5. Conclusion

Chapter 20. Random Spreads and Forest Fires

20.1. Introduction

20.2. Random spread

20.3. Forecast of the burnt zones

20.4. Discussion: estimating and choosing

20.5. Conclusions

Bibliography

List of Authors

Index

To our families who have put up with us as we were writing this book, for nearly three years now.

Deepest love and thanks to Laurence, Annick Zoé, Ilan, Sophie and Shaï.

First published 2010 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Adapted and updated from two volumes Morphologie mathématique 1 & 2 published 2008 and 2010 in France by Hermes Science/Lavoisier © LAVOISIER 2008, 2010

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.iste.co.uk

www.wiley.com

© ISTE Ltd 2010

The rights of Laurent Najman and Hugues Talbot to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Mathematical morphology / edited by Laurent Najman, Hugues Talbot.

p. cm.

“Adapted and updated from two volumes Morphologie mathématique 1, 2 published 2008 and 2010 in France by Hermes Science/Lavoisier”

Includes bibliographical references and index.

ISBN 978-1-84821-215-2

1. Image analysis. 2. Image processing--Mathematics. I. Najman, Laurent. II. Talbot, Hugues.

TA1637.M35963 2010

621.36’70151--dc22

2010020106

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-215-2

Preface

Mathematical morphology is a discipline of image analysis that was introduced in the mid-1960s by two researchers at the École des Mines in Paris: Georges Matheron [MAT 75] and Jean Serra [SER 82, SER 88c]. Historically, this was the first consistent nonlinear image analysis theory, which from the very start included not only theoretical results but also many practical aspects. Its initial objective was to facilitate studies of mineral deposits via sampling. It was implemented using dedicated image processing hardware, akin to analog computers in many ways. Mathematical morphology was endowed from the very beginning with the three pillars which ensured its success: a solid theoretical foundation, a large body of applications and an efficient implementation.

Since this heroic era, many developments have been proposed. Indeed, many unforeseen applications have been developed: in materials science and in the life sciences, for example. The techniques eventually become popular internationally and improved to the level where they are now, more than 40 years after their beginning. Since 1993, a regular and well-attended series of international symposiums dedicated to the discipline have taken place and many journals have mathematical morphology tracks and special issues. Mathematical morphology is now part of the basic body of techniques taught to any student of image processing courses anywhere; most image processing software packages feature morphology toolboxes and filters, including the most popular programs such as Photoshop or Matlab. Far from being an academic pursuit, morphology is used in industry and businesses at many levels, for example: quality control in industrial production, medical imaging, document processing and much more.

In spite of this popularity, researchers and practitioners in mathematical morphology often find that their operators and functions are not understood as well as they could be. For instance, many newcomers to the discipline think it only applies to binary images (images featuring only two levels: pure black and pure white). On the contrary, mathematical morphology is a complete theory capable of handling the most varied image types in a way that is often subtle yet efficient. Morphology can be used to process certain types of noise in images, but can also be used more generally in filtering, segmentation, classification, analysis and coding of visual-type data. It can also be used to process general graphs, surfaces, implicit and explicit volumes, manifolds and time or spectral series in both deterministic and stochastic contexts.

One of the reasons for this lack of understanding might be the relative lack of recent and comprehensive books on the topic [DOU 93, DOU 03b, HEI 94a, SOI 03a]. We were therefore very honored when Henri Maître, director of the Image and Signal collection at Hermès Publishing in France, asked us to propose, compile and edit contributions from some of the best-known researchers and practitioners in the field in order to showcase the capabilities of mathematical morphology. Thanks to ISTE and John Wiley and Sons, we are now pleased to provide this book in English. Its content has been thoroughly revised and significantly expanded from the French language version.

The primary goal of this book is to expose the state of the art in mathematical morphology in a didactic fashion. However, our authors did not limit themselves to this exercise, but also developed some original and novel content. They took advantage of this opportunity to reformulate, rework and rethink the themes they work with most often, in order to make them available to a greater audience in a unique format. We are also of course very honored by the confidence afforded to us by all our numerous contributors. We take this opportunity to thank them and applaud their efforts. This book has taken a very long time to come to fruition, but our authors have been a pleasure to work with all along. We hope the end result meets their expectation. Among our authors, we particularly wish to thank Christian Ronse and Jean Serra, who have both helped us immensely to improved the general quality of the book.

The 20 chapters are divided into 5 parts as follows:

– The first part explains the fundamental aspects of the discipline. Starting with a general introduction, two more theoretical chapters follow. The first of these is concerned with mathematical structure, including a modernized formalism which is the result of several decades of work.

– The second part extends morphology into image analysis, in particular detailing how estimations, choices and measurements can be made. This is achived through links with other disciplines such as stereology, geostatistics and fuzzy logic.

– The third part concerns the theory of morphological filtering and segmentation, insisting on modern connected approaches from both the theoretical and practical aspects.

– The fourth part exposes some practical aspects of mathematical morphology, in particular, how to deal with color and multivariate data. Links to discrete geometry and topology and some algorithmic aspects are included, without which applications would be impossible.

– Finally, the fifth part illustrates all the previous work via a sampling of interesting, representative and varied applications.

In more detail, the first part introduces the theoretical foundations and general principles of mathematical morphology:

– Chapter 1, written by both of us, is a didactic introduction to mathematical morphology that does not require any specific knowledge and should be accessible to any person with a general scientific background.

– Chapter 2, written by Christian Ronse and Jean Serra, deals with the algebraic foundations of mathematical morphology. It introduces basic operators though the framework of complete lattice. It provides the notion of adjunction, necessary for operator composition. It illustrates the generality of the lattice framework applied to filtering and introduces the notions of segmentation by connection and by filtering of hierarchies.

– Chapter 3, written by Gilles Bertrand, Michel Couprie, Jean Cousty and Laurent Najman, analyses the watershed line operator in discrete spaces. The watershed line is the premier mathematical morphology tool for segmentation. In this chapter, several definitions are proposed with varied fields of applications from a purely discrete point of view. These definitions draw from concepts originating from topology and mathematical optimization, in pixel images but also graphs and complexes.

The second part deals with analysis, estimations and measurements:

– Chapter 4, written by Jean Serra and ourselves, is an introduction to the theory of measurements in image analysis and mathematical morphology, with a stereological perspective. The goal of this approach is to endow mathematical morphology with the ability to extract reliable, quantitative measurements from visual information.

– Chapter 5, written by Christian Lantuéjoul, describes some of the probabilistic aspects of mathematical morphology. In particular, the chapter discusses sampling, simulations and border effects.

– Chapter 6, written by Isabelle Bloch, describes the state of the art in fuzzy morphology. This extension makes it possible to manage uncertainty and imprecision in a complementary matter to probabilistic approaches.

The third part concerns the theory of morphological filtering and segmentation:

– Chapter 7, written by Philippe Salembier, studies connected morphological filtering using the component tree. The component tree is a fundamental notion in modern morphology, allowing powerful operators to be implemented efficiently.

– Chapter 8, written by Jean Serra, Corinne Vachier and Fernand Meyer, is about levelings. This class of connected operators has increasing importance in image filtering. Like all connected operators, they reduce noise while preserving contours.

– Chapter 9, written by Fernand Meyer and Laurent Najman, is about hierarchical morphological segmentation. The main tool is again the watershed line. The chapter describes this tool in a coherent manner, which makes it possible to build segmentation hierarchies. This notion is important when dealing with multiresolution issues, for parameter optimization or in order to propose fast interactive segmentations.

The fourth part contains a subset of interesting topics in morphology that are applied more in nature. This includes granulometries and skeletonization, multivariate and color morphology and some algorithmic aspects of morphology:

– Chapter 10, written by Michel Couprie and Hugues Talbot, discusses granulometries, distances and topological operators. Combined, these notions lead to efficient and interesting skeletonization operators. These operators reduce the amount of information needed to represent objects while conserving topological properties.

– Chapter 11, written by Jesus Angulo and Jocelyn Chanussot, deals with the way multivariate and color data might be processed using mathematical morphology. As this type of data is becoming increasingly prevalent, this is of particular importance.

– Chapter 12, written by Thierry Géraud, Hugues Talbot and Marc Van Droogen-broeck, deals with the implementation aspects of the discipline and with associated algorithmic matters. This aspect is of crucial importance for applications.

Finally, the fifth and last part illustrates the previous chapters with detailed applications and applications fields:

– Chapter 13, written by Michael Wilkinson, Erik Urbach, Andre Jalba and Jos Roerdink, concerns a methodology for the analysis of diatoms which uses morphological texture analysis very effectively.

– Chapter 14, written by Jean Cousty, Laurent Najman and Michel Couprie, shows an application to the 3D+t spatio-temporal segmentation of the left ventricle of the human heart using magnetic resonance imaging (MRI).

– Chapter 15, written by Benoît Naegel, Nicolas Passat and Christian Ronse, is a description of a segmentation and analysis method of the brain vascular network.

– Chapter 16, written by Beatriz Marcotegui and Philippe Salembier, concerns image coding and compression using morphological segmentation.

– Chapter 17, written by Pierre Soille, shows applications of mathematical morphology techniques to remote sensing.

– Chapter 18, written by Dan Bloomberg and Luc Vincent, is a description of a vast array of morphological techniques applied to scanned document analysis.

– Chapter 19, written by Dominique Jeulin, outlines recent progress in the analysis of materials, in particular using microtomography techniques.

– Chapter 20, written by Jean Serra, combines random sets and deterministic morphological operators to analyze the spread of forest fires in Malaysia.

A web site is dedicated to this book at the following URL: http://www.mathematicalmorphology.org/books/najman-talbot. Supplementarymaterial is available there, including color versions of many of our illustrations.

We sincerely hope that this presentation of modern mathematical morphology will allow a larger public to understand, appreciate, explore and exploit this rich and powerful discipline of image analysis.

Laurent NAJMANHugues TALBOTJune 2010

PART I

Foundations

Chapter 1

Introduction to Mathematical Morphology1

In this chapter we endeavor to introduce in a concise way the main aspects of Mathematical Morphology, as well as what constitutes its field. This question is difficult, not so much as a technical matter but as a question of starting point. Historically, mathematical morphology began as a technique to study random sets with applications to the mining industry. It was rapidly extended to work with two-dimensional (2D) images in a deterministic framework first with binary images, then gray-level and later to color and multispectral data and in dimensions > 2. The framework of mathematical morphology encompasses many various mathematical disciplines from set theory including lattice theory, random sets, probabilities, measure theory, topology, discrete and continuous geometry, as well as algorithmic considerations and finally applications.

The main principle of morphological analysis is to extract knowledge from the response of various transformations which are generally nonlinear.

One difficulty in the way mathematical morphology has been developed and expanded [MAT 75, SER 82, SER 88c] (see also [HEI 94a, SCH 94, SOI 03a]) is that its general properties do not fall within the general topics taught at school and universities (with the exception of relatively advanced graduate-level courses). Classical mathematics define a function as an operator associating a single point in a domain with a single value. A contrario, in morphology we associate whole sets with other whole sets. The consequences of this are important. For instance, if a point generally has zero measure, this is not generally the case for sets. Consequently, while a probability of the presence of a point may be zero, this is not the case for a set.

In addition, we can compare morphology to other image processing disciplines. For instance, linear operator theory assumes that images are merely a multidimensional signal. We also assume that signals combine themselves additively. The main mathematical structure is the vector space and basic operators are those that preserve this structure and commute with basic rules (in this case, addition and multiplication by a constant). From this point deriving convolution operators is natural; hence it is also natural to study Fourier or wavelet transforms. It is also natural to study decomposition by projections on basis vectors. This way is of course extremely productive and fruitful, but it is not the complete story.

Indeed, very often a 2D image is not only a signal but corresponds to a projection of a larger 3D reality onto a sensor via an optical system of some kind. Two objects that overlap each other due to the projections do not add their feature but, on the contrary, create occlusions. The addition is not the most natural operator in this case. It makes more sense to think in terms of overlapping objects and therefore, in terms of sets, their union, intersections and so on. With morphology, we characterize what is seen via geometrical transforms, taking into account shapes, connectivity, orientation, size, etc. The mathematical structure that is most adapted to this context is not the vector space, but the generalization of set theory to complete lattices [BIR 95].

1.1. First steps with mathematical morphology: dilations and erosions

In order to be able to define mathematical morphology operators, we need to introduce the abstract notion of complete lattice. We shall then be able to perform morphology on any instance of such a lattice.

1.1.1. The notion of complete lattice

1.1.2. Examples of lattices

Figure 1.1 is an example of a lattice. This instance is simple but informative, as it corresponds to the lattice of primary additive colors (red, green and blue). Each element of the lattice is a binary 3-vector, where 0 represents the absence of a primary color and 1 its presence. The color black is represented by [0,0,0] and white by [1,1,1]. Pure red is [1,0,0], pure green is [0,1,0], and so on. Magenta is represented by [1,0,1]. In this lattice, there does not exist a way to directly compare pure green and pure blue or magenta and yellow: the order is not . However, white is greater (brighter) than all colors and black is smaller (darker). Whatever subset of colors is chosen, it is always possible to define a by selecting the maximal individual component among the colors of the set (e.g. the supremum of [1,0,0] and [0,0,1] is [1,0,1]). This supremum may not be in the subset, but it belongs to the original lattice. Similarly, the is defined by taking the minimal individual component.