Discrete wavelet transform of finite-length signals must necessarily handle the signal boundaries. The state-of-the-art approaches treat such boundaries in a complicated and inflexible way, using special prolog or epilog phases. This holds true in particular for images decomposed into a number of scales, exemplary in JPEG 2000 coding system. In this paper, the state-of-the-art approaches are extended to perform the treatment using a compact streaming core, possibly in multi-scale fashion. We present the core focused on CDF 5 3 wavelet and the symmetric border extension method, both employed in the JPEG 2000. As a result of our work, every input sample is visited only once, while the results are produced immediately, i.e. without buffering.
The polyphase matrix @cite_5 @cite_9 @cite_1 is a convenient tool to express the transform filters. The lifting scheme factorizes this matrix into a series of shorter filterings. In detail, the polyphase matrix can be factorized @cite_13 , so that , where @math is a non-zero constant, and polynomials @math represent the individual lifting steps. Focusing on the CDF 5 3 wavelet as an example, the forward transform in can be expressed @cite_9 by the dual polyphase matrix , where @math are real constants, and the @math is called the scaling factor. For details about the lifting scheme, see @cite_9 @cite_12 . Unlike a convolution scheme, the lifting allows @cite_10 formulation of the transforms mapping integers to integers.
@cite_10 @cite_9 @cite_1 @cite_5 @cite_13 @cite_12
1975358183 2015370045 658512522 565312106 2117188745
Abstract Invertible wavelet transforms that map integers to integers have important applications in lossless coding. In this paper we present two approaches to build integer to integer wavelet transforms. The first approach is to adapt the precoder of Laroiaet al,which is used in information transmission; we combine it with expansion factors for the high and low pass band in subband filtering. The second approach builds upon the idea of factoring wavelet transforms into so-called lifting steps. This allows the construction of an integer version of every wavelet transform. Finally, we use these approaches in a lossless image coder and compare the results to those given in the literature. This article is essentially tutorial in nature. We show how any discrete wavelet transform or two band subband filtering with finite filters can be decomposed into a finite sequence of simple filtering steps, which we call lifting steps but that are also known as ladder structures. This decomposition corresponds to a factorization of the polyphase matrix of the wavelet or subband filters into elementary matrices. That such a factorization is possible is well-known to algebraists (and expressed by the formula SL(n; R(Z, z-I)) = E(n; R(z, z-l))); it is also used in linear systems theory in the electrical engineering community. We present here a self-contained derivation, building the decomposition from basic principles such as the Euclidean algorithm, with a focus on applying it to wavelet filtering. This factorization provides an alternative for the lattice factorization, with the advantage that it can also be used in the biorthogonal, i.e., non-unitary case. Like the lattice factorization, the decomposition presented here asymptotically reduces the computational complexity of the transform by a factor two. It has other applications, such as the possibility of defining a wavelet-like transform that maps integers to integers. 1. On rainbows and spectra 2. From Euclid to Hilbert: 2.1 Introduction 2.2 Vector spaces 2.3 Hilbert spaces 2.4 Approximations, projections, and decompositions 2.5 Bases and frames 2.6 Computational aspects 2.A Elements of analysis and topology 2.B Elements of linear algebra 2.C Elements of probability 2.D Basis concepts Exercises with solutions Exercises 3. Sequences and discrete-time systems: 3.1 Introduction 3.2 Sequences 3.3 Systems 3.4 Discrete-time Fourier Transform 3.5 z-Transform 3.6 Discrete Fourier Transform 3.7 Multirate sequences and systems 3.8 Stochastic processes and systems 3.9 Computational aspects 3.A Elements of analysis 3.B Elements of algebra Exercises with solutions Exercises 4. Functions and continuous-time systems: 4.1 Introduction 4.2 Functions 4.3 Systems 4.4 Fourier Transform 4.5 Fourier series 4.6 Stochastic processes and systems Exercises with solutions Exercises 5. Sampling and interpolation: 5.1 Introduction 5.2 Finite-dimensional vectors 5.3 Sequences 5.4 Functions 5.5 Periodic functions 5.6 Computational aspects Exercises with solutions Exercises 6. Approximation and compression: 6.1 Introduction 6.2 Approximation of functions on finite intervals by polynomials 6.3 Approximation of functions by splines 6.4 Approximation of functions and sequences by series truncation 6.5 Compression 6.6 Computational aspects Exercises with solutions Exercises 7. Localization and uncertainty: 7.1 Introduction 7.2 Localization for functions 7.3 Localization for sequences 7.4 Tiling the time-frequency plane 7.5 Examples of local Fourier and wavelet bases 7.6 Recap and a glimpse forward Exercises with solutions Exercises. 1. Introduction 2. Introduction to abstract algebra 3. Fast algorithms for the discrete Fourier transform 4. Fast algorithms based on doubling strategies 5. Fast algorithms for short convolutions 6. Architecture of filters and transforms 7. Fast algorithms for solving Toeplitz systems 8. Fast algorithms for trellis search 9. Numbers and fields 10. Computation in finite fields and rings 11. Fast algorithms and multidimensional convolutions 12. Fast algorithms and multidimensional transforms Appendices: A. A collection of cyclic convolution algorithms B. A collection of Winograd small FFT algorithms. Abstract We present the lifting scheme, a new idea for constructing compactly supported wavelets with compactly supported duals. The lifting scheme uses a simple relationship between all multiresolution analyses with the same scaling function. It isolates the degrees of freedom remaining after fixing the biorthogonality relations. Then one has full control over these degrees of freedom to custom design the wavelet for a particular application. The lifting scheme can also speed up the fast wavelet transform. We illustrate the use of the lifting scheme in the construction of wavelets with interpolating scaling functions.