Implementing the DWT

Question

I have been given the task to implement the 5/3 CDF transform for image compression.

Given that the impulse response for the low and high pass are:

• $h_1 = [-0.5, 1 ,-0.5]$ (High Pass)
• $h_2 = [-0.125, 0.25, 0.75, 0.25, -0.125]$ (Low Pass)

Say I want to start by computing the horizontal 1D DWT for an image. Now given that the pixels of a row obtained are $x[n]$, we can compute the convolution $y[n] = x[n]*h[n]$. At the beginning of the convolution process we have partial overlap, then full overlap and then partial overlap again. But due to the last part of the partial overlap we obtain extra values.

For the high pass filter I end up with 2 more and for the low pass 4 more. This means that the values obtained for the row pixels are now slightly larger. What am I do about this with respect to programming? Do I eliminate the last few values so $y[n]$ will match $x[n]$ in size?

Another very important question, I have implemented this regardless but I face an even greater problem. While I am fairly new to python, the algorithm I implemented is very very slow. Is there are faster way to implement this rather than using convolution? I will refrain from uploading the code here, because I am not sure if my problem is applicable to this forum or stack overflow. I shall upload it upon request.

Answer 1

Treating boundaries correctly is non trivial for wavelets and filter banks in general. Symmetric/anti-symmetric filters (such as with biorthogonal wavelets as the 5/3 or the 9/7) help a little. Yet, with dyadic sub-sampling, without playing too heavily on polyphase matrices and symmetries, I would suggest the following procedure:

• choose a level $L$ for the iterated decomposition
• find an image size that can be divided by $2^L$
• extend the original image to that size (symmetry/anti-symmetry, or zero-padding but not the best)
• extend the smallest filter with zero-padding to match the longest filter size, so both filters have the same padded length.

Cleverer/sparser exist, but they are more involved. Now the number of coefficients ought to be similar. As for the Python, this is more "language-related", and not adapted to SE.DSP. IN 1D, the lifting scheme can improve the computation burden by a factor of 2 in terms of basioc operations.