Mathematical Morphology

Mathematical Morphology is a tool for extracting image components that are useful for representation and description. The technique was originally developed by Matheron and Serra [3] at the Ecole des Mines in Paris. It is a set-theoretic method of image analysis providing a quantitative description of geometrical structures. (At the Ecole des Mines they were interested in analysing geological data and the structure of materials). Morphology can provide boundaries of objects, their skeletons, and their convex hulls. It is also useful for many pre- and post-processing techniques, especially in edge thinning and pruning.

Generally speaking most morphological operations are based on simple expanding and shrinking operations. The primary application of morphology occurs in binary images, though it is also used on grey level images. It can also be useful on range images. (A range image is one where grey levels represent the distance from the sensor to the objects in the scene rather than the intensity of light reflected from them).

Set operations

The two basic morphological set transformations are erosion and dilation

These transformations involve the interaction between an image A (the object of interest) and a structuring set B, called the structuring element.

Typically the structuring element B is a circular disc in the plane, but it can be any shape. The image and structuring element sets need not be restricted to sets in the 2D plane, but could be defined in 1, 2, 3 (or higher) dimensions.

Let A and B be subsets of Z². The translation of A by x is denoted A_x and is defined as

$$A_x = \{c : c = a + x, \mbox{for } a \in A\}.$$

The reflection of B, denoted $\hat{B}$, is defined as

$$\hat{B} = \{x : x = -b, \mbox{for } b \in B\}.$$

The complement of A is denoted A^c, and the difference of two sets A and B is denoted A - B.

Dilation

Dilation of the object A by the structuring element B is given by

$$A \oplus B = \{x : {\hat{B}}_x \cap A \neq \O \}.$$

The result is a new set made up of all points generated by obtaining the reflection of B about its origin and then shifting this relection by x.

Consider the example where A is a rectangle and B is a disc centred on the origin. (Note that if B is not centred on the origin we will get a translation of the object as well.) Since B is symmetric, $\hat{B} = B$.

 

Figure 3: A is dilated by the structuring element B.

This definition becomes very intuitive when the structuring element B is viewed as a convolution mask.

Erosion

Erosion of the object A by a structuring element B is given by

$$A \ominus B = \{ x : B_x \subseteq A \}.$$

 

Figure 4: A is eroded by the structuring element B to give the internal dashed shape.

Dilation and erosion are duals of each other with respect to set complementation and reflection. That is,

$$(A \ominus B)^c = A^c \oplus \hat{B}.$$

To see this, consider first the left hand side:

$$(A \ominus B)^c = \{x : B_x \subseteq A \}^c.$$

Now, if B_x is contained in A, then $B_x \cap A^c = \O$, and so

$$(A \ominus B)^c = \{x : B_x \cap A^c= \O \}^c.$$

But the complement of the set of all xs that satisfy $B_x \cap A^c = \O$ is just the set of all xs such that $B_x \cap A^c \neq \O$. Thus

$$(A \ominus B)^c = \{x : B_x \cap A^c \neq \O \} = A^c \oplus \hat{B}.$$

Applications of morphological operations

Erosion and dilation can be used in a variety of ways, in parallel and series, to give other transformations including thickening, thinning, skeletonisation and many others.

Two very important transformations are opening and closing. Now intuitively, dilation expands an image object and erosion shrinks it. Opening generally smooths a contour in an image, breaking narrow isthmuses and eliminating thin protrusions. Closing tends to narrow smooth sections of contours, fusing narrow breaks and long thin gulfs, eliminating small holes, and filling gaps in contours.

The opening of A by B, denoted by $A \circ B$, is given by the erosion by B, followed by the dilation by B, that is

$$A \circ B = (A \ominus B)\oplus B.$$

 

Figure 5: The opening (given by the dark dashed lines) of A (given by the solid lines. The structuring element B is a disc. The internal dashed structure is A eroded by B.

Opening is like `rounding from the inside': the opening of A by B is obtained by taking the union of all translates of B that fit inside A. Parts of A that are smaller than B are removed. Thus

$$A \circ B = \bigcup\{B_x : B_x \subseteq A \}.$$

 

Figure 6: The opening of A by the structuring element B.

Closing is the dual operation of opening and is denoted by $A \bullet B$. It is produced by the dilation of A by B, followed by the erosion by B:

$$A \bullet B = (A \oplus B)\ominus B.$$

 

Figure 7: The closing of A by the structuring element B.

This is like `smoothing from the outside'. Holes are filled in and narrow valleys are `closed'.

Just as with dilation and erosion, opening and closing are dual operations. That is

$$(A \bullet B)^c = (A^c \circ B^c).$$

The opening operation satisfies the following properties:

1.

$A \circ B$ is a subset of A.

2.

If C is a subset of D, then $C \circ B$ is a subset of $D \circ B$.

3.

$(A \circ B) \circ B = A \circ B$.

Similarly

1.

A is a subset of $A \bullet B$.

2.

If C is a subset of D, then $C \bullet B$ is a subset of $D \bullet B$.

3.

$(A \bullet B) \bullet B = A \bullet B$.

Property 3, in both cases, is known as idempotency. It means that any application of the operation more than once will have no further effect on the result.

The morphological filter $(A \circ B) \bullet B$ can be used to eliminate `salt and pepper' noise. Salt and pepper noise is random, uniformly distributed small noisy elements often found corrupting real images. It will appear as black dots or small blobs on a white background, and white dots or small blobs on the black object. The background noise is eliminated at the erosion stage, under the assumption that all noise components are physically smaller than the structuring element B. Erosion on its own will increase the size of the noise components on the object. However, these are eliminated at the closing operation.

The important thing to note is that morphological operations preserve the main geometric structures of the object. Only features `smaller than' the structuring element are affected by transformations. All other features at `larger scales' are not degraded. (This is not the case with linear transformations, such as convolution).

The boundary of a set A, denoted $\partial{A}$, can be obtained by first eroding A with B, where B is a suitable structuring element, and then performing the set difference between A and its erosion. That is

$$\partial{A} = A - (A \ominus B).$$

Typically, B would be a $3 \times 3$ matrix of 1s.

Region filling can be accomplished iteratively using dilations, complementation, and intersections. Suppose we have an image A containing a subset whose elements are 8-connected boundary points of a region. Beginning with a point p inside the boundary, the objective is to fill the entire region with 1s.

Since, by assumption, all non-boundary points are labeled 0, we begin by assigning 1 to p, and then construct

$$X_k = (X_{k-1} \oplus B) \cap A^c, \mbox{for } k = 1, 2, \ldots$$

where X₀ = p, and B is the `cross' structuring element shown in figure 8. The algorithm terminates when X_k = X_k-1. The set union of X_k and A contains the filled set and its boundary.

 

Figure 8: The region in A is filled using the structuring element B.

Likewise, connected components can also be extracted using morphological operations. If Y represents a connected component in an image A and a point p in Y is known, then the following iterative expression yields all the elements of Y:

$$X_k = (X_{k-1} \oplus B) \cap A, \mbox{for } k = 1, 2, \ldots$$

where X₀ = p and B is a $3 \times 3$ matrix of 1s. If X_k = X_k-1 the algorithm has converged and we let Y = X_k.

An important step in representing the structural shape of a planar region is to reduce it to a graph. This is very commonly used in robot path planning. This reduction is most commonly achieved by reducing the region to its skeleton.

The skeleton of a region is defined by the medial axis transformation (MAT). The MAT of a region R with border B is defined as follows: for each point p in R, we find its closest neighbour in B. If p has more than one such closest neighbour, then p belongs to the medial axis (or skeleton) of R. Of course, closest depends on the metric used. Figure 9 shows some examples with the usual Euclidean metric.

 

Figure 9: The skeletons of three simple regions.

Direct implementation of the MAT is computationally prohibitive. However, the skeleton of a set can be expressed in terms of erosions and openings. Thus, it can be shown that

$$S(A) = \bigcup_{k=0}^K S_k(A),$$

where

$$S_k(A) = \bigcup_{k=0}^K \{(A \ominus kB) - [(A \ominus kB) \circ B],$$

B is a structuring element, $(A \ominus kB)$ indicates k successive erosions of A, and K is the last iterative step before A erodes to an empty set.

Thus A can be reconstructed from its skeleton subsets S_k(A) using the equation

$$A = \bigcup_{k=0}^K (S_k(A) \oplus kB),$$

where $S_k(A) \oplus kB$ represents k successive dilations of S_k(A).