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, were introduced 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.
The basic morphological operators are erosion, dilation, opening and closing.
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.
Mathematical Morphology was developed in 1964 by 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: Hit-or-miss 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 the mid-1970s to mid-1980s, 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, top-hat 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, especially in the field of non-linear filtering of noisy images.
In 1986, 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: Fontainebleau, France (1994); Atlanta, USA (1996); Amsterdam, Netherlands (1998); Palo Alto, CA, USA (2000); Sydney, Australia (2002); Paris, France (2005); Rio de Janeiro, Brazil (2007); Groningen, Netherlands (2009); Intra (Verbania), Italy (2011); Uppsala, Sweden (2013); Reykjavík, Iceland (2015); Fontainebleau, France (2017); and Saarbrücken, Germany (2019).[1]
Rd
Zd
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 the 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):
E=R2
E=Z2
E=Z2
The basic operations are shift-invariant (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.
The erosion of the binary image A by the structuring element B is defined by
A\ominusB=\{z\inE|Bz\subseteqA\},
where Bz is the translation of B by the vector z, i.e.,
Bz=\{b+z\midb\inB\}
\forallz\inE
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
A\ominusB=capbA-b
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".
The dilation of A by the structuring element B is defined by
A ⊕ B=cupbAb.
The dilation is commutative, also given by
A ⊕ B=B ⊕ A=cupaBa
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
A ⊕ B=\{z\inE\mid
| s) | |
| (B | |
| z |
\capA ≠ \varnothing\}
Bs=\{x\inE\mid-x\inB\}
Example application: dilation is the dual operation 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.
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\circB=(A\ominusB) ⊕ B.
The opening is also given by
A\circB=
| cup | |
| Bx\subseteqA |
Bx
Example application: Let's assume someone has written a note on a non-soaking paper and that the writing looks as if 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.
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\bulletB=(A ⊕ B)\ominusB.
The closing can also be obtained by
A\bulletB=(Ac\circBs)c
Xc=\{x\inE\midx\notinX\}
Here are some properties of the basic binary morphological operators (dilation, erosion, opening and closing):
A\subseteqC
A ⊕ B\subseteqC ⊕ B
A\ominusB\subseteqC\ominusB
A ⊕ B=B ⊕ A
A\ominusB\subseteqA\circB\subseteqA\subseteqA\bulletB\subseteqA ⊕ B
(A ⊕ B) ⊕ C=A ⊕ (B ⊕ C)
(A\ominusB)\ominusC=A\ominus(B ⊕ C)
A ⊕ B=(Ac\ominusBs)c
A\bulletB=(Ac\circBs)c
A\subseteq(C\ominusB)
(A ⊕ B)\subseteqC
A\circB\subseteqA
A\subseteqA\bulletB
In grayscale morphology, images are functions mapping a Euclidean space or grid E into
R\cup\{infty,-infty\}
R
infty
-infty
Grayscale structuring elements are also functions of the same format, called "structuring functions".
Denoting an image by f(x) the structuring function by b(x) and the support of b by B, the grayscale dilation of f by b is given by
(f ⊕ b)(x)=\supy[f(x-y)+b(y)],
where "sup" denotes the supremum.
Similarly, the erosion of f by b is given by
(f\ominusb)(x)=infy[f(x+y)-b(y)],
where "inf" denotes the infimum.
Just like in binary morphology, the opening and closing are given respectively by
f\circb=(f\ominusb) ⊕ b,
f\bulletb=(f ⊕ b)\ominusb.
It is common to use flat structuring elements in morphological applications. Flat structuring functions are functions b(x) in the form
b(x)=\begin{cases} 0,&x\inB,\\ -infty&otherwise, \end{cases}
where
B\subseteqE
In this case, the dilation and erosion are greatly simplified, and given respectively by
(f ⊕ b)(x)=
| \sup | |
| z\inBs |
f(x+z),
(f\ominusb)(x)=infzf(x+z).
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.
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.Along this line one should also look into Continuous Morphology[2]
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").
Let
(L,\leq)
\wedge
\vee
\emptyset
\{Xi\}
A dilation is any operator
\delta\colonL → L
veei\delta(Xi)=\delta\left(veeiXi\right)
\delta(\emptyset)=\emptyset
An erosion is any operator
\varepsilon\colonL → L
wedgei\varepsilon(Xi)=\varepsilon\left(wedgeiXi\right)
\varepsilon(U)=U
Dilations and erosions form Galois connections. That is, for every dilation
\delta
\varepsilon
X\leq\varepsilon(Y)\Leftrightarrow\delta(X)\leqY
for all
X,Y\inL
Similarly, for every erosion there is one and only one dilation satisfying the above connection.
Furthermore, if two operators satisfy the connection, then
\delta
\varepsilon
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 vice versa.
For every adjunction
(\varepsilon,\delta)
\gamma\colonL\toL
\phi\colonL\toL
\gamma=\delta\varepsilon,
\phi=\varepsilon\delta.
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 anti-extensive. Algebraic closings are operators in L that are idempotent, increasing, and extensive.
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
\leq
Similarly, grayscale morphology is another particular case, where L is the set of functions mapping E into
R\cup\{infty,-infty\}
\leq
\vee
\wedge
f\leqg
f(x)\leqg(x),\forallx\inE
f\wedgeg
(f\wedgeg)(x)=f(x)\wedgeg(x)
f\veeg
(f\veeg)(x)=f(x)\veeg(x)