Abstract: A novel method for dominant skeleton extraction of textures using different wavelet transforms, is proposed in this study. The skeleton varies depending on the shape of structuring element. If the structuring element is homothetic to the object, the object is covered with only one magnification of the structuring element. By this, the skeleton is reduced to one point. The present study considers the skeleton from a binary texture. The proposed method derives from the above that a total number of pixels within the skeleton is the minimum when structuring element is homothetic to the primitive. This provides the scope that the texture is composed of one primitive, which minimizes the total number of pixels. For evaluating such skeleton primitive the present study utilized a 3x3 structuring element, as the skeleton primitives. All possible skeleton primitives combinations of 3x3 mask are evaluated on all textures. The skeleton primitive that is making the least number of skeleton points is considered as dominant skeleton primitive. Based on the extraction of skeleton primitives a classification is made on textures using Haar, Daubechies, Coiflet and Symlet wavelets. Experimental results indicate a good classification and also a comparison is made among these four wavelet results. Present method is experimented on Brodatz textures using these four wavelets.
INTRODUCTION
Analysis of texture requires the identification of proper attributes or features that differentiate the textures for classification, segmentation and recognition. The features are assumed to be uniform within the regions containing the same texture. Various feature extraction and classification techniques have been suggested in the past for the purpose of texture analysis. Initially, texture analysis was based on the first order or second order statistics of textures (Haralick et al., 1973; Weszka et al., 1976; Chen and Pavlidis, 1983). It is well known that the co-occurrence matrix features are first proposed by Haralick et al. (1973). However, there are 14 features to be computed for different distances at different orientations which increase the computational and time complexity. Even if all the features are used, the correct classification rate of 60-70% was only reported in the literature. Then, Gaussian Markov Random Fields (GMRF) and Gibbs random fields were proposed to characterize textures (Chellappa and Chatterjee, 1985; Cohen et al., 1991). Later, local linear transformations are used to compute texture features (Laws, 1980; Unser, 1986). The above traditional statistical approaches to texture analysis such as co-occurrence matrices, second order statistics, GMRF and local linear transforms are restricted to the analysis of spatial interactions over relatively small neighborhoods on a single scale. As a consequence, their performance is best for the analysis of micro-textures only (Unser, 1995). More recently methods based on multi-resolution or multi-channel analysis such as Gabor filters and wavelet transform have received a lot of attention (Bovik et al., 1990; Chang and Jay Kuo, 1993; Unser, 1995). A major disadvantage in using Gabor transform is that the output of Gabor filter banks are not mutually orthogonal, which may result in a significant correlation between texture features. Moreover, these transformations are usually not reversible, which limits their applicability for texture synthesis. Most of these can be avoided if one uses the wavelet transform, which provides a precise and unifying frame work for the analysis and characterization of a signal at different scales (Unser, 1995). Another advantage of wavelet transform over Gabor filter is that the low pass and high pass filters used in the wavelet transform remain the same between two consecutive scales while the Gabor approach requires filters of different parameters (Chang and Jay Kuo, 1993). In other words, Gabor filters require proper tuning of filter parameters at different scales.
Study of patterns on textures is recognized as an important step in characterization and classification of textures. Textures are classified recently by various pattern methods: preprocessed images (Vijaya Kumar et al., 2007a) long linear patterns (Krishna et al., 2005; Vijaya Kumar et al., 2007b) and edge direction movements (Eswara Reddy et al., 2007), Avoiding Complex Patterns (Vijaya Kumar et al., 2008a) marble texture description (Suresh et al., 2008). Textures are also described and classified by using various wavelet transforms: one based on primitive patterns (Vijaya Kumar et al., 2008b) and another based on statistical parameters (Raju et al., 2008).
Skeletonization is an important tool for many image processing applications. The result of the skeletonization of an image is its skeleton. Skeleton is essentially a one-pixel-thick line that passes through the centre, or medial axis, of an object. An accurate skeleton possesses significant properties that makes it suitable for pattern recognition, machine vision and image compression. Skeletonization allows the extraction of important features such as an image`s topology, orientation and composition. Since its conception by Blum (1967) skeletonization has been studied extensively and there now exist many techniques and algorithms for performing skeletonization. There currently exist many skeletonization methods, each utilizing different algorithms and different information contained in an image. Recently new algorithms for skeletonizaiton and thinning for 2D images based on primitive concept approach are proposed by Vijaya Kumar et al. (2008c, d). Most of the methods, however, fall into one of the two broad categories: Pixel based method and Non-pixel based method. In the pixel-based method, each foreground pixel is utilized for computation in the skeletonization process. Techniques used in the pixel-based method include thinning (Lam et al., 1992; Unser, 1986) and distance transform (Unser, 1986). In the nonpixel based method, the skeleton of a shape is analytically derived from the border of the image. There are two types of nonpixel based methods, which are based on either cross section (Pavlidis, 1986) or Voronoi diagrams (Ogniewicz and Kubler, 1995). These methods attempt to determine the symmetric points of a shape without the intermediate step of the grassfire propagation. The fundamental concept of these methods is that the local symmetric axes of a shape are derived from pairs of contour pixels or a contour segment representing a sequence of the contour pixels. Although more than 300 skeletonization algorithms have been proposed by Lam (1992) the improvement is still required, since the existing approximation algorithms of skeletonization often suffer from one or more of the drawbacks (Chang and Yan, 1999; Ge and Fitzpatrick, 1996; Lam, 1992; Smith, 1987; Zou and Yan, 1999). To overcome these problems, a novel wavelet-based method is presented in this study.
The wavelet transform is a multi-resolution technique, which can be implemented as a pyramid or tree structure and is similar to sub-band decomposition (Antonini et al., 1992; Daubechies, 1992). There are various wavelet transforms like Haar, Daubechies, Coiflet, Symlet and etc. They differ with each other in the formation and reconstruction. The wavelet transform divides the original image into four subbands and they are denoted by LL, HL, LL and HH frequency subbands. The HH subimage represents diagonal details (high frequencies in both directions ), HL gives horizontal high frequencies (vertical edges), LH gives vertical high frequencies (horizontal edges) and the image LL corresponds to the lowest frequencies. At the subsequent scale of analysis, the image LL undergoes the decomposition using the same filters, having always the lowest frequency component located in the upper left corner of the image. Each stage of the analysis produces next 4 subimages whose size is reduced twice when compared to the previous scale. i.e. for level n it gives get a total of 4+(n-1)*3 subbands. The size of the wavelet representation is the same as the size of the original. The Haar wavelet is the first known wavelet and was proposed in 1909 by Alfred Haar. Haar used these functions to give an example of a countable orthonormal system for the space of square-integrable functions on the real line. The Haar wavelet`s scaling function coefficients are h{k} = {0.5, 0.5} and wavelet function coefficients are g{k} = {0.5, -0.5}. The Daubechies (1992) are a family of orthogonal wavelets defining a discrete wavelet transform and characterized by a maximal number of vanishing moments for some given support. With each wavelet type of this class, there is a scaling function which generates an orthogonal multiresolution analysis.
MATERIALS AND METHODS
On a 3x3 structuring element by assuming always center pixel as one, one can have 28 combinations. However the present study has not considered the following structuring element as shown in Fig. 1 for extracting skeleton primitives. By this there will be a total of 255 structuring elements on a 3x3 mask. These structuring elements are used for evaluating skeleton points, means the skeleton of an object has the property that it is reduced to one point when the structuring element used for the skeletonization is exactly homothetic to the object.
| Fig. 1: | Structuring element that has not been considered for skeletonization |
| Fig. 2: | Structuring element weight representation |
This method minimizes the number of pixels contained in the skeleton. If the texture is composed of one primitive, the structuring element minimizes the number of pixels which is homothetic to the primitive because of the above property of the skeleton.
The structuring elements are represented by weight based system as shown in Fig. 2 which are called as Structuring Element Weight (SEW). Some of the skeleton structuring elements with their weights are represented
The present study proposes a novel method of the texture primitive description that requires no assumption on the distribution of grain sizes or the granulometric moments of the primitives. The present study employs the morphological skeleton for this method. The most commonly employed morphological skeleton of a binary object is explained intuitively as follows: At first it locate the largest magnification included within the object and cover the object by sweeping the magnification within the object. Then gradually smaller magnifications are employed for covering the residual area until the whole object is covered. The skeleton varies depending on the shape of the structuring element. If the structuring element is homothetic to the object, the object is covered with only one magnification of the structuring element. In this case the skeleton is reduced to one point. The present study consider here obtaining the skeleton from a binary texture. It is derived from the above property that the total number of pixels within the skeleton is the minimum when the structuring element is homothetic to the primitive, if the present paper assumes that the texture is composed of one primitive, i.e., contains grains that are magnifications of the primitive. This indicates that the primitive is described by the optimal structuring element minimizing the total number of pixels within the skeleton.
| Fig. 3: | Representation of structuring element with corresponding weights (a) 3 (b) 5 (c) 7 (d) 23 (e) 31 (f) 63 (g) 165 (h) 207 and (i) 255 |
This primitive description method has an advantage that no assumption on the sizing distribution of grains in the texture is required.
The entire process is explained in Algorithm 1 and 2. The present study have used four wavelet transforms namely, Haar, Daubechies (Db6), Coiflet (Cf6) and Symlet (Sym8) Wavelet transform.
Algorithm 1: To find Skeleton of an image
Begin
End
Algorithm 2: Texture skeleton primitive extraction
Begin
End
RESULTS
The Table 1-4 indicate the dominant skeleton primitives on all 24 Brodatz textures (Brodatz, 1966) using Haar, Db6, Cf6 and Sym8 wavelet transforms, respectively. Based on this the dominant skeleton subset is applied on all 24 Brodatz textures for skeletonization purpose using Haar, Db6, Cf6 and Sym8 wavelet transforms.
| Table 1: | Textures with least skeleton points corresponding to their SEW by using Haar wavelet transform |
Due to lack of space the present paper is presenting three Brodatz skeletonized textures using Haar, Db6, Cf6 and Sym8 in Fig. 4-6, respectively.
The skeleton images of dominant primitive skeleton with weight 255 is not showing any difference for textures D2 and D10 in all four wavelet transforms. However the skeletoned image D25 with weight 255 is not similar in the four wavelet transformed images.
| Table 2: | Textures with least skeleton points corresponding to their SEW by using Db6 Wavelet Transform |
| Table 3: | Textures with least skeleton points corresponding to their SEW by using Cf6 Wavelet Transform |
| Table 4: | Textures with least skeleton points corresponding to their SEW by using Sym8 Wavelet Transform |
| Fig. 4: | The skeletonization of the Texture D2 using (a) Haar wavelet (b) Db6 wavelet (c) Cf6 wavelet and (d) Sym8 wavelet |
Textures are also grouped by the skeleton primitive weight. The groups are listed in the following Table 5.
From Table 5, it is clearly evident that a total of 17 textures are having a common structuring element weight of 255. One texture is having a common structuring element weight of 24. That is 18 out of 24 textures are showing a common classification in all four wavelets, which results a 75% correct classification.
| Fig. 5: | The skeletonization of the Texture D10 using (a) Haar wavelet (b) Db6 wavelet (c) Cf6 wavelet and (d) Sym8 wavelet |
| Fig. 6: | The skeletonization of the Texture D25 using (a) Haar wavelet (b) Db6 wavelet (c) Cf6 wavelet and (d) Sym8 wavelet |
| Table 5: | Texture groups according to SEW |
CONCLUSION
The present research have proposed a novel scheme of texture classification using skeleton primitives. The results indicate that even though the structuring element weight is same for some texture, the result may vary depending on the wavelets that are used. The common classification rate is 75% among the four wavelets for the 3x3 structuring element. The present paper has not used 2x2 square structuring element, for images because they are sensitive to stroke thickness, size and orientations. To reduce the orientation effect and sensitiveness to skeletonization, the present paper employed in the present system a 3x3 skeleton primitive. The same method can be extended to 5x5, 7x7...NxN masks also.
ACKNOWLEDGMENTS
The authors would like to express their gratitude to Sri K.V.V. Satya Narayana Raju, Chairman and K. Sashi Kiran Varma, Managing Director, Chaitanya group of Institutions for providing necessary infrastructure. Authors would like to thank anonymous reviewers for their valuable comments and Dr. G.V.S. Ananta Lakshmi for her invaluable suggestions which led to improvise the presentation quality of this study.