snibgo's ImageMagick pages

Haar wavelet pyramids

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

References

Sample input

As an example input, we use:

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

set SRC=hw_toes.png
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. "-scale" gives us one of the pixels, and "sample:offset=75" tells it to give us the second.

%IM%convert ^
  %SRC% ^
  -scale 50%%x100%% ^
  hw_1_a.png
hw_1_a.pngjpg
%IM%convert ^
  %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
hw_1_h.pngjpg

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
hw_s1_a.pngjpg hw_s1_h.pngjpg

Verify the script:

%IM%compare -metric RMSE hw_1_h.png hw_s1_h.png NULL: 
0 (0)

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.

%IM%convert ^
  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 +write mpr:TILE +delete ) ^
  ( -clone 0 -tile mpr:TILE  -draw "color 0,0 reset" +write m.png ) ^
  -compose Over -composite ^
  hw_1_iah.png
hw_1_iah.pngjpg

Check that we re-created the input:

%IM%compare -metric RMSE hw_toes.png hw_1_iah.png NULL: 
0.979592 (1.49476e-005)

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
hw_s1_iah.pngjpg

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.

%IM%convert hw_1_a.png -rotate -90 %TEMP%\hw_1_a_t1.png
%IM%convert 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

%IM%convert hw_2_a.png -rotate 90 hw_2_a.png
%IM%convert hw_2_h.png -rotate 90 hw_2_h.png
%IM%convert hw_2_v.png -rotate 90 hw_2_v.png
%IM%convert hw_2_d.png -rotate 90 hw_2_d.png
hw_2_a.pngjpg hw_2_h.pngjpg
hw_2_v.pngjpg hw_2_d.pngjpg

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

%IM%convert hw_2_a.png -auto-level hw_2_a_al.png
%IM%convert hw_2_h.png -auto-level hw_2_h_al.png
%IM%convert hw_2_v.png -auto-level hw_2_v_al.png
%IM%convert hw_2_d.png -auto-level hw_2_d_al.png
hw_2_a_al.pngjpg hw_2_h_al.pngjpg
hw_2_v_al.pngjpg hw_2_d_al.pngjpg

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
hw_4s_ahvd.pngjpg

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

call %PICTBAT%haar4bbi hw_2.png hw_recon.png

%IM%compare -metric RMSE hw_toes.png hw_recon.png NULL: 
2.04708 (3.12365e-005)
hw_recon.pngjpg

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
hw_4s_l1_ahvd.pngjpg
call %PICTBAT%haar4bb hw_4s_l1_a.png hw_4s_l2.png
hw_4s_l2_ahvd.pngjpg
call %PICTBAT%haar4bb hw_4s_l2_a.png hw_4s_l3.png
hw_4s_l3_ahvd.pngjpg
call %PICTBAT%haar4bb hw_4s_l3_a.png hw_4s_l4.png
hw_4s_l4_ahvd.pngjpg
call %PICTBAT%haar4bb hw_4s_l4_a.png hw_4s_l5.png
hw_4s_l5_ahvd.pngjpg
call %PICTBAT%haar4bb hw_4s_l5_a.png hw_4s_l6.png
hw_4s_l6_ahvd.pngjpg
call %PICTBAT%haar4bb hw_4s_l6_a.png hw_4s_l7.png
hw_4s_l7_ahvd.pngjpg

We can composite all these images together:

%IM%convert ^
  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
hw_4s_comp_ahvd.pngjpg

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 2n sides (which wastes spaces and procesing time). The script iterates until each of the _a etc images are 1x1.

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

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
hw_toes_pyr_rcn.pngjpg
%IM%compare -metric RMSE %SRC% hw_toes_pyr_rcn.png NULL: 
9.77427 (0.000149146)

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

Build the pyramid.

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

Collapse the pyramid.

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

Future

The code in these scripts is grossy inefficient, taking ten convert 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:

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

%IM%convert ^
  %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

%IM%convert ^
  %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" ) ^
  -compose Over -composite ^
  %3

haar4bb.bat

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 %IM%compare -metric RMSE %INFILE% inv%EXT% NULL:

%IM%convert %BASE%_tmp1%EXT% -rotate -90 %BASE%_tmp1%EXT%
%IM%convert %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%

%IM%convert %BASE%_a%EXT% -rotate 90 %BASE%_a%EXT%
%IM%convert %BASE%_h%EXT% -rotate 90 %BASE%_h%EXT%
%IM%convert %BASE%_v%EXT% -rotate 90 %BASE%_v%EXT%
%IM%convert %BASE%_d%EXT% -rotate 90 %BASE%_d%EXT%

%IM%convert ^
  ( %BASE%_a%EXT% %BASE%_h%EXT% %AUTO% +append ) ^
  ( %BASE%_v%EXT% %BASE%_d%EXT% %AUTO% +append ) ^
  -append ^
  %BASE%_ahvd%EXT%

endlocal

haar4bbi.bat

rem Given %1 _a, _h, _v and _d images, reconstruct image %2.

setlocal enabledelayedexpansion

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

set PREF=h4bbi_

%IM%convert %BASE%_a%EXT% -rotate -90 %PREF%%BASE%_a%EXT%
%IM%convert %BASE%_h%EXT% -rotate -90 %PREF%%BASE%_h%EXT%
%IM%convert %BASE%_v%EXT% -rotate -90 %PREF%%BASE%_v%EXT%
%IM%convert %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%

%IM%convert %PREF%%BASE%_iah%EXT% -rotate 90 %PREF%%BASE%_iah%EXT%
%IM%convert %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.

@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 (`%IM%identify ^
  -ping ^
  -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 (`%IM%identify ^
  -ping ^
  -format "EXT_DIM=%%[fx:2^%NUM_OCT%]\n" ^
  %INFILE%`) do set %%L

echo NUM_OCT=%NUM_OCT% EXT_DIM=%EXT_DIM%

%IM%convert ^
  %INFILE% ^
  -extent %EXT_DIM%x%EXT_DIM% ^
  %TMP_PREF%img%TMP_EXT%

set LEV_IN=%TMP_PREF%img%TMP_EXT%

rem set NUM_OCT=4

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%
)

%IM%convert ^
  %FILE_LIST% ^
  -layers merge ^
  %OUTFILE%

call echoRestore

endlocal & set mkhpOUTFILE=%OUTFILE%

rcnHaarPyr.bat

rem from %1 a Haar wavelet pyramid, reconstruct an image %2.

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

@setlocal enabledelayedexpansion

rem @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 (`%IM%identify ^
  -ping ^
  -format "NUM_OCT=%%[fx:ceil(log(max(h,w))/log(2))]\n" ^
  %INFILE%`) do set %%L

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

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

  %IM%convert ^
    %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 (
    %IM%convert !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
)

%IM%convert %IN_AVG% %OUTFILE%

call echoRestore

endlocal & set rhpOUTFILE=%OUTFILE%

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

%IM%identify -version
Version: ImageMagick 6.9.2-5 Q16 x64 2015-10-31 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2015 ImageMagick Studio LLC
License: http://www.imagemagick.org/script/license.php
Visual C++: 180031101
Features: Cipher DPC Modules OpenMP 
Delegates (built-in): bzlib cairo freetype jng jp2 jpeg lcms lqr openexr pangocairo png ps rsvg tiff webp xml zlib

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 22-May-2016 21:15:07.

Copyright © 2016 Alan Gibson.