Subscribe Now Subscribe Today
Research Article
 

Characterization of Decomposed Convex Components of Water Bodies



S. Dinesh
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

In this research, water body characterization is performed by decomposing the water bodies into convex components using morphological decomposition. Opening by reconstruction is implemented on the decomposed convex components using square kernels of increasing sizes. A power law relationship is observed between the number of decomposed convex components removed at each iteration of opening by reconstruction and the kernel size. The scaling exponent of this power law is the fractal dimension of the water bodies, which indicates the measure of complexity of the self-similarity of the water bodies. The iterative opening by reconstruction process is implemented on the individual water bodies to compute their fractal dimensions. The computed fractal dimensions are shape dependant and consider the topological regions of water bodies rather than their geometric boundaries.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

S. Dinesh , 2007. Characterization of Decomposed Convex Components of Water Bodies. Journal of Applied Sciences, 7: 1574-1581.

DOI: 10.3923/jas.2007.1574.1581

URL: https://scialert.net/abstract/?doi=jas.2007.1574.1581

INTRODUCTION

Convexity is considered as one of the basic descriptors of shapes. Convexity in image processing has been studied for quite some time (Valentine, 1964; Stern, 1989; Boxer, 1993; Held and Abe, 1994; Popov, 1996; Zunic and Rosin, 2004; Rosin and Mumford, 2004; Rahtu et al., 2004, 2006; Kolesnikov and Franti, 2005; Varosanec, 2007) and has numerous applications, including shape decomposition (Latecki and Lakämper, 1999; Rosin, 2000), camouflage breaking (Tankus and Yeshurun, 2000), object indexing (Latecki and Lakämper, 2000), measurement of border irregularities measurement in medical image analysis (Lee et al., 2003), handwritten word recognition (Kapp et al., 2007) and estimation of derivatives of holomorphic functions (Li, 2007).

An object P is said to be convex if it has the following property: If points A and B belong to P, then all points from the line segment [AB] belong to P as well. The smallest convex set which includes P is called the convex hull of P and is denoted as CH(P). The convexity measure C(P) is defined to be:

Image for - Characterization of Decomposed Convex Components of Water Bodies
(1)

In previous research efforts (Dinesh and Pathmanabhan, 2007a, b; Dinesh, 2007a, b), the characterization of the convexity of water bodies was performed by first computing the convex hulls of the corresponding water bodies. In Dinesh and Pathmanabhan (2007a and b), a fractal power law relationship is observed between the convexity measures and areas of water bodies. Convex hull computation increases the sizes of water bodies. This enlargement is not even; smaller water bodies undergo smaller enlargements compared to larger water bodies and hence, convex hull computation alters the water body size distribution. The computed convex hulls have a more even shapiness index distribution compared to the water bodies, as the water bodies are random chaotic objects while convex hulls are well defined polygons. Convex hull computation also causes a loss of homotopic information. In Dinesh (2007a,b), a fractal power law relationship is observed between the average convexity measures of the simulated droughts/floods of water bodies and the level of droughting/flooding. The scaling exponent of this power law, which was named as a fractal dimension, indicates the rate of change of the convexity of water bodies over varying levels of droughting/flooding.

In this research, water body characterization is performed by decomposing water bodies into convex components using the morphological decomposition (Pitas and Venetsanopoulos, 1990). These decomposed convex components are employed to compute the fractal dimensions of the water bodies.

MATHEMATICAL MORPHOLOGY

Mathematical morphology is a branch of image processing that deals with the extraction of image components that are useful for representational and descriptional purposes. The fundamental morphological operators are discussed in Matheron (1975), Serra (1982) and Soille (2003). Morphological operators generally require two inputs; the input image A, which can be in binary or grayscale form and the kernel B, which is used to determine the precise effect of the operator.

Dilation sets the pixel values within the kernel to the maximum value of the pixel neighbourhood. The dilation operation is expressed as:

Image for - Characterization of Decomposed Convex Components of Water Bodies
(2)

Erosion sets the pixels values within the kernel to the minimum value of the kernel. Erosion is the dual operator of dilation:

Image for - Characterization of Decomposed Convex Components of Water Bodies
(3)

where Ac denotes the complement of A and B is symmetric with respect to reflection about the origin.

An opening (Eq. 4) is defined as an erosion followed by a dilation using the same kernel for both operation. Binary opening preserves foreground regions that have a similar shape to this kernel, or that can completely contain the kernel, while eliminating all other regions of foreground pixels.

Image for - Characterization of Decomposed Convex Components of Water Bodies
(4)

Morphological reconstruction allows for the isolation of certain features within an image based on the manipulation of a mask image X and a marker image Y. It is founded on the concept of geodesic transformations, where dilations or erosion of a marker image are performed until stability is achieved (represented by a mask image) (Vincent, 1993).

The geodesic dilation, δG used in the reconstruction process is performed through iteration of elementary geodesic dilations, δ(1), until stability is achieved.

Image for - Characterization of Decomposed Convex Components of Water Bodies
(5)

The elementary dilation process is performed using a standard dilation of size one followed by an intersection.

Image for - Characterization of Decomposed Convex Components of Water Bodies
(6)

The operation in equation 6 is used for elementary dilation in binary reconstruction. (Vincent, 1993).

Morphological reconstruction is a useful filtering tool. Figure 1a shows an image with circles of various sizes. In order to filter the smaller sized circles, first opening is performed using a square kernel of size 30. The circles that are unable to completely contain the kernel are removed, while the shape of remaining circles is altered (Fig. 1b). Morphological reconstruction is implemented with Fig. 1a being the mask and Fig. 1b being the marker. This restores the original shape of the remaining circles (Fig. 1c). This process is known as opening by reconstruction.

Morphological decomposition (Pitas and Venetsanopoulos, 1990) is a shape representation algorithm that decomposes 2D binary objects into convex components. Each convex component is a subset of the given object and the union of all such components returns the original object. The morphological decomposition of an object into a union of convex components is performed in the following way. The set of maximal inscribable convex components in the object A, that have maximum radius, is found.

Image for - Characterization of Decomposed Convex Components of Water Bodies
Fig. 1: The application of morphological reconstruction in filtering. (a) The original image. (b) The opened image and (c) The reconstructed image

This set is obtained in the following way. The first set of decomposition is subtracted from the object. The set of maximal inscribable disks in the remaining radius, is found. This set is the second cluster of the decomposition. The first and second sets of the maximal inscribable disks are subtracted from the object and the procedure is repeated until the remainder of the object is an empty set. The whole procedure can be described using the following recursive process:

Image for - Characterization of Decomposed Convex Components of Water Bodies
(7)

Image for - Characterization of Decomposed Convex Components of Water Bodies
(8)

Image for - Characterization of Decomposed Convex Components of Water Bodies
(9)

where ni denotes the number of iterations of erosion and dilation required for the object A-A’I-1 to become an empty set.

CHARACTERIZATION OF DECOMPOSED CONVEX COMPONENTS OF WATER BODIES

Figure 2 shows a number of water bodies of varying shape and sizes situated in the flood plain region of Gothavary River, India. The water bodies were traced from IRS 1D remotely sensed data. Due to the impracticalities of dealing with incomplete water bodies, only the complete water bodies are considered (Fig. 3). A total of 67 distinct individual water bodies (Fig. 4) are identified using the connected component labeling algorithm proposed in Pitas (1993).

Morphological decomposition is implemented on the water bodies using a size 3 disk kernel. The rate of decay of the water bodies into convex components of decreasing size (Fig. 5) depends on the area and geometric organization of the water bodies. The decomposed convex components of the water bodies are shown in Fig. 6. The union of the decomposed convex components is shown in Fig. 7, where each category of convex components is assigned with different grey levels.

The decomposition of the water bodies into convex components allows for the possibility to represent water bodies of varying shapes and sizes as unions of simple objects. It is observed that more number of smaller size category convex components exists in the water bodies compared to larger convex components. In order to characterize the size distribution of the decomposed convex components, opening by reconstruction is implemented iteratively on the convex components using square kernels of increasing sizes. In each iteration, opening removes convex components that are unable to completely cover the kernel, while modifying the shape of the remaining convex components. The reconstruction step returns the original shape of the remaining convex components.

Image for - Characterization of Decomposed Convex Components of Water Bodies
Fig. 2: Water bodies traced from IRS 1D remotely sensed data

Image for - Characterization of Decomposed Convex Components of Water Bodies
Fig. 3: The water bodies after removal of incomplete water bodies

Image for - Characterization of Decomposed Convex Components of Water Bodies
Fig. 4:
Identification of the individual water bodies using connected component labeling. The water body count number is determined by the grey level; the brighter the grey level, the larger the water body number

Image for - Characterization of Decomposed Convex Components of Water Bodies
Fig. 5: The evolution of decay of the water bodies into convex components of deceasing size

Image for - Characterization of Decomposed Convex Components of Water Bodies
Fig. 6: The decomposed convex components of the water bodies

Image for - Characterization of Decomposed Convex Components of Water Bodies
Fig. 7: The union of the decomposed convex components of the water bodies

Image for - Characterization of Decomposed Convex Components of Water Bodies
Fig. 8: Log-log plot of the number of decomposed convex components removed in each iteration of opening by reconstruction N against the kernel size r

A log-log plot of the number of convex components removed in each iteration of opening by reconstruction N against the kernel size r is drawn (Fig. 8). A power law relationship is observed between the two parameters:

Image for - Characterization of Decomposed Convex Components of Water Bodies
(10)

Image for - Characterization of Decomposed Convex Components of Water Bodies
(11)

where 7.140 is a constant of proportionality c and 1.887 is the fractal dimension of the water bodies D, which indicates the measure of complexity of the self-similarity of the water body. This power law relationship is consistent with the decomposition power law relationships derived in Manna and Hermann (1991), Dodds and Weitz (2001 and 2003), Teo et al. (2004), Radhakrishnan et al. (2004), Sagar and Chockalingam (2004) and Chockalingam and Sagar (2005).

Table 1: The computed fractal dimensions of the individual water bodies
Image for - Characterization of Decomposed Convex Components of Water Bodies

The iterative opening by reconstruction process is implemented on the individual water bodies. The fractal dimension of each individual water body is the slope of the log-log plot of N against r for the corresponding water body. The computed fractal dimensions for the individual water bodies are shown in Table 1.

This approach to fractal dimension computation takes only into account the internal regions of the water bodies, while discarding the non-water body regions. As the number and size distribution of the decomposed convex components depend on the shape of the water bodies, the computed water body fractal dimensions are shape dependant.

CONCLUSIONS

In this research, the characterization of the decomposed convex components of water bodies was performed. Morphological decomposition was used to decompose water bodies into convex components. Opening by reconstruction was implemented on the decomposed convex components using square kernels of increasing sizes. A power law relationship was observed between the number of decomposed convex components removed in each iteration of opening by reconstruction and the kernel size. The scaling exponent of this power law is the fractal dimension of the water bodies, which indicates the measure of complexity of the self-similarity of the water bodies. The iterative opening by reconstruction process was implemented on the individual water bodies to compute their fractal dimensions. The computed fractal dimensions are shape dependant and consider the topological regions of water bodies rather than their geometric boundaries.

REFERENCES
1:  Boxer, L., 1993. Computing deviations from convexity in polygons. Pattern Recog. Lett., 14: 163-167.

2:  Chockalingam, L. and B.S.D. Sagar, 2005. Morphometry of network and non-network space of basins. J. Geophys. Res., 110: B08203-B08203.
Direct Link  |  

3:  Dinesh, S., 2007. Zconvex characterization of simulated droughts and floods of water bodies. J. Applied Sci., 7: 1516-1521.
CrossRef  |  Direct Link  |  

4:  Dinesh, S., 2007. Characterization of convexity of simulated droughts and floods of water bodies. Proceedings of the World Engineering Congress (WEC'2007), Aug. 5-9, Penang, Malaysia.

5:  Dinesh, S. and A. Pathmanabhan, 2007. Characterization of convexity of water bodies. J. Spatial Hydrol.

6:  Dinesh, S. and A. Pathmanabhan, 2007. Convex characterization of water bodies. Proceedings of the 3rd International Conference on Research and Education in Mathematics (ICREM3), Apr. 10-12, The Legend Hotel, Kuala Lumpur, Malaysia.

7:  Dodds, P.S. and W.E. Weitz, 2002. Packing of limited growth. Phys. Rev. E, 65: 056108-056108.
CrossRef  |  Direct Link  |  

8:  Dodds, P.S. and W.E. Weitz, 2003. Packing-limited growth of irregular objects. Phys. Rev. E, 67: 016117.1-016117.7.
Direct Link  |  

9:  Duchane, P. and D. Lewis, 1996. Visilog 5 Documentation. 1st Edn., Noesis Vision, Quebec, Canada.

10:  Held, A. and K. Abe, 1994. On approximate convexity. Pattern Recog. Lett., 15: 611-618.

11:  Kapp, M.N., C.O.A. Freitas and R. Sabourin, 2007. Methodology for the design of NN-based month-word recognizers written on Brazilian bank checks. Image Vision Comput., 25: 40-49.
Direct Link  |  

12:  Kolesnikov, A. and P. Franti, 2005. Optimal algorithm for convexity measure calculation. Proceedings of the International Conference on Image Processing, September 11-14, 2005, IEEE Computer Society, pp: 353-356.

13:  Latecki, L.J. and R. Lakamper, 1999. Convexity rule for shape decomposition based on discrete contour evolution. Comput. Vision Image Understand., 73: 441-454.
Direct Link  |  

14:  Latecki, L.J. and R. Lakamper, 2000. Shape similarity measure based on correspondence of visual parts. IEEE Trans. Pattern Anal. Mach. Intell., 22: 1185-1190.
CrossRef  |  Direct Link  |  

15:  Lee, T.K., D. McLean and M.S. Atkins, 2003. Irregularity index: A new border irregularity measure for cutaneous lesions. Med. Image Anal., 7: 47-64.
PubMed  |  Direct Link  |  

16:  Li, J.L., 2007. Estimates for derivatives of holomorphic functions in a hyperbolic domain. J. Math. Anal. Appl., 329: 581-591.
Direct Link  |  

17:  Manna, S.S. and H.J. Hermann, 1991. Precise determination of the dimension of Apollonian packing and space filling bearings. J. Phys. A: Math. Theor., 24: 481-490.
Direct Link  |  

18:  Matheron, G., 1975. Random Sets and Integral Geometry. 1st Edn., Wiley, New York.

19:  Pitas, I., 1993. Digital Image Processing Algorithms. 1st Edn. Prentice Hall, London.

20:  Pitas, I. and A.N. Venetsapoulus, 1993. Morphological shape decomposition. IEEE Trans. Pattern Anal. Mach. Intell., 12: 38-45.
CrossRef  |  Direct Link  |  

21:  Popov, A.T., 1996. Fuzzy morphology and fuzzy convexity measures. Proceedings of 13th International Conference on Pattern Recognition, August 25-29, 1996, Vienna, Austria, pp: 611-614.

22:  Radhakrishnan, P., L.L. Teo and B.S.D. Sagar, 2004. Estimation of fractal dimension through morphological decomposition. Chaos. Solitons Fractals, 21: 563-572.
Direct Link  |  

23:  Rahtu, E., M. Salo and J. Heikkla, 2004. Convexity recognition using multiscale autoconvolution. Proceeding of the 17th International Conference on Pattern Recognition, August 26, 2004, IEEE Computer Society Washington, DC, USA., pp: 692-695.

24:  Rahtu, E., M. Salo and J. Heikkila, 2006. A new convexity measure based on a probabilistic interpretation of images. IEEE Trans. Pattern Anal. Mach. Intell., 28: 1501-1512.
Direct Link  |  

25:  Rosin, P.L., 2000. Shape partitioning by convexity. IEEE Trans. Syst. Man Cybern. Part A, 30: 202-210.
CrossRef  |  Direct Link  |  

26:  Rosin, P.L. and C.L. Mumford, 2004. A symmetric convexity measure. Proceedings of the 17th International Conference on Pattern Recognition, August 23-26, 2004, IEEE Computer Society Washington, DC., USA., pp: 11-14.

27:  Sagar, B.S.D. and L. Chockalingam, 2004. Fractal dimension of non-network space of a basin. Gepphys. Rev. Lett., 31: L12502.1-L12502.4.
Direct Link  |  

28:  Serra, J., 1982. Image Analysis and Mathematical Morphology. 1st Edn. Academic Press, London.

29:  Soille, P., 2003. Morphological Image Analysis: Principles and Applications. Springer Verlag, Berlin.

30:  Stern, H.I., 1989. Polygonal entropy: A convexity measure. Pattern Recog. Letters, 10: 229-235.

31:  Tankus, A. and Y. Yeshurun, 2000. A convexity based camouflage breaking. Proceedings of the 15th International Conference on Pattern Recognition, September 3-7, 2000, Barcelona, Spain, pp: 454-457.

32:  Teo, L.L., P. Radhakrishnan and B.S.D. Sagar, 2004. Morphological decomposition of sandstone pore-space: Fractal power-laws. Chaos. Solitons Fractals, 19: 339-346.
Direct Link  |  

33:  Valentine, F., 1964. Convex Sets. McGraw Hill, San Francisco.

34:  Varosanec, S., 2007. On H-convexity. J. Math. Anal. Applic., 326: 303-311.
Direct Link  |  

35:  Vincent, L., 1993. Morphological reconstruction in image analysis: Applications and efficient algorithms. IEEE Trans. Image Process., 2: 176-201.
CrossRef  |  

36:  Zunic, J. and P.L. Rosin, 2004. A new convexity measure for polygons. IEEE Trans. Pattern Anal. Mach. Intell., 26: 923-934.
CrossRef  |  Direct Link  |  

©  2021 Science Alert. All Rights Reserved