Haar wavelet pyramids

A blast from the past: Alfred Haar invented these in 1909.

References
Sample input
Forwards building block
Inverse building block
Stage 2
Scripts to build and collapse pyramids
Future
Scripts

References

Wikipedia: Haar wavelet
On the Theory of Orthogonal Function Systems, Alfred Haar, 1909. English translation.
Wavelets for Kids: a Tutorial Introduction, Brani Vidakovic and Peter Mueller, 1991.

Sample input

As an example input, we use:

%IMG7%magick ^
  toes.png ^
  -crop 256x256+0+0 +repage ^
  -resize "256x256^!" ^
  hw_toes.png

set SRC=hw_toes.png

This is a square image with each dimension a power of two. Thus it can be halved and halved again until it is exactly 1x1 pixel. At each stage, it can be doubled in size to exactly restore the original size. This simplifies the processing.

Forwards building block

From one input image, we create two output images, each half the width of the input. In both the outputs, each pixel is derived from two adjacent input pixels. In the first output, each pixel is the average of two adjacent input pixels. In the second output, each pixel is the difference of two adjacent input pixels.

So the total output has the same number of pixels as the input (provided the width was divisible by two). We haven't lost any data.

The first output is easy: scaling by 50% horizontally gives us the average of each pair of pixels.

For the second output, finding the difference is a bit tricky. Suppose the two pixels in the top-left of the image have values a and b, in that order. These are the values in %SRC%. We want the value of b minus a. By scaling the average back up to size, we have a second image, with values (a+b)/2 in both positions. If we subtract the source from this, then the first pixel will contain (a+b)/2-a and the second pixel will contain (a+b)/2-b = a/2-b/2, which is the desired value. We don't care about the first pixel, but want the value of the second pixel. "-sample" gives us one of the pixels, and "sample:offset=75" tells it to give us the second.

%IMG7%magick ^
  %SRC% ^
  -scale 50%%x100%% ^
  hw_1_a.png

%IMG7%magick ^
  %SRC% ^
  ( hw_1_a.png ^
    -scale 200%%x100% ^
  ) ^
  -compose Mathematics ^
    -define compose:args=0,1,-1,0.5 ^
    -composite ^
  -define sample:offset=75 ^
  -sample 50%%x100%% ^
  hw_1_h.png

This process, of taking one input and creating two half-width outputs, is the building block of the overall process. I put this into a script, haarbb.bat.

call %PICTBAT%haarbb %SRC% hw_s1_a.png hw_s1_h.png

Verify the script does the same as individual commands:

%IMG7%magick compare -metric RMSE hw_1_h.png hw_s1_h.png NULL:

0.707121 (1.079e-05)

Inverse building block

We can do the inverse: from the two outputs of the basic building block we can re-create the input.

The two outputs are the average and difference, specifically a/2+b/2 and a/2-b/2.

Add these together and we get a. Subtract the second from the first and we get b. Composite a and b with a mask such that in each pair of pixels, the left pixel is from a and the right pixels is from b.

%IMG7%magick ^
  hw_1_a.png ^
  hw_1_h.png ^
  ( -clone 0-1 ^
    -compose Mathematics -define compose:args=0,1,1,-0.5 -composite ^
    -scale 200%%x100%% ^
  ) ^
  ( -clone 0-1 ^
    -compose Mathematics -define compose:args=0,-1,1,0.5 -composite ^
    -scale 200%%x100%% ^
  ) ^
  -delete 0-1 ^
  ( xc:Black xc:White +append +repage +write mpr:TILE +delete ) ^
  ( -clone 0 -tile mpr:TILE  -draw "color 0,0 reset" -alpha off ) ^
  -compose Over -composite ^
  hw_1_iah.png

Check that we re-created the input:

%IMG7%magick compare -metric RMSE hw_toes.png hw_1_iah.png NULL:

1.11805 (1.70603e-05)

Yes, we did.

Put this inverse building block into a script, haarbbi.bat.

call %PICTBAT%haarbbi ^
  hw_s1_a.png ^
  hw_s1_h.png ^
  hw_s1_iah.png

Stage 2

Next, we take the two outputs from the forwards building block, rotate them backwards by 90°, and put both these images through the same basic building block to create four outputs, then rotate these the other way.

%IMG7%magick hw_1_a.png -rotate -90 %TEMP%\hw_1_a_t1.png
%IMG7%magick hw_1_h.png -rotate -90 %TEMP%\hw_1_h_t1.png

call %PICTBAT%haarbb %TEMP%\hw_1_a_t1.png hw_2_a.png hw_2_h.png
call %PICTBAT%haarbb %TEMP%\hw_1_h_t1.png hw_2_v.png hw_2_d.png

%IMG7%magick hw_2_a.png -rotate 90 hw_2_a.png
%IMG7%magick hw_2_h.png -rotate 90 hw_2_h.png
%IMG7%magick hw_2_v.png -rotate 90 hw_2_v.png
%IMG7%magick hw_2_d.png -rotate 90 hw_2_d.png

So we can see the data, prettify with -auto-level.
(This is not for further processing.)

%IMG7%magick hw_2_a.png -auto-level hw_2_a_al.png
%IMG7%magick hw_2_h.png -auto-level hw_2_h_al.png
%IMG7%magick hw_2_v.png -auto-level hw_2_v_al.png
%IMG7%magick hw_2_d.png -auto-level hw_2_d_al.png

The initials AHVD are for Average, Horizontal, Vertical and Detail.

Put both stage 1 and stage 2 into a script, haar4bb.bat, which also creates a pretty image that puts all four images into one. The script has one input and creates five outputs. Instead of naming them individually, the script takes one input filename and a single output filename like a.ext and creates outputs suffixed _a, _h, _v, _d and _ahvd. If the script is given "a" as the third argument, it will auto-level each of the four images before appending them.

call %PICTBAT%haar4bb %SRC% hw_4s.png

The inverse script, haar4bbi.bat, takes the four images and reconstructs the source.

call %PICTBAT%haar4bbi hw_2.png hw_recon.png

%IMG7%magick compare -metric RMSE hw_toes.png hw_recon.png NULL:

2.23607 (3.41202e-05)

The top-left image, suffixed _a, has each pixel set to the average of four pixels from the input. We iterate the process by feeding this image into the same script.

call %PICTBAT%haar4bb hw_4s_a.png hw_4s_l1.png
call %PICTBAT%haar4bb hw_4s_l1_a.png hw_4s_l2.png
call %PICTBAT%haar4bb hw_4s_l2_a.png hw_4s_l3.png
call %PICTBAT%haar4bb hw_4s_l3_a.png hw_4s_l4.png
call %PICTBAT%haar4bb hw_4s_l4_a.png hw_4s_l5.png
call %PICTBAT%haar4bb hw_4s_l5_a.png hw_4s_l6.png
call %PICTBAT%haar4bb hw_4s_l6_a.png hw_4s_l7.png

We can composite all these images together:

%IMG7%magick ^
  hw_4s_ahvd.png ^
  hw_4s_l1_ahvd.png ^
  hw_4s_l2_ahvd.png ^
  hw_4s_l3_ahvd.png ^
  hw_4s_l4_ahvd.png ^
  hw_4s_l5_ahvd.png ^
  hw_4s_l6_ahvd.png ^
  hw_4s_l7_ahvd.png ^
  -layers merge ^
  hw_4s_comp_ahvd.png

If we haven't auto-levelled, this image contains exactly the data we need to reconstruct the original image. It would be the complete pyramid, in one convenient package, the same size as the input image.

Scripts to build and collapse pyramids

Based on the above worked example, we can now write a script to build a Haar wavelet pyramid from an image, and another to collapse a pyramid into an image.

The script mkHaarPyr.bat creates a pyramid from an image. I haven't yet played with non-power-of-2 sizes, so for now the script extends the image if necessary to be square with 2ⁿ sides (which wastes spaces and processing time). The script iterates until each of the _a etc images are 1x1.

call %PICTBAT%mkHaarPyr ^
  hw_toes.png ^
  hw_toes_pyr.png

The resulting pyramid is impressively gray.

The script rcnHaarPyr.bat reconstructs an image from a Haar wavelet pyramid. It "collapses" the pyramid.

call %PICTBAT%rcnHaarPyr ^
  hw_toes_pyr.png ^
  hw_toes_pyr_rcn.png

%IMG7%magick compare -metric RMSE %SRC% hw_toes_pyr_rcn.png NULL:

56.1191 (0.000856323)

If the image isn't square, with sides 2ⁿ, it extends the image first. Then rcnHaarPyr.bat doesn't know the original size, so we get blank (white) space.

Build the pyramid.

call %PICTBAT%mkHaarPyr ^
  toes.png ^
  hw_toes_ns_pyr.png

Collapse the pyramid.

call %PICTBAT%rcnHaarPyr ^
  hw_toes_ns_pyr.png ^
  hw_toes_ns_pyr_rcn.png

Future

The code in these scripts is grossy inefficient, taking ten magick commands per level. A 7000x5000 pixel images takes around 20s to contruct the pyramid with 13 levels. The job could be done by a process module in a single pass of the image per level. But I needed to write these scripts in order to understand the process. It also forms a test-bed for experimentation.

Scripts could also:

identify (find rectangles of) elements (which level, and a, h, v or d) in the pyramid;
expand elements to full size;
inter-pyramid operations: blend etc.

What if we don't want to halve the image each time, but use some other fraction?

How about limiting levels, at either end?

Does transparency work sensibly?

Scripts

For convenience, .bat scripts are also available in a single zip file. See Zipped BAT files.

haarbb.bat

@rem
@rem Updated:
@rem   12-August-2022 for IM v7.
@rem

%IMG7%magick ^
  %1 ^
  ( +clone ^
    -scale 50%%x100%% ^
    +write %2 ^
    -scale 200%%x100%% ^
  ) ^
  -compose Mathematics -define compose:args=0,1,-1,0.5 -composite ^
  -define sample:offset=75 ^
  -sample 50%%x100%% ^
  %3

haarbbi.bat

@rem
@rem Updated:
@rem   12-August-2022 for IM v7.
@rem

%IMG7%magick ^
  %1 ^
  %2 ^
  ( -clone 0-1 ^
    -compose Mathematics -define compose:args=0,1,1,-0.5 -composite ^
    -scale 200%%x100%% ^
  ) ^
  ( -clone 0-1 ^
    -compose Mathematics -define compose:args=0,-1,1,0.5 -composite ^
    -scale 200%%x100%% ^
  ) ^
  -delete 0-1 ^
  ( xc:Black xc:White +append +write mpr:TILE +delete ) ^
  ( -clone 0 -tile mpr:TILE -draw "color 0,0 reset" -alpha off ) ^
  -compose Over -composite ^
  %3

haar4bb.bat

@rem
@rem Updated:
@rem   12-August-2022 for IM v7.
@rem

setlocal enabledelayedexpansion

set INFILE=%1

set BASE=%~dpn2
set EXT=%~x2

if "%3"=="a" (
  set AUTO=-auto-level
) else (
  set AUTO=
)

call %PICTBAT%haarbb %INFILE% %BASE%_tmp1%EXT% %BASE%_tmp2%EXT%

rem call haarWaveletInv %BASE%_tmp1%EXT% %BASE%_tmp2.png inv%EXT%
rem %IMG7%magick compare -metric RMSE %INFILE% inv%EXT% NULL:

%IMG7%magick %BASE%_tmp1%EXT% -rotate -90 %BASE%_tmp1%EXT%
%IMG7%magick %BASE%_tmp2%EXT% -rotate -90 %BASE%_tmp2%EXT%

call %PICTBAT%haarbb %BASE%_tmp1%EXT% %BASE%_a%EXT% %BASE%_h%EXT%
call %PICTBAT%haarbb %BASE%_tmp2%EXT% %BASE%_v%EXT% %BASE%_d%EXT%

%IMG7%magick %BASE%_a%EXT% -rotate 90 %BASE%_a%EXT%
%IMG7%magick %BASE%_h%EXT% -rotate 90 %BASE%_h%EXT%
%IMG7%magick %BASE%_v%EXT% -rotate 90 %BASE%_v%EXT%
%IMG7%magick %BASE%_d%EXT% -rotate 90 %BASE%_d%EXT%

%IMG7%magick ^
  ( %BASE%_a%EXT% %BASE%_h%EXT% %AUTO% +append +repage ) ^
  ( %BASE%_v%EXT% %BASE%_d%EXT% %AUTO% +append +repage ) ^
  -append +repage ^
  %BASE%_ahvd%EXT%

endlocal

haar4bbi.bat

rem Given %1 _a, _h, _v and _d images, reconstruct image %2.
@rem
@rem Updated:
@rem   12-August-2022 for IM v7.
@rem

setlocal enabledelayedexpansion

set BASE=%~n1
set EXT=%~x1
set OUTFILE=%2

set PREF=h4bbi_

%IMG7%magick %BASE%_a%EXT% -rotate -90 %PREF%%BASE%_a%EXT%
%IMG7%magick %BASE%_h%EXT% -rotate -90 %PREF%%BASE%_h%EXT%
%IMG7%magick %BASE%_v%EXT% -rotate -90 %PREF%%BASE%_v%EXT%
%IMG7%magick %BASE%_d%EXT% -rotate -90 %PREF%%BASE%_d%EXT%

call %PICTBAT%haarbbi %PREF%%BASE%_a%EXT% %PREF%%BASE%_h%EXT% %PREF%%BASE%_iah%EXT%
call %PICTBAT%haarbbi %PREF%%BASE%_v%EXT% %PREF%%BASE%_d%EXT% %PREF%%BASE%_ivd%EXT%

%IMG7%magick %PREF%%BASE%_iah%EXT% -rotate 90 %PREF%%BASE%_iah%EXT%
%IMG7%magick %PREF%%BASE%_ivd%EXT% -rotate 90 %PREF%%BASE%_ivd%EXT%

call %PICTBAT%haarbbi %PREF%%BASE%_iah%EXT% %PREF%%BASE%_ivd%EXT% %OUTFILE%

endlocal

mkHaarPyr.bat

rem From image %1,
rem makes Haar wavelet pyramid %2.
@rem
@rem Updated:
@rem   12-August-2022 for IM v7.
@rem

@if "%1"=="" findstr /B "rem @rem" %~f0 & exit /B 1

@setlocal

@call echoOffSave

call %PICTBAT%setInOut %1 mkhp

if not "%2"=="" set OUTFILE=%2

set TMP_EXT=.miff
set TMP_PREF=%TEMP%\mkhp_

set NUM_OCT=
for /F "usebackq" %%L in (`%IMG7%magick identify ^
  -format "NUM_OCT=%%[fx:ceil(log(max(h,w))/log(2))]\n" ^
  %INFILE%`) do set %%L

if "%NUM_OCT%"=="" exit /B 1

for /F "usebackq" %%L in (`%IMG7%magick identify ^
  -format "EXT_DIM=%%[fx:2^%NUM_OCT%]\n" ^
  %INFILE%`) do set %%L

echo NUM_OCT=%NUM_OCT% EXT_DIM=%EXT_DIM%

%IMG7%magick ^
  %INFILE% ^
  -extent %EXT_DIM%x%EXT_DIM% ^
  %TMP_PREF%img%TMP_EXT%

set LEV_IN=%TMP_PREF%img%TMP_EXT%

set FILE_LIST=
for /L %%I in (1,1,%NUM_OCT%) do (
  echo %%I

  call %PICTBAT%haar4bb !LEV_IN! %TMP_PREF%_l%%I%TMP_EXT%

  set FILE_LIST=!FILE_LIST! %TMP_PREF%_l%%I_ahvd%TMP_EXT%

  set LEV_IN=%TMP_PREF%_l%%I_a%TMP_EXT%
)

%IMG7%magick ^
  %FILE_LIST% ^
  -layers merge ^
  %OUTFILE%

call echoRestore

endlocal & set mkhpOUTFILE=%OUTFILE%

rcnHaarPyr.bat

rem from %1 a Haar wavelet pyramid, reconstruct an image %2.
@rem
@rem Updated:
@rem   12-August-2022 for IM v7.
@rem

@if "%1"=="" findstr /B "rem @rem" %~f0 & exit /B 1

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 rhp

if not "%2"=="" set OUTFILE=%2


set PREF=rhp_
set TMP_EXT=.miff

set NUM_OCT=
for /F "usebackq" %%L in (`%IMG7%magick identify ^
  -format "NUM_OCT=%%[fx:ceil(log(max(h,w))/log(2))]\n" ^
  %INFILE%`) do set %%L

if "%NUM_OCT%"=="" exit /B 1

echo %0: NUM_OCT=%NUM_OCT%

set IN_AVG=
set DIM=1
set FILE_LIST=
for /L %%I in (1,1,%NUM_OCT%) do (
  echo %%I DIM=!DIM!

  %IMG7%magick ^
    %INFILE% ^
    ^( -clone 0 ^
        -crop !DIM!x!DIM!+0+0 +repage +write %PREF%_%%I_a%TMP_EXT% ^
        +delete ^) ^
    ^( -clone 0 ^
       -crop !DIM!x!DIM!+!DIM!+0 +repage +write %PREF%_%%I_h%TMP_EXT% ^
        +delete ^) ^
    ^( -clone 0 ^
        -crop !DIM!x!DIM!+0+!DIM! +repage +write %PREF%_%%I_v%TMP_EXT% ^
        +delete ^) ^
    ^( -clone 0 ^
        -crop !DIM!x!DIM!+!DIM!+!DIM! +repage +write %PREF%_%%I_d%TMP_EXT% ^
        +delete ^) ^
    NULL:

  if %%I GTR 1 (
    %IMG7%magick !IN_AVG! %PREF%_%%I_a%TMP_EXT%
  )

  call %PICTBAT%haar4bbi %PREF%_%%I%TMP_EXT% %PREF%_%%I_rcn%TMP_EXT%

  set IN_AVG=%PREF%_%%I_rcn%TMP_EXT%

  set /A DIM*=2
)

%IMG7%magick %IN_AVG% %OUTFILE%

call echoRestore

endlocal & set rhpOUTFILE=%OUTFILE%

All images on this page were created by the commands shown, using:

%IMG7%magick -version

Version: ImageMagick 7.1.0-42 Q16-HDRI x64 396d87c:20220709 https://imagemagick.org
Copyright: (C) 1999 ImageMagick Studio LLC
License: https://imagemagick.org/script/license.php
Features: Cipher DPC HDRI OpenCL 
Delegates (built-in): bzlib cairo freetype gslib heic jng jp2 jpeg jxl lcms lqr lzma openexr pangocairo png ps raqm raw rsvg tiff webp xml zip zlib
Compiler: Visual Studio 2022 (193231332)

Source file for this web page is haar.h1. To re-create this web page, execute "procH1 haar".

This page, including the images, is my copyright. Anyone is permitted to use or adapt any of the code, scripts or images for any purpose, including commercial use.

Anyone is permitted to re-publish this page, but only for non-commercial use.

Anyone is permitted to link to this page, including for commercial use.

Page version v1.0 20-Nov-2015.

Page created 12-Aug-2022 17:42:14.