Skip to main content
SpringerLink
Log in

Local discriminant bases and their applications

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

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 selects 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 (CARTTM). The performance of these statistical methods 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 component from data consisting of signal and textured background.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  8. T.M. Cover and P. Hart, “Nearest neighbor pattern classification,”IEEE Trans. Inform. Theory, Vol. IT-13, pp. 21–27, 1967.

    Google Scholar 

  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.

    Google Scholar 

  10. K. Fukunaga,Introduction to Statistical Pattern Recognition, Academic Press: San Diego, CA, second edition, 1990.

    Google Scholar 

  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.

    Google Scholar 

  12. G.J. McLachlan,Discriminant Analysis and Statistical Pattern Recognition, John Wiley & Sons: New York, 1992.

    Google Scholar 

  13. S. Watanabe,Pattern Recognition: Human and Mechanical, John Wiley & Sons: New York, 1985.

    Google Scholar 

  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.

    Google Scholar 

  16. J. M. Chambers and T.R. Hastie,Statistical Models in S, Chapman & Hall: New York, 1992.

    Google Scholar 

  17. J. Rissanen,Stochastic Complexity in Statistical Inquiry, World Scientific: Singapore, 1989.

    Google Scholar 

  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.

    Google Scholar 

  19. C.S. Wallace and J.D. Patrick, “Coding decision trees,”Machine Learning, Vol. 11, pp. 7–22, 1993.

    Google Scholar 

  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.

    Google Scholar 

  21. Y. Meyer,Wavelets: Algorithms and Applications, SIAM: Philadelphia, PA, 1993. Translated and revised by R.D. Ryan.

    Google Scholar 

  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.

    Google Scholar 

  23. I. Daubechies,Ten Lectures on Wavelets, SIAM: Philadelphia, PA, 1992.

    Google Scholar 

  24. Y. Meyer,Wavelets and Operators, Cambridge University Press: New York, 1993. Translated by D.H. Salinger.

    Google Scholar 

  25. M.V. Wickerhauser,Adapted Wavelet Analysis from Theory to Software, A.K. Peters: Wellesley, MA, 1994.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  28. H.S. Malvar, “The LOT: transform coding without blocking effects,”IEEE Trans. Acoust., Speech, Signal Processing, Vol. 37, pp. 553–559, 1989.

    Google Scholar 

  29. H.S. Malvar, “Lapped transforms for efficient transform/subband coding,”IEEE Trans. Acoust., Speech, Signal Processing, Vol. 38, pp. 969–978, 1990.

    Google Scholar 

  30. K.R. Rao and P. Yip,Discrete Cosine Transform: Algorithms, Advantages, and Applications, Academic Press: San Diego, CA, 1990.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  33. M.V. Wickerhauser, “High-resolution still picture compression,”Digital Signal Processing: A Review Journal, Vol. 2, pp. 204–226, 1992.

    Google Scholar 

  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.

    Google Scholar 

  35. C.E. Shannon and W. Weaver,The Mathematical Theory of Communication, The University of Illinois Press: Urbana, IL, 1949.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  40. M. Basseville, “Distance measures for signal processing and pattern recognition,”Signal Processing, Vol. 18, pp. 349–369, 1989.

    Google Scholar 

  41. J.N. Kapur and H.K. Kesavan,Entropy Optimization Principles with Applications, Academic Press: San Diego, CA, 1992.

    Google Scholar 

  42. S. Kullback and R.A. Leibler, “On information and sufficiency,”Ann. Math. Statist., Vol. 22, pp. 79–86, 1951.

    Google Scholar 

  43. P.J. Huber, “Projection pursuit (with discussion),”Ann. Statist., Vol. 13, pp. 435–525, 1985.

    Google Scholar 

  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.

    Google Scholar 

  45. P. Brodatz,Textures: A Photographic Album for Artists and Designers, Dover: New York, 1966.

    Google Scholar 

  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.

    Google Scholar 

  48. L. Breiman, “Bagging predictors,” Dept. of Statistics, Univ. of California, Berkeley, CA, Tech. Rep. 421, Sep. 1994.

    Google Scholar 

  49. B. Efron and R.J. Tibshirani,An Introduction to the Bootstrap, Chapman & Hall: New York, 1993.

    Google Scholar 

  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.

    Google Scholar 

  51. W.S. Harlan, J.F. Claerbout, and F. Rocca, “Signal/noise separation and velocity estimation,”Geophysics, Vol. 49, pp. 1869–1880, 1984.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Schlumberger-Doll Research, Old Quarry Road, 06877, Ridgefield, CT, USA

    Naoki Saito

  2. Department of Mathematics, Yale University, 06520, New Haven, CT, USA

    Ronald R. Coifman

Authors
  1. Naoki Saito
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ronald R. Coifman
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported by Schlumberger-Doll Research and by ARPA ATR program.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Saito, N., Coifman, R.R. Local discriminant bases and their applications. J Math Imaging Vis 5, 337–358 (1995). https://doi.org/10.1007/BF01250288

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01250288

Keywords

Search

Navigation