snibgo's ImageMagick pages

Alignment by brute force

The alignment of two images can be tested at every possible offset.

• Sample inputs
• The process
• The script
• With alpha
• Future
• See also
• Scripts

Suppose an area from photo A overlaps the same-size area on photo B. We can crop each image to the overlapping area, and compare these overlaps. RMSE (root mean squared error) gives us a measure of how closely the overlap areas match. We can try every possible overlapping offset to find the one with the best (smallest) RMSE.

If the images are both WxH pixels, the size of the overlapping area will vary between 1x1 and WxH pixels. The number of offsets to test is (2W-1).(2H-1) = 4WH-2W-2H+1.

Sample inputs

As examples, we use two very small images. So we can see them, we use a script to enlarge them.

%IMG7%magick ^ -size 3x2 ^ xc:red ^ -fill Blue -draw "point 1,0" ^ abf_src1.png set bpSCALE=37 set bpGAP=9 call %PICTBAT%blockPix abf_src1.png
%IMG7%magick ^ -size 3x2 ^ xc:lime ^ -fill Blue -draw "point 2,0" ^ abf_src2.png call %PICTBAT%blockPix abf_src2.png

The process

We generate all the possible alignments of these two images ...

for /L %%y in (-1,1,1) do (
  set /A oy=46*%%y+4
  for /L %%x in (-2,1,2) do (
    set /A ox=46*%%x-6

    %IMG7%magick ^
      abf_src1_bp.png ^
      ^( abf_src2_bp.png -repage +!ox!+!oy! ^) ^
      -background None -layers merge +repage ^
      abf_%%y_%%x.png
  )
)

... and show them:

The two images have fully saturated red, green or blue pixels. In all of the overlaps except one, corresponding pixels in the two overlapping sections are different colours. In one overlapping position, the blue pixel from one image corresponds to the blue pixel in the other image. This is the best alignment.

The script

The script alignBF.bat runs a single magick command that reads the two images, generates every pair of overlaps, and finds the RMSE for each pair. It finds the lowest RMSE, and writes results to a text file. The script assumes the photos are the same size. It could be modified to remove that restriction.

Caution: If the two images have WxH pixels, there are 4WH-2H-2W+1 possible offset positions. When W=7500 and H=5000, this is about 150 million offsets. As most comparisons will take more than a second, alignment by brute force is not feasible on the full-size photos.

Find the alignment with the lowest RMSE:

call %PICTBAT%alignBF abf_src1.png abf_src2.png

The script writes the result to a CSV file, and puts the name of that file in abfDATAFILE.

type %abfDATAFILE% 

0.707107,-1,0,2,2,0,0,1,0

The data is:

• The best RMSE score. (0.707)
• The x- and y-offset of the second image with respect to the first. (-1,0)
• The width and height of the overlapping areas. (2,2)
• The top-left position of the overlap within the first image. (0,0: the best overlap starts at 0,0 in the red image.)
• The top-left position of the overlap within the second image. (1,0: the best overlap starts at 1,0 in the green image.)

We can read the data with:

for /F "tokens=1-9 delims=," %%A in (%agpDATAFILE%) do (
  set OV_COMP=%%A
  set OV_X=%%B
  set OV_Y=%%C
  set OV_W=%%D
  set OV_H=%%E
  set OV_X1=%%F
  set OV_Y1=%%G
  set OV_X2=%%H
  set OV_Y2=%%I
)

The script optionally takes parameters that limit the extents of the offsets to be tested. This means we can do a full search using reduced versions of images, and use the result to limit the search space of full-size versions. See Alignment by Gaussian pyramid.

With alpha

One or other image may contain transparency. For comparisons, I don't want fully-transparent pixels to count towards a similarity score. A fully-transparent pixel doesn't exist, conceptually (see Alvy Ray Smith, "A Sprite Theory of Image Computing"). The process module rmsealpha does what I want, and the script alignBFalpha.bat uses it.

call %PICTBAT%alignBFalpha abf_src1.png abf_src2.png

echo %abfaDODGY% 

1 

The script writes the result to a CSV file, and puts the name of that file in abfaDATAFILE.

type %abfaDATAFILE% 

0.81649658,-2,-1,1,1,0,0,2,1

There is a substantial overhead in calling process modules, about 0.1 seconds per invocation on my laptop, so this is slower than alignBF.bat.

Future

The returned score is the simple RMSE. In real life, we would give more weight when matching images contain significant detail rather than, say, a clear blue sky matching another clear blue sky. The scripts may be enhanced to provide this.

All the work done by alignBFalpha.bat could be written as a single process module, massively improving performance.

See also

• Overlapping photographs, which uses this brute force script to find the alignment of Gaussian pyramids.
• Alignment by matching points.
• Simple alignment by matching areas.

Scripts

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

alignBF.bat

The script uses utility programs cGroup.exe and cJoin.exe. I don't provide source or binaries of these. Here, they reduce the data file to contain only the line with the lowest RMSE score. The work could be done by sorting numerically, in reverse, and finding the first line.

rem Find x-y alignment of two same-size images %1 and %2 by brute force comparison.
@rem We find the position that scores the best RMSE.
@rem Fairly fast when WW*HH is small, or search space is small.
@rem
@rem Optional:
@rem   %3 is width of both
@rem   %4 is height of both
@rem   %5,%6 top-left to try
@rem   %7,%8 botton-right to try
@rem
@rem Returns name of a file containing CSV data.
@rem If best is at an extreme, probably dodgy.
@rem
@rem Updated:
@rem   15 May 2016 use %IML% for @script.
@rem   22-August-2022 Upgraded for IM v7.
@rem

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

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 abf


set SCR_FILE=%sioCODE%.scr
set DATA_FILE=%sioCODE%_data.csv
set DATA_FILE2=%sioCODE%_data2.csv
set DATA_FILE3=%sioCODE%_data3.csv

set SRC1=%1
set SRC2=%2

set WW=%3
set HH=%4

if "%WW%"=="." set WW=
if "%HH%"=="." set HH=

set FIND_DIMS=0
if "%WW%"=="" set FIND_DIMS=1
if "%HH%"=="" set FIND_DIMS=1

if %FIND_DIMS%==1 for /F "usebackq" %%L in (`%IMG7%magick identify ^
  -format "WW=%%w\nHH=%%h" ^
  %SRC1%`) do set %%L

if "%WW%"=="" (
  echo %0: can't identify SRC1 [%SRC1%]
  exit /B 1
)

echo %SRC1% %SRC2% >%SCR_FILE%

set /A WWm1=%WW%-1
set /A HHm1=%HH%-1

set FirstX=%5
set FirstY=%6
set LastX=%7
set LastY=%8

if "%FirstX%"=="." set /A FirstX=
if "%FirstY%"=="." set /A FirstY=
if "%LastX%"=="." set /A LastX=
if "%LastY%"=="." set /A LastY=

if "%FirstX%"=="" set /A FirstX=-%WWm1%
if "%FirstY%"=="" set /A FirstY=-%HHm1%

if "%LastX%"=="" set /A LastX=%WWm1%
if "%LastY%"=="" set /A LastY=%HHm1%

rem First or Last might be beyond -+WWm1 etc.

if %FirstX% LSS -%WWm1% set /A FirstX=-%WWm1%
if %FirstY% LSS -%HHm1% set /A FirstY=-%HHm1%
if %LastX% GTR %WWm1% set /A LastX=%WWm1%
if %LastY% GTR %HHm1% set /A LastY=%HHm1%

echo %~n0: WWm1=%WWm1% HHm1=%HHm1% FirstX=%FirstX% FirstY=%FirstY% LastX=%LastX% LastY=%LastY%

set MIN_COMP=999

rem Optional -auto-level -auto-gamma  to each crop?
for /L %%y in (%FirstY%,1,%LastY%) do (

  if %%y GEQ 0 (
    set /A H=%HH%-%%y
    set /A Y1=%%y
    set /A Y2=0
  ) else (
    set /A H=%HH%+%%y
    set /A Y1=0
    set /A Y2=-%%y
  )

  for /L %%x in (%FirstX%,1,%LastX%) do (

    if %%x GEQ 0 (
      set /A W=%WW%-%%x
      set /A X1=%%x
      set /A X2=0
    ) else (
      set /A W=%WW%+%%x
      set /A X1=0
      set /A X2=-%%x
    )

    ( echo ^( -clone 0-1
      echo   ^( -clone 0 -crop !W!x!H!+!X1!+!Y1! +repage -auto-level ^)
      echo   ^( -clone 1 -crop !W!x!H!+!X2!+!Y2! +repage -auto-level ^)
      echo   -delete 0-1
      echo   -metric RMSE -compare
      echo   -format "%%[distortion],%%x,%%y,!W!,!H!,!X1!,!Y1!,!X2!,!Y2!\n"
      echo   -write info:
      echo   +delete
      echo ^)
    )
  )
)>>%SCR_FILE%

echo -exit >>%SCR_FILE%

%IMG7%magick -script %SCR_FILE% >%DATA_FILE%
if ERRORLEVEL 1 exit /B 1

cGroup /p0 /i%DATA_FILE% /n0 /o%DATA_FILE2% /u
cJoin  /p0 /i%DATA_FILE2%,%DATA_FILE% /o%DATA_FILE3% /k0 /K0 /n /c2

for /F "tokens=1-9 delims=," %%A in (%DATA_FILE3%) do (
  set COMP=%%A
  set BESTX=%%B
  set BESTY=%%C
  set W=%%D
  set H=%%E
  set X1=%%F
  set Y1=%%G
  set X2=%%H
  set Y2=%%I
)

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

set DODGY=1
if not "%BESTX%"=="%FirstX%" if not "%BESTX%"=="%LastX%" if not "%BESTY%"=="%FirstY%" if not "%BESTY%"=="%LastY%" set DODGY=0

echo %~n0: %COMP% %X% %Y% BESTX=%BESTX% BESTY=%BESTY% X1=%X1% Y1=%Y1% X2=%X2% Y2=%Y2%


call echoRestore

@endlocal & set abfDATAFILE=%DATA_FILE3%& set abfDODGY=%DODGY%

alignBFalpha.bat

The script uses utility programs cGroup.exe and cJoin.exe. I don't provide source or binaries of these. Here, they reduce the data file to contain only the line with the lowest RMSE score. The work could be done by sorting numerically, in reverse, and finding the first line.

rem Find x-y alignment of two same-size images %1 and %2 by brute force comparison,
rem where fully-transparent pixels are wildcard.
rem Uses process module rmsealpha.

@rem We find the position that scores the best RMSE.
@rem Fairly fast when WW*HH is small, or search space is small.
@rem
@rem Optional:
@rem   %2 is width of both
@rem   %3 is height of both
@rem   %5,%6 top-left to try
@rem   %7,%8 botton-right to try
@rem
@rem Returns name of a file containing CSV data.
@rem If best is at an extreme, probably dodgy.
@rem
@rem Updated:
@rem   22-August-2022 Upgraded for IM v7.
@rem

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

@setlocal enabledelayedexpansion

rem @call echoOffSave

call %PICTBAT%setInOut %1 abfa


set SCR_FILE=%sioCODE%.scr
set DATA_FILE=%sioCODE%_data.csv
set DATA_FILE2=%sioCODE%_data2.csv
set DATA_FILE3=%sioCODE%_data3.csv

set SRC1=%1
set SRC2=%2

set WW=%3
set HH=%4

if "%WW%"=="." set WW=
if "%HH%"=="." set HH=

set FIND_DIMS=0
if "%WW%"=="" set FIND_DIMS=1
if "%HH%"=="" set FIND_DIMS=1

if %FIND_DIMS%==1 for /F "usebackq" %%L in (`%IMG7%magick identify ^
  -format "WW=%%w\nHH=%%h" ^
  %SRC1%`) do set %%L

if "%WW%"=="" (
  echo %0: can't identify SRC1 [%SRC1%]
  exit /B 1
)

echo %SRC1% %SRC2% >%SCR_FILE%

set /A WWm1=%WW%-1
set /A HHm1=%HH%-1

set FirstX=%5
set FirstY=%6
set LastX=%7
set LastY=%8

if "%FirstX%"=="." set /A FirstX=
if "%FirstY%"=="." set /A FirstY=
if "%LastX%"=="." set /A LastX=
if "%LastY%"=="." set /A LastY=

if "%FirstX%"=="" set /A FirstX=-%WWm1%
if "%FirstY%"=="" set /A FirstY=-%HHm1%

if "%LastX%"=="" set /A LastX=%WWm1%
if "%LastY%"=="" set /A LastY=%HHm1%

echo %~n0: FirstX=%FirstX% FirstY=%FirstY% LastX=%LastX% LastY=%LastY%

set MIN_COMP=999

rem Optional -auto-level -auto-gamma  to each crop?
for /L %%y in (%FirstY%,1,%LastY%) do (

  if %%y GEQ 0 (
    set /A H=%HH%-%%y
    set /A Y1=%%y
    set /A Y2=0
  ) else (
    set /A H=%HH%+%%y
    set /A Y1=0
    set /A Y2=-%%y
  )

  for /L %%x in (%FirstX%,1,%LastX%) do (

    if %%x GEQ 0 (
      set /A W=%WW%-%%x
      set /A X1=%%x
      set /A X2=0
    ) else (
      set /A W=%WW%+%%x
      set /A X1=0
      set /A X2=-%%x
    )

    ( echo ^( -clone 0-1
      echo   ^( -clone 0 -crop !W!x!H!+!X1!+!Y1! +repage -auto-level ^)
      echo   ^( -clone 1 -crop !W!x!H!+!X2!+!Y2! +repage -auto-level ^)
      echo   -delete 0-1
      echo   -process 'rmsealpha just_score stdout'
      echo   -format ",%%x,%%y,!W!,!H!,!X1!,!Y1!,!X2!,!Y2!\n"
      echo   -delete 0
      echo   +write info:
      echo   -delete 0
      echo ^)
      echo -exit
    ) >>%SCR_FILE%
  )
)

%IM7DEV%magick @%SCR_FILE% >%DATA_FILE% 2^>^&1
if ERRORLEVEL 1 exit /B 1

:: Get the row with the smallest value in the first column.
cGroup  /i%DATA_FILE% /n0 /o%DATA_FILE2% /u
cJoin   /i%DATA_FILE2%,%DATA_FILE% /o%DATA_FILE3% /k0 /K0 /n /c2

for /F "tokens=1-9 delims=," %%A in (%DATA_FILE3%) do (
  set COMP=%%A
  set BESTX=%%B
  set BESTY=%%C
  set W=%%D
  set H=%%E
  set X1=%%F
  set Y1=%%G
  set X2=%%H
  set Y2=%%I
)

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

set DODGY=1
if not "%BESTX%"=="%FirstX%" if not "%BESTX%"=="%LastX%" if not "%BESTY%"=="%FirstY%" if not "%BESTY%"=="%LastY%" set DODGY=0

echo %~n0: %COMP% %X% %Y% X1=%X1% Y1=%Y1% X2=%X2% Y2=%Y2%


call echoRestore

endlocal & set abfaDATAFILE=%DATA_FILE3%& set abfaDODGY=%DODGY%

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

%IM7DEV%magick -version

Version: ImageMagick 7.1.0-20 Q32-HDRI x86_64 2021-12-29 https://imagemagick.org
Copyright: (C) 1999-2021 ImageMagick Studio LLC
License: https://imagemagick.org/script/license.php
Features: Cipher DPC HDRI Modules OpenMP(4.5) 
Delegates (built-in): bzlib cairo fontconfig fpx freetype jbig jng jpeg lcms ltdl lzma pangocairo png raqm rsvg tiff webp wmf x xml zip zlib
Compiler: gcc (11.2)

Page version v1.0 12-October-2015.

Page created 08-Sep-2022 00:37:00.

Copyright © 2022 Alan Gibson.