Mathematical morphology

From Wikipedia, the free encyclopedia

For other uses, see 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 continuous-space 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 images and multi-band images. The subsequent generalization to complete lattices is widely accepted today as MM's theoretical foundation.

1 History
2 Binary morphology
- 2.1 Structuring element
- 2.2 Basic operators
3 Grayscale Morphology
- 3.1 Flat structuring functions
4 Bibliography
5 External links

[edit] History

Mathematical Morphology was born in 1964 from the collaborative work of Georges Matheron and Jean Serra, at the Ecole de 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 Ecole de Mines de Paris in Fountainebleau, France, lead by Matheron and Serra.

During the rest of the 1960's and most of the 1970's, MM dealt essentially with binary images, treated as sets, and generated a large number of binary operators and techniques: Hit-or-miss transform, dilation, erosion, opening, closing, thinning, skeletonization, ultimate erosion, conditional bisector, and others. A random approach was also developed, based on novel image models. Most of the work was developed in Fontainebleau.

From mid-1970's to mid-1980's, 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 gradient, top-hat transform and the Watershed (MM's main segmentation approach).

In the 1980's and 1990's, MM gained a wider recognition, as research centers in several countries became 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 1990's and 2000's 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, ISMM's were organized every 2 or 3 years, each time in a different part of the world: Fontainebleau, France (1994); Atlanta, USA (1996); Amsterdam, Netherlands (1998); Palo Alto, CA, (2000); Sydney, Australia (2002); Paris, France (2004); and Rio de Janeiro, Brazil (2007). The next ISMM is scheduled to take place in Groningen, Netherlands, in 2009.

[edit] Binary morphology

In binary morphology, an image is viewed as a subset of an Euclidean space R^d or the integer grid Z^d, for some dimension d.

[edit] Structuring element

The basic idea in binary morphology is to probe an image with a simple, pre-defined 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 a some examples of widely used structuring elements (denoted by B):

When E=R², B is an open disk of radius r, centered at the origin.
When E=Z², 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)}.
When E=Z², B is the "cross" given by: B={(-1,0),(0,-1),(0,0),(0,1),(1,0)}.

[edit] Basic operators

The basic operations are shift-invariant (translation invariant) operators strongly related to Minkowski addition and subtraction.

Let E be an Euclidean space or an integer grid, and A a binary image in E.

[edit] Erosion

The erosion of the binary image A by the structuring element B is defined by:

$A \ominus B = \{z\in E | B_{z} \subseteq A\}$ ,

where B_z is the translation of B by the vector z, i.e., $B_z = \{b+z|b\in B\}$ , $\forall z\in E$ .

When the structuring element B has a center (e.g., 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 8 centered at the origin.

The erosion of A by B is also given by the expression: $A \ominus B = \bigcap_{b\in B} A_{-b}$ .

[edit] Dilation

The dilation of A by the structuring element B is defined by:

$A \oplus B = \bigcup_{b\in B} A_b$ .

The dilation is commutative, also given by: $A \oplus B = B\oplus A = \bigcup_{a\in A} B_a$ .

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 12, with rounded corners, centered at the origin. The radius of the rounded corners is 2.

If B is symmetrical with respect to the origin of E, then the dilation can also be obtained by: $A \oplus B = \{z \in E| (\hat{B})_{z} \cap A\neq \varnothing\}$ .

[edit] 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:

$A \circ B = (A \ominus B) \oplus B$ .

The opening is also given by $A \circ B = \bigcup_{B_x\in A} B_x$ , 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 radius 10, and a disc of radius 2 as the structuring element, the opening is a square of radius 10 with rounded corners, where the corner radius is 2.

[edit] 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:

$A \bullet B = (A \oplus B) \ominus B$ .

The closing can also be obtained by $A \bullet B = (A^{c} \circ B^{s})^{c}$ , where X^c denotes the complement of X relative to E, and X^s denotes the symmetric of X, that is, $X^{c}=\{x\in E | x\not \in X\}$ and $X^{s}=\{x\in E | -x \in X\}$ . 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.

[edit] 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 $A\subseteq C$ , then $A\oplus B \subseteq C\oplus B$ , and $A\ominus B \subseteq C\ominus B$ , etc.
The dilation is commutative.
If the origin of E belongs to the structuring element B, then $A\ominus B\subseteq A\circ B\subseteq A\subseteq A\bullet B\subseteq A\oplus B$ .
The dilation is associative, i.e., $(A\oplus B)\oplus C = A\oplus (B\oplus C)$ . Moreover, the erosion satisfies $(A\ominus B)\ominus C = A\ominus (B\oplus C)$ .
Erosion and dilation satisfy the duality $A \oplus B = (A^{c} \ominus B^{s})^{c}$ .
Opening and closing satisfy the duality $A \bullet B = (A^{c} \circ B^{s})^{c}$ .
The dilation is distributive over set union
The erosion is distributive over set intersection
The dilation is a pseudo-inverse of the erosion, and vice-versa, according to $A\subseteq (C\ominus B)$ if and only if $(A\oplus B)\subseteq C$ .
Opening and closing are idempotent.
Opening is anti-extensive, i.e., $A\circ B\subseteq A$ , whereas the closing is extensive, i.e., $A\subseteq A\bullet B$ .

[edit] Grayscale Morphology

In grayscale morphology, images are functions mapping an Euclidean space or grid E into $\mathbb{R}\cup\{\infty,-\infty\}$ , where $\mathbb{R}$ is the set of reals, $\infty$ is an element larger than any real number, and $-\infty$ is an element smaller than any real number.

Structuring elements (now called "structuring functions") and are also functions of the same format.

Denoting an image by f(x) and the structuring function by b(x), the grayscale dilation of f by b is given by

$(f\oplus b)(x)=\sup_{y\in E}[f(y)+b(x-y)]$ ,

where "sup" denotes the supremum.

Similarly, the erosion of f by b is given by

$(f\ominus b)(x)=\inf_{y\in E}[f(y)-b(y-x)]$ ,

where "inf" denotes the infimum.

Just like in binary morphology, the opening and closing are given respectively by

$f\circ b=(f\ominus b)\oplus b$ , and

$f\bullet b=(f\oplus b)\ominus b$ .

[edit] Flat structuring functions

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

$b(x)=\left\{\begin{array}{ll}0,&x\in B,\\-\infty,&\mbox{otherwise}\end{array}\right.$ ,

where $B\subseteq E$ .

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

$(f\oplus b)(x)=\sup_{z\in B^{s}}f(z-x)$ , and

$(f\ominus b)(x)=\inf_{z\in B}f(z-x)$ .

In the discrete case (E is a grid), 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 struturing element, the morphological operators rely only on the relative ordering of pixel values, not on their numerical values, and therefore are especially suited to the processing of binary images and grayscale images whose light transfer function is not known.

By combining these operators one can obtain algorithms for many image processing tasks, such as feature detection, image segmentation, image sharpening, image filtering, and granulometry.

[edit] Bibliography

Image Analysis and Mathematical Morphology by Jean Serra, ISBN 0126372403 (1982)
Image Analysis and Mathematical Morphology, Volume 2: Theoretical Advances by Jean Serra, ISBN 0-12-637241-1 (1988)
An Introduction to Morphological Image Processing by Edward R. Dougherty, ISBN 0-8194-0845-X (1992)
Pierre Soille, "Introduction" in Mathematical Morphology and Its Applications to Image Processing, J. Serra and P. Soille (Eds.), pp. 1-4, ISBN 0-7923-3093-5 (1994)
Jean Serra, "Appendix A: The 'Centre de Morphologie Mathématique', and overview" in Mathematical Morphology and Its Applications to Image Processing, J. Serra and P. Soille (Eds.), pp. 369-374, ISBN 0-7923-3093-5 (1994)
Christian Ronse, Laurent Najman, and Etienne Decencière, "Foreword" in Mathematical Morphology: 40 Years On, ISBN-10: 1-4020-3442-3 (2005)

[edit] External links

Lectures on Image Processing: A collection of 18 lectures in pdf format from Vanderbilt University. Lectures 16-18 are on Mathematical Morphology, by Alan Peters
Center of Mathematical Morphology, Paris School of Mines
History of Mathematical Morphology, by Jean Serra
Morphology Digest, a newsletter on mathematical morphology, by Pierre Soille
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

Categories: Image processing | Digital geometry