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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.