0.10 Wavelet-based signal processing and applications  (Page 8/13)

Some comments have to be made at this point. Similar to traditional approaches (e.g., low pass filtering), there is a trade-off betweensuppression of noise and oversmoothing of image details, although to a smaller extent. Also, hard thresholding yields better results in terms ofthe $l_2$ error. That is not surprising since the observation value $y_i$ itself is clearly a better estimate for the real value $x_i$ than a shrunk value in a zero mean noise scenario. However, the estimatedfunction obtained from hard thresholding typically exhibits undesired, spurious oscillations and does not have the desired smoothness properties.

Shift-invariant or nondecimated discrete wavelet transform

As is well known, the discrete wavelet transform is not shift invariant; i.e., there is no “simple” relationship between the wavelet coefficientsof the original and the shifted signal Since we deal with finite length signals, we really mean circular shift. . In this section we will develop a shift-invariant DWT using ideas of a nondecimated filter bank ora redundant DWT [link] , [link] , [link] . Because this system is redundant, it is not a basis but will be a frame or tight frame (see Section: Overcomplete Representations, Frames, Redundant Transforms, and Adaptive Bases ). Let $X=Wx$ be the (orthogonal) DWT of $x$ and $S_R$ be a matrix performing a circular right shift by $R$ with $R\in \mathbf{Z}$ . Then

which establishes the connection between the wavelet transforms of two shifted versions of a signal, $x$ and $x_s$ , by the orthogonal matrix $W{S}_R{W}^{-1}$ . As an illustrative example, consider [link] .

The first and most obvious way of computing a shift invariant discrete wavelet transform (SIDWT) is simply computing the wavelet transform of all shifts. Usually the two band wavelet transform is computed as follows: 1) filter the input signal by a low-pass and a high-pass filter,respectively, 2) downsample each filter output, and 3) iterate the low-pass output. Because of the downsampling, the number of output valuesat each stage of the filter bank (corresponding to coarser and coarser scales of the DWT) is equal to the number of the input values. Precisely $N$ values have to be stored. The computational complexity is $O\left(N\right)$ . Directly computing the wavelet transform of all shifts therefore requiresthe storage of $N^2$ elements and has computational complexity $O\left(N^2\right)$ .

Beylkin [link] , Shensa [link] , and the Rice group Those are the ones we are aware of. independently realized that 1) there are only $NlogN$ different coefficient values among those corresponding to all shifts of the input signal and 2) those can becomputed with computational complexity $NlogN$ . This can be easily seen by considering one stage of the filter bank. Let

where $y$ is the output of either the high-pass or the low-pass filter in the analysis filter bank, $x$ the input and the matrix $h$ describes the filtering operation. Downsampling of $y$ by a factor of two means keeping the even indexed elements and discarding the odd ones. Consider the caseof an input signal shifted by one. Then the output signal is shifted by one as well, and sampling with the same operator as before corresponds tokeeping the odd-indexed coefficients as opposed to the even ones. Thus, the set of data points to be further processed is completely different.However, for a shift of the input signal by two, the downsampled output signal differs from the output of the nonshifted input only by a shift ofone. This is easily generalized for any odd and even shift and we see that the set of wavelet coefficients of the first stage of the filter bank forarbitrary shifts consists of only $2N$ different values. Considering the fact that only the low-pass component ( $N$ values) is iterated, one recognizes that after $L$ stages exactly $LN$ values result. Using the same arguments as in the shift variant case, one can prove that thecomputational complexity is $O(NlogN)$ . The derivation for the synthesis is analogous.