
Research Article


Characterization of Decomposed Convex Components of Water Bodies 

S. Dinesh



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 selfsimilarity 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.





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: 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: Erosion sets the pixels values within the kernel to the minimum value of the kernel. Erosion is the dual operator of dilation: where A^{c} 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.
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. The elementary dilation process is performed using a standard dilation of size one followed by an intersection. 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.

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:
where n_{i} denotes the number of iterations of erosion and dilation required for the object AA’_{I1} 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.

Fig. 2: 
Water bodies traced from IRS 1D remotely sensed data 
 Fig. 3: 
The
water bodies after removal of incomplete 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 

Fig. 5: 
The evolution of decay of the water bodies into convex components
of deceasing size 

Fig. 6: 
The decomposed convex components of the water bodies 

Fig. 7: 
The union of the decomposed convex components of the water
bodies 
 Fig. 8: 
Loglog
plot of the number of decomposed convex components removed in each iteration
of opening by reconstruction N against the kernel size r 
A loglog 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:
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 selfsimilarity 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 

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 loglog 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 nonwater 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 selfsimilarity 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: 163167.
2: Chockalingam, L. and B.S.D. Sagar, 2005. Morphometry of network and nonnetwork space of basins. J. Geophys. Res., 110: B08203B08203. Direct Link 
3: Dinesh, S., 2007. Zconvex characterization of simulated droughts and floods of water bodies. J. Applied Sci., 7: 15161521. 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. 59, 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. 1012, The Legend Hotel, Kuala Lumpur, Malaysia.
7: Dodds, P.S. and W.E. Weitz, 2002. Packing of limited growth. Phys. Rev. E, 65: 056108056108. CrossRef  Direct Link 
8: Dodds, P.S. and W.E. Weitz, 2003. Packinglimited growth of irregular objects. Phys. Rev. E, 67: 016117.1016117.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: 611618.
11: Kapp, M.N., C.O.A. Freitas and R. Sabourin, 2007. Methodology for the design of NNbased monthword recognizers written on Brazilian bank checks. Image Vision Comput., 25: 4049. Direct Link 
12: Kolesnikov, A. and P. Franti, 2005. Optimal algorithm for convexity measure calculation. Proceedings of the International Conference on Image Processing, September 1114, 2005, IEEE Computer Society, pp: 353356.
13: Latecki, L.J. and R. Lakamper, 1999. Convexity rule for shape decomposition based on discrete contour evolution. Comput. Vision Image Understand., 73: 441454. 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: 11851190. 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: 4764. PubMed  Direct Link 
16: Li, J.L., 2007. Estimates for derivatives of holomorphic functions in a hyperbolic domain. J. Math. Anal. Appl., 329: 581591. 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: 481490. 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: 3845. CrossRef  Direct Link 
21: Popov, A.T., 1996. Fuzzy morphology and fuzzy convexity measures. Proceedings of 13th International Conference on Pattern Recognition, August 2529, 1996, Vienna, Austria, pp: 611614.
22: Radhakrishnan, P., L.L. Teo and B.S.D. Sagar, 2004. Estimation of fractal dimension through morphological decomposition. Chaos. Solitons Fractals, 21: 563572. 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: 692695.
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: 15011512. Direct Link 
25: Rosin, P.L., 2000. Shape partitioning by convexity. IEEE Trans. Syst. Man Cybern. Part A, 30: 202210. 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 2326, 2004, IEEE Computer Society Washington, DC., USA., pp: 1114.
27: Sagar, B.S.D. and L. Chockalingam, 2004. Fractal dimension of nonnetwork space of a basin. Gepphys. Rev. Lett., 31: L12502.1L12502.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: 229235.
31: Tankus, A. and Y. Yeshurun, 2000. A convexity based camouflage breaking. Proceedings of the 15th International Conference on Pattern Recognition, September 37, 2000, Barcelona, Spain, pp: 454457.
32: Teo, L.L., P. Radhakrishnan and B.S.D. Sagar, 2004. Morphological decomposition of sandstone porespace: Fractal powerlaws. Chaos. Solitons Fractals, 19: 339346. Direct Link 
33: Valentine, F., 1964. Convex Sets. McGraw Hill, San Francisco.
34: Varosanec, S., 2007. On Hconvexity. J. Math. Anal. Applic., 326: 303311. Direct Link 
35: Vincent, L., 1993. Morphological reconstruction in image analysis: Applications and efficient algorithms. IEEE Trans. Image Process., 2: 176201. CrossRef 
36: Zunic, J. and P.L. Rosin, 2004. A new convexity measure for polygons. IEEE Trans. Pattern Anal. Mach. Intell., 26: 923934. CrossRef  Direct Link 



