Chapter 11 Mathematical Morphology

Contents:

11.1 Introduction

Morphology (the study of the form of obejcts) is an important basis for image processing. It simplifies an image by removing irrelevant details and errors with which the essential characteristics of the form of objects remain intact. The objects can easily be recognized.

Morphological operations are often used in machine vision and robotic applications. The basic operations of mathematical morphology are: dilation, erosion, opening and closing. These can be applied to both binary and gray value images. There are hardware implementations (especially for 3*3 or 5*5 operations) which work at video speed.

For an overview on morphology see: R. Haralick, S. Sternberg, X. Zhuang: Image Analysis using Mathematical Morphology.  IEEE PAMI 9, 532, (1987)

Set theory is the mathematical basis for morphology. Sets in Euclidic space E2 (or rather Z2 : the set of pairs of integers) describe the object pixels in a binary image, either the black or white pixels. Z3 sets are used for describing the 3-D or time series of 2-D binary images as well as 2-D gray level images.

Elementary operations [fig 9.1 and 9.2] on A: a subset or En with n-tuple elements a=(a1,a2,...an).

Translation over dEn:     Ad = { xEn | x = a + d, for some aA}
Complement (negation):     Ac = { xEn | x A }
Reflection (transposition):    Ar = { xEn | x = -a,  for some aA}
Intersection of A and B:   A B = {xEn | x A and x B}
Union of A and B:   A B= {xEn | x A or x B}
Difference between A and B:        A-B = {xEn | x A and x B} = A Bc

11.2 Dilation

The dilation operator on sets A and B are defined by:

AB = { c En | c = a + b, for some a  A, b  B }

A is normally the image, while B is often a smaller structuring element.

Dilation with a discrete "disk", the origin being inside of it, gives an isotrope "swelling" or "expansion" of the image; see also fig. 9.5.

On the left is the original image (from Tutorial Mathematical Morphology) , on the right the result after swelling; note that here the white pixels have been chosen as the object pixels.

On the disk on the left some places have been marked red, black indicates the original pixels and white the pixels that were added in. This implementation is based on an equivalence definition of dilation:

AB = { x |  (Brx A )  }

Br is placed on each pixel x of the image and if there is at least one pixel in A in

Br then x belongs to AB .

Dilation with a 3*3 square, containing the origin, is called "fill", "expand" or "grow", see [fig 9.4].

Dilation is communitative and associative:

AB = BA
A(BC) = (AB)C

This is used in software and hardware implementations to save on operations; if B and C each have N elements then this can have BC N2 elements.

On the far right you can see that dilation can be done using a 4 by 4 square with 16 pixels, with 4 consecutive dilations, and with 4 structure elements each with 2 pixels. To the left you can see that if the origin is not in B, then it is possible that A  B have no pixels in common with A.

Furthermore it can be shown that:
A  B =  [bB] Ab     and     Ad  B = (A  B) d     and     Ad  B-d = A  B

The first equation can be seen in the first figure of this section, where B contains the elements (0,0) and (0,1) and A B = A(0,0) A(0,1) = A A(0,1). These equations form the basis for the implementation of dilation using the digital hardware available on many image-processing cards. Shifts in the operation pipeline can then be compensated by scrolling the output buffer.

The following equations can be used for a quicker implementation:
(A  B)  C = (A  C)  (B  C)     and     A  (B  C) = (A  B)  (A  C)

For the combination of intersection and dilation the following is true:
(A  B)  C  (A  C)  (B  C)     and     A  (B  C)  (A  B)  (A  C)

Furthermore the dilation increases:
AB  A  C  B  C   for an image and   AB  C  A  C  B   for a structure element

11.3 Erosion

There are several equivalent definitions which can be given for erosion:
AB = { cEn | (c + b) A for every b B }
         = { cEn | Bc  A }
         = { cEn | for every bB there is an aA such that  c = a-b}
         = [b B] A-b

Erosion is not commutative nor is it equal to the difference of the sets.

(0,0)B(AB) A

thus resulting in "shrinking" of the original image, see [fig. 9.6]

Erosion of the same image used in the previous dilation section.

Here follow some equations for the acceleration of hardware and software implementations:

AdB = (AB)d     and     ABd = (AB)-d
A  (B  C) = (AB)  (A C)
(A  B)c = Ac  Br (erosion-dilation duality)     and     (A  B)c = Ac  Bc   (DeMorgan's law)
A  (B  C) = (A  B)  C   (replace erosion by 2 smaller ones)

Some implications:

AB  A  C  B  C
BC  A  B  A  C  (a larger structure element erodes more)

Union and erosion: (A B) C (AC) (B C)

11.4 Opening and closing

These operations are a combination of dilation and erosion:

opening: AK = (AK) K      closing: AK = (AK) K

Geometric characteristics, see [fig. 9.8 and 9.9]:

A  B =  [ {y | By  A ] By   or 
  { x  A | there is a y such that x By and By  A}
  representing the union of translations of B which are contained in A
A  B = [ [ { y | Byr  Ac } ] Byr ] c
  representing the complement of the union of all translations

To the left is the open operation on the same original from the previous section. The structure element moves along the inside of the object and the black pixels disappear. To the right is the close operation, the structure element moves along the outside of the object and the white pixels are added.

The original image (from Tutorial Mathematical Morphology), here the real pixel size is that of the small black or white blocks.

Erosion of the original image with a 3 by 3 structure element.

Followed by a dilation of the previous eroded image, thus the open operation on the original image. Two thin connections in the object have been broken. A small protrusion and a small island have been eliminated.

Dilation of the original image with a 3 by 3 structure element.

Followed by the erosion of the dilated image, thus the close operation on the original image. A hole in the object has been filled, as well as two small dents in the contour. A small hole between the two pairs of the object has been filled.

Thus opening with a disk structure element (see fig. 9.10):
    - breaks thin connections within an object
    - eliminates small islands and sharp protrusions

and closing with a disk structure element:
   - fills thin connections within an object
   - eliminates small holes and fills dents in contours
   - fills small gaps in parts of an object

11.4.1 Idem potent

From the geometric definitions of opening the following can be deduced:

BK  B    (this is called: opening is anti-extensive), thus:
(AK)K  AK (replacement of B by AK)   (1)

From the geometric definitions of closing the following can be deduced:

A  AK      (this is called: closing is extensive)
A B  A  C  B  C      (indicated by dilation), thus
AK  (AK)  K      (replace C by K and B by AK )
(AK) K =  ( (AK)  K)K      (rewrite the definition of )
                   = (AK) K       (apply the definition of  ), thus
AK  (AK)  K    (2)

From (1) and (2) it follows that:    AK = (AK) K = (AK) K     (already shown above) (3)

In the same manner the following can be deduced:    AK = (AK) K = (AK) K

From this follows:

AK = (AK)  K     (write out the definition of )
          = ((AK) K)  K      ( apply (3))
         = (AK) K         (apply the definition of   )
AK = (AK) K

thus opening and closing are idem potent operations.

Duality of opening and closing: (AK)c = Ac Kr
Furthermore, opening and closing are invariant under the translation of the structure element:
      AKx = AK and AKx = AK

11.4.2 In combination

Top left is the original image with a lot of noise, see fig. 9.11. Top right is the opening thereof with a 3 by 3 structure element, and the result of closing on that image is shown below it.

The center image in the left column is the closing of the original image and below it the opening of that.

11.5 Some algorithms

The goal of the "hit-miss" operation is to find the pixels x, for which B1x is in A and where no pixel in B2x is in A, thus B2x is in Ac. With B1 and B2 being structure elements not having pixels in common ( B2B1c ) or else the set of x will be empty. The definition of the "hit-miss" operation is:

AB = { xEn | B1x  A  and  B2x  Ac}

We thus get the pixels x for which B1x is in A ("hit") and B2x is not in A ("miss"). It can be shown that:

AB = ( A B1 )  ( Ac B2 ) = ( A B1 ) - ( A B2r )

  Original image (white pixels)

  B1
 Erosion with B1

 Searching for white pixels, 
   that do not have 4-connected 
     neighboring pixels.

  Complement

  B2
 Erosion with B2
 Intersection yields the resulting image

Edge extraction, see [fig. 9.13]: GB(A) = A - (A B)

Filling regions that are defined by a 8-connected boundary can be done by an iterative process, see [fig. 9.15]:

 X0 = p (a random pixel in the region)
 Xk = (Xk-1  B)  Ac (this is called a conditional dilation)
 stop the iteration when Xk = Xk-1
 Xk  A  is then the region belonging to its edge.

Finding a connected component in an image, see [fig 9.17]:

 X0 = p (a random pixel of the component)
 Xk = (Xk-1  B)  A  stop when Xk = Xk-1

The thinning of a set A by a composed structure element B:
      A  B = A - ( A  B) = A  ( A  B)c

usually A is thinned symmetrically by a row of structure elements {B}, that are rotated versions of each other:
      {B} = {B1,B2,B3,...,Bn}
      A  {B} = (( ... ((A  B1)  B2) ...)  Bn)

this is repeated until no more changes occur, see [fig. 9.21]. The center picture shows the results using {B} from fig. 9.21, the bottom one with a slightly different {B}.

Growing (or thickening) of a set is defined in the same manner, see [fig. 9.22]:

 A  B  = A  ( A  B)
 A  {B} = (( ... ((A  B1)  B2) ...)  Bn)

The skeleton of a region A, pixels from which the area can be built up of with the aid of structure element B, can also be defined as ( see [fig. 9.24] ):

 S(A) = k=0K Sk(A)
 Sk(A)= (A  kB) - ( (A  kB)  B )       ( A  kB means k successive erosions)
 K = max{ k | A  kB   }
 A = k=0K (Sk(A)  kB)

Also protrusions of a figure, of for example less than 3 pixels, can be removed (pruning), see [fig. 9.25].

L. Vincent (Signal Processing 22,1991,3-23) gives an efficient algorithm for the implementation of morphological operations with random structure elements, assuming a chain code encoding of the binary objects.

11.6 Gray level images

For morphological operations on gray level images we use sets in EN. The first (N-1) coordinates conventionally form the spatial domain and the last coordinate is for the surface. For gray level images N=3, the first two coordinates of an element in a set are the (x,y) in the image and the third is the gray level. Concepts such as top or top-surface of a set and the shadow (umbra) of a surface are used in the definitions of the operations.

Let A be EN and define the domain of A as:   D = { x EN-1  | there is a yE, (x,y)A}

The top or top-surface of A is a function  T[A] : D -> E:   T[A] (x) = Max { y | (x,y) A }

Set B ( B EN-1 E) is a shadow if and only if: (x,y)B (x,z)B for every z y

Let f : D -> E be a function, then  U[f] ( U[f] D E ) the shadow set of f: U[f] = { (x,y)D E | y  f(x) }

Let F,K EN-1 domains and f: F -> E  and  k : K -> E the functions belonging to it.
Then define dilation as ( see [fig. 9.27] ):

f k = T [ U[f] U[k] ] thus (f k )(x) = max { z K, x-z F | f(x-z) + k(z) }

erosion is defined as ( see [fig. 9.28] ):

f k = T [ U[f] U[k] ]   thus   (f k )(x) = min { z K, x+z  F  |  f(x+z) - k (z) }

See [fig. 9.29] for the result of dilation and erosion on a gray level image. The properties of gray level dilation and erosion are equivalent to those of binary operations, for example:

 (f k)c (x) = (fc kr ) (x)     with      fc (x) = -f(x) en f r(x) = f(-x)

Opening and closing are defined as follows:

f  k = (f  k )  k          f  k = (f  k )  k

To the left is the geometric interpretation of it, see also [fig. 9.30]. See fig. 9.31 for the results on the image of fig. 9.29. The duality of open and close is:

-(f  k) = (-f)  kr            f  k = - ( (-f)  kr)

To the far left is the original image, in the center the opening of it with a disk with radius 3 as the structure element. All the thin white bands have disappeared, only the broad one remains. To the right the closing, all the valleys where the structure element does not fit have been filled, only the three broad black bands remain.

The bottom row is the top view of the three images above.

The images come from mmtutor.

Last updated on April 4th 2003 Theo Schouten.