9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Its probably just another power normalizer. Is your energy conserved? $\endgroup$ – Spacey May 1 '12 at 16:29
  • $\begingroup$ On what random data image sizes did you try? Might it happen that 1.4629 is in reality $\sqrt{2}$ in disguise, due to border effects? $\endgroup$ – Laurent Duval Dec 13 '15 at 20:28
0
$\begingroup$

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.

$\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.