The MATLAB function waveletcdf97.m included in this package is a selfcontained Mfunction for applying the Cohen–Daubechies–Feauveau 9/7 (CDF 9/7) wavelet transform. This wavelet is an especially effective biorthogonal wavelet, used by the FBI for fingerprint compression and selected for the JPEG2000 standard [1]. Function UsageY = waveletcdf97(X, L) decomposes X with L stages of the CDF 9/7 wavelet. For the inverse transform, waveletcdf97(X, L) inverts L stages. Filter boundary handling is halfsample symmetric. X may be of any size; it need not have size divisible by 2^{L}. For example, if X has length 9, one stage of decomposition produces a lowpass subband of length 5 and a highpass subband of length 4. Transforms of any length have perfect reconstruction (exact inversion). If X is a matrix, waveletcdf97 performs a (tensor) 2D wavelet transform. If X has three dimensions, the 2D transform is applied along the first two dimensions. DemosThis package includes a demo program, waveletcdf97_demo, that uses waveletcdf97 for signal approximation. Signal approximation is the problem of representing a signal with as few components as possible. This is similar to lossy image compression, but ignoring the problems of quantization and encoding. Wavelets are particularly efficient for approximating piecewisesmooth signals. This first demo uses the CDF 9/7 wavelet to represent a piecewisesmooth signal. NumComponents = 40; % Approximation with 40 components The figure below shows the resulting wavelet approximation using only 40 out of 512 components. Fourier approximation with 40 components is shown for comparison. The wavelet approximation has L^{2} error of 0.014 while the Fourier approximation has error of 2.244. The second demo applies waveletcdf97 to image approximation. First, the input image is converted from RGB to the JPEG Y'CbCr colorspace. The Y'CbCr image is transformed using waveletcdf97, all but the largest transform coefficients are set to zero, and then inverse transformed. X = double(imread('palm.jpg'))/255; % Load the demo image
TestsIn the first test, a random signal X is transformed one stage, then inverse transformed, and the result is compared to the original. Mathematically, the transform is exactly inverted—the scheme is said to have perfect reconstruction. This test verifies that this property holds to machine precision. Runs = 100; % Number of runs to average Code output:
length(X) = 15 Error = 3.34e016 The CDF 9/7 wavelet is designed such that where the input signal is locally a polynomial of cubic degree or lower, the resulting detail (highpass) coefficients are equal to zero. A wavelet is said to have "N vanishing moments" if it has this property on polynomials up to degree N1, so CDF 9/7 has 4 vanishing moments. This test transforms a piecewise polynomial signal and displays the largest detail coefficient magnitudes, verifying that the vanishing moments hold to reasonable accuracy. N = 64; Code output:
Locally constant Largest detail coefficient = 1.41e012 ImplementationThe code is written specialized for the CDF 9/7 wavelet in lifting scheme implementation. Sweldens' lifting scheme [2] represents a wavelet transform as a sequence of predict and update steps. Let X=[X(1), X(2), ... X(2N)] be an array of length 2N. The lifting scheme begins with the "polyphase decomposition," splitting X into two subbands, each of length N: X_{o}=[X(1),X(3),X(5),... X(2N1)], X_{e}=[X(2),X(4),X(6), ... X(2N)]. Since X_{o} and X_{e} can be merged to recover X, no information has been lost. Next, the scheme performs lifting steps on the subbands X_{o} and X_{e}. Let p be a filter, then X_{e}'= X_{e} + p∗X_{o} is called a prediction step, where ∗ denotes convolution. Similarly, X_{o}'= X_{o} + u∗X_{e} is called an update step. Notice that X_{e} can always be recovered from X_{e}' with X_{e}'= X_{e}  p∗X_{o}. This simple relationship between a forward step and an inverse step is the key to the lifting scheme: any sequence of prediction and update steps can be undone to recover X_{o} and X_{e}. Any FIR wavelet transform can be factored into a sequence of lifting steps [3]. For the CDF 9/7 wavelet, the lifting scheme decomposition used in waveletcdf97 is
The subbands are then normalized with X_{o}^{3} = κ X_{o}^{2} and X_{e}^{3} = κ^{−1} X_{e}^{2}. For a multilevel decomposition, the algorithm above is repeated with X = X_{o}^{3}. The numbers α, β, δ, γ, κ are irrational values approximately equal to
The inverse transform is done by performing the lifting steps in the reverse order and with α, β, δ, γ negated. What if X has odd length 2N1? The trick is to extrapolate one extra element X(2N)=x in such a way that transforming the augmented X has X_{e}^{3}(N)=0. This zero element can then be thrown away without losing information. The result is a decomposition with N elements in X_{o}^{3} and N1 elements in X_{e}^{3} for a total of 2N1 elements; the decomposition is nonredundant. To invert an oddlength transform, append the zero element X_{e}^{3}(N)=0 and proceed with the usual evenlength inverse transform. The formula for the extrapolated element x such that X_{e}^{3}(N)=0 is a linear function of the elements of X that depends on the filter boundary handling. For the halfsample symmetric boundary handling used in waveletcdf97, the extrapolation is
References

Research >