0
$\begingroup$

I'm working on my own implementation of the discrete Haar wavelet transform, I understand the wavelet theory and how to construct the Haar matrix of size N to perform the transform, but obviously there is a problem using the Haar matrix in application - it's simply too big.

I am working on an application that applies the Haar transform to an audio signal. If I sample the signal at 44.1 kHz, even a one second recording would require a 2^16 by 2^16 Haar matrix to do the transform in one step, which is obviously impractical and a hardware constrained machine such as a phone wouldn't have the capability to hold such a matrix in memory.

The other method I've seen used is that a 2X2 Haar matrix is applied to the entire signal iteratively, and the results are stored in two arrays - one array holding the "average" Haar coefficients (first element of the output vector) and the other holding the "difference" coefficients (second element of the output vector). The process is then repeated over the "average" coefficients - as these coefficients are essentially the result of a lowpass filter. Each time the process is repeated the number of elements needed to process in the following step is halved, until only one lowpass coefficient is left. This seems fine, and definitely works but when I started to think about it, it just seems that it would be really slow.

My main question is, what's a good way to implement a fast and efficient haar transform? Or a practical way to apply one of these two methods?

PS: I've been learning about this completely on my own, so if I made some mistakes in my explanation or way of thinking about this stuff let me know.

PSS: I've never done any kind of audio processing before, so if you know about some other filters that I should apply to the raw signal before doing a wavelet transform let me know!

PSSS: I know that the Haar wavelet may not be the best for this type of signal processing, but when I tried to learn about using other DWTs such as the Daubechies wavelets, the literature seemed very confusing, or at least was directed at more advanced readers. If anyone could point me in the direction of how to implement other DWTs, that would be great.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

The Haar wavelet is actually a part of the Daubechies wavelet, for the case D=2. There's some example code on wikipedia that shows the Daubachies transform.

The Haar transform is just a low pass filter combined with a high pass filter, with the coefficients being placed in the first and second halves of the signal. Then, this iteratively (or recursively) keep going.

The low pass filter is just the sum of two components while the high pass filter is their difference.

For the Haar wavelet case, you can check out my vectorized code on Github. Here, idwt2 stands for "Inverse Discrete Wavelet Transform 2D."

Improve this answer
$\endgroup$
7
  • $\begingroup$ Hey Scott, thanks for the reply. I'm guessing that some of the functions you were using, like "cblas_scopy" are part of one of the packages you included in the declarations, correct? $\endgroup$
    – themantalope
    Commented Nov 20, 2013 at 2:18
  • $\begingroup$ Correct. They're part of BLAS, which (in my case) is part of Apple's Accelerate framework. If you want without those functions, look at the code's history (around Sept 2013). $\endgroup$
    – Scott
    Commented Nov 20, 2013 at 18:54
  • $\begingroup$ Ok, thanks. I'll just need to do some research about what all that stuff is actually doing. $\endgroup$
    – themantalope
    Commented Nov 21, 2013 at 5:35
  • $\begingroup$ It just adds the first two components (a low pass filter) and then subtracts the same components (a high pass filter). There's more info here: cs.ucf.edu/~mali/haar and on the wiki page: en.wikipedia.org/wiki/Haar_wavelet $\endgroup$
    – Scott
    Commented Nov 21, 2013 at 18:33
  • $\begingroup$ Haha, well yes, that's what the haar lowpass and high pass filters do, I guess I was just saying I want to see how exactly how those methods work. $\endgroup$
    – themantalope
    Commented Nov 23, 2013 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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