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->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(x1, x2) and (y1, y2) 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 S1, S2 and S3. 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 S1, S2 and S3 and (b) S is decomposed successively into S1, S2 and S3, via S1,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. 

References

Abbott L, Haralick R M and Zhuang X (1988) Pipeline Architectures for Morphologic Image Analysis, Machine Vision and Applications, 1 (1): 23-40.

 

Andreadis I, Gasteratos A and Tsalides P (1996) An ASIC for Fast Grey-Scale Dilation, Microprocessors and Microsystems, 20 (2): 89-95.

 

Bloch I and Maitre H (1995) Fuzzy Mathematical Morphologies: A Comparative Study, Pattern Recognition, 28 (9): 1341-1387.

 

Botha E C and Casasent D P (1989) Applications of Optical Morphological Transformations, Optical Engineering, 28 (5): 501-505.

 

Broggi A, Conte G, Gregoretti F, Sansoe C, Passerone R and Reyneri L M (1998) Design and Implementation of the PAPRICA Parallel Architecture, The Journal of VLSI Signal Processing, 19 (1): 5-18.

 

Broggi A, Conte G, Gregoretti F, Sansoe C and Reyneri L M (1997) The Evolution of the PAPRICA System, Computer-Aided Engineering Journal, 4 (2): 114-136.

 

Camps O I, Kanungo T and Haralick R M (1996) Grey-Scale Structuring Element Decomposition, IEEE Transactions on Image Processing, 5 (1): 111-120.

 

Casasent D (1994) General-Purpose Optical Pattern Recognition Image Processors, Proceedings of the IEEE, 82 (11): 1724-1734.

 

Chen C and Yang D L (1995) Realisation of Morphological Operations, IEE Proceedings: Circuits Devices and Systems, 142 (6): 364-368.

 

Chen K (1989) Bit-Serial Realizations of a Class of Nonlinear Filters Based on Positive Boolean Functions, IEEE Transactions on Circuits and Systems, 36: 785-794.

 

Diamantaras I and Kung S Y (1997) A Linear Systolic Array for Real-Time Morphological Image Processing, Journal of VLSI Signal Processing, 17 (1): 43-55.

 

Diamantaras I, Zimerman K H and Kung S Y (1990) "Integrated Fast Implementation of Mathematical Morphology Operations in Image Processing", IEEE International Symposium on Circuits and Systems, New Orleans, pp 1442-1445.

 

Dougherty E R and Astola J (1994): Introduction to Non-linear Image Processing, SPIE, Bellingham, Washington.

 

Duff M J B (1982): CLIP4, in Fu K S and Ichikawa T, eds., Special Computer Architectures for Pattern Processing, CRC Press, Boca Raton, Florida.

 

Duff M J B (1988) "Some Constrains on the Limitations of Image Processing Computer Architectures", IARP Workshop on CV - Special Hardware and Industrial Application, Tokyo, Japan, pp 1-5.

 

Duncan R (1990) A Survey of Parallel Computer Architectures, IEEE Computer, 23: 5-16.

 

Fitch J P (1987) Software and VLSI Algorithm for Generalized Ranked Order Filtering, IEEE Transactions on Circuits and Systems, CAS-34 (5): 553-559.

 

Fitch J P, Coyle E J and Gallagher Jr. N C (1984) Median Filtering by Threshold Decomposition, IEEE Transactions on Acoustics Speech and Signal Processing, ASSP-32 (6): 1183-1188.

 

Fitch J P, Coyle E J and Gallagher Jr. N C (1985) Threshold Decomposition of Multidimensional Ranked Order Operations, IEEE Transactions on Circuits and Systems, CS-32 (5): 445 450.

 

Flynn M J (1966) Very High Speed Computing Systems, Proceedings of the IEEE, 56 (12): 1901-1909.

 

Fountain T J, Matthews K N and Duff M J B (1988) The CLIP7A Image Processor, IEEE Transactions on Pattern Analysis and Machine Intelligence, 10 (3): 310-319.

 

Frieder O (1990) Multiprocessor Algorithms for Relational-Database Operator on Hypercube Systems, IEEE Computer, 23: 13-28.

 

Gader P D (1991) Separable Decompositions and Approximations of Greyscale Morphological Templates, CVGIP: Image Understanding, 53 (3): 288-296.

 

Gasteratos A and Andreadis I (1999): Soft Mathematical Morphology: Extensions, Algorithms and Implementations, in Hawkes P W, ed., Advances in Imaging and Electron Physics, 110, Academic Press, pp. 63-99.

 

Gasteratos A and Andreadis I (2000) Non-Linear Image Processing in Hardware, Pattern Recognition, Special Issue on Mathematical Morphology, 33 (6): 1013-1021.

 

Gasteratos A, Andreadis I and Tsalides P (1996) Improvement of the Majority Gate Algorithm for Grey-Scale Dilation/Erosion, Electronics Letters, 32 (9): 806-807.

 

Gasteratos A, Andreadis I and Tsalides P (1997a) Extension And Very Large Scale Integration Implementation Of The Majority-Gate Algorithm For Gray-Scale Morphological Operations, Optical Engineering, 36 (3): 857-861.

 

Gasteratos A, Andreadis I and Tsalides P (1997b) Realization of Rank-Order Filters Based on Majority Gate, Pattern Recognition, 30 (9): 1571-1576.

 

Gasteratos A, Andreadis I and Tsalides P (1998a) Fuzzy Soft Mathematical Morphology, IEE Proceedings: Vision Image and Signal Processing, 145 (1): 40-49.

 

Gasteratos A, Andreadis I and Tsalides P (1998b) Realisation of Soft Morphological Filters, IEE Proceedings - Circuits Devices and Systems, 145 (3): 201-206.

 

Gasteratos A, Andreadis I and Tsalides P (1998c) "Soft Morphological Structuring Element Decomposition", International Symposium on Mathematical Morphology '98, Amsterdam, The Netherlands, pp 407-413.

 

Gerritsen F and Aardema L G (1981) Design and Use of DIP-1: A Fast Flexible and Dynamicaly Microprogrammable Image Processor, Pattern Recognition, 14 (1): 1-6.

 

Giardina C R and Dougherty E R (1988): Morphological Methods in Image and Signal Processing, Prentice-Hall, Englewood Cliffs, New Jersey.

 

Haralick R M and Shapiro L G (1992): Computer and Robot Vision, Addison-Wesley, New York.

 

Haralick R M, Somani A K, Wittenbrink C, Johnson R, Cooper K, Shapiro L G, Phillips I T, Hwang J-N, Cheung W, Yao Y H, ChenC-H, Yang L, Daugherty B, Loberski B, Loving K, Miller T, Parkins L and Soos S (1995) Proteus: a reconfigurable computational network for computer vision, Machine Vision and Applications, 8 (2): 85-100.

 

Haralick R M, Sternberg S R and Zhuang X (1987) Image Analysis Using Mathematical Morphology, IEEE Transactions on Pattern Analysis and Machine Intelligence, 9 (4): 532-550.

 

Heijmans H J A M and Roerdink J B T M, eds., (1998): Mathematical Morphology and its Applications to Image and Signal Processing, Kluwer Academic Publishers, Dordrecht-Boston-London.

 

Hwang K and Briggs F A (1987): Computer Architecture and Parallel Processing, McGraw-Hill, Singapore.

 

Jonker P P (1992): Morphological Image Processing : Architecture and VLSI Design, Kluwer Academic Publishers, Amsterdam, The Netherlands.

 

Klein J C and Serra J (1977) The Texture Analyzer, Journal of Microscopy, 95: 349-356.

 

Ko S J, Morales A and Lee K H (1995) A Fast Implementation Algorithm and a Bit Serial Realization Method for Greyscale Morphological Opening and Closing, IEEE Transactions on Signal Processing, 43 (12): 3058-3061.

 

Kojima S and Miyakawa T (1996) One-Dimensional Processing Architecture for Gray-Scale Morphology, Systems and Computers in Japan, 27 (12): 1-9.

 

Koskinen L, Astola J and Neuvo Y (1991) "Soft Morphological Filters", Proceedings of SPIE Symposium on Image Algebra and Morphological Image Processing, 262-270.

 

Kuosmanen P and Astola J (1995) Soft Morphological Filtering, Journal of Mathematical Imaging and Vision, 5 (3): 231-262.

 

Lin R and Wong E K (1992) Logic Gate Implementation for Gray-Scale Morphology, Pattern Recognition Letters, 13: 481-487.

 

Luck L and Chakrabaty C (1995) A Digit-Serial Architecture For Gray-Scale Morphological Filtering, IEEE Transactions on Image Processing, 4 (3): 387-391.

 

Mano M M (1991): Digital Design, Prentice-Hall, Englewood Cliffs, NJ.

 

Maragos P, Schafer R W and Butt M A, eds., (1996): Mathematical Morphology and its Applications to Image and Signal Processing, Kluwer Academic Publishers, Dordrecht-Boston-London.

 

Park H and Chin R T (1994) Optimal Decomposition of Convex Morphological Structuring Elements for 4-Connected Parallel Processors, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16 (3): 304-313.

 

Park H and Chin R T (1995) Decomposition Of Arbitrarily Shaped Morphological Structuring Elements, IEEE Transactions on Pattern Analysis and Machine Intelligence, 17 (1): 2-5.

 

Petkov N (1993): Systolic Parallel Processing, North-Holland, Amsterdam, The Netherlands.

 

Pitas I and Venetsanopoulos A N (1990): Nonlinear Digital Filters: Principles and Applications, Kluwer Academic Publishers, Boston, Massachusetts, U.S.A.

 

Preston K J, Duff M J B, Levialdi S, Norgen P and Toriwaki J I (1979) Basics of Cellular Logic With Some Applications in Medical Image Processing, Proceedings of the IEEE, 67: 826-857.

 

Pu C C and Shih F Y (1995) Threshold Decomposition of Grey-Scale Soft Morphology into Binary Soft Morphology, CVGIP-Graphical Models and Image Processing, 57 (6): 522-526.

 

Reeves A P (1984) Parallel Computer Architectures for Image Processing, Computer Vision, Graphics and Image Processing, 25 (1): 68-88.

 

Robin F, Renaudin M, Privat G and v.d. Bossche N (1996) Functionally Asynchronous Array Processor for Morphological Filtering of Greyscale Images, IEE Proceedings: Computers and Digital Techniques, 143 (5): 273-281.

 

Rosenfeld A (1983) Parallel Image Processing Using Cellular Arrays, IEEE Computer, 16: 14-20.

 

Schmitt L A and Wilson S S (1988) The AIS-5000 Parallel Processor, IEEE Transactions on Pattern Analysis and Machine Intelligence, 10 (3): 320-330.

 

Serra J (1982): Image Analysis and Mathematical Morphology, Academic Press, London.

 

Serra J (1986) Introduction to Mathematical Morphology, Computer Vision, Graphics, and Image Processing, 35 (3): 283-305.

 

Serra J, ed., (1989): Image Analysis and Mathematical Morphology: Theoretical Advances, Academic Press, London.

 

Serra J and Soille P, eds., (1994): Mathematical Morphology and its Applications to Image Processing, Kluwer Academic Publishers, Dordrecht-Boston-London.

 

Shih F Y and Mitchell O R (1989) Threshold Decomposition of Gray-Scale Morphology into Binary Morphology, IEEE Transactions on Pattern Analysis and Machine Intelligence, 11 (1): 31-42.

 

Shih F Y and Mitchell O R (1991) Decomposition Of Grey-Scale Morphological Structuring Elements, Pattern Recognition, 24 (3): 195-203.

 

Shinha D and Dougherty E R (1992) Fuzzy Mathematical Morphology, Journal of Visual Communication and Image Representation, 3 (3): 286-302.

 

Singh B V and Siddiqi M U (1996) A Simplified Algorithm for Approximate Separable Decomposition of Morphological Templates, Pattern Recognition, 29 (9): 1519-1522.

 

Siskos S, Vlassis S and Pitas I (1998) Analog Implementation of Fast Min-Max Filtering, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 45 (7): 913-918.

 

Soille P (1999): Morphological Image Analysis: Principles and Applications, Springer-Verlag, Berlin, Germany.

 

Urahama K and Nagao T (1995) Direct Analog Rank Filtering, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 42 (7): 385-388.

 

Vlassis S, Siskos S and Pitas I (1998) "Analog Implementation of an Order Statistics Filter", 9th Mediterranean Electrotechnical Conference, MELECON 98, 649 -653.

 

Wendt P D, Coyle E J and Gallagher Jr. N C (1986) Stack Filters, IEEE Transactions on Acoustics Speech and Signal Processing, ASSP-34: 898-911.

 

Xu J (1996) Morphological Decomposition of 2-D Binary Shapes into Simpler Shape Parts, Pattern Recognition Letters, 17 (7):759-769.

 

Zhuang X and Haralick R M (1986) Morphological Structuring Element Decomposition, Computer Vision, Graphics and Image Processing, 35 (3): 370-382.