Mathematical Morphology And Image Processing Technology Essay

Published:

Mathematical morphology is a well-founded non-linear theory of image processing [42, 49, 53, 57, 127]. Its geometry-oriented nature provides an efficient framework for analyzing object shape characteristics such as size and connectivity, which are not easily accessed by linear approaches. Morphological operations take into consideration the geometrical shape of the image objects to be analyzed. The initial form of mathematical morphology is applied to binary images and usually referred to as standard mathematical morphology in the literature in order to be discriminated by its later extensions such as the gray scale and the soft mathematical morphology. Mathematical morphology is theoretically founded on set theory. It contributes a wide range of operators to image processing, based on a few simple mathematical concepts. In general mathematical morphological operators transform the original image into another image through the interaction with some other image of certain shape and size, known as structuring element. Geometric features of the image that are similar in shape and size of the structuring element are preserved, while other features are suppressed. Therefore, morphological operations can simplify the image data, preserving their shape characteristics and eliminate irrelevancies. The operators are particularly useful for the analysis of binary images, boundary detection, noise removal, image enhancement and image segmentation. The advantages of morphological approaches over linear approaches are direct geometric interpretation, simplicity and efficiency in hardware implementation.

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

The hardware complexity of implementing morphological operations depends on the size of the structuring elements. The complexity increases even exponentially in some cases. Known hardware implementations of morphological operations are capable of processing structuring elements only up to 3 3 pixels [53]. If higher order structuring elements are needed, they are decomposed into smaller elements. One decomposition strategy is, for example, to present the structuring element as successive dilation of smaller structuring elements. This is known as the "chain rule for dilation" [49]. But all structuring elements cannot be decomposed.

2.1.1 Applications of Morphology

Morphological Image Processing has found its application in the following areas: Image-pre-processing (noise filtering, shape simplification), Enhancement of object structure (Skeletonizing, thinning, thickening & object marking), Segmentation of objects, Quantitative description of objects (Area, perimeter & various projections).

2.1.2 Morphological processing and transforms:

Fundamental definitions

An image is a function of two real (coordinate) variables a (x, y) or two discrete variables a [m, n]. An alternative definition of an image can be based on the notion that an image consists of a set (or collection) of either continuous or discrete coordinates. In a sense the set corresponds to the points or pixels that belong to the objects in the image. This is illustrated in Figure 2.1, which contains two objects or sets A and B. Note that the coordinate system is required. For the moment the present study will consider the pixel values to be binary. Further it restricts the discussion to discrete space (Z2).

The basic Minkowski set operations addition and subtraction can be defined, based on assumptions that the individual elements that comprise B are not only pixels but also vectors as they have a clear coordinate position with respect to [0,0]. For given two sets A and B, the operations are computed by the following equations 2.1 and 2.2.

Minkowski addition - (2.1)

Minkowski subtraction - (2.2)

Figure 2.1 A Binary Image Containing Two Object Sets A and B.

2.1.3 Dilation and Erosion

The fundamental mathematical morphology operations dilation and erosion based on Minkowski algebra are defined by the following equations 2.3 and 2.4.

Dilation- (2.3)

Erosion- (2.4)

Where, these two operations are illustrated in Figure 2.2 for the objects defined in Figure 2.1.

While either set A or B can be thought of as an image, A is usually considered as the image and B is called a structuring element.

(a) (b)

Figure 2.2 A Binary Image Containing Two Object Sets A and B.

(a) Dilation D (A, B) (b) Erosion E (A, B).

Dilation, in general, causes objects to dilate or grow in size; erosion causes objects to shrink. The amount and the way that they grow or shrink depend upon the choice of the structuring element. Dilating or eroding without specifying the structural element makes no more sense than trying to low pass filter an image without specifying the filter. The two most common structuring elements (given a Cartesian grid) are the 4-connected and 8-connected sets, N4 and N8. They are illustrated in Figure 2.3.

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

(a) (b)

Figure 2.3 The Standard Structuring Elements. (a) N4 (b) N8.

Dilation and Erosion have the following properties computed by the following equations 2.5 to 2.9.

Commutative - (2.5)

Non-Commutative - (2.6)

Associative - (2.7)

Translation Invariance - (2.8)

Duality - (2.9)

With A as an object and as the background, equation 2.9 says that the dilation of an object is equivalent to the erosion of the background. Likewise, the erosion of the object is equivalent to the dilation of the background except for the special cases given in the following equation 2.10.

Non-Inverses - (2.10)

Erosion has the following translation property as given by the following equation 2.11.

Translation Invariance - (2.11)

2.1.4 Opening and Closing

One can combine dilation and erosion to build two important higher order operations called opening and closing given by the following equations 2.12 and 2.13.

Opening - (2.12)

Closing - (2.13)

The opening and closing have the following properties computed by the equations 2.14 to 2.21.

Duality - (2.14)

Translation - (2.15)

For the opening with structuring element B and images A, A1, and A2, where A1 is a sub image of:

Antiextensivity - (2.16)

Increasing monotonicity - (2.17)

Idempotence - (2.18)

For the closing with structuring element B and images A, A1, and A2, where A1 is a sub image of A2 (A1 A2):

Extensivity - (2.19)

Increasing monotonicity - (2.20)

Idempotence - (2.21)

The two properties given by equations 2.20 and 2.21 are so important to mathematical morphology that they can be considered as the reason for defining erosion with -B instead of B in equation 2.13.

Hit-or-Miss Operation: The hit-or-miss operator is defined as follows. Given an image A and two structuring elements B1 and B2, the set definition and Boolean definition are given by following equation 2.22.

Hit-or -Miss - (2.22)

Where B1 and B2 are bounded, disjoint structuring elements. Two sets are disjoint if, the empty set. In an important sense the hit-or-miss operator is the morphological equivalent of template matching, a well-known technique for matching patterns based upon cross-correlation. Here, the present study proposes a template B1 for the object and a template B2 for the background.

2.1.5 Skeleton

The informal definition of a skeleton is a line representation of an object that is: i) one-pixel thick ii) through the middle of the object and iii) preserves the topology of the object. These are not always realizable. Figure 2.4 shows counter examples for skeleton definition.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(b)

Figure 2.4 Counter examples to the Three Requirements.

In the first example, Figure 2.4 (a), it is not possible to generate a line that is one pixel thick and in the center of an object while generating a path that reflects the simplicity of the object. In Figure 2.4 (b) it is not possible to remove a pixel from the 8-connected object and simultaneously preserve the topology, the notion of connectedness of the object. Nevertheless, there are a variety of techniques that attempt to achieve this goal and to produce a skeleton.

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

A basic formulation is based on the work of Lantuejoul. The skeleton subset Sk(A) is defined by the following equation 2.23.

Skeleton subsets - (2.23)

Where K is the largest value of k before the set Sk(A) becomes empty. The structuring element B is chosen (in Z2) to approximate a circular disc, that is, convex, bounded and symmetric. The skeleton is then the union of the skeleton subsets as given by the equation 2.24.

Skeleton - (2.24)

The original object can be reconstructed with the given knowledge of the skeleton subsets Sk (A), the structuring element B, and k as given by the following equation 2.25.

Reconstruction - (2.25)

However, the skeleton computed by the equation 2.24 does not preserve the topology.

An alternative point-of-view is to implement a thinning, an erosion that reduces the thickness of an object without permitting it to vanish. A general thinning algorithm based on hit-or-miss operation is given by the following equation 2.26.

Thinning - (2.26)

Depending on the choice of B1 and B2, a large variety of thinning algorithms and through repeated application, Skeletonizing algorithms are implemented.

2.1.6 Gray Value Morphological Processing

The techniques of morphological filtering can be extended to gray-level images. To simplify matters the present study restricted the presentation to structuring elements, B, that comprise a finite number of pixels and are convex and bounded. However, the structuring element has gray values associated with every coordinate position as does the image A.

Gray-level dilation, DG(), is given by the following equation 2.27.

Dilation - (2.27)

For a given output coordinate [m,n], the structuring element is summed with a shifted version of the image and the maximum encountered over all shifts within the JÃ-K domain of B is used as the result.

Gray-level erosion EG(A,B), is given by the following equation 2.28.

Erosion - (2.28)

The duality between gray level erosion and gray level dilation is more complex than in the binary case. The duality operation is given by the following equation 2.29.

Duality - (2.29)

Where " " means that.

The definitions of higher order operations such as gray level opening and gray level closing are given by the following equations 2.30 and 2.31.

Opening - (2.30)

Closing - (2.31)

The important properties that were discussed earlier such as idempotence, translation invariance, increasing in A, and so forth are also applicable to gray level morphological processing.

In many situations the seeming complexity of gray level morphological processing is significantly reduced through the use of symmetric structuring elements where. The most common of these is based on the use of B = constant = 0. For this important case and using again the domain, the definitions above reduce to the following equations 2.32 to 2.35.

Dilation - (2.32)

Erosion - (2.33)

Opening - (2.34)

Closing - (2.35)

The remarkable conclusion is that the maximum filter and the minimum filter are gray level dilation and gray level erosion for the specific structuring element given by the shape of the filter window with the gray value "0" inside the window.

For a rectangular window, JÃ-K, the two dimensional maximum or minimum filter is separable into two, one-dimensional windows. Further, a one-dimensional maximum or minimum filter can be written in incremental form. This means that gray-level dilations and erosions have a computational complexity per pixel that is O(constant), that is, independent of J and K.

The operations defined above can be used to produce morphological algorithms for smoothing, gradient determination and a version of the Laplacian.

2.2 BASIC SKELETONIZATION TECHNIQUES

In this section some skeletonization techniques using mathematical morphology, are discussed.

2.2.1 Pavlidis Thinning Algorithm

The Pavlidis thinning transform is a simple thinning transform [108]. It provides an excellent illustration for translating set theoretic notation into image algebra formulation and it is explained below.

Let denote the source image and let A denote the support of a i.e., The inside boundary of A is denoted by. The set consists of those points of whose only neighbours are in.

The algorithm proceeds by starting with, setting equal to A, and iterating the statement given by the following equation 2.36.

(2.36)

until .

It is important to note that the algorithms described may result in the thinned region having disconnected components. This situation can be remedied by replacing equation 2.36 with the following equation 2.37.

(2.37)

Where is the outside boundary of region R. The trade-off for connectivity is high computational cost and the possibility that the thinned image may not be reduced as much.

The Pavlidis thinning algorithm is applied on English alphabets and results are shown in Figure 2.5.

Figure 2.5 Pavlidis Thinning Algorithm for English Alphabets.

2.2.2 Medial Axis Transform (MAT)

The MAT is unique. The original image can be reconstructed from its medial axis transform. The MAT evolved through Blum's work on animal vision systems [17, 18, 19, 38, 66, 78, 93, 108, 120, 121]. His interest involved how animal vision systems extract geometric shape information. There exists a wide range application that finds a minimal representation of an image useful [93]. The MAT is especially useful for image compression since reconstruction of an image from its MAT is possible.

Let, and let A denotes the support of a. The MA is the set,, consisting of those points x for which there exists a ball of radius rx , centered at x, that is contained in A and intersects the boundary of A in at least two distinct points. The MAT m is a gray level image defined over x by the following equation 2.38.

(2.38)

The reconstruction of the domain of the original image a in terms of the MA m is given by the following equation 2.39.

(2.39)

The original image a is computed by the following equation 2.40.

(2.40)

Let a denote the source image. Usually, the neighborhood N is a digital disk of a specified radius. The shape of the digital disk will depend on the distance function used. The MAT will be stored in the image variable m. Reconstruction from MAT is given by the following equation 2.41.

(2.41)

Because each MA value is greater than the associated neighborhood radius, the transformation encodes isolated points (with value 1) and yields exact reconstruction.

The MAT Algorithm is applied on English alphabets and results are shown in Figure 2.6. The original image reconstructed from its MAT is shown in Figure 2.7.

Figure 2.6 Medial Axis Transform Algorithm for English Alphabets.

2.2.3 Zhang-Suen Skeletonizing

The Zhang-Suen transform is one of many derivatives of Rutovitz thinning algorithm [43, 78, 93, 122, 169]. A Zhang-Suen algorithm repeatedly removes boundary points from a region in a binary image until an irreducible skeleton remains. Deleting or removing a point in this context means to change its pixel value from 1 to 0. Not every boundary point qualifies for deletion. The 8-neighbourhood of the boundary point is examined first. Only if the configuration of the 8-neighbourhood satisfies certain criteria will the boundary point be removed.

The Zhang-Suen Skeletonizing reduces regions of a Boolean image to 8-connected skeletons of unit thickness. Each iteration of the algorithm consists of two sub iterations. The first sub iteration examines a 3Ã-3 neighbourhood of every southeast boundary point and northwest corner point. The configuration of its 3Ã-3 neighbourhood will determine whether the point can be deleted without corrupting the ideal skeleton. On the second sub iteration a similar process is carried out to select northwest boundary points and southeast corner points that can be removed without corrupting the ideal skeleton.

The Zhang_Suen Skeletonizing Algorithm is applied on English alphabets and results are shown in Figure 2.8.

Figure 2.7 Reconstruction from Medial Axis Transform for English

Alphabets.

2.3. SUMMARY

Since the present study is mainly motivated by the concepts of mathematical morphology, an in depth study on the basic concepts was done, and various skeletonization algorithms were discussed in

Figure 2.8 Zhang_Suen Skeletonizing for English Alphabets.

the current chapter. Pavlidis, MAT and Zhang-suen skeletonizing algorithms are applied on the English alphabet set. The experimental results clearly indicate that the Pavlidis algorithm fails in the skeletonization process of single pixel width. The Zhang-suen skeletonizing algorithms fail in yielding thinned images for some of the alphabet set, this is due to its 8-connected approach. The MAT algorithm proves to be better when compared to the other two algorithms. However all the three algorithms suffer in the skeletonization process of complex shapes. To overcome this, next chapters presents innovative algorithms, of shape representation using morphological skeleton transforms.