Abstract

In 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 mathematical tool that separates a signal into a representation that shows signal details and trends as a function of time. This representation can be used to characterize transient events, reduce noise, compress data, and perform many other operations. The main advantages of wavelet methods over traditional Fourier methods are the use of localized basis functions and the faster computation speed. Wavelet transform has used for more applications. Now 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. As for the applications of wavelet theory to pattern recognition, can be considered them to be two ways1?

1 System-component-oriented

2 Application-task-oriented

And Figure 1 displays the two ways. It is clear that the two sides are related to each other. Each group of the right side relates to the component of the left side. For instance, invariant representation is related to feature extraction 1.

Figure 1: Pattern recognition with wavelet

Feature extraction is a heart of a pattern recognition 2. Some authors 3, 4 extract 1-D features from 2-D patterns. The advantage of this approach is that we can save space for the database and reduce the time for matching through the whole database. The apparent drawback is that the recognition rate may not be very high because less information from the original pattern is retained. In this paper, we use 2-D features for pattern recognition in order to achieve higher recognition rate.

Fourier descriptor has been a powerful tool for pattern recognition 5. 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 6. 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 7, 8.

The study 9 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. Objectives

In 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. Discrete Wavelet Transform

The concept of the discrete wavelet transform is shown in Figure 2.

gn

2

X1,Ln

2

hn

xn

X1,Hn

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 down-sampling by the factor of 2, 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 just like the mother wavelet function in the continuous wavelet transform, and hn is the just like the scaling function in the continuous wavelet transform. The coefficients of Daubechies filters are usually used for hn and gn. x1,Ln is the rough part of the input 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 Transform

2D wavelet transform is shown in Figure 3. 2D wavelet transform is the combination of two 1D wavelet transform. First, we do the 1D wavelet transform along n, and then do the 1D wavelet transform along m.

Figure 3: The concept of 2D discrete wavelet transforms.

When we use the 2D discrete wavelet transform in an image, 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 xLL is just like the original image, and the HL, xLH, xHH

are respectively corresponding to the horizontal edges, vertical edges, and corners.

2. Fourier-wavelet descriptor for pattern recognition

Given a pattern image which may consist of several disconnected parts such as road signs or oriental characters, we are going to derive invariant features from it. The translation invariance can be achieved by translating the origin of the coordinate system to the center of mass of the pattern, denoted by . The scale invariance can be obtained by transforming the pattern image into a polar coordinate system. Let be the longest distance from to a point on the pattern. We draw concentric circles centered at with radius . Also, we form angularly equispaced radial vectors departing from with angular step . For any small region:

We calculate the average value of over this region, and assign the average value to in the polar coordinate system. The feature obtained in this way is also invariant to scaling, but the rows may be circularly shifted if we different orientation.

With regard to rotational invariance, we can apply 1-D Fourier transform along the axis of the polar angle ? of to obtain its spectrum. Since the spectra of Fourier transform of circularly shifted signals are the same, we obtain a feature which is also rotation invariant. As we know wavelet coefficients represent pattern features at different resolution levels, we apply the wavelet transform along the axis to the radius of the resulting so that we can query the pattern feature database from coarse scales to find scales.

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 1 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 10, 11 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 12. 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

In order to test the efficiency of PFW algorithms, we use a set of printed Chinese characters in our experiment. In 13, Fourier descriptors together with a new associative memory classifier for recognition were developed and tested on the same set of Chinese characters. The original Chinese character is represented by pixels, and so is the polarised character. Since the spectrum of 1-D Fourier transform is symmetric, we only keep half of the Fourier coefficients. Therefore, the size of is and so is the size of the wavelet coefficients .

Because translation will not change the relative position of the center of mass of the character, our major concern is the system’s performance on rotation and scaling. For each character, we tested six rotation angles and six scaling factors. The six-rotation angles are 30o, 60o, 90o, 120o, 180o and 270o, and the six different scaling factors are and . We get recognition rate for all the rotation angles. The recognition results for different scaling factors are given in Table 1, while the recognition results for the combination of rotation and scaling are shown in Table 2. These results demonstrate the effectiveness of this feature extraction algorithm against geometric distortion.

The above experimental results are obtained by using Haar wavelet. We also test Daubechies-4, Coiflet-3, and Symmlet-8. 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.

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: Recognition result for different scaling factors.

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: Recognition rate for different rotation angles and scaling factors.

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.