Morphology

Morphology is a part of image processing, somewhat different from earlier topics discussed in this course, although we have touched upon it earlier. It involves non-linear operators operating on objects in an image, and is useful in many aspects such as ¹

image preprocessing,
enhancing object structure,
object segmentation,
quantitative object description.

Although morphology can be understood in the same way for both binary images and general graylevel images, it can be useful to view them separately. Most of this content can also be found in the text book ², albeit with some different notation.

General overview

Let our image be defined as

$\begin{align} f &:\quad \Omega \to \mathbb{R} \\ &:\quad x \mapsto f(x), \end{align}$

where $\Omega \subset \mathbb{R}^{d}$ for a $d$ dimensional image. In a similar way, we define a function

$\begin{align} s &:\quad \Omega_s \to \mathbb{R} \\ &:\quad y \mapsto s(y), \end{align}$

sometimes called a structuring element, where $\Omega_s \subset \mathbb{R}^{d}$ for a $d$ dimensional structure element. From this, we can define some common morphological operators.

Dilation

$\begin{align} f \oplus s &:\quad \Omega \to \mathbb{R} \\ &:\quad x \mapsto \sup_{\substack{y \in \Omega_s \\ x - y \in \Omega}} \{f(x - y) + s(y)\} \end{align}$

Erosion

$\begin{align} f \ominus s &:\quad \Omega \to \mathbb{R} \\ &:\quad x \mapsto \inf_{\substack{y \in \Omega_s \\ x + y \in \Omega}} \{f(x + y) - s(y)\} \end{align}$

Opening

$f \circ s = (f \ominus s) \oplus s. \label{eq:opening} \tag{1}$

Closing

$f \bullet s = (f \oplus s) \ominus s. \label{eq:closing} \tag{2}$

For the above operators, the following convenient relation apply

$(f \ominus s)(x) \le (f \circ s)(x) \le f(x) \le (f \bullet s)(x) \le (f \oplus s)(x) \label{eq:relation} \tag{4}$

provided that $s(y) \ge 0 \quad \forall y \in \Omega_s$ .

Graylevel images

Now, our image is defined as

$\begin{align} f &:\quad \Omega \to \mathbb{N} \\ &:\quad x \mapsto f(x), \end{align}$

where the range is $\{0, 1, \cdots, 2^b - 1\}$ for a $b$ -bit image, and the discrete image has domain $\Omega \subset \mathbb{Z}^d$ . The structuring element is now

$\begin{align} s &:\quad \Omega_s \to \mathbb{N} \\ &:\quad y \mapsto s(y), \end{align}$

where $\Omega_s \in \mathbb{Z}^d$ . The litterature often differentiate between a flat structuring element where $s(y) = \alpha$ for all $y \in \Omega_s$ , and a non-flat structuring element where the values vary.

Dilation is now

$(f \oplus s)(x) = \max_{\substack{y \in \Omega_s \\ x - y \in \Omega}} \{f(x - y) + s(y)\} \label{eq:dilation} \tag{4}$

and erosion is given by

$(f \ominus s)(x) = \min_{\substack{y \in \Omega_s \\ x + y \in \Omega}} \{f(x + y) - s(y)\}. \label{eq:erosion} \tag{5}$

The equations for morphological opening in Equation \eqref{eq:opening} and morphological closing in Equation \eqref{eq:closing} still apply.

For some reason, some authors use different definitions with flat structuring elements. These definitions are as the ones above, but without adding or substracting the value of the structure element, which is equivalent to using a flat structuring element with $\alpha = 0$ in the definition above (Equation \eqref{eq:dilation} and Equation \eqref{eq:erosion}). Some common grey-level operations follow.

Top-hat and bottom-hat transformation

The top-hat transformation detects bright regions on a dark background

$T_s(f)(x) = f(x) - (f \circ s)(x)$

The bottom-hat detects dark regions on a bright background

$B_s(f)(x) = (f \bullet s)(x) - f(x)$

Morphological filtering

To filter bright noise, apply opening followed by closing

$b_s(f)(x) = ((f \circ s) \bullet s)(x)$

To filter dark noise, apply closing followed by opening

$d_s(f)(x) = (f \bullet s) \circ s)(x)$

The rationale is that opening smooths bright values down, and closing smooths dark values up.

Morphological gradient

Grey level dilation will under certain conditions produce an image with equal or brighter values, likewise, grey level erosion will produce an image with equal or darker values. With this we can produce an image that highlights contrast difference by looking at the difference between dilation and erosion

$G_s(f)(x) = (f \oplus s)(x) - (f \ominus s)(x)$

Binary image

In this case it is more common to use a set-theoretic (more formally, a naive-set theoretic) representation, but for consistency, we first show the functional representation.

Functional representation

Our image is defined as

$\begin{align} f &:\quad \Omega \to \{0,1\} \\ &:\quad x \mapsto f(x), \end{align}$

and the structuring element as

$\begin{align} s &:\quad \Omega_s \to \{0\} \\ &:\quad y \mapsto 0, \end{align}$

Note that we have defined $s$ to only map to zero, this is in order to be consistent with what is defined as binary morphology, which sometimes only cares about restructuring the foreground and background regions of the original image. But as we shall see, this is also what happens when employing the definition above.

Dilation now becomes

$(f \oplus s)(x) = \max_{\substack{y \in \Omega_s \\ x - y \in \Omega}} \{f(x - y)\}$

and erosion is given by

$(f \ominus s)(x) = \min_{\substack{y \in \Omega_s \\ x + y \in \Omega}} \{f(x + y)\}.$

Set representation

Let our image be represented on a two-dimensional lattice, where each pixel has a position and a value (either foreground or background). Let $F(A) \subset A$ be the set of foreground elements of in some image region $A$ , and $B(A) \subset A$ be the set of background elements. They make up a partition of $A$ such that $F(A) \cup B(A) = A$ and $F(A) \cap B(A) = \varnothing$ . For some set $\Omega$ , let us write $\Omega_F = F(\Omega)$ and $\Omega_B = B(\Omega)$ , then the foreground elements of the dilation and erosion operator becomes

$F(f \oplus s)) = \{x \in \Omega : (x + \Omega_s) \cap \Omega_F \neq \varnothing\}$ $F(f \ominus s)) = \{x \in \Omega : (x + \Omega_s) \subset \Omega_F\}$

where $x + \Omega_s = \{x + y : y \in \Omega\}$ . This shows the relationship between the functional notation we used for graylevel images, and the notation we will use below, which is most common for binary images.

Dilation of an object $A \subset \Omega$ with and object $S$ becomes

$A \oplus S = \{x \in \Omega : (x + S) \cap A \neq \varnothing\}$

and erosion of $A$ by $S$ is given by

$A \ominus S = \{x \in \Omega : (x + S) \subset A\}.$

Opening and closing are still defined in the same way from dilation and erosion, and we have that

$(A \ominus S) \subset (A \circ S) \subset A \subset (A \bullet S) \subset (A \oplus S)$

analogous to the relation in Equation \eqref{eq:relation}.

The other operations given above is also valid (and more or less useful) for binary images using the diation and erosion operators defined. Some additional operations and applications is also worth mentioning.

Edge detection

The dilated edge of $A$ by $S$ is given by

$\partial_S^D(A) = (A \oplus S) \setminus A$

while the eroded edge is given by

$\partial_S^E(A) = A \setminus (A \ominus S),$

where $X \setminus Y$ denotes the relative compliment (set-theoretic difference) of the set $Y$ in $X$ , $X \setminus Y = \{x \in X : x \notin Y\}$ .

Hit-or-miss transformation

This is used to detect the location of a given object $S = (S_f, S_b)$ in an object $A$ . Often $A$ and $S_f$ is a set of foreground elements, and $S_b$ is a set of bacground elements. So this hit-or-miss-transformation $A \circledast S$ gives the locations of the origin of $S$ in $A$ where $S_f \subset A$ and $S_b \subset A^c$ .

$A \circledast S = (A \ominus S_f) \cap (A^c \ominus S_b)$

where $A^c$ is the compliment of $A \subset \Omega$ , $A^c = \{x \in \Omega : x \notin A\}$ .

Convex hulls

The convex hull $C(A)$ of $A \subset \Omega_F$ is the smallest convex set covering $A$ . This can be found with morphology in the following way.

Define four structuring elements, where the idea of a foreground and background part from the hit-or-miss transformation apply. In the following, the non-zero elements of the structuring element superscripted with hit must match the pattern of $A$ , while the non-zero elements in the structuring element superscirpted with miss must match the pattern of $A^c$ .

$S_1^{hit}: \begin{array}{|c|c|c|} \hline 1 & 0 & 0 \\ \hline 1 & 0 & 0 \\ \hline 1 & 0 & 0 \\ \hline \end{array}, \quad S_1^{miss}: \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline 0 & 1 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array},$ $S_2^{hit}: \begin{array}{|c|c|c|} \hline 1 & 1 & 1 \\ \hline 0 & 0 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array}, \quad S_2^{miss}: \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline 0 & 1 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array},$ $S_3^{hit}: \begin{array}{|c|c|c|} \hline 0 & 0 & 1 \\ \hline 0 & 0 & 1 \\ \hline 0 & 0 & 1 \\ \hline \end{array}, \quad S_3^{miss}: \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline 0 & 1 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array},$ $S_4^{hit}: \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline 0 & 0 & 0 \\ \hline 1 & 1 & 1 \\ \hline \end{array}, \quad S_4^{miss}: \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline 0 & 1 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array}.$

For each $S_i$ , apply hit-or-miss on $A$ with $S_i$ until no changes occur, and let $D_i = A \cup (A \circledast S_i)$ . Then, $C'(A) = \cup_{i = 1}^4 D_i$ is a convex region covering $A$ , but it is not necesseraly the smallest one.

To get a smaller one, we intersect this with the rectangle element $M$ which is the smallest rectangle region covering $A$ , i.e.

$M = \{x = (x_1, x_2) \in \Omega \subset \mathbb{Z}^2 : x_1 \in [x_1^{min}, x_1^{max}], x_2 \in [x_2^{min}, x_2^{max}]\}$

where

$\begin{align} x_1^{min} &= \min\{x_1 : (x_1, x_2) \in A\}, \\ x_1^{max} &= \max\{x_1 : (x_1, x_2) \in A\}, \\ x_2^{min} &= \min\{x_2 : (x_1, x_2) \in A\}, \\ x_2^{max} &= \max\{x_2 : (x_1, x_2) \in A\}. \end{align}$

Finally, $C(A) = C'(A) \cap M$ .

Extracting connected components

This is used to detect, or extract a connected component $A \subset \Omega_F \subset \Omega$ . The idea is to grow a region $C \subset A$ until all connected components of $C$ are accounted for. First set $C_0$ equal to a point $x \in A$ . Dilate $C_0$ with either a square- or a plus-shaped structuring element $S$ , and let $C_1$ be the intersection of this dilated region and the original region $A$ .

$\begin{align} C_0 &= x \in A \\ C_k &= (C_{k-1} \oplus S) \cap A, \quad k = 1, \cdots, K. \end{align}$

This continues iteratively until we see no change, i.e. $K$ is the first iteration $k$ where $C_k = C_{k - 1}$ .

This can be seen as region growing, and applied to the compliment $A^c$ it can be used to fill holes.

Thinning and thickening

Thinning a region $A$ with an object $S$ can be defined as

$\begin{align} A \otimes S &= A \setminus (A \circledast S) \\ &= A \cap (A \circledast S)^c \end{align}$

But a more useful approach is a sequential thinning with multiple structuring elements, which, when defined with the hit-or-miss notation above are

$S_1^{hit}: \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline 0 & 1 & 0 \\ \hline 1 & 1 & 1 \\ \hline \end{array}, \quad S_1^{miss}: \begin{array}{|c|c|c|} \hline 1 & 1 & 1 \\ \hline 0 & 0 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array}.$ $S_2^{hit}: \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline 1 & 1 & 0 \\ \hline 1 & 1 & 0 \\ \hline \end{array}, \quad S_2^{miss}: \begin{array}{|c|c|c|} \hline 0 & 1 & 1 \\ \hline 0 & 0 & 1 \\ \hline 0 & 0 & 0 \\ \hline \end{array}.$

Following this pattern, where $S_{i+1}$ is rotated clockwise w.r.t. $S_i$ , we continue this until

$S_8^{hit}: \begin{array}{|c|c|c|} \hline 0 & 0 & 0 \\ \hline 0 & 1 & 1 \\ \hline 0 & 1 & 1 \\ \hline \end{array}, \quad S_9^{miss}: \begin{array}{|c|c|c|} \hline 1 & 1 & 0 \\ \hline 1 & 0 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array}.$

With this, we apply the iteration

$\begin{align} D_0 &= A \\ D_k &= D_{k-1} \otimes \{S_1, \cdots, S_8\} = ( \cdots ((D_{k-1} \otimes S_1) \otimes S_2) \cdots ) \otimes S_8 \end{align}$

for $K$ iterations until $D_K = D_{K-1}$ and we terminate with $D_K$ as the result of the thinning.

In the same manner, we define the dual operator thickening

$A \odot S = A \cup (A \circledast S),$

which also can be defined as a sequential operation analogous to thinning.

Skeleton

The skeleton $T(A)$ of $A$ can be obtained via a structuring element $S$ as

$T(A) = \cup_{k = 0}^K T_k(A)$

with

$T_k(A) = (A \ominus kS) \setminus ((A \ominus kS) \circ S)$

where $(A \ominus kS)$ denote $k$ successive erosions of $A$ with $S$

$A \ominus kS = ( \cdots ((A \ominus S) \ominus S) \cdots ) \ominus S$

and $K$ is the last iteration before $A$ is eroded to the empty set

$K = \max \{k : (A \ominus kS) \neq \varnothing\}.$

It can be shown that $A$ can be reconstructed from this skeleton via

$A = \cup_{k = 0}^K (T_k(A) \oplus kS).$

References

Milan Sonka, Vaclav Hlavac, Roger Boyle. Image Processing, Analysis, and Machine Vision. 2008. ↩
Rafael C. Gonzalez, Richard E. Woods. Digital Image Processing. 3rd ed. 2008. ↩