2
$\begingroup$

I want to learn the computational complexity of the 2D Discrete Haar (Wavelet) Transform (DHWT). The number of operations (divisions, summations etc.) is the main focus. I think there are many different ideas on that. There are even papers claiming that we do not need any multiplications for it. I am confused. Any help? Thanks.

Edit: I should have added the orthogonality requirement for the Haar transform.

$\endgroup$
  • $\begingroup$ If you don't normalise the Haar basis then you don't need any multiplications, because the basis functions takes its values from {0,-1,1}. $\endgroup$ – Jazzmaniac Aug 28 '15 at 16:30
  • $\begingroup$ SE.DSP wishes you a happy new year 2017, with a kind reminding signal that your question or its answers may require some action from you (edit, update, votes, acceptance, etc.) $\endgroup$ – Laurent Duval Jan 22 '17 at 16:37
1
$\begingroup$

Roughly $N_{\mathrm{op}} = 8\times 4^N/3$ or $N_{\mathrm{op}} = 16\times 4^N/3$. Let us first focus on "There are even papers claiming that we do not need any multiplications for it." and suppose you would like to avoid them. Finally, you can save a little if you abandon orthonormality, even linearity.

The most basic implementation of the Haar wavelet takes $p_0$ and $p_1$ and computes $d = p_0-p_1$ and $a=p_0+p_1$. Apply that horizontally and vertically on a block of four pixels, you need 8 $\pm$. So on a $2^N \times 2^N$ image, you have $2^{N-1} \times 2^{N-1}$ blocks you need $8\times 2^{N-1} \times 2^{N-1} \pm$. On the next level, you iterate on only one low-pass $ 2^{N-1} \times 2^{N-1} $ image, and get $8\times 2^{N-2} \times 2^{N-2} \pm$ more. Down to $J$ levels, you get roughly $$N_{\mathrm{op}\pm} = 8\times 4^N(1-4^{-J})/3 \quad \pm (\mathrm{plus}\;\mathrm{or}\;\mathrm{minus})$$ overall. This transform is not orthonormal, and the $\pm$ may yield too-high amplitude on limited arithmetic.

Another implementation is sometimes termed S+P transform (Sequential + Prediction or Said+Pearlman) or lifting Haar wavelet, and uses a different normalization on the low-pass coefficient. Take again $p_0$ and $p_1$ and computes $d = p_0-p_1$ and $a=p_1+d/2$. At first you add a divide, but it is a binary shift per two $\pm$, it does not cost much. What you gain here is that computations can be performed in place: $p_0 = p_0-p_1$ and $p_1=p_1+p_0/2$. Which could be useful in application where memory costs.

None of them use multiplies.

If you want orthonormality, using divisions by $\sqrt{2}$, then you can add as much multiplies/division as additions/subtractions. The reason is: you know compute $d = (p_0-p_1)/\sqrt{2}$ and $a=(p_0+p_1)/\sqrt{2}$, so for each add or substract, you have one more multiply/divide.

Some other tricks may save you operations, but only quite few in comparison of the above numbers.

Finally, all of this should be balanced with material properties: acceleration, parallelization, CPU/GPU tricks, SIMD instructions can improve the above figures in practice.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I realized from your comment, I should add that I really require orthogonality. Therefore, I am interested in this version where division/multiplications are unavoidable. I will modify my question: If I have an $2^Nx2^N$ array, how many divisions and multiplications do I need for orthogonal Haar transform? Do you mean by "as much multiplies" $8×4N(1−4−J)/3$ divisons or something else. Can I also ask you for a source about the computational complexity? $\endgroup$ – oneoneonezero Aug 29 '15 at 9:17
  • $\begingroup$ Indeed, you can divide by $\sqrt{2}$ or multiply by $\sqrt{2}/2$, so I consider multiply and divide as the same operation. $\endgroup$ – Laurent Duval Aug 29 '15 at 9:23
  • $\begingroup$ What I mean is whether I can take the number of divisions/multiplications as $2^{N-1}$ for the first level and does it continue like $2^{N-2}$ etc. at each level? $\endgroup$ – oneoneonezero Aug 29 '15 at 9:27
  • $\begingroup$ Yes, roughly if you use standard wavelet decomposition $\endgroup$ – Laurent Duval Aug 29 '15 at 9:29
  • 1
    $\begingroup$ @LaurentDuval, the basis is orthogonal even if it's not normalised. The factor therefore guarantees orthonormality and not orthogonality. $\endgroup$ – Jazzmaniac Aug 29 '15 at 10:15
2
$\begingroup$

This is just to address the lack of multiplications: why would there be?

enter image description here

The coefficients of the Haar wavelet (in 1D or 2D) are always +1 or -1. There is no point in doing a multiplication to find the value or its negative.

Check out these notes, particularly this page:

enter image description here

$\endgroup$

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.