7
$\begingroup$

I am interested in implementations of the Haar transform, and its inverse, such that when composed always result in the identity operation. My inputs are discrete ordinals within a given range - and I need the output of the Haar transform to be similarly discrete ordinal (or fixed-point) numbers.

I've worked on the basis that if my input signal consists uniformly distributed samples on the range $0..(2^n-1)$ and, so does my transformed signal, then in principle, my original signal should be reproduced perfectly by the inverse haar.

I've dabbled with this (Matlab) implementation using GNU Octave:

http://people.sc.fsu.edu/~jburkardt/m_src/haar/haar.html

Which uses double precision values... forcing me to use round() to establish a discrete representation of the transformed data so as to fit the transformed representation into the same state-space as the original. Unsurprisingly, I found I needed to use round() again to the output from the inverse transform.

It will probably come as no surprise that round(haar_2d_inverse(round(haar_2d(signal)))) is not quite the identity function for most values of signal... Anecdotally, there are typically a few out-by-one errors in the reconstructed signal - which seem roughly symmetric (+1 or -1 on a small number of the reconstructed samples) and this seems almost independent on the choice of n.

What I'd like to know is if there are 'better' implementations of haar_2d and haar_2d_inverse that work on ordinal samples? Are the anomalies the consequence of the Haar implementation itself or the way I've applied round() at the intermediate stage? If the latter, can I rectify this by scaling before rounding?

$\endgroup$
  • $\begingroup$ Seems like you'd need fixed-point math, rather than trying to approximate it w/ floating-point. $\endgroup$ – datageist Jun 4 '12 at 17:00
  • $\begingroup$ I suspect you're right - datageist - but that dependence on root-2 is relevant and might make this tricky. I'm surprised that I can't find a sample implementation with a google search. $\endgroup$ – aSteve Jun 4 '12 at 20:38
1
$\begingroup$

I think in 2D Haar, $\sqrt{2}$ is not required, if the transform is applied simultaneously in both directions. It'd be of the form of $\frac{a+b+c+d}{2}$, which requires only fixed point implementation with the Q point being chosen based on number of levels. I had used this to implement Haar in C for embedded systems, and it works without rounding/truncation errors.

Note:
My rep's not 50, so posting as answer. If anyone can move it to the comments it'd be good.
$\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.