---
tags: image processing
---
{%hackmd theme-dark %}
# Morphological Image Processing
[TOC]
## Fundamentals
### basic terminology
In image processing, we use morphology with two types of set of pixels:
1. ***objects***
Sets of **foreground** pixels.

2. ***structure elements***
Specified in terms of **both** foreground and background pixels (sometimes we don't care about if the pixel is foreground or background so we denoted it by $\times$)
SE elements are used in a form similar to spatial convolution kernels (also have padding and sliding through the image).

### basic sets
For convinient, we represent the origin of a set (SE) in figures using a dot ($\cdot$):

#### reflection of a set
A ***reflection*** of a set (SE) $B$ about its origin, denoted by $\hat B$, is defined as
$$
\hat B = \{w | w = -b, b \in B \}
$$
Some examples:

#### translation of a set
A ***translation*** of a set $B$ by point $z = (z_1, z_2)$ denoted $(B)_z$ is defined as
$$
(B)_z = \{c | c = b + z, b \in B\}
$$
For example:

## Erosion and Dilation

### erosion
With $A$ and $B$ as sets in $Z^2$, the ***erosion*** of $A$ by $B$, denoted $A \ominus B$, is defined as
$$
A \ominus B = \left\{ z \middle| (B)_z \subseteq A \right\}
$$
For example, consider the following figure:
The translation of $B$ by point $z_1$ denoted by $(B)_{z_1}$ is not a subset of $A$. Therefore, $z_1$ is not a element in $A \ominus B$. On the other hand, $(B)_{z_2}$ doesn't share any common elements with the background and thus $z_2$ is in $A \ominus B$.

### dilation
The ***dilation*** of $A$ by $B$ is the set of all displacements, z, such that the foreground elements of $\hat B$ overlap at least one element of $A$:
$$
A \oplus B = \left\{ z \middle| [(\hat B)_z \ \cap A \neq \phi \right\}
$$
(Note that $B$ **is reflected** before being operated with $A$)
Example:
We can designed the SE to achieve more dilation vertically than horizontally:
The result becomes

> **Example**
> Use dilation to repaire broken characters in an image:
> 

### Duality
Erosion and dilation are ***duals*** **of each other** with respect to set complementation and reflection. That is,
$$
(A \ominus B)^c = A^c \oplus \hat B
$$
and
$$
(A \oplus B)^c = A^c \ominus B
$$
where $A^c$ is the set of background pixels. The following is a illustration of the first duality:
#### proof
$$
\begin{align}
(A \ominus B)^c
&=
\left\{ z | (B)_z \cap A \subseteq A\right\}^c
\notag \\
&=
\left\{ z | (B)_z \cup A^c = \phi\right\}^c
\notag \\
&=
\left\{ z | (B)_z \cup A^c \neq \phi\right\}
\end{align}
$$
Notice that the reflection of $\hat B$ is $B$. Thus, by the definition of dilation, we have
$$
\begin{align}
(A \ominus B)^c
&=
\left\{ z | (B)_z \cup A^c \neq \phi\right\}
\notag \\
&= A^C \oplus \hat B
\end{align}
$$

## Opening and Closing
### opening
The ***opening*** of set $A$ by structuering element $B$, denoted by $A \circ B$, is defined as
$$
A \circ B =
(A \ominus B) \oplus B
$$
Geometrical interpretation: The opening of $A$ by $B$ is the union of all the translations of $B$ so that $B$ **fit entirely in** $A$. The following is a illustration:
Observe that the resuling opening is a set composed of 2 disjoint subsets because $B$ could not fit in the narrow segment in the center of $A$.
$\Rightarrow$ Opening tends to **eliminate regions narrower than the SE**.

The interpretation that the opening of A by B is the union of all the translations of B such that B fits entirely within A can be written in equation form as
$$
A \circ B = \bigcup \left\{ (B)_z \middle | (B)_z \subseteq A \right\}
$$

### closing
The ***closing*** of set $A$ by structure elements $B$, denoted $A \bullet B$, is defined as
$$
A \bullet B = (A \oplus B) \ominus B
$$
Closing has a similar geometric interpretation, except that now we translate $B$ **outside** $A$. The closing is then the **complement of the union of all translations of $B$ that do not overlap**:
Based on this interpretation, we can write the closing of $A$ by $B$ as
$$
A \bullet B
= \left[
\bigcup \left\{
(B)_z \middle | (B)_z \cap A = \phi
\right\}
\right]^c
$$

>**Example**
>
> Unlike opening, closing tends to join narrow breaks, fills long thin gulfs, and fills objects smaller than the structuring element.

### duality
Opening and closing are duals of each other with respect to set complementation and reflection:
$$
\begin{align}
(A \circ B)^c = (A^c \bullet \hat B)
\end{align}
$$
and
$$
\begin{align}
(A \bullet B)^c = (A^c \circ \hat B)
\end{align}
$$

### properties
Opening has the following properties:
* $A \circ B \subseteq A$
* $C \subseteq D \Rightarrow C \circ B \subseteq D \circ B$
* $(A \circ B) \circ B = A \circ B$ (mutiple openings of a set **have no effect after the operation has been applies once.)
Similarly, closing satisfies the following properties:
* $A \subseteq A \bullet B$
* $C \subseteq D \Rightarrow C \bullet B \subseteq D \bullet B$
* $(A \bullet B) \bullet B = A \bullet B$ (mutiple closing of a set **have no effect** after the operation has been applies once.)

## The Hit-or-miss Transform
The morphological ***hit-or-miss transform*** (HMT) is a basic tool for **shape detection**.

Let $I$ be a binary image composed of foreground ($A$) and background pixels, respectively.The HMT utilizes *two* structuring elements: $B_1$ , for detecting shapes in the foreground, and $B_2$ , for detecting shapes in the background. The HMT of image $I$ is defined as
$$
\begin{align}
I \circledast B_{1, 2}
&= \left\{
z \middle |
(B_1)_z \subseteq A,
(B_2)_z \subseteq A^c
\right\}
\\
&= (A \ominus B_1) \cap (A^c \ominus B_2)
\end{align}
$$
In words, this equation says that the morphological HMT is the set of translations, $z$, of structuring elements $B_1$ and $B_2$ such that, **simultaneously**, $B_1$ found a match in the foreground (i.e., $B_1$ is contained in $A$) and $B_2$ found a match in the background (i.e., $B_2$ is contained in $A^c$).

Concept: the nature of a shape is characterized by the geometrical arrangement of **both foreground and background pixels**.

> **Example**
> Suppose we want to fine the location of the origin of object (set) $D$ in the image $I$：
>
> We let $B_1$ to be equal to $D$ itself. Because $D$ is composed of background elements in $I^c$, and terosion works with foreground elements, $B_2$ has to be desined to **detect the border of** $D$, which is composed of foreground pixels in $I^c$.
> $\Rightarrow$ It consists of a rectangle of foreground elements **one pixel thick**. The size of the rectangle is such that is enclosed the size of $D$.

Actually, the operations in the previous example can be redefined as follows:
We define a structuring element, $B$, identical to $D$, but **having in addition a border of background elements with a width of one pixel**:
We can use a structuring element formed in such a way to restate the HMT as
$$
\begin{align}
I \circledast B = \left\{
z \middle | (B)_z \subseteq I
\right\}
\end{align}
$$
The form is the same as erosion, but now we test to see if $(B)_z$ is a subset of image $I$, which is composed of **both foreground and background pixels**.

For example, the following SE is designed to detect one-pixel holes:

The following SE is capable of detecting the foreground corner pixel of the top:

The following SE shows a SE composed of foreground, background, and **“don’t care”** elements (denoted by $\times$). You can think of the value of a don’t care element as **always matching its corresponding pixel** in an image:

## Basic Morphological Algorithms
### boundary extraction
The boundary of a set $A$ of foreground pixels, denoted by $\beta(A)$, can be obtrained by first eroding $A$ by a suitable structureing element $B$, and then performing the set difference between $A$ and its erosion. That is,
$$
\begin{align}
\beta(A) = A - (A\ominus B)
\end{align}
$$
Illustration:

### hole filling
Problem:
Let $A$ denote a set whose elements are 8-connected boundaries, with each boundary enclosing a background region (hole). Given a point *in each hole*, the objective is to fill all the holes with foreground elements (1's).

First, we begin by forming an array $X_0$ (same size as $I$) of 0's and set the pixels that are **known to be holes** to $1$. For example:
Then we use the following procedure to fill all the holes with 1's:
$$
\begin{align}
X_k = (X_{k-1} \oplus B) \cap I^c
\end{align}
$$
The procedure terminate when $X_k = X_{k-1}$. The dilation is used to enlarge the area to be filled and the intersection at each step with $I^c$ **limits the result to inside the region of interest**. See an example:

This procedure can be automated completed without denoting the point in each hole using [this algorithm](#automatic-algorithm-for-filling-holes).
### extraction of connected components
Similar to [hole filling](#Hole-Filling), we first form an image $X_0$ whose elements are 0, except each location know to correspond to a point in each connected component in $A$ which we set to foreground value. Then we apply:
$$
\begin{align}
X_k = (X_{k-1} \oplus B) \cap I
\end{align}
$$

### thining
Thinning of a set $A$ of foreground pixels by a SE $B$, denoted $A \otimes B$, can be defined in terms of the HMT:
$$
\begin{align}
A \odot B = A - (A \circledast B) \\
= B \cap (A \circledast B)^c
\end{align}
$$
For thinning $A$ **symmertrically**, a more useful expression is based on a *sequence* of SEs:
$$
\begin{align}
\{ B \} = \{ B^1, B^2, \ldots , B^n\}
\end{align}
$$
Now we define thinning by a seqence of SEs as
$$
\begin{align}
A \otimes \{B\} = \left(
\left(
\ldots \left(
\left(
A \otimes B^1
\right)
\otimes B^2
\right)
\right) \ldots B^n
\right)
\end{align}
$$
The entire process is repeated until no further changes occur after one complete pass through all SEs.

The following is a set of SEs used routinely for thinning:
(Note that $B^i$ is equal to $B^{i-1}$ rotated clockwise by $45^\circ$)
Using this set of SEs to thin $A$:

### thickening
Thickening is defined by
$$
\begin{align}
A \odot B = A \cup (A \circledast B)
\end{align}
$$
where $B$ is a ES for thickening. As in thinning, thickening can be defined as a sequential operation:
$$
\begin{align}
A \odot \{B\} = \left(
\left(
\ldots \left(
\left(
A \odot B^1
\right)
\odot B^2
\right)
\right) \ldots \odot B^n
\right)
\end{align}
$$
The SE used for thickening have the **same form** as those in thinning but with **all 1's and 0's interchanged**.

Actually, thickening is the **morphological dual** of thinning. Thus, a usual procedure for thickening is as following:
1. Thin the **background** ($A^c$) of the set in question.
2. **Complement the result**.
Depending on the structure of $A$, this procedure can **result in disconnected points**:
Note that the thinned background *forms a boundary for the thickening process*, which is a useful feature not presenting in the direct implementation of thickening using the original definition.

### skeletons
The notion of a ***skeleton*** $S(A)$ of a set $A$ is intuitively simple:
We deduce from this figure that
1. If $z$ is a point of $S( A)$, and $( D )_z$ is the *largest* disk centered at $z$ and contained in $A$
$\Rightarrow$ *one cannot find a larger disk* (not necessarily centered at $z$) containing $( D )_z$ and simultaneously included in $A$. A disk $( D )_z$ satisfying these conditions is called a maximum disk.
2. If $( D )_z$ is a maximum disk, it *touches the boundary* of $A$ at **two or more** different places.

The skeleton of $A$ can be expressed in terms of erosions and opennings. That is, it can be [shown](https://books.google.com.tw/books/about/Image_Analysis_and_Mathematical_Morpholo.html?id=RQIUAQAAIAAJ&redir_esc=y) that
$$
\begin{align}
S(A) = \bigcup_{k=1}^K S_k(A)
\end{align}
$$
with
$$
\begin{align}
S_k(A) = (A \ominus kB) - (A \ominus kB) \circ B
\end{align}
$$
where $B$ is a SE, and $(A \ominus kB)$ indicates $k$ **sucessive erosions** starting with $A$. That is:
$$
\begin{align}
A \ominus kB = \left(
\left(
\ldots \left(
\left(
A \ominus B
\right)
\ominus B
\right)
\right) \ldots \ominus B
\right)
\end{align}
$$
, where $K$ is the last iterative step before $A$ erodes to an empty set.

It can be shown that $A$ can be reconstructed from the subsets $S_0, \ldots, S_k$:
$$
A = \bigcup_{k=1}^K (S_k(A) \oplus kB)
$$
where $(S_k(A) \oplus kB)$ is
$$
\begin{align}
\left(
\left(
\ldots \left(
\left(
S_k (A) \oplus B
\right)
\oplus B
\right)
\right) \ldots \oplus B
\right)
\end{align}
$$
Example:

## Morphological Reconstruction
### geodesic dilation and erosion
Let $F$ denote the marker image and $G$ the mask image. We assume in this discussion that both are binary images and that $F \subseteq G$. The ***geodesic dilation of size 1*** of the marker image with repect to the mask, denoted by $D_G^{(1)} (F)$, is defined as
$$
D_G^{(1)} (F) = (F \oplus B) \cap G
$$
The ***geodesic dilation of size n*** of $F$ with respect to $G$ is recursively defined as
$$
D_H^{(n)} = D_G^{(1)}
\left(
D_G^{(n-1)} (F)
\right)
$$
where $n \ge 1$ and $D_G^{(0)} (F) = F$. The intersection operation guarantees that mask $G$ will **limit the growth (dilation) of marker** $F$.
> **Example**
> The following is a simple example of a geodesic dilation of size 1:
> 

The ***geodesic erosion of size 1*** of marker $F$ with respect to mask $G$ is defined as
$$
E_G^{(1)} (F) = (F \ominus B) \cup G
$$
The geodesic erosion of size n of $F$ with respect to $G$ is defined as
$$
E_G^{(n)} (F) = E_G^{(1)} \left( E_G^{(n-1)} (F)\right)
$$
where $n \ge 1$ and $E_G^{(0)} (F) = F$. The set union is performed at each step, and guarantees that geodesic erosion of an image remains greater than or equal to its mask image.
> **Eample**
> The following is an illustraion of a geodesic erosion of size:
> 

Actually, geodesic dilation and erosion are duals with respect to set complementation.

### morphological reconstruction by dilation and by erosion
Morphological reconstruction by dilation of a marker image $F$ with respect to a mask imgae $G$, denoted $R_G^D(F)$, is defined as the geodesic dilation of $F$ with respect to $G$, iterated **until stability is achieved**; that is,
$$
R_{G}^{D}(F)=D_{G}^{(k)}(F)
$$
with k such that $D_{G}^{(k)}(F)=D_{G}^{(k+1)}(F)$.
> **Example**
> Continue from the previous example, the following figure is the illustration of morphological reconstruction:
> 

In a similar manner, the ***morphological reonstruction by erosion*** of a marker image $F$ with respect to a mask image $G$ is defined as the geodesic erosion of $F$ with respect to $G$, iterated until stability:
$$
R_{G}^{E}(F)=E_{G}^{(k)}(F)
$$
where $E_{G}^{(k)}(F)=E_{G}^{(k+1)}(F)$.

Reconstruction by dilation and erosion are duals with respect to set complementation.

### automatic algorithm for filling holes
Main concept: first, we try to find the background pixels surrounding the objects (foreground) in the image. To do this, we dilate the **boundary background pixels** without stepping over the boundary of the objects (no exporsure to the holes). These pixels are the background pixels contained in the holes. Thus, we can flip the background pixels that are not in the set we just obtained (i.e. they are in the hole). The algorithm is described as follows.

Let $I ( x, y)$ denote a binary image, and suppose that we form a marker image $F$ that is $0$ everywhere, except at the image border, where it is set to $1 − I$, that is,
$$
F(x, y)=\left\{\begin{array}{cl}
1-I(x, y) & \text { if }(x, y) \text { is on the border of } I \\
0 & \text { otherwise }
\end{array}\right.
$$
Then, the we can get a image equal to $I$ with all holes filled:
$$
H = [R_{I^c}^D(F)]^c
$$
Here is an illustration: