---
tags: Digital Image Processing
disqus: hackmd
---
# Part 16

## Mathematical Morphology

Morphology is used a lot in biology, indicating the structure of different plants, animals, etc.

Here, it will be used to consider the structure and shape of objects in images.

One of its applications can be that it is used to cover up holes in a thresholded image.

Some other applications include object quantification, image segmentation, skeletonization, convex hull, etc.

### Image as Point Sets
Consider the binary image shown. Instead of looking at it as a combination of pixels spatially arranged, we can register the locations of the segmented object and define it as a set. So, $X = \{(2,0),(2,1),(1,3),...\}$. Similarly, the background pixels can be represented as $X^c = \{(0,0),(1,0),(0,1),...\}$.

Now, morphological operations can be performed on sets of coordinates, instead of the whole image.

Just as a review of basic set theory,
Another form of set operation is reflection operation. So, reflection of set $B$ can be represented as $\hat{B} = \{w | w = -b, b \in B \}$.

Translation operation on a set can be defined as $A_z = \{c|c = a + z, a \in A\}$.

### Morphological Transformation ($\psi$)

This transformation gives the relation of image $X$ with a point set $B$, called structuring element. This element can be translated over the original image, to give the output.

One such transformation is known as dilation $\oplus$.

Given the structuring element $B$ and image $X$, the dilation can be done as,
\begin{equation}
X \oplus B = \{p \in \mathbb{Z}^2, p = x + b, x \in X, b \in B\}
\end{equation}
It can also be defined as,
\begin{equation}
X \oplus B = \{p \in \mathbb{Z}^2, (\hat{B})_p \cap X \neq \phi\}
\end{equation}


Another operation is known as erosion. In case of dilation, we have vector addition. Here, subtraction is performed. For the same initial conditions, the operation can be defined as,
\begin{equation}
X \ominus B = \{p \in \mathbb{Z}^2 | p + b \in X \text{ }\forall \text{ }b \in B\}
\end{equation}
Another definition can be,
\begin{equation}
X \ominus B = \{p \in \mathbb{Z}^2 | (B)_p \subseteq X\}
\end{equation}

Performing erosion on it yields,

### Properties of Dilation

1. Dilation operation is commutative. $X \oplus B = B \oplus X$.
2. It is associative. $(X \oplus B) \oplus C = X \oplus (B \oplus C)$.
3. $X \oplus B = \cup_{\forall \text{ }b \in B\text{ }}x_b$.
4. Translation Invariance. $X_h \oplus B = (X \oplus B)_h$.
5. Dilation is an increasing transformation, that is if $X \subseteq Y$, then $X \oplus B \subseteq Y \oplus B$.

### Properties of Erosion

1. $X \ominus B = \cap_{\forall \text{ } b \in B\text{ }}x_{-b}$.
2. If $(0,0) \in B$, then $X \ominus B \subseteq X$.
3. Translation. $X \ominus B = (X \ominus B)_h$.
4. Increasing transformation property. If $X \subseteq Y$, then $X \ominus B \subseteq Y \ominus B$.
5. It is not commutative, that is $X \ominus B \neq B \ominus X$.
6. It is not associative as well.

### Closing and Opening Operation

Consider the image
Here, we can see that two objects are segmented, however, due to the presence of noise, we see two defects segmented such as incomplete segmentation of the first object and also that the two objects are connected, even though they are different segmented entities.

The structuring element is considered as,

The first step done is dilation, causing the image to be like,
The side effect is that the object expands by one pixel from each side. Now, the same structuring element is used to erode. So, we get,
Here, we see that one of the defects is now resolved. This operation can be represented as
\begin{equation}
X. B = (X \oplus B) \ominus B
\end{equation}
This is known as closing operation. Such kind of operation is useful for removing internal noise.

Now, only the external noise remains. For removing it, it is possible to perform erosion operation, followed by dilation. Therefore, we get the final image as,

This is known as closing operation, represented as,
\begin{equation}
X o B = (X \ominus B) \oplus B
\end{equation}

### Hit or Miss Transform


### Boundary Extraction

Consider the object region, whose boundary we need to extract.
Given point set $A$, the boundary set can be represented as $A = \beta(A)$. It is equal to $A - (A \ominus B)$. We assume the same structuring element.

After erosion, followed by subtraction, we are left with,
So, we get the boundary.

### Region Filling

Given the image, we need to fill the region inside it.
Here, the structuring element is taken as,
The centre is considered as the origin.

We consider an arbitrary point inside the hollow space as $x_0 = p$. This can be dilated iteratively such that for $x_k$, $x_k = x_{k - 1} \oplus B$, where $B$ is the structuring element. To avoid overflow of pixels, we take its intersection with the pixels apart from the given boundary as $A^c$. Therefore, $x_k = (x_{k - 1} \oplus B) \cap A^c$. Convergence is reached when $x_k = x_{k - 1}$, which is when the iterative dilation is stopped.

### Connected Component Extraction

Extract all connected points $Y$ of a subset of $A$ which is connected.

Therefore, $x_k = (x_{k - 1} \oplus B) \cap A, k = 1,2,3,...$. Convergence when $x_k = x_{k - 1}$. Also, then, $Y = x_k$.

We have the input image as,
The structuring element is,

On performing the operation, we are able to obtain, (initial point $x_0 = p$)

### Convex Hull

A set $S$ is said to be a convex set, if we take any pair of points, join a straight line and other points also lie on this line. Other points not belonging to this line implies that the set will not be convex.
Here, LHS set is convex, but RHS set is not.

A minimal point set with $S$ which is convex is known as convex hull and denoted as $H$. Therefore, $H - S$ is known as convex deficiency.

Consider structuring elements $B^i, i = 1,2,3,4$. The four structuring elements are used for getting the convex hull and are represented as,

The operation is defined as,
\begin{equation}
x_k^i = (x_{k - 1}^i * B^i) \cup A
\end{equation}
Where $*$ is hit and miss transform. This to be done independently for each of the structuring element. It is assumed as $x_0^i = A$. Convergence is when $x_k^i = x_{k - 1}^i$. Consider the point set $D^i = x_{conv}^i$, which is the final converged form for a structuring element.

So, the convex hull is defined as,
\begin{equation}
C(A) = \bigcup_{i = 1}^{4} D_i
\end{equation}
The input image is considered as,
Therefore, we get the convex hull as,

However, this is not a minimal set.
We can obtain, with some threshold limits on the four sides, the minimal sets. This is the convex hull.

### Thinning

This can be used to skeletonize the image, to get the structure of object segmented. The operation can be defined as $A \otimes B = A - (A * B)$, where $*$ is hit and miss transform. This can also be represented as $A \otimes B = A \cap (A * B)^c$. The structuring elements are $B = \{B^1, B^2, ..., B^n\}$, where $B^i$ is the rotated version of $B^{i - 1}$. Therefore, $A \otimes \{ B \}$ is performed, till there is convergence.
These are the structuring elements, where 'x' are the don't care conditions. The centre of each of them is considered as the origin.

Consider the following binary image,

Now, each structuring element is passed sequentially, producing a single iteration. Such many iterations are performed until there is convergence.

Finally, we get the following as the output,

Similarly, the opposite, which is thickening, is defined as,
\begin{equation}
A \odot B = A \cup (A * B)
\end{equation}

Another form of its representation is as follows,
1. $A \to A^c$
2. C = $A^c \otimes \{B\}$.
3. $C \to C^c$, which is the thickened version of the point set $A$.

### Skeletonization

Given point set $A$, we can obtain the skeleton of $A$, $S(A)$ as,
\begin{equation}
S(A) = \bigcup_{k = 0}^M S_k(A)
\end{equation}
Where,
\begin{equation}
S_k(A) = (A \ominus kB) - (A \ominus kB)oB
\end{equation}
And,
\begin{equation}
M = \max{(k|A \ominus kB \neq \phi)}
\end{equation}

This can be related with the original point set as,
\begin{equation}
A = \bigcup_{k = 0}^M (S_k(A) \oplus kB)
\end{equation}

### Morphological Operations on Grayscale Images

Consider the point set $A$ present in $n$ dimensional euclidean space. $n - 1$ coordinates denote the spatial domain coordinates, whereas the coordinate number $n$ denotes the value of the function. For example, in $(x,y,z)$, we have the first two coordinates in the spatial domain, whereas the third coordinate is the value at the location or $z = f(x,y)$.

So, a grey level image will be represented as a triplet.

Consider the point set $A = \{(1,1),(1,2),(1,5),(2,3),(2,7),(3,1),(3,3),(3,5)\}$. The first three elements point to $1$, next two as $2$ and the rest as $3$.

With the groups obtained, find the maximal spatial coordinate in each group. So, for each group, we have max values at $5$, $7$ and $5$ respectively.

So, top surface has points as $(1,5), (2,7), (3,5)$. Formally, top surface can be defined as $T[A](x) = \max\{y| (x,y) \in A\}$.

The region of support is defined as $F = \{x \in E^{n - 1}, y \in E, (x,y) \in A\}$, where $E$ is defined as a dimension of euclidean space.

Geometrically, it can be defined as,

Given $F \subseteq E^{n - 1}$ and $f: F \to E$, we can define umbra of $f$ as $U[f] \subseteq F \times E$.
\begin{equation}
U[f] = \{(x,y) \in F \times E\, y \leq f(x)\}
\end{equation}
So, it includes the points, including top surface and points below the top surface.

Using this terminology, the dilation operation can be represented as,
\begin{equation}
f \oplus k = T[U[f] \oplus U[k]]
\end{equation}
Similarly, erosion can be defined as,
\begin{equation}
f \ominus k = T[U[f] \ominus U[k]]
\end{equation}