 Mathematical morphology

Mathematical morphology (MM) is a theory and technique for the analysis and processing of geometrical structures, based on set theory, lattice theory, topology, and random functions. MM is most commonly applied to digital images, but it can be employed as well on graphs, surface meshes, solids, and many other spatial structures.
Topological and geometrical continuousspace concepts such as size, shape, convexity, connectivity, and geodesic distance, can be characterized by MM on both continuous and discrete spaces. MM is also the foundation of morphological image processing, which consists of a set of operators that transform images according to the above characterizations.
MM was originally developed for binary images, and was later extended to grayscale functions and images. The subsequent generalization to complete lattices is widely accepted today as MM's theoretical foundation.
Contents
History
Mathematical Morphology was born in 1964 from the collaborative work of Georges Matheron and Jean Serra, at the École des Mines de Paris, France. Matheron supervised the PhD thesis of Serra, devoted to the quantification of mineral characteristics from thin cross sections, and this work resulted in a novel practical approach, as well as theoretical advancements in integral geometry and topology.
In 1968, the Centre de Morphologie Mathématique was founded by the École des Mines de Paris in Fontainebleau, France, led by Matheron and Serra.
During the rest of the 1960s and most of the 1970s, MM dealt essentially with binary images, treated as sets, and generated a large number of binary operators and techniques: Hitormiss transform, dilation, erosion, opening, closing, granulometry, thinning, skeletonization, ultimate erosion, conditional bisector, and others. A random approach was also developed, based on novel image models. Most of the work in that period was developed in Fontainebleau.
From mid1970s to mid1980s, MM was generalized to grayscale functions and images as well. Besides extending the main concepts (such as dilation, erosion, etc...) to functions, this generalization yielded new operators, such as morphological gradients, tophat transform and the Watershed (MM's main segmentation approach).
In the 1980s and 1990s, MM gained a wider recognition, as research centers in several countries began to adopt and investigate the method. MM started to be applied to a large number of imaging problems and applications.
In 1986, Jean Serra further generalized MM, this time to a theoretical framework based on complete lattices. This generalization brought flexibility to the theory, enabling its application to a much larger number of structures, including color images, video, graphs, meshes, etc. At the same time, Matheron and Serra also formulated a theory for morphological filtering, based on the new lattice framework.
The 1990s and 2000s also saw further theoretical advancements, including the concepts of connections and levelings.
In 1993, the first International Symposium on Mathematical Morphology (ISMM) took place in Barcelona, Spain. Since then, ISMMs are organized every 2–3 years, each time in a different part of the world: Fontainebleau, France (1994); Atlanta, USA (1996); Amsterdam, Netherlands (1998); Palo Alto, CA, USA (2000); Sydney, Australia (2002); Paris, France (2004); Rio de Janeiro, Brazil (2007); Groningen, Netherlands (2009); and Intra (Verbania), Italy (2011).
References
 "Introduction" by Pierre Soille, in (Serra et al. (Eds.) 1994), pgs. 14.
 "Appendix A: The 'Centre de Morphologie Mathématique', an overview" by Jean Serra, in (Serra et al. (Eds.) 1994), pgs. 369374.
 "Foreword" in (Ronse et al. (Eds.) 2005)
Binary morphology
In binary morphology, an image is viewed as a subset of an Euclidean space or the integer grid , for some dimension d.
Structuring element
The basic idea in binary morphology is to probe an image with a simple, predefined shape, drawing conclusions on how this shape fits or misses the shapes in the image. This simple "probe" is called structuring element, and is itself a binary image (i.e., a subset of the space or grid).
Here are some examples of widely used structuring elements (denoted by B):
 Let ; B is an open disk of radius r, centered at the origin.
 Let ; B is a 3x3 square, that is, B={(1,1), (1,0), (1,1), (0,1), (0,0), (0,1), (1,1), (1,0), (1,1)}.
 Let ; B is the "cross" given by: B={(1,0), (0,1), (0,0), (0,1), (1,0)}.
Basic operators
The basic operations are shiftinvariant (translation invariant) operators strongly related to Minkowski addition.
Let E be a Euclidean space or an integer grid, and A a binary image in E.
Erosion
The erosion of the binary image A by the structuring element B is defined by:

 ,
where B_{z} is the translation of B by the vector z, i.e., , .
When the structuring element B has a center (e.g., B is a disk or a square), and this center is located on the origin of E, then the erosion of A by B can be understood as the locus of points reached by the center of B when B moves inside A. For example, the erosion of a square of side 10, centered at the origin, by a disc of radius 2, also centered at the origin, is a square of side 6 centered at the origin.
The erosion of A by B is also given by the expression: .
Example application: Assume we have received a fax of a dark photocopy. Everything looks like it was written with a pen that is bleeding. Erosion process will allow thicker lines to get skinny and detect the hole inside the letter "o".
Dilation
The dilation of A by the structuring element B is defined by:

 .
The dilation is commutative, also given by: .
If B has a center on the origin, as before, then the dilation of A by B can be understood as the locus of the points covered by B when the center of B moves inside A. In the above example, the dilation of the square of side 10 by the disk of radius 2 is a square of side 14, with rounded corners, centered at the origin. The radius of the rounded corners is 2.
The dilation can also be obtained by: , where B^{s} denotes the symmetric of B, that is, .
Example application: Dilation is the opposite of the erosion. Figures that are very lightly drawn get thick when "dilated". Easiest way to describe it is to imagine the same fax/text is written with a thicker pen.
Opening
The opening of A by B is obtained by the erosion of A by B, followed by dilation of the resulting image by B:

 .
The opening is also given by , which means that it is the locus of translations of the structuring element B inside the image A. In the case of the square of side 10, and a disc of radius 2 as the structuring element, the opening is a square of side 10 with rounded corners, where the corner radius is 2.
Example application: Let's assume someone has written a note on a nonsoaking paper that writing looks like it is growing tiny hairy roots all over. Opening essentially removes the outer tiny "hairline" leaks and restores the text. The side effect is that it rounds off things. The sharp edges start to disappear.
Closing
The closing of A by B is obtained by the dilation of A by B, followed by erosion of the resulting structure by B:

 .
The closing can also be obtained by , where X^{c} denotes the complement of X relative to E (that is, ). The above means that the closing is the complement of the locus of translations of the symmetric of the structuring element outside the image A.
Properties of the basic operators
Here are some properties of the basic binary morphological operators (dilation, erosion, opening and closing):
 They are translation invariant.
 They are increasing, that is, if , then , and , etc.
 The dilation is commutative.
 If the origin of E belongs to the structuring element B, then .
 The dilation is associative, i.e., . Moreover, the erosion satisfies .
 Erosion and dilation satisfy the duality .
 Opening and closing satisfy the duality .
 The dilation is distributive over set union
 The erosion is distributive over set intersection
 The dilation is a pseudoinverse of the erosion, and viceversa, in the following sense: if and only if .
 Opening and closing are idempotent.
 Opening is antiextensive, i.e., , whereas the closing is extensive, i.e., .
Other operators and tools
 Hitormiss transform
 Pruning transform
 Morphological skeleton
 Filtering by reconstruction
 Ultimate erosions and conditional bisectors
 Granulometry
 Geodesic distance functions
Grayscale morphology
In grayscale morphology, images are functions mapping a Euclidean space or grid E into , where is the set of reals, is an element larger than any real number, and is an element smaller than any real number.
Grayscale structuring elements are also functions of the same format, called "structuring functions".
Denoting an image by f(x) and the structuring function by b(x), the grayscale dilation of f by b is given by

 ,
where "sup" denotes the supremum.
Similarly, the erosion of f by b is given by

 ,
where "inf" denotes the infimum.
Just like in binary morphology, the opening and closing are given respectively by

 , and

 .
Flat structuring functions
It is common to use flat structuring elements in morphological applications. Flat structuring functions are functions b(x) in the form

 ,
where .
In this case, the dilation and erosion are greatly simplified, and given respectively by

 , and

 .
In the bounded, discrete case (E is a grid and B is bounded), the supremum and infimum operators can be replaced by the maximum and minimum. Thus, dilation and erosion are particular cases of order statistics filters, with dilation returning the maximum value within a moving window (the symmetric of the structuring function support B), and the erosion returning the minimum value within the moving window B.
In the case of flat structuring element, the morphological operators depend only on the relative ordering of pixel values, regardless their numerical values, and therefore are especially suited to the processing of binary images and grayscale images whose light transfer function is not known.
Other operators and tools
By combining these operators one can obtain algorithms for many image processing tasks, such as feature detection, image segmentation, image sharpening, image filtering, and classification.
Mathematical morphology on complete lattices
Complete lattices are partially ordered sets, where every subset has an infimum and a supremum. In particular, it contains a least element and a greatest element (also denoted "universe").
Adjunctions (Dilation and Erosion)
Let be a complete lattice, with infimum and supremum symbolized by and , respectively. Its universe and least element are symbolized by U and , respectively. Moreover, let {X_{i}} be a collection of elements from L.
A dilation is any operator that distributes over the supremum, and preserves the least element. I.e.:
 ,
 .
An erosion is any operator that distributes over the infimum, and preserves the universe. I.e.:
 ,
 ε(U) = U.
Dilations and erosions form Galois connections. That is, for all dilation δ there is one and only one erosion ε that satisfies
for all .
Similarly, for all erosion there is one and only one dilation satisfying the above connection.
Furthermore, if two operators satisfy the connection, then δ must be a dilation, and ε an erosion.
Pairs of erosions and dilations satisfying the above connection are called "adjunctions", and the erosion is said to be the adjoint erosion of the dilation, and viceversa.
Opening and Closing
For all adjunction (ε,δ), the morphological opening and morphological closing are defined as follows:

 γ = δε, and

 ϕ = εδ.
The morphological opening and closing are particular cases of algebraic opening (or simply opening) and algebraic closing (or simply closing). Algebraic openings are operators in L that are idempotent, increasing, and antiextensive. Algebraic closings are operators in L that are idempotent, increasing, and extensive.
Particular cases
Binary morphology is a particular case of lattice morphology, where L is the power set of E (Euclidean space or grid), that is, L is the set of all subsets of E, and is the set inclusion. In this case, the infimum is set intersection, and the supremum is set union.
Similarly, grayscale morphology is another particular case, where L is the set of functions mapping E into , and , , and , are the pointwise order, supremum, and infimum, respectively. That is, is f and g are functions in L, then if and only if ; the infimum is given by ; and the supremum is given by .
See also
References
 Image Analysis and Mathematical Morphology by Jean Serra, ISBN 0126372403 (1982)
 Image Analysis and Mathematical Morphology, Volume 2: Theoretical Advances by Jean Serra, ISBN 0126372411 (1988)
 An Introduction to Morphological Image Processing by Edward R. Dougherty, ISBN 081940845X (1992)
 Morphological Image Analysis; Principles and Applications by Pierre Soille, ISBN 3540656715 (1999), 2nd edition (2003)
 Mathematical Morphology and its Application to Signal Processing, J. Serra and Ph. Salembier (Eds.), proceedings of the 1st International workshop on mathematical morphology and its applications to signal processing (ISMM'93), ISBN 8476532717 (1993)
 Mathematical Morphology and Its Applications to Image Processing, J. Serra and P. Soille (Eds.), proceedings of the 2nd international symposium on mathematical morphology (ISMM'94), ISBN 0792330935 (1994)
 Mathematical Morphology and its Applications to Image and Signal Processing, Henk J.A.M. Heijmans and Jos B.T.M. Roerdink (Eds.), proceedings of the 4th international symposium on mathematical morphology (ISMM'98), ISBN 0792351339 (1998)
 Mathematical Morphology: 40 Years On, Christian Ronse, Laurent Najman, and Etienne Decencière (Eds.), ISBN 1402034423 (2005)
 Mathematical Morphology and its Applications to Signal and Image Processing, Gerald J.F. Banon, Junior Barrera, Ulisses M. BragaNeto (Eds.), proceedings of the 8th international symposium on mathematical morphology (ISMM'07), ISBN 9788517000324 (2007)
 Mathematical morphology: from theory to applications, Laurent Najman and Hugues Talbot (Eds). ISTEWiley. ISBN 9781848212152. (520 pp.) June 2010
External links
 Online course on mathematical morphology, by Jean Serra (in English, French, and Spanish)
 Center of Mathematical Morphology, Paris School of Mines
 History of Mathematical Morphology, by Georges Matheron and Jean Serra
 Morphology Digest, a newsletter on mathematical morphology, by Pierre Soille
 Lectures on Image Processing: A collection of 18 lectures in pdf format from Vanderbilt University. Lectures 1618 are on Mathematical Morphology, by Alan Peters
 Mathematical Morphology; from Computer Vision lectures, by Robyn Owens
 Free SIMD Optimized Image processing library
 Java applet demonstration
 FILTERS : a free open source image processing library
 Fast morphological erosions, dilations, openings, and closings
 Morphological analysis of neurons using Matlab
Wikimedia Foundation. 2010.
Look at other dictionaries:
mathematical morphology — noun A theory and technique for the analysis and processing of geometrical structures, based on set theory, lattice theory, topology, and random functions … Wiktionary
Morphology — may mean: Morphology (linguistics), the study of the structure and content of word forms Morphology (biology), the study of the form or shape of an organism or part thereof Morphology (molecular), study of how the shape and form of molecules… … Wikipedia
morphology — Synonyms and related words: IC analysis, accidence, affix, affixation, allomorph, anatomist, anatomy, angiography, angiology, anthropotomy, bound morpheme, bowwow theory, comparative linguistics, conjugation, cutting, declension, derivation,… … Moby Thesaurus
Dilation (morphology) — Dilation is one of the basic operations in mathematical morphology. Originally developed for binary images, it has been expanded first to grayscale images, and then to complete lattices. The dilation operation usually uses a structuring element… … Wikipedia
Closing (morphology) — The closing of the dark blue shape (union of two squares) by a disk, resulting in the union of the dark blue shape and the light blue areas. In mathematical morphology, the closing of a set (binary image) A by a structuring element B is the… … Wikipedia
Opening (morphology) — The opening of the dark blue square by a disk, resulting in the light blue square with round corners. In mathematical morphology, opening is the dilation of the erosion of a set A by a structuring element B: where … Wikipedia
Erosion (morphology) — Erosion is one of two fundamental operations (the other being dilation) in Morphological image processing from which all other morphological operations are based. It was originally defined for binary images, later being extended to grayscale… … Wikipedia
Granulometry (morphology) — In mathematical morphology, granulometry is an approach to compute a size distribution of grains in binary images, using a series of morphological opening operations. It was introduced by Georges Matheron in the 1960 s, and is the basis for the… … Wikipedia
Pruning (morphology) — The pruning algorithm is a technique used for digital image processing based on mathematical morphology. It is used as a complement to the skeleton and thinning algorithms to remove unwanted parasitic components.The process in itself will remove… … Wikipedia
Jean Serra — Infobox Scientist name = Jean Serra 277px image width = 313px birth date = 1940 birth place = Algeria citizenship = flagFrance work institution = Centre de Morphologie Mathématique, École des Mines de Paris field = Mathematics, geology known… … Wikipedia