0
$\begingroup$

Good morning,

I am doing an SWT by hand to understand it better, and have a couple of questions. Maybe someone here has experience with this?

I am using the book "Conceptual Wavelets" by Fugal, where they also perform an SWT by hand. This is the page I'm referring to: From "Conceptual Wavelets" by Fugal

Now the details coefficients we get in the book are -80 0 0 0 80 0 0 0 0.

When I did the convolution by hand I got this same result. Matlab agrees also.

However, when I do a level 1 SWT in Python or Matlab, the details coefficients look like this: 0 0 0 56.6 0 0 0 -56.6

I understand that the numbers are different - the book uses [1 -1] as wavelet filter, and most algorithms use [1/(sqrt(2)) -1/(sqrt(2))]. (I don't know why, it's not explained in the book.)

But the Matlab result is shifted to the left! Somehow, Matlab gets rid of the delay in the result during the computation of the details coefficients. They also reduce the convolution back to the right length. In the book, all of these transformations are done at the end, to get the original data back.

So my questions are:

  • Is the delay always 1, for every 1D SWT?
  • How does Matlab calculate its result, and how can I replicate this in my calculation? Is it always a shift to the left? Which element do I drop to reduce the size of the result? A simple convolution seems to be not enough.
  • (And if someone happens to know a source that mentions why haar filter values are so often 1/(sqrt(2)), I'd be happy to learn about that, too.)

Thanks in advance

$\endgroup$
3
$\begingroup$

Why normalized filters

Last question first, "Why $1/\sqrt2$": Because it makes the (Euclidean) norm of the filter $1$, so that the whole wavelet filter bank operation (if done right, that is, the decimated version) is orthogonal/isometric. It is a design choice, there is nothing wrong in staying with the integer values and correct the combined factor during reconstruction.

The book example is not really the standard wavelet transform

However, the book you cite is doing the wavelet transform undecimated. Which is a valid mathematical transform, but leaving out the decimation step, the down- and up-sampling, will lead to data bloat. By applying the two filters, the amount of data representing the signal is doubled, so some of that is redundant. This redundancy can be reduced by transmitting (or keeping for further processing) only every second element of these sequences.

Undecimated or otherwise redundant transforms give freedom in how to represent the signal, that is, in some non-linear post-processing one can set some of the data to zero and compensate (more-or-less) lossless-ly by changing other coefficients. However here I think this example is just a teaching aid.

Decimated version of the examples

So taking of cD1 and cA1 only every second entry gives cD1(2:2:end)=[0 0 0 0] and cA1(2:2:end)=[160 160 0 0], together they encode the same signal, which now has more zeros and is thus better suited for compression. In the reconstruction, zeros will be added to fill the gaps, and then the convolution with the reversed/biorthogonal filters is applied. So

[1 -1]*[0 0 0 0 0 0 0 0] = [0 0 0 0 0 0 0 0 0]

and

[1 1]*[160 0 160 0 0 0 0 0] = [160 160 160 160 0 0 0 0 0]

so that in the sum the result is twice the original signal, $(\sqrt2)^2$, with a zero added at the end.


If one shifts the whole process by one place, the reduced signals are [ -80 0 80 0] and [80 160 80 0] so that in the reconstruction one has to add

[1 -1]*[-80 0 0 0 80 0 0 0] = [-80 80 0 0 80 -80 0 0 0]

and

[1 1]*[80 0 160 0 80 0 0 0] = [80 80 160 160 80 80 0 0 0] 

to give [0 160 160 160 160 0 0 0 0]. Here we get, additional to the factor 2, also the shift, or an additional zero at the start of the sequence. However, by using the first, third etc. elements in down-sampling, we used implicitly an extension of the sequence S to the left by zero. This additional zero element is what is obtained now explicitly in the reconstruction.


In general wavelet transforms, the wavelet filters have lengths larger than 2, leading to more "interesting" boundary effects that include a shift by about the length of the filter.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the detailed answer. Consequently, if we take the 2nd, 4th, 6th element and so forth, we implicitly extend the sequence to the right by zero? Where does that implicit assumption come from? When I type "swt(...)" in Matlab, there is no decimation either, though, is it? Since the stationary wavelet transform is not decimated? So, when I do not decimate, and use all data points, what implicit assumption about the sequence do I make? And why does the Matlab result (0 0 0 56.6 0 0 0 -56.6) not only add a zero but shift the -56 to the other end of the sequence? Cheers $\endgroup$ – wavelet_guest Jan 23 at 10:48
  • $\begingroup$ And is the result multiplied by factor 2 because it is always multiplied by the Euclidean Norm of the filter? (And do therefore highpass and lowpass deconstruction filters of the same wavelet always have the same Euclidean Norm?) $\endgroup$ – wavelet_guest Jan 23 at 10:52
  • $\begingroup$ The SWT does not increase the data dimension, so it is non-redundant, so it has to do the decimation on every stage. I do not know what this specific function does, only one stage of the DWT or the full cascade. // You get the factor 2 because the Haar transform is the DFT of size 2, the same where in a DFT of size N you get a factor N. // In a professional implementation of a fast DWT one would downsample first, that is blockify or reshape as sequence of pairs, then apply the filters that now have matrix coefficients. This reduces the need for sequence extension. $\endgroup$ – Lutz Lehmann Jan 23 at 12:22
  • $\begingroup$ The swt(...) function in Matlab does the max number of levels. In Python, I think, you can choose how many levels you want for your transform. However, it does not do a DWT, it does a SWT, (also called UDWT), which(according to Wikipedia (en.wikipedia.org/wiki/Stationary_wavelet_transform)) is "inherently redundant". Because in the SWT, each level of the transform has the same length as the original sequence. When you write DFT, do you mean Discrete Fourier Transform? How would the Haar transform have anything to do with that? I thought those were two completely different approaches. $\endgroup$ – wavelet_guest Jan 23 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.