User:Renatokeshet/Topological skeleton

Binary morphology

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

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 are some examples of widely used structuring elements (denoted by B):

• Let $E=\mathbb {R} ^{2}$; B is an open disk of radius r, centered at the origin.
• Let $E=\mathbb {Z} ^{2}$; 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 $E=\mathbb {Z} ^{2}$; B is the "cross" given by: B={(-1,0), (0,-1), (0,0), (0,1), (1,0)}.

Basic operators

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.

Erosion

The erosion of the dark-blue square by a disk, resulting in the light-blue square.

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., 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\ominus B=\bigcap _{b\in B}A_{-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".

Dilation

The dilation of the dark-blue square by a disk, resulting in the light-blue square with rounded corners.

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

The dilation can also be obtained by: $A\oplus B=\{z\in E|(B^{s})_{z}\cap A\neq \varnothing \}$, where B^s denotes the symmetric of B, that is, $B^{s}=\{x\in E|-x\in B\}$.

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 the dark-blue square by a disk, resulting in the light-blue square with round corners.

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}\subseteq 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.

Example application: Let's assume someone has written a note on a non-soaking 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 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.

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 (that is, $X^{c}=\{x\in E|x\not \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.

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, in the following sense: $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$.

Grayscale morphology

Watershed of the gradient of the cardiac image

In grayscale morphology, images are functions mapping a 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.

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

$(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$.

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

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 $(L,\leq )$ be a complete lattice, with infimum and minimum symbolized by $\wedge$ and $\vee$, respectively. Its universe and least element are symbolized by U and $\emptyset$, respectively. Moreover, let $\{X_{i}\}$ be a collection of elements from L.

A dilation is any operator $\delta :L\rightarrow L$ that distributes over the supremum, and preserves the least element. I.e.:

• $\bigvee _{i}\delta (X_{i})=\delta \left(\bigvee _{i}X_{i}\right)$,
• $\delta (\emptyset )=\emptyset$.

An erosion is any operator $\varepsilon :L\rightarrow L$ that distributes over the infimum, and preserves the universe. I.e.:

• $\bigwedge _{i}\varepsilon (X_{i})=\varepsilon \left(\bigwedge _{i}X_{i}\right)$,
• $\varepsilon (U)=U$.

Dilations and erosions form Galois connections. That is, for all dilation $\delta$ there is one and only one erosion $\varepsilon$ that satisfies

$X\leq \varepsilon (Y)\Leftrightarrow \delta (X)\leq Y$

for all $X,Y\in L$.

Similarly, for all erosion there is one and only one dilation satisfying the above connection.

Furthermore, if two operators satisfy the connection, then $\delta$ must be a dilation, and $\varepsilon$ 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 vice-versa.

Opening and Closing

For all adjunction $(\varepsilon ,\delta )$, the morphological opening $\gamma :L\rightarrow L$ and morphological closing $\phi :L\rightarrow L$ are defined as follows:

$\gamma =\delta \varepsilon$, and

$\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.

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 $\leq$ 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 $\mathbb {R} \cup \{\infty ,-\infty \}$, and $\leq$, $\vee$, and $\wedge$, are the point-wise order, supremum, and infimum, respectively. That is, is f and g are functions in L, then $f\leq g$ if and only if $f(x)\leq g(x),\forall x\in E$; the infimum $f\wedge g$ is given by $(f\wedge g)(x)=f(x)\wedge g(x)$; and the supremum $f\vee g$ is given by $(f\vee g)(x)=f(x)\vee g(x)$.

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 0-12-637241-1 (1988)
• An Introduction to Morphological Image Processing by Edward R. Dougherty, ISBN 0-8194-0845-X (1992)
• Morphological Image Analysis; Principles and Applications by Pierre Soille, ISBN 3540-65671-5 (1999), 2nd edition (2003)

External links

• Fast morphological erosions, dilations, openings, and closings

[[Category:Image processing]] [[Category:Digital geometry]] [[Category:Mathematical morphology]]