What is the normalization factor for the quincunx lattice wavelet transform, and how do you find it?

Question

On pages 57-60 (preview was available last I checked, images here in case), there is a quincunx lattice transform described.

Lattice:

o • o • o • o •
• o • o • o • o
o • o • o • o •
• o • o • o • o
o • o • o • o •
• o • o • o • o
o • o • o • o •
• o • o • o • o

Basically you do these Predict operations on the black points:

x[ m][n ] -= 1/4 * ( LEFT + RIGHT + DOWN + UP )

Where $LEFT = x[ m ][ n-1 ]$, $RIGHT= x[m][n+1]$, $DOWN=x[m+1][n]$, $UP=x[m-1][n]$.

You then do updates on the white points:

x[ m][n] += 1/8 * ( LEFT + RIGHT + DOWN + UP )

Then you will never touch the black values again, so you effectively have:

o x o x o x o x
x o x o x o x o
o x o x o x o x
x o x o x o x o
o x o x o x o x
x o x o x o x o
o x o x o x o x
x o x o x o x o

You turn your head 45 degrees to see this is just another rectangular lattice, and you label them odd/even again:

o   o   o   o 
  •   •   •   •
o   o   o   o 
  •   •   •   •
o   o   o   o 
  •   •   •   •
o   o   o   o 
  •   •   •   •

You repeat this again and again, until you have 1 "average" left.

Now in the Haar wavelet transform, there is a power loss in each level that we correct with a normalization factor of √2.

Here, there is a computed power loss factor of about 1.4629 after the first step of the first level (found by running 5,000,000 transforms on random data and finding the ratio of powerBefore/powerAfter and averaging).

I don't know how to show/compute how this power loss is found, and where the 1.46 number comes from.

Answer 1

I don't think there is any single best number for normalisation because it depends on the structure of the values in your lattice.

In the simplest case where all values are equal, the predict operation zeros the black points and the update does not change the white points. Because each predict-update pair halves the number of nonzero points, multiplying the lattice by sqrt(2) after each pair of steps would conserve energy.

With all values independent with zero mean and equal variance, the predict step multiplies the variance of the black points by 5/4 and then the update step multiplies the variance of the white points by 281/256 so energy increases at each step.

Answer 2

The quincunx lattice wavelet you describe is also called (as far as I know) the red-black wavelet transform. You can find one illustrated description in The Red-Black Wavelet Transform by Geert Uytterhoeven and Adhemar Bultheel. Apparently, the transform is not orthogonal, but biorthogonal:

Biorthogonality: The splitting in red and black or blue and yellow pixels creates trivial biorthogonal basis functions. Since lifting steps preserve the biorthogonality properties the transform as a whole has biorthogonal basis functions, too [5].

It is also describes in Wavelet Families of Increasing Order in Arbitrary Dimensions by Sweldens and Kovacevic. Properties (smoothness, Sobolev index, approximation order, etc.) can be found in Quincunx fundamental refinable functions and Quincunx biorthogonal wavelets by Bin Han and Rongqing Jia.

Being biorthogonal only, one doesn't expect the quincunx lattice to preserve energy. Which is ok for classical image compression applications.