Efficient algorithms for local discrete wavelet transform with haar basis

V.N. Kopenkov

Full text of article: Russian language.

Abstract:

In this paper we propose two new fast algorithms for computing a local discrete wavelet transform of a regular signal as illustrated by Haar wavelet basis, give expressions for their computational complexity, and compare them with each other, as well as with the existing fast wavelet transform algorithm. We also give recommendations how to use each of the proposed algorithms. In particular, we indicate preference regions for these algorithms, i.e. task options for calculation of the wavelet transform, for which these algorithms are computationally efficient. Based on the analysis of algorithms’ complexity, with regard to additional features offered by the recursive algorithm, we may come to conclusion about its advantages compared with the existing alternative fast wavelet transform algorithm. We summarized the considered algorithms for a two-dimensional case.

Key words:

local discrete wavelet transform, computational complexity, recursive algorithm.

Citation: Kopenkov VN. Efficient algorithms for calculating a local discrete wavelet transform based on Haar wavelet basis [In Russian]. Computer Optics 2008; 32(1): 78-84.

References:

- Daubechies I. Ten Lectures on Wavelets. CBMS-NSF Lecture Notes nr. 61, SIAM 1992; 377 pp.
- Mallat S. A wavelet tour of signal processing. Academic Press 1999; 637 pp.
- Holschneider M, Kronland-Martinet R, Morlet J, Tchamitchian Ph. A real-time algorithm for signal analysis with help of the wavelet transform. Wavelets, Time-Frequency Methods and Phase Space. Berlin: Springer-Verlag 1989; A: 289-297.
- Chernov AV, Myasnikov VV, Sergeyev VV. Fast Method for Local Image Processing and Analysis. Pattern Recognition and Image Analysis 1999; 9(4): 572-577.
- Myasnikov VV. Methods for Designing Recursive FIR Filters. Proceedings of International Conference “Computer Vision and Graphics” (ICCVG 2004). Warsaw, Poland, September 22-24; Springer 2004; 845-850.
- Kopenkov VN, Myasnikov VV. Fast algorithms for local discrete wavelet transform with Haar basis [In Russian]. Samara International Scientific and Technical Conference, PIT 2006; 2: 113-118.

© 2009, ИСОИ РАН

Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 332-56-22, факс: +7 (846 2) 332-56-20