Scale-invariant pattern recognition using a combined Mellin radial harmonic function and the bidimensional empirical mode decomposition

doi:10.1364/OE.17.016581

« Show journal navigation

Scale-invariant pattern recognition using a combined Mellin radial harmonic function and the bidimensional empirical mode decomposition

Qingbo yin, Liran Shen, Jong-Nam Kim, and Yong-Jae Jeong »View Author Affiliations

Optics Express, Vol. 17, Issue 19, pp. 16581-16589 (2009)
http://dx.doi.org/10.1364/OE.17.016581

View Full Text Article

Acrobat PDF (1542 KB)

Journal Search
Article Lookup

Article Tools

Citations

Alert me when this article is cited
Export Citation/Save

Article Navigation

▸ Article Outline
– Abstract
1. Introduction
2. Theory
3. Simulation and results
4. Conclusions
– References and links

Article Tools
Full Text
Article Info
References
Cited By
Figures
Metrics
Download PDF

Viewing Equations in the
HTML Article

Optimal Viewing Recommendations

Full Text
Article Info
References (6)
Cited By
Figures (5)
Metrics

Abstract

A novel scale and shift invariant pattern recognition method is proposed to improve the discrimination capability and noise robustness by combining the bidimensional empirical mode decomposition with the Mellin radial harmonic decomposition. The flatness of its peak intensity response versus scale change is improved. This property is important, since we can detect a large range of scaled patterns (from 0.2 to 1) using a global threshold. Within this range, the correlation peak intensity is relatively uniform with a variance below 20%. This proposed filter has been tested experimentally to confirm the result from numerical simulation for cases both with and without input white noise.

1. Introduction

A major goal of the pattern recognition is to find methods that could provide some distortion-invariant recognition, i.e. the detection process has low sensitivity to the deformations of input objects. Typically, three deformations are considered: position, rotation, and scale changes of the input. The scale-invariant pattern recognition is a more difficult problem and requires special attention owing to the difference in energy for different scales and no inherent periodicity.

In 1988, Mendlovic introduced the Mellin radial harmonic function into a filter design, which is called the RHF filter, for scale-invariant pattern recognition [1

D. Mendlovic, E. Maron, and N. Konforti, “Shift and scale invariant pattern recognition using Mellin radial harmonics,” Opt. Commun. 67, 172–176(1988). [CrossRef]

]. However, with varying scale of the input pattern, this method results in variations of correlation peak intensity (CPI). This characteristic severely limits the allowable scale range for the input pattern. To improve the discrimination capability, several methods have been proposed, which include mainly the phase-only radial harmonic filter (PORHF), wavelet radial harmonic filter (MRHW) and so on [2

A. Moya, J. J. Esteve-Taboada, J. Garcia, and C. “Ferreira, Shift- and scale-invariant recognition of contour objects with logarithmic radial harmonic filters,” Appl. Opt. 39, 5347–5351(2000). [CrossRef]

, 3

Yih-Shyang Cheng and Hui-Chi Chen, “Improved performance of scale-invariant pattern recognition using a combined Mellin radial harmonic function and wavelet transform,” Opt. Eng. 46, 107204 (Oct. 29, 2007) [CrossRef]

]. But the phase-only based filters provide poor discrimination in a noisy environment. The wavelet transform performs the function of a bandpass filter, which partially removes the lower-frequency part, and also reduces the high-frequency noise. However, its main disadvantage is that the wavelet basis function must be designated in advance and the different basis functions will lead the different results.

In the present paper, scale-invariant pattern recognition is achieved by combining bidimensional empirical mode decomposition (BEMD) in the RHF filter design, which is named as BEMD_RHF filter. The BEMD_RHF is obtained by making the high frequency component (the first IMF) as the reference pattern of the RHF filter, and the edge of the residual of the input pattern without the first three IMFs as the test pattern for denoising. The proposed filter provides a wider allowable scale change of the object.

2. Theory

Shift- and scale-invariant pattern recognition can be achieved by using radial-harmonic expansion, in which the reference image is decomposed into a series of radial harmonic components [1

D. Mendlovic, E. Maron, and N. Konforti, “Shift and scale invariant pattern recognition using Mellin radial harmonics,” Opt. Commun. 67, 172–176(1988). [CrossRef]

]. The shift- and scale-invariant correlation is thus achieved if a single harmonic component from the expansion is used as a matched filter. A 2-D pattern f(r,θ) can be decomposed into a set of

RHF {r^{i 2 πm - 1}}

in polar coordinates:

f (r, θ) = \sum_{m = - \infty}^{\infty} f_{m} (θ) r^{i 2 π m - 1}

(1)

Where the coefficient for the m’th order is

f_{m} (θ; x_{0}, y_{0}) = L^{- 1} \int_{r_{0}}^{R_{0}} f (r, θ; x_{0}, y_{0}) r^{- i 2 π m - 1} rdr

(2)

and (x ₀, y ₀) is the expansion center. The finite radius R ₀ covering the pattern and the smallest radius r ₀ define the range of the expansion, where proper choice of the integer L=lnR ₀-lnr ₀ is required. The M’ th-order RHF is chosen as the RHF filter function:

f_{M} (r, θ; x_{0}, y_{0}) = f_{M} (θ; x_{0}, y_{0}) r^{i 2 π M - 1}

(3)

Thus, the CPI for the RHF filter and input pattern g(r,θ) can be written as

{∣ C_{gf} (x_{1}, y_{1}; x_{0}, y_{0}) ∣}^{2} = {∣ \int_{0}^{2 π} \int_{r_{0}}^{R_{0}} g (r, θ; x_{1}, y_{1}) f_{M}^{*} (r, θ; x_{0}, y_{0}) rdrd θ ∣}^{2}

= {∣ \int_{0}^{2 π} \int_{r_{0}}^{R_{0}} [\sum_{m = - \infty}^{\infty} g_{m} (θ; x_{1}, y_{1}) r^{i 2 π m - 1}] [f_{M}^{*} (θ; x_{0}, y_{0}) r^{- i 2 π M - 1}] rdrd θ ∣}^{2}

= {∣ \int_{0}^{2 π} \int_{r_{0}}^{R_{0}} \sum_{m = - \infty}^{\infty} [g_{m} (θ; x_{1}, y_{1}) f_{M}^{*} (θ; x_{0}, y_{0}) r^{i 2 π (m - M) - 1}] drd θ ∣}^{2}

= {\begin{array}{c} 0 & m \neq M \\ {∣ \int_{0}^{2 π} \int_{r_{0}}^{R_{0}} g_{M} (θ; x_{1}, y_{1}) f_{M}^{*} (θ; x_{0}, y_{0}) r^{- 1} drd θ ∣}^{2} & m = M \end{array}

= {∣ L \int_{0}^{2 π} g_{M} (θ; x_{1}, y_{1}) f_{M}^{*} (θ; x_{0}, y_{0}) d θ ∣}^{2}

(4)

For an input pattern

g^{β} (r, θ) = g (\frac{r}{β}, θ)

, the CPI for this scaled pattern and RHF filter becomes

{∣ C_{g^{β} f} (x_{1}, y_{1}; x_{0}, y_{0}) ∣}^{2} = {∣ \int_{0}^{2 π} \int_{r_{0}}^{R_{0}} g (\frac{r}{β}, θ; x_{1}, y_{1}) f_{M}^{*} (r, θ; x_{0}, y_{0}) rdrd θ ∣}^{2}

= ∣ \int_{0}^{2 π} \int_{r_{0}}^{R_{0}} [\sum_{m = - \infty}^{\infty} g_{m} (θ; x_{1}, y_{1}) r^{i 2 π m - 1} β^{1 - i 2 π m}] \times

{[f_{M}^{*} (θ; x_{0}, y_{0}) r^{- i 2 π M - 1}] rdrd θ ∣}^{2}

= β^{2} {∣ L \int_{0}^{2 π} g_{M} (θ; x_{1}, y_{1}) f_{M}^{*} (θ; x_{0}, y_{0}) d θ ∣}^{2}

= β^{2} {∣ C_{gf} (x_{1}, y_{1}; x_{0}, y_{0}) ∣}^{2}

(5)

The CPI of the RHF filter is proportional to the square of the scale factor; it is not fully scale-invariant. This effect might severely limit the allowable range of the scale of the input pattern, particularly when the sidelobes of the CPI are large or the noise level is high.

BEMD is the 2-D extension of the empirical mode decomposition [4

J. C. Nunes, Y. Bouaoune, E. Deléchelle, O. Niang, and Ph. Bunel, “Image analysis by bidimensional empirical mode decomposition,” Image Vision Comput. 21, 1019–1026(2003). [CrossRef]

]. It decomposes a nonstationary and nonlinear signal in a finite number of high and low frequency oscillations of zero mean, called intrinsic mode functions (IMF). The decomposition is carried out through a fully data-driven sifting process, so that no basis functions need to be fixed. Let the original image be denoted as I, a bidimensional IMF as BIMF, and the residue as R. In the decomposition process, ith BIMF F_i is obtained from its source image S_i , where S_i is a residue image obtained as S_i =I - ∑i-1j=1(F_j ) and S ₁=I.

The steps of the BEMD process can be summarized and simplified as follows:

1) Detect the extrema (both maxima and minima) of the image S_i when i=1, S_i =I;

2) Compute the 2-D upper and lower envelope;

3) Determine the mean m of upper and lower envelopes;

4) Subtract out the mean from the image: S_i -m=h, and let S_i =h

5) Repeat steps 2–4 until h is a BIMF, F_i ;

6) Let i=i+1, S_i =I - ∑i-1j=1(F_j ) if the stopping criterions are not satisfied, go to 1), otherwise finish the process.

This process gets several BIMFs, and a residue R. Components superposition reconstructs the data:

I = \sum_{i = 1}^{n} (F_{i}) + R

(6)

The empirical mode decomposition (EMD) or BEMD is a sifting process that decomposes a signal into IMFs or BIMFs and a residue based basically on the local frequency or oscillation information. The first IMF/BIMF contains the highest local frequencies of oscillation or the highest local spatial scales, the final IMF/BIMF contains the lowest local frequencies of the oscillation and the residue R only contains the trend of the signal. More details about the EMD and BEMD can refer to Ref. [4

J. C. Nunes, Y. Bouaoune, E. Deléchelle, O. Niang, and Ph. Bunel, “Image analysis by bidimensional empirical mode decomposition,” Image Vision Comput. 21, 1019–1026(2003). [CrossRef]

, 5

C. Damerval, S. Meignen, and V. Perrier, “A fast algorithm for bidimensional EMD,” IEEE Signal Process Lett. 12, 701–704 (2005). [CrossRef]

The theory of scale invariant pattern recognition using RHF functions is taken as the guideline for our filter design; the difference is that we use the BEMD-filtered object pattern as the original reference pattern for harmonic expansion.

And to decrease the factor β ² of Eq. (5), a contour object could be used to remove the useless low-frequency components by digital preprocessing to extract the edges of the original block images [2

]. To utilize the contour of the object, the first BIMF, F ₁(f) of the reference image f (x, y) is used to act as the reference pattern, and is expanded as the combination Eq. (1) of RHF. And one particular order, radial{F ₁(f)}, in Eq. (3) is chosen as the filter function. Then this filter and the input pattern F ₁(g) of the input image g(x, y) are used to perform the correlation operation.

∣ C_{gf} (x_{1}, y_{1}; x_{0}, y_{0}) ∣ = ∣ radial {F_{1} (f)} \otimes F_{1} (g) ∣

(7)

The symbol ⊗ denotes the correlation operation.

Since the reference image generally can be obtained without noise and real input images for recognition often contain random noise, it is necessary to test the proposed method for noisy patterns as well. It has been observed that the first BIMF F ₁(g) constitutes most of the noise in the signal [4

J. C. Nunes, Y. Bouaoune, E. Deléchelle, O. Niang, and Ph. Bunel, “Image analysis by bidimensional empirical mode decomposition,” Image Vision Comput. 21, 1019–1026(2003). [CrossRef]

]. Hence removal of the first BIMF F ₁(g) reduces high spatial frequencies. Since BEMD is local in nature, image blurring is reduced. Filtering occurs in time space rather than in frequency space; therefore, any nonlinearity and nonstationarity present in the data are preserved. Although F ₁(g) has been observed to contain most of the noise, the first few BIMFs from BEMD still usually contain a lot of the noise in the input image; therefore, removing them and reconstructing the image with the remaining BIMFs tend to denoise the image. The number of BIMFs needed to be removed depends on the level of noise in the image. In this paper, the first three BIMFs of the input image g(x, y) were discarded as

Resid (g_{\vec{4}}) = ∣ g - ∣ F_{1} (g) ∣ - ∣ F_{2} (g) ∣ - ∣ F_{3} (g) ∣ ∣

(8)

The edge of the residual of the input image g(x, y), Edge(Resid(g⃗)), is used to perform the correlation operation. The Laplacian of Gaussian method is used to find the edge of Resid(g ₄⃗).

∣ C_{gf} (x_{1}, y_{1}; x_{0}, y_{0}) ∣ = ∣ radial {F_{1} (f)} \otimes Edge (Resid (g_{\vec{4}})) ∣

(9)

3. Simulation and results

3.1. Experimental setup

The performance of the proposed method, BEMD-RHF, is evaluated via computer simulation. Each of the patterns under consideration is expressed as a 256×256 matrix. Matlab codes for BEMD are as developed by Damerval et al., which details can be found in [5

C. Damerval, S. Meignen, and V. Perrier, “A fast algorithm for bidimensional EMD,” IEEE Signal Process Lett. 12, 701–704 (2005). [CrossRef]

, 6

C. Damerval, “BEMD Toolbox : Bidimensional Empirical Mode Decomposition”. http://ljk.imag.fr/membres/Christophe.Damerval/software.html

]. And the programs of BEMD-RHF were developed in Matlab and executed in Intel Pentium 2.4G Hz system with 512MB RAM.

The F16 fighter is used as the reference image, which is shown in Fig. 1(a). There are 6 BIMFs and 1 residue extracted from the reference image, which are shown in Figs. 1(b)–1(h).

Fig. 1. The reference object and the BEMD components. (a) F16 fighter as the reference object. (b) to (g): the corresponding BIMFs of the F16 (from BIMF1 to BIMF6).(h) the residue of BEMD decomposition.

In the construction of the filter, the radial harmonic expansion is performed on this reference with the geometrical center as the expansion center. The first order radial harmonic is taken as the RHF.

3.2. Shift and scale invariant

The first experiment was performed to observe the shift and scale invariant. The input image contains four scaled versions of the F16 fighter with scale factors β=1, 0.8, 0.5, 0.2, as shown in Fig. 2(a). Using the traditional RHF filter, PORHF and BEMD_RHF of expansion order 1 obtained from the object of Fig. 1(a), the correlation intensity distribution for the input objects of Fig. 2(a) is shown in Figs. 2(b), 2(d) and 2(f). To simplify the comparison of the peak intensity, the corresponding cross-sectional intensity distribution through all the correlation peaks is shown in Figs. 2(c), 2(e) and 2(g).

The shift- and scale-invariance for the RHF, the PORHF and the BEMD_RHF are achieved. As seen from the Fig. 2, the normalized CPIs for the RHF and PORHF approximately follow the rule of Eq. (5) for scale β equal to 1, 0.8, 0.5 and 0.2. At the same time, it can be observed that the BEMD_RHF presents better flatness of the peak intensity versus the scale change. This result indicates that the problem of quasi-invariance is solved.

The second experiment was performed to observe the capability to distinguish the scaled reference pattern from the false target. The input image contains four scaled versions of the F16 fighter with scale factors β=1, 0.8, 0.5, 0.2 and one Mig25 with scale factor β=1, as shown in Fig. 3(a). The four scaled versions of the F16 fighter are respectively in the top left corner, bottom left corner, top right corner and bottom right corner of the input image. And the Mig25 is in the center of input image.

The correlation intensity distribution and the corresponding cross-sectional intensity distribution through the correlation peaks are shown in Figs. 3(b) and 3(c). The normalized CPIs (0.83:0.87:1:0.82) for the four F16s are larger than that (0.27) for the Mig25. In this case a nonlinear effect on the CPI appears, such that the CPI does not depend on the size of the input object. As seen from Fig. 3(c), the difference among the CPIs for the F16 is reduced to less than 20%. It is obvious that it is easy to distinguish two categories when a threshold is used. The threshold can be set in a wide gap from 0.8 to 0.3. It proves that the discrimination capability and the scale invariant property of the proposed BEMD_RHF are excellent and outstanding.

Fig. 2. Shift and scale invariance test. (a) Four scaled versions of the F16 fighter with scale factors β=1,0.8,0.5,0.2. (b) to (g): The correlation intensity distribution and the corresponding cross-sectional intensity distribution when using (b) and (c) the RHF, (d) and (e) the PORHF, (f) and (g) the BEMD_RHF.

Fig. 3. Distinguishing the scaled versions of the reference pattern from the false target. (a) The input image with 4 scaled F16 and 1 Mig25. (b) The correlation intensity distribution. (c) The corresponding cross-sectional intensity distribution.

To analyze how the CPI depends on the scale factor β of the F16 for the MRHW (M=1, a=0.5) and the BEMD_RHF, we simulate some typical cases and present the results in Fig. 4. In Fig. 4, both of the CPI curves for the MRHW and BEMD_RHF do not depend on the scale factor β in any explicit way. It can be found that the recognition range of the BEMD_RHF is wider than the MRHW almost at the whole range for scale change whether the threshold is taken at any value. The variance for the CPI curve of BEMD_RHF is a better uniformity than the MRHW (M=1, a=0.5). For instance, if the threshold is set at 0.6, the recognition range of the BEMD_RHF is from 0.15 to 1, which is wider than of the MRHW (from 0.25 to 1).

Fig. 4. Comparing the normalized correlation peak intensity of BEMD_RHF with that of the MRHW when the scale factor changes from 0.1 to 1.

3.3. Noise robustness

Since real images often contain random noise introduced either by the transmission through a noisy channel or by the imaging process, it is necessary to test the proposed method for noisy images as well. To examine the robustness of the proposed method to additive noise, we do experiments using additive white Gaussian noise with zero mean and a variance dependent on the required signal to noise rate (SNR).

Fig. 5. Noise robustness test. (a),(d),(g),(j), (m) and (p) The input images with SNR=25, 15, 5, 0, -2, and -5; (b), (e), (h), (k), (n), (q) and (c), (f), (i), (l), (o), (r) The corresponding correlation intensity distribution planes and the corresponding cross-sectional intensity distributions through the correlation peaks

We added white Gaussian noise to the input image of Fig. 3(a). Some examples of noisy images, at the considered values of SNR, are given in Fig. 5. And Figs. 5(a), 5(d), 5(g), 5(j), 5(m) and 5(p) are the input images with SNR=25, 15, 5, 0, -2, and -5 respectively. Therefore, Figs. 5(b), 5(e), 5(h), 5(k), 5(n), 5(q) and Figs. 5(c), 5(f), 5(i), 5(l), 5(o), 5(r) show the corresponding correlation intensity distribution planes and the corresponding cross-sectional intensity distributions through the correlation peaks. As shown in Fig. 5, there is not obvious performance degradation to recognize the different scaled version of the F16 when SNR is larger than 0, and the additive noise can only affect markedly the CPIs of the false target. The noise produces some random correlation intensity distribution in the output plane but does not affect the correlation peaks in a significant way. All of the CPIs of the four scaled F16 are larger than 0.6. The CPIs of the Mig25 are smaller than 0.4, and increase as the SNR decrease gradually. When SNR is smaller than 0, the additive noise blur the diversity (difference) of two categories gradually as the SNR decrease.

4. Conclusions

The traditional Mellin radial harmonic function of an object is capable of identifying objects at different scale factors, which correlation intensity peaks depend on the squared value of the scale factor. This is an important disadvantage, and limits the allowable range of the scale change. EMD is a new multiresolution decomposition method that decomposes signals into basis functions that are adapted from the signals themselves, and can act as a bandpass filter in a correlator that simultaneously reduces the low-frequency component of the object and high-frequency component of the noise.

A novel method BEMD_RHF is proposed for scale invariant pattern recognition by combining the BEMD with the Mellin radial harmonic decomposition. Compared with the RHF and the PORHF, the noise robustness and discrimination of the BEMD_RHF is improved. The flatness of its peak intensity response versus scale change is also improved. This property is important, since we can detect a large range of scaled patterns (0.2<β<1) using a global threshold. Within this range, the CPI is relatively uniform with a variance below 20%. This proposed BEMD_RHF filter has been tested experimentally to confirm the results from numerical simulation for cases both with and without input white noise.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No.60803087). The authors would like to thank the anonymous reviewers for their constructive comments, which helped us to improve this paper.

References and Links

1.	D. Mendlovic, E. Maron, and N. Konforti, “Shift and scale invariant pattern recognition using Mellin radial harmonics,” Opt. Commun. 67, 172–176(1988). [CrossRef]
2.	A. Moya, J. J. Esteve-Taboada, J. Garcia, and C. “Ferreira, Shift- and scale-invariant recognition of contour objects with logarithmic radial harmonic filters,” Appl. Opt. 39, 5347–5351(2000). [CrossRef]
3.	Yih-Shyang Cheng and Hui-Chi Chen, “Improved performance of scale-invariant pattern recognition using a combined Mellin radial harmonic function and wavelet transform,” Opt. Eng. 46, 107204 (Oct. 29, 2007) [CrossRef]
4.	J. C. Nunes, Y. Bouaoune, E. Deléchelle, O. Niang, and Ph. Bunel, “Image analysis by bidimensional empirical mode decomposition,” Image Vision Comput. 21, 1019–1026(2003). [CrossRef]
5.	C. Damerval, S. Meignen, and V. Perrier, “A fast algorithm for bidimensional EMD,” IEEE Signal Process Lett. 12, 701–704 (2005). [CrossRef]
6.	C. Damerval, “BEMD Toolbox : Bidimensional Empirical Mode Decomposition”. http://ljk.imag.fr/membres/Christophe.Damerval/software.html

OCIS Codes
(100.0100) Image processing : Image processing
(100.4550) Image processing : Correlators
(100.5010) Image processing : Pattern recognition

ToC Category:
Image Processing

History
Original Manuscript: February 2, 2009
Revised Manuscript: April 8, 2009
Manuscript Accepted: April 18, 2009
Published: September 2, 2009

Citation
Qingbo yin, Liran Shen, Jong-Nam Kim, and Yong-Jae Jeong, "Scale-invariant pattern recognition using a combined Mellin radial harmonic function and the bidimensional empirical mode decomposition," Opt. Express 17, 16581-16589 (2009)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-19-16581

Sort: Author | Year | Journal | Reset

References

D. Mendlovic, E. Maron, and N. Konforti, "Shift and scale invariant pattern recognition using Mellin radial harmonics," Opt. Commun. 67, 172-176(1988). [CrossRef]
A. Moya, J. J. Esteve-Taboada, J. Garcia, and C. Ferreira, "Shift- and scale-invariant recognition of contour objects with logarithmic radial harmonic filters," Appl. Opt. 39, 5347-5351(2000). [CrossRef]
Y.-S. Cheng and H.-C. Chen, "Improved performance of scale-invariant pattern recognition using a combined Mellin radial harmonic function and wavelet transform," Opt. Eng. 46, 107204 (Oct. 29, 2007) [CrossRef]
J. C. Nunes, Y. Bouaoune, E. Deléchelle, O. Niang, and Ph. Bunel, "Image analysis by bidimensional empirical mode decomposition," Image Vision Comput. 21, 1019-1026(2003). [CrossRef]
C. Damerval, S. Meignen, and V. Perrier, "A fast algorithm for bidimensional EMD," IEEE Signal Process Lett. 12, 701-704 (2005). [CrossRef]
C. Damerval, "BEMD Toolbox : Bidimensional Empirical Mode Decomposition," http://ljk.imag.fr/membres/Christophe.Damerval/software.html.

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Click here to see a list of articles that cite this paper