﻿

# Alignment by brute force

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

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.

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

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

## 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

`0 `

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

`type %abfaDATAFILE% `
`0.707107,-1,0,2,2,0,0,1,0`

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.

## 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.

@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 (`%IM%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%

rem type %SCR_FILE%

%IML%convert @%SCR_FILE% NULL: >%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.

@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 (`%IM%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 ^)
) >>%SCR_FILE%
)
)

%IMDEV%convert @%SCR_FILE% NULL: >%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

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

`%IM%identify -version`
```Version: ImageMagick 6.9.5-3 Q16 x86 2016-07-22 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2015 ImageMagick Studio LLC
Visual C++: 180040629
Features: Cipher DPC Modules OpenMP
Delegates (built-in): bzlib cairo flif freetype jng jp2 jpeg lcms lqr openexr pangocairo png ps rsvg tiff webp xml zlib```
`%IMDEV%identify -version`
```Version: ImageMagick 6.9.3-7 Q32 x86_64 2017-12-23 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2016 ImageMagick Studio LLC
Features: Cipher DPC HDRI Modules OpenMP
Delegates (built-in): bzlib cairo fftw fontconfig freetype fpx jbig jng jpeg lcms ltdl lzma pangocairo png rsvg tiff webp wmf x xml zlib```

To improve internet download speeds, some images may have been automatically converted (by ImageMagick, of course) from PNG to JPG.

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

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 12-October-2015.

Page created 28-Dec-2017 18:25:20.