Fun with LGT 5/3 wavelet transform

LGT 5/3 wavelet transform is the second simplest lossless wavelet transform (the first one is Haar transform of course) so it’s used in a variety of image formats (most famously in JPEG-2000) and intermediate video codecs. Recently I helped one guy with implementing it and while explaining things about it I understood it myself, so here I’m going to write it down for posterity.

Usually it’s said that forward transform coefficients are [-1/8, 2/8, 6/8, 2/8, -1/8] (lowpass) and [-1/2, 1, -1/2] (highpass) and inverse transform coefficients are [1/2, 1, 1/2] (lowpass) and [-1/8, -2/8, 6/8, -2/8, -1/8] (highpass). In reality if you implement inverse transform using those coefficients you get wrong results.

Here’s a simple table to present how input coefficients map to output ones:

x[-1] x[0] x[1] x[2] x[3] x[4] x[5]
hi[0] -4/8 8/8 -4/8
lo[0] -1/8 2/8 6/8 2/8 -1/8
hi[1] -4/8 8/8 -4/8
lo[1] -1/8 2/8 6/8 2/8 -1/8
hi[2] -4/8 8/8 -4/8

(x[-1] is a mirrored value equal to x[1])

As you can see from the table, x[1] can be restored as lo[0] - (hi[0] + hi[1])/4. With some more calculations you can derive x[2] as (-hi[0] + 4*lo[0] + 6*hi[1] + 4*lo[1] - hi[2])/8. Those are not exactly the coefficients you wanted, are they?

It turns out the trick is that actual high- and low-pass values are multiplied by sqrt(2) and -1/sqrt(2) correspondingly so when you’re using them in calculations you’d need to multiply them by -1/2 or -2 and thus get the proper coefficients. But since we use integer-only calculations we don’t scale the output by an irrational number and the inverse transform coefficients had to be modified.

And from here we can move to a lifting transform where calculations are made on data in place, without temporary buffers. As mentioned above, we can restore odd elements as simply as x[2n+1] = lo[n] - (hi[n] + hi[n+1])/4. But what to do with even elements? hi[n] = x[2n] - (x[2n-1] + x[2n+1])/2 so x[2n] = hi[n] + (x[2n-1] + x[2n+1])/2. Thus we can get interleaved data, replace low-pass coefficients with restored data and use them to restore the other half of coefficients replacing high-pass data.
The same can be applied to forward transform as well.

If you’re not afraid of mathematics you can actually read and understand the theory behind them, how such filters are constructed, what they’re good for and so on. I’d rather stop here.

2 Responses to “Fun with LGT 5/3 wavelet transform”

  1. Paul says:

    Please, never stop talking about wavelets. There so many discovered and yet to be discovered stuff.

  2. Kostya says:

    I agree with you that it’s a trite stuff, but sadly in multimedia (like in many other areas) people don’t understand the stuff they use. Even some codecs are designed that way.