Specialized Hardware Structures for Morphological Image Processing

II. Mathematical Morphology Operations and Structuring Elements

a. Definitions

The basic morphological operations are dilation and erosion. In the gray-scale 1-D case these are defined as follows (Haralick et al. 1987):

and (1)

(2)

respectively.

where are the spatial co-ordinates,

f :F->Z is the gray-scale image,

k :K->Z is the gray -scale structuring element and

, are the domains of the gray-scale image and gray-scale structuring element.

Figure 1.Grey-scale morphological operations on a 1D random function f with a 1D structuring element k. k consists of five discrete values; the center is equal to 30, whilst the other four are equal to 20. (a) dilation and (b) erosion. As it can be seen dilation extends the function to values closer to 255, whereas erosion shrinks it to values closer to 0.

A graphical illustration of formulae (1) and (2), for a random function f is given in Fig. 1. Of course, in the 2-D case the same formulae are applied, provided that pairs of co-ordinates such as(x₁, x₂) and (y₁, y₂) replace x and y respectively. The other morphological transforms are composed by dilation and erosion. A synopsis of the most widely used transforms is given in Table 1. A detailed description of these transforms can be found in (Serra 1982).

Table 1. Synopsis of the most widely used gray-scale morphological transforms.

Operation	Equation
Opening
Closing
Hit or Miss Transform
Top Hat Transform
Thickening
Thinning
Edge Detectors

f : F->E is the image, k: K->E is the structuring element, U(f) is the umbra of function f.

b. Structuring Elements

On a rectangular grid two pixels are neighbors either when they have a joint edge or when they have at least one joint corner. The most common neighborhoods are the 4-neighbourhood and the 8-neighbourhood, shown in Figs. 2a and 2b respectively. In mathematical morphology the joint of the “central” with its neighbors does not define the neighborhood.

Figure 2. (a) 4-neighbourhood and (b) 8-neighbourhood.

The role of the neighborhood is undertaken by the structuring element. More specifically the shape of the structuring element determines the shape of the neighborhood. Generally, the image processing machines and the special purpose morphological hardware structures are capable of processing neighborhoods (i.e. structuring elements) up 3x3 pixels. A reason for that is the hardware complexity, which increases according to structuring element size even exponentially in some cases. Furthermore, the large majority of low-level image processing operations are confined to small neighborhoods (Duff 1988). The more spaced two pixels in the image the less relevance the information for each other. However, in the case that an algorithm demands a structuring element bigger than 3x3, one of the decomposition techniques should be utilized (Camps et al. 1996; Gader 1991; Gasteratos et al. 1998c; Park and Chin 1994; Park and Chin 1995; Shih and Mitchell 1991; Singh and Siddiqi 1996; Xu 1996; Zhuang and Haralick 1986). One decomposition strategy is to present the structuring element as successive dilations of smaller structuring elements. This is known as the “chain rule for dilations” (Haralick and Shapiro 1992; Haralick et al. 1987); an example of such a “chain” of binary structuring elements is shown in Fig. 3. The solid cycle denotes the structuring element’s origin, whilst the hollow denotes any other pixel of the structuring element. The structuring element S can be decomposed into the smaller structuring elements S₁, S₂ and S₃. However, it should be stated that not all the structuring elements are possible to be decomposed following this strategy.

Figure 3.The chain rule for dilations (the solid cycle denotes the origin of structuring element and the hollow denotes any other pixel of the structuring element): (a) structuring element S is decomposed into S₁, S₂ and S₃ and (b) S is decomposed successively into S₁, S₂ and S₃, via S_1,2.

Algorithms for optimal structuring element decomposition according to this technique are described in (Park and Chin 1994; Park and Chin 1995; Xu 1996; Zhuang and Haralick 1986) for binary morphology and in (Camps et al. 1996) for gray-scale morphology. An algorithm for decomposing gray-scale structuring elements with rectangular support into horizontal and vertical structuring elements are presented in (Gader 1991). This algorithm has been improved with respect both to computation and accuracy in (Singh and Siddiqi 1996). Several methods for decomposing gray-scale structuring elements into combined structures of segmented small components are presented in (Shih and Mitchell 1991). A real time hardware structure for decomposition of gray-scale soft morphological structuring elements, using pipelining of the data, has been presented in (Gasteratos et al. 1998c). The domain of the structuring element is divided into non-overlapping sub-domains, as shown in Fig. 4 for a 9 9-pixel structuring element. In this figure the shaded area denotes the core of the structuring element. The morphological operations are computed locally in the sub-domains. From these local results the global morphological operation is composed.