Study and Analysis of Wavelet Transform for Pattern RecognitionAbstractIn this paper, we study the application of wavelet transforms in an important area which is pattern recognition. In the area of pattern recognition, we propose and implement invariant descriptor for the recognition of 2-D patterns. The invariant descriptor can be used for any pattern. We first transform the pattern to polar coordinate (r, ?) using the center of mass of the pattern as origin, then apply the Fourier transform along the axis of polar angle ? and the wavelet transform along the axis of radius r. By this way the features are obtained by invariant to translation and rotation. The results show that the invariant descriptor is the efficient representation and can be provided for reliable recognition rate.1. Introduction A wavelet transform is a numerical tool to show a signal details and pattern as a function of time.
This representation can be utilized to describe transient events, decrease noise, compress data, and perform numerous different operations. Wavelet investigation manages extension of function not in term of trigonometric polynomials but rather as far as wavelets, which are created as interpretations and expansions of a fixed function called mother wavelet. The wavelets are localized in time and frequency; there are a closer connection between the represented function and coefficient function. The goal of wavelet transform is to characterize the basis function and find effective techniques for their calculation.
It can be demonstrated that each application utilizing the Fast Fourier transform (FFT) can be defined utilizing wavelets to give more frequency information and localized temporal. Therefore, wavelet spectrum can be used instead of frequency spectrum. 1 Wavelet transform has used for more applications. in this study, we will introduce wavelet for pattern recognition. Pattern recognition can do with not only wavelet transform but also other transforms and mathematics. With respect to the applications of wavelet transform for pattern recognition.
The uses of wavelet method can be viewed as two ways: “1. System-component-oriented. 2. Application-task-oriented.”2.
The two ways can be shown as in Figure 1And Figure 1 displays the two ways. The two groups are identified with each other, this meaning the segment of group in right side are identifies with the segment of the left side. For example, invariant representation is related to feature extraction 2. Figure 1: wavelet method for pattern recognition. The heart of pattern recognition techniques is Feature extraction 3. A few study 4, 5 separate 1-D features from 2-D patterns. The benefit of this approach is that we can save space for the database and reduce the time for matching through the entire database. The apparent drawback is that the recognition rate may not be high because less data from the first pattern is held.
In this study, we utilize 2-D features for pattern recognition with a specific end goal to get higher recognition rate.Fourier descriptor has been a powerful tool for pattern recognition 6. It has many useful properties, one of which is that shifts in the time domain do not affect the spectrum in the frequency domain, i.e.
Fourier transform is translation invariant with respect to the spectrum. However, the frequency information obtained from the Fourier descriptor is global; a local variation of the shape can affect all the Fourier coefficients. In addition, Fourier descriptor does not have a multi-resolution representation. Therefore, we are expecting descriptor that could have better properties.In the past few years, wavelet basis functions have become popular for localized frequency analysis, since they have short time resolution for high frequencies and longtime resolution for low frequencies.
Although wavelet descriptors have many advantages, they are not translation invariant. A small shift of the original signal will cause totally different wavelet coefficients. This is the reason why wavelet transform is not widely used in pattern recognition community. Thus the Fourier descriptor and wavelet descriptor both have good properties and drawbacks, In this study we are going to combine them in order to compensate each other to obtain a descriptor which is not only invariant under translation, rotation and scaling, but also has a multi-resolution matching ability. It should be mentioned that both Fourier transform and wavelet transform used in this paper are discrete transforms.
1.1. Literature review Wavelet is a relatively recent development mathematics in the 1980s, and it can be applied in lots of fields, like JPEG2000. JPEG2000 is a new technique for image compression. In the standard JPEG, discrete Fourier transform (DFT) is used, and in the JPEG2000, discrete wavelet transform used to replace DFT 7. Another application of wavelet transform is Edge and Corner Detection, an important issue in pattern recognition is to locate the edges. With wavelet transform, analyze a portion of a signal with different scales can be used. Then the noise and actual corner can be distinguished more precisely.
Wavelet transform also can be used in Filter design, as the wavelet transform can distinguish the noise and signal edge. We can design an anti-noise filter without distortion of the original signal 8, 9.The study 10 introduce another application of wavelet transform which is an analysis of the Electrocardiogram (ECG). An ECG is not smooth with many sudden transitions.
If we analyze the spectrum, noises and desired signal transitions cannot be separated using ordinary filters. Here wavelet transform can also remove the noise and preserve the features of ECG.In the present study, we study and analysis the wavelet transform for pattern recognition which depends on feature extraction of the data. 1.2. ObjectivesIn this paper we use 2-D features for pattern recognition in order to achieve higher recognition rate.
Using PFW algorithm to test the system’s performance on rotation and scaling for a character. The paper is organized as follows. Section 2 is a brief overview of the discrete wavelet transform. Section 3 derives the algorithm and provides a brief overview of its connection with the ring-project approach.
Section 4 introduces a set of wavelet filters and shows the multi-resolution technique of wavelet transform. And finally, as an example, Section 5 gives experimental results for recognizing printed Chinese characters. 2. MethodologyFeature extraction 49 is a crucial processing step for pattern recognition, and most research has been given to discovering measures that show a pattern and that at the same time contain enough information to ensure reliable recognition. In general, good features must fulfill the following requirements: first, intraclass variance must be little, which implies that features got from various examples of the similar class out to be close( for example numerically close if numerical features are selected). Futhermore, the intraclass partition ought to be large. i.e.
that features got from testes of various classes should contrast altogether. Moreover, features ought tobe independent of the size and location of the pattern. This independence can be accomplished by processing or by extracting features that are translation, rotation, and scale invariant. In this study we present a PFW algorithm for invariant pattern recognition based on a mix of wavelet transform and Fourier transform so as to repay each other to get descriptor in ability of multi-resolution matching. It ought to be specified that both wavelet transform and Fourier transform is discrete transform.2.
1 Discrete Wavelet Transform The discrete wavelet transform can be represented as in Figure 2. Figure 2: The concept of the discrete wavelet transform. Where xn is the input, hn is the high pass filter, gn is the low pass filter, and?2 is the factor of 2 down-sampling, x1, Ln is the output of the low pass filter, and x1, Hn is the output of the high pass filter. Where the gn is much the same as mother wavelet function in the continuous wavelet transform, and hn is the simply like the scaling function in the continuous wavelet transform.
The coefficients of Daubechies filters are normally utilized for hn and gn. x1,Ln is the rough piece of the information xn, and x1,Hn is the detail part of input. In image compression, we usually keep x1, Ln and discard x1, Hn to achieve the compression.2.1. 2D Wavelet Transform2D wavelet transform is appeared in Figure 3. 2D wavelet transform is the combination of two 1D wavelet transform. First, we do the 1D wavelet transform along n, and after that do the 1D wavelet transform along m.
Figure 3: The principle of 2D discrete wavelet transforms.The output of the 2D discrete wavelet transform in an image contain 4 part of the output, , we will obtain 4 part of the output, which the size of each part is one-fourth of the original size. Figure 4 is the output of Lena processed by 2D discrete wavelet transform. Figure 4: Lena processed by 2D discrete wavelet transform. We can see that the LL is just like the original image, and the HL is vertical details, LH is a horizontal details, and HH is a diagonal or corner details. 3. Fourier-wavelet descriptor for pattern recognition Consider we have pattern image which includes many separate parts like oriented characters or road signs, we want to achieve invariant features from it. To obtain the invariance translation, the origin of the Cartesian coordinate system should be changed to the center of the mass of the pattern, which defined as by changing the pattern image to the polar coordinate system and finding the maximum distance ( ), from the origin to the point on the pattern by this ways the scaling invariance can be obtained.
And then draw circles with radius and centered at the origin . For every small region we change the form of angularly equi-spaced to the radial vectors and angular step . After that to obtain in the polar coordinate system we find the average value of for each region over this region . The result of is feature invariant to scaling. But if we use varied orientation the rows may be shifted circularly.1-D Fourier transform for the polar angle ? of can be applied with respect to invariance rotational to achieve its spectrum. As we know the Fourier transform of the circular signals are equally, therefore the features that obtained is also invariant rotation. Since wavelet coefficients can be represent pattern features at varied resolution steps, so the wavelet transform with respect to the radius of the result .
The pattern feature database contains all scales of wavelet coefficients for each pattern in the training dataset. For the coarset scale, the target feature is matched against all possible patterns in the database. Since the number of coefficients is the coarset scale is quite small, the matching process can be carried out quickly even though the number of patterns in the database may be very large. During each scale we have three decisions to make: (1) If only one valid target identifications is found, we terminate the matching process and mark the target to be unambiguously identified; (2) If all pattern have to be rejected, then we stop the querying process and mark the target as an unknown target; (3) If we have more than one valid target identifications, we, over on to the next finer scale and follow the same procedure as above. Because at finer scales we only need to consider those patterns marked to be refined by the last step, we can fulfill the querying process quickly even through we have more coefficients at finer scales. The matching process continues in this way until we identify the target or reject it. The steps of the algorithm called PFW can be summarized as follows:1. Find the centroid of the pattern and transform into the polar coordinate system to obtain .
2. Conduct 1-D Fourier transform on along the axis of polar angle ? and obtain its spectrum: 3. Apply 1-D wavelet transform on along the axis of radius r: 4. Use the wavelet coefficients to query the pattern feature database at different resolution levels.Figure 5 is the block diagram of the PFW algorithm, and Figure 6 depicts how a printed Chinese character is transformed after each step of the PFW algorithm. Figure 6(a) is the character in (x,y) coordinate system.
Figure 6(b) is the polarized character in a polar coordinate system where each unit in the axis of the Polar Angle represents 6 degrees. Figure 6(c) shows the spectral density of the Fourier transform , and Figure 6(d) show the wavelet coefficients Figure 5: Block diagram of the PFW algorithm. Figure 6: An illustration of how a printed Chinese character is transformed after each step of the PFW algorithm. (a) The original printed Chinese character in Cartesian coordinates (b) The polarized character in polar coordinates where each unit in the axis of the Polar Angle represents 6 degrees (c) The Fourier spectrum of the polarized character (d) The wavelet coefficients based on the Fourier spectrum. It is noted that the feature extracted by PFW algorithm is a superset of that of the Ring-Projection approach.
The study 2 introduces the Ring-Projection of a pattern by Where r is the radius of the ring. It is shown that is equal to the patterned mass distributed along circular rings. From Fourier transform we have When , we get the average value along the axis of radius i.e. The PFW algorithm extracts more features from the pattern than the Ring-Projection approach does.
Therefore, we expect the PFW algorithm gives higher recognition rate. 4. Wavelet and Multi-resolution Analysis The wavelet transform 11, 12 is well suited for localized frequency analysis because the wavelet basis functions have short time resolution for high frequencies and longtime resolution for low frequencies. In addition, wavelet representation provides a coarse-to-fine strategy, called multireslolution matching 13. The matching starts from the coarset scale and moves on to the finer scales.
The costs for different levels are quite different. Since the coarset scale matching, while only a few patterns will need information at finer scales to be identified. Therefore, the process of multiresolution matching will be faster compared to the conventional matching techniques.
The basic equation of the multiresolution analysis theory is the dilation (or scaling) equation, Which defines the cascade for the multiresolution approximation space using the wavelet family with the scaling function . It has been shown that except the Haar wavelet, all other wavelets with desirable properties can only be expressed by the implicit equation. Nevertheless, once the coefficients ‘s are known, all other properties of this family are completely determined. Associated with the scaling function , we can define the wavelet function by: Where Figure 7: The wavelet families used in our experiment In order to test the performance of different wavelet family, we use the following wavelet filters.These wavelet filters are reproduced from WAVELAB developed by D.L. Donoho.The Haar filter is discontinuous and can be considered a Daubechies-2.
Its scaling filter is The Daubechies-4 filter has its advantage on its most compact support of 4 and its orthonormality. The size 4 is indeed shortest even span in which the second derivatives are computable. Its scaling filter is The Coiflet filters are designed to give both the mother and father wavelets 2, 4, 6, 8, or 10 vanishing moments.
Here we only test the 2 vanishing moment case. Its scaling filter is The Symmlet-8 is the least asymmetric compactly-supported wavelets with 8 vanishing moments. Its scaling filter is (-0.107148901418, -0.041910965125, 0.703739068656, 1.
136658243408, 0.421234534204, -0.140317624179, -0.017824701442, 0.04557045896) 5. Experimental Results Our experiment in this study, we use a chines character to test the performance of PFW algorithm.The original character is defined as pixels, and so the character is polarized in polar coordinate. Because of Fourier transform is symmetric, the half of the Fourier coefficients are remained, therefore became also it’s a size of the wavelet coefficients.
The main goal of this study is to test the system’s efficiency on scaling and rotation factors, therefore we test six scaling factors and six rotation angles for every character. The sic scaling factors are 0.5, 0.6, 0.7, 0.8, 0.9, and 1.
2, and the six different rotation angles are30o, 60o, 90o, 120o, 180o and 270o. As a result, for the different rotation angles we obtain %100 recognition rate. Table 1 shows different scaling factor and the results of recognition, while table 2 shows the results of recognition in combination of scaling and rotation together. Percentage (%) Scaling Factor 0.5 0.
6 0.7 0.8 0.9 1.2 Recognition Rate 98.
82 100 100 100 100 100 Error Rate 0 0 0 0 0 0 Rejection Rate 1.18 0 0 0 0 0 Table 1: Scaling factors and Recognition Rate. Scaling Factor Rotation Angle 30o 60o 90o 120o 180o 270o 0.5 96.65% 96.47% 92.94% 90.59% 92.
94% 95.29% 0.8 100% 100% 100% 100% 100% 100% 1.
2 100% 100% 100% 100% 100% 100% Table 2: Different scaling and angles factor with recognition rate. The Haar wavelet transform is used in the above experiment, but also the other wavelet types such as (Daubechies-4, Coiflet-3, and Symmlet-8) are use. The results were nearly the same this means %100 of recognition rate are obtained for most experimenting cases.The experimental results are nearly the same no matter which wavelet family is used, i.e. we obtain correct rate for most testing cases. Since the wavelet coefficients of a signal have a multiresolution representation of the original signal, we use a coarse-to-fine matching strategy.
The coarse scale wavelet coefficients normally represent the global shape of the signal, while the fine scale coefficients represent the details of the signal. Due to noise introduced in the original image and the errors accumulated in the process of polarization, the detail confidence is becoming less important than the coarse scale coefficients. However, for characters with similar shapes, the coefficients at finer scales have to be used in order to discriminate them. . Conclusion The PFW algorithm proposed by this paper is a computational reliable tool for pattern recognition. The algorithm is invariant to translation, rotation, and scaling. We achieve very high recognition rate for all different rotation angles and scaling factors by using different wavelets. We employ a multi-resolution matching technique in our algorithm so that the matching process can be accomplished cheaply.
It should be noted that although our experiments are done on a set of printed Chinese characters, our method is equally applicable to other pattern recognition problems. Future work can also be done for recognizing more deformed and noisy patterns by incorporating neural network into the PFW algorithm. References 1 A. Yamamoto and D. T. L.
Lee, “Wavelet Analysis?: Theory and Applications,” Hewlett-Packard J., no. December, pp. 44–52, 1994.2 Y. Y. Tang, L.
H. Yang, J. Liu, H.
Ma, wavelet theory and its application to pattern recognition. singapore: world scientific, 2000.3 ØivindDue Trier‡Anil K.Jain§TorfinnTaxt, “feature extraction methods for character recognition a-survey,” Sci. Direct, vol.
29, no. 4, pp. 641–662, 1996.
4 po-C. and W.-G. L. Shuen-Shyang Wang, C. H. L.
and C. Y. S. Yuan Y. Tang, Bing F. Li, Hong Ma, Jiming Liu, and Gene c.-H.
Chang and C.-C. Jay Kuo, “wavelet descriptor of planar curves,” ICPR96, vol. 5, pp. 1735–1742, 1996.
5 Gene c.-H. Chang and C.-C.
Jay Kuo, “wavelet descriptor of planar curves: Theory and applications,” IEEE Trans. Image Process., vol. 5, pp. 56–70, 1996.6 G. H. Granlund, “Fourier Processing for Handwritten Character Recognition,” IEEE Transcomput, vol.
21, pp. 195–201, 1992.7 M.
Rabbani and R. Joshi, An overview of the jpeg 2000 still image compression standard. 2002.8 J. M. Shapiro, “Embeddes image coding using zerotrees of wavelet coefficients,” vol. 41, pp. 3445–3462, 1993.
9 A. S. and W. A. Pearlman, “A new, fast, and efficient image codec based on set partitioning in hierarchical trees,” vol. 6, pp.
243–250, 1996.10 P. M. A. K.
Louis and A. Rieder, “Wavelet Theory and Applications,” John Wiley, 1997.11 C. K. Chui, An introduction to Wavelets. Boston: Academic Press, 1992.
12 I. Daubechies, “Orthonormal Bases of Compactly Supported Wavelets,” Pure Appl. Math.
, vol. 315, pp. 909–996, 1988.13 S. Mallat, “Multiresulotion Approximationa and Wavelet Orthonormal Bases of L2(R),” Trans. Amer. Math.
Soc, vol. 315, pp. 69–87, 1989.14 C. Y.
S. and T. D. B.
Ming Zhang, “Feature Extraction In Character Recognition With Associative Memory Classifier,” Int. J. Pattern Recognit. Artif. Intell., vol.
10, pp. 325–348, 1996.
