×

zbMATH — the first resource for mathematics

Local discriminant bases and their applications. (English) Zbl 0863.94004
Summary: We describe an extension to the “best-basis” method to select an orthonormal basis suitable for signal/image classification problems from a large collection of orthonormal bases consisting of wavelet packets or local trigonometric bases. The original best-basis algorithm select a basis minimizing entropy from such a “library of orthonormal bases’ whereas the proposed algorithm selects a basis maximizing a certain discriminant measure (e.g., relative entropy) among classes. Once such a basis is selected, a small number of most significant coordinates (features) are fed into a traditional classifier such as Linear Discriminant Analysis (LDA) or Classification and Regression Tree \((\text{CART}^{\text{TM}})\). The performance of these statistical method is enhanced since the proposed methods reduce the dimensionality of the problem at hand without losing important information for that problem. Here, the basis functions which are well-localized in the time-frequency plane are used as feature-extractors. We applied our method to two signal classification problems and an image texture classification problem. These experiments show the superiority of our method over the direct application of these classifiers on the input signals. As a further application, we also describe a method to extract signal components from data consisting of signal and textured background.

MSC:
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
68W10 Parallel algorithms in computer science
62B10 Statistical aspects of information-theoretic topics
62H30 Classification and discrimination; cluster analysis (statistical aspects)
Software:
bootstrap; R
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. R. Coifman and N. Saito, ?Constructions of local orthonormal bases for classification and regression,?C. R. Acad. Sci. Paris, Série I, Vol. 319, pp. 191-196, 1994. · Zbl 0801.62004
[2] N. Saito and R.R. Coifman, ?Local discriminant bases,? inMathematical Imaging: Wavelet Applications in Signal and Image Processing, A.F. Laine and M.A. Unser (eds.),Proc. SPIE 2303, pp. 2-14, 1994.
[3] N. Saito,Local Feature Extraction and Its Applications Using a Library of Bases, Ph.D. Thesis, Dept. of Mathematics, Yale University, New Haven, CT 06520 USA, Dec. 1994.
[4] N. Saito and R.R. Coifman, ?Local feature extraction for classification and regression using a library of bases,? in preparation.
[5] N. Saito and R.R. Coifman, ?Extraction of geological information from acoustic well-logging waveforms using time-frequency atoms,?Geophysics, 1995 (submitted).
[6] R. A. Fisher, ?The use of multiple measurements in taxonomic problems,?Ann. Eugenics, Vol. 7, pp. 179-188, 1936.
[7] L. Breiman, J.H. Friedman, R.A. Olshen, and C.J. Stone,Classification and Regression Trees, Chapman & Hall: New York, 1993. Previously published by Wadsworth & Brooks/Cole in 1984. · Zbl 0541.62042
[8] T.M. Cover and P. Hart, ?Nearest neighbor pattern classification,?IEEE Trans. Inform. Theory, Vol. IT-13, pp. 21-27, 1967. · Zbl 0154.44505 · doi:10.1109/TIT.1967.1053964
[9] B.D. Ripley, ?Statistical aspects of neural networks,? inNetworks and Chaos: Statistical and Probabilistic Aspects, O.E. Barndorff-Nielsen, J.L. Jensen, D.R. Cox, and W.S. Kendall (eds.), Ch. 2, pp. 40-123, Chapman & Hall: New York, 1993. · Zbl 0825.68531
[10] K. Fukunaga,Introduction to Statistical Pattern Recognition, Academic Press: San Diego, CA, second edition, 1990. · Zbl 0711.62052
[11] S.M. Weiss and C.A. Kulikowski,Computer Systems That Learn: Classification and Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert Systems, Morgan Kaufmann: San Francisco, CA, 1991.
[12] G.J. McLachlan,Discriminant Analysis and Statistical Pattern Recognition, John Wiley & Sons: New York, 1992. · Zbl 1108.62317
[13] S. Watanabe,Pattern Recognition: Human and Mechanical, John Wiley & Sons: New York, 1985.
[14] StatSci,S-PLUS Reference Manual, Vol. 1 & 2, version 3.2, Seattle, WA, Dec. 1993.
[15] R.A. Becker, J.M. Chambers, and A.R. Wilks,The New S Language: A Programming Environment for Data Analysis and Graphics, Chapman & Hall: New York, 1988. · Zbl 0642.68003
[16] J. M. Chambers and T.R. Hastie,Statistical Models in S, Chapman & Hall: New York, 1992. · Zbl 0776.62007
[17] J. Rissanen,Stochastic Complexity in Statistical Inquiry, World Scientific: Singapore, 1989. · Zbl 0800.68508
[18] J. R. Quinlan and R.L. Rivest, ?Inferring decision trees using the minimum description length principle,?Information and Control, Vol. 80, pp. 227-248, 1989. · Zbl 0664.94015
[19] C.S. Wallace and J.D. Patrick, ?Coding decision trees,?Machine Learning, Vol. 11, pp. 7-22, 1993. · Zbl 0850.94027 · doi:10.1023/A:1022646101185
[20] R.R. Coifman and M.V. Wickerhauser, ?Entropy-based algorithms for best basis selection,?IEEE Trans. Inform. Theory, Vol. 38, pp. 713-719, 1992. · Zbl 0849.94005 · doi:10.1109/18.119732
[21] Y. Meyer,Wavelets: Algorithms and Applications, SIAM: Philadelphia, PA, 1993. Translated and revised by R.D. Ryan.
[22] N. Saito and G. Beylkin, ?Multiresolution representations using the auto-correlation functions of compactly supported wavelets,?IEEE Trans. Signal Processing, Vol. 41, pp. 3584-3590, 1993. · Zbl 0841.94019 · doi:10.1109/78.258102
[23] I. Daubechies,Ten Lectures on Wavelets, SIAM: Philadelphia, PA, 1992. · Zbl 0776.42018
[24] Y. Meyer,Wavelets and Operators, Cambridge University Press: New York, 1993. Translated by D.H. Salinger. · Zbl 0810.42015
[25] M.V. Wickerhauser,Adapted Wavelet Analysis from Theory to Software, A.K. Peters: Wellesley, MA, 1994. · Zbl 0818.42011
[26] R.R. Coifman and Y. Meyer, ?Remarques sur l’analyse de fourier à fenêtre,?C. R. Acad. Sci. Paris, Série I, Vol. 312, pp. 259-261, 1991. · Zbl 0748.42012
[27] P. Auscher, G. Weiss, and M.V. Wickerhauser, ?Local sine and cosine bases of Coifman and Meyer and the construction of smooth wavelets,? inWavelets: A Tutorial in Theory and Applications C.K. Chui (ed.), pp. 237-256, Academic Press: San Diego, CA, 1992. · Zbl 0767.42009
[28] H.S. Malvar, ?The LOT: transform coding without blocking effects,?IEEE Trans. Acoust., Speech, Signal Processing, Vol. 37, pp. 553-559, 1989. · doi:10.1109/29.17536
[29] H.S. Malvar, ?Lapped transforms for efficient transform/subband coding,?IEEE Trans. Acoust., Speech, Signal Processing, Vol. 38, pp. 969-978, 1990. · doi:10.1109/29.56057
[30] K.R. Rao and P. Yip,Discrete Cosine Transform: Algorithms, Advantages, and Applications, Academic Press: San Diego, CA, 1990. · Zbl 0726.65162
[31] J. Kova?evi? and M. Vetterli, ?Nonseparable multidimensional perfect reconstruction filter banks and wavelet bases forR n,?IEEE Trans. Inform. Theory, Vol. 38, pp. 533-555, 1992. · doi:10.1109/18.119722
[32] K. Gröchenig and W.R. Madych, ?Multiresolution analysis, Haar bases, and self-similar tilings ofR n,?IEEE Trans. Inform. Theory, Vol. 38, pp. 556-568, 1992. · Zbl 0742.42012 · doi:10.1109/18.119723
[33] M.V. Wickerhauser, ?High-resolution still picture compression,?Digital Signal Processing: A Review Journal, Vol. 2, pp. 204-226, 1992. · doi:10.1016/1051-2004(92)90010-V
[34] N. Otsu, ?Mathematical studies on feature extraction in pattern recognition,? (in Japanese), Researches of the Electrotechnical Laboratory, No. 818, Electrotechnical Laboratory, 1-1-;4, Umezono, Sakura-machi, Niihari-gun, Ibaraki, Japan, July 1981.
[35] C.E. Shannon and W. Weaver,The Mathematical Theory of Communication, The University of Illinois Press: Urbana, IL, 1949. · Zbl 0041.25804
[36] S. Watanabe, ?Karhunen-Loève expansion and factor analysis: theoretical remarks and applications,? inTrans. 4th Prague Conf. Inform. Theory, Statist. Decision Functions, Random Processes, Prague, 1967, pp. 635-660.
[37] M.V. Wickerhauser, ?Fast approximate factor analysis,? inCurves and Surfaces in Computer Vision and Graphics II, Proc. SPIE 1610, pp. 23-32, 1991.
[38] R.R. Coifman and F. Majid, ?Adapted waveform analysis and denoising,? inProgress in Wavelet Analysis and Applications, Y. Meyer and S. Roques (eds.), pp. 63-76, Editions Frontieres: B.P.33, 91192 Gif-sur-Yvette Cedex, France, 1993. · Zbl 0878.94009
[39] N. Saito, ?Simultaneous noise suppression and signal compression using a library of orthonormal bases and the minimum description length criterion,? inWavelets in Geophysics, E. Foufoula-Georgiou and P. Kumar (eds.), Ch. XI, pp. 299-324, Academic Press: San Diego, CA, 1994.
[40] M. Basseville, ?Distance measures for signal processing and pattern recognition,?Signal Processing, Vol. 18, pp. 349-369, 1989. · doi:10.1016/0165-1684(89)90079-0
[41] J.N. Kapur and H.K. Kesavan,Entropy Optimization Principles with Applications, Academic Press: San Diego, CA, 1992. · Zbl 0718.62007
[42] S. Kullback and R.A. Leibler, ?On information and sufficiency,?Ann. Math. Statist., Vol. 22, pp. 79-86, 1951. · Zbl 0042.38403 · doi:10.1214/aoms/1177729694
[43] P.J. Huber, ?Projection pursuit (with discussion),?Ann. Statist., Vol. 13, pp. 435-525, 1985. · Zbl 0595.62059 · doi:10.1214/aos/1176349519
[44] T. Chang and C.-C.J. Kuo, ?Texture analysis and classification with tree-structured wavelet transform,?IEEE Trans. Image Processing, Vol. 2, pp. 429-441, 1993. · doi:10.1109/83.242353
[45] P. Brodatz,Textures: A Photographic Album for Artists and Designers, Dover: New York, 1966.
[46] L. Woog,Wavelet-packet based signal enhancement and denoising algorithms, Ph.D. Thesis, Dept. of Comput. Sci., Yale University, 1995, in preparation.
[47] R.R. Coifman and D. Donoho, ?Translation-invariant denoising,? inWavelets and Statistics, A. Antoniadis (ed.), Springer-Verlag: New York, 1995. · Zbl 0866.94008
[48] L. Breiman, ?Bagging predictors,? Dept. of Statistics, Univ. of California, Berkeley, CA, Tech. Rep. 421, Sep. 1994.
[49] B. Efron and R.J. Tibshirani,An Introduction to the Bootstrap, Chapman & Hall: New York, 1993. · Zbl 0835.62038
[50] R.R. Coifman and M.V. Wickerhauser, ?Wavelets and adapted waveform analysis,?Wavelets: Mathematics and Applications, J. Benedetto and M. Frazier (eds.), Ch. 10, CRC Press: Boca Raton, FL, 1993. · Zbl 0795.42019
[51] W.S. Harlan, J.F. Claerbout, and F. Rocca, ?Signal/noise separation and velocity estimation,?Geophysics, Vol. 49, pp. 1869-1880, 1984. · doi:10.1190/1.1441600
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.