snibgo's ImageMagick pages

What rotation and scale?

Given one image that could be a rotation and scale of another image, what is the best rotation angle and scale factor?

Sample inputs

We crop a photograph, and make four variations.

set wrsDEBUG=1

set ANG=100
set FACT1=130
set FACT2=70
set DEP=+depth

%IM%convert ^
  \pictures\20140430\GOPR0166.JPG ^
  -crop 700x500+2114+2190 +repage ^
  -gravity Center ^
  ( -clone 0 ^
    -crop 300x200+0+0 +repage ^
    %DEP% -write wrs_src1.png ^
    +delete ^
  ) ^
  ( -clone 0 ^
    -rotate %ANG% +repage ^
    -resize %FACT1%%% +repage ^
    -crop 300x200+0+0 +repage ^
    %DEP% -write wrs_src2.png ^
    +delete ^
  ) ^
  ( -clone 0 ^
    -rotate %ANG% +repage ^
    -resize %FACT2%%% +repage ^
    -crop 300x200+0+0 +repage ^
    %DEP% -write wrs_src3.png ^
    +delete ^
  ) ^
  ( -clone 0 ^
    -rotate -%ANG% +repage ^
    -resize %FACT1%%% +repage ^
    -crop 300x200+0+0 +repage ^
    %DEP% -write wrs_src4.png ^
    +delete ^
  ) ^
  ( -clone 0 ^
    -rotate -%ANG% +repage ^
    -resize %FACT2%%% +repage ^
    -crop 300x200+0+0 +repage ^
    %DEP% -write wrs_src5.png ^
    +delete ^
  ) ^
  NULL:
wrs_src1.pngjpg

From the above, we effectively make four copies at two different
scales and two different rotations (images #2, #3, #4 and #5):

wrs_src2.pngjpg wrs_src3.pngjpg
wrs_src4.pngjpg wrs_src5.pngjpg

If the method works, it should find both the rotation angle and scale factor for all four images.

The method

See the pages What rotation? and What scale?, which are building blocks for this page.

If one image is thought to be both a rotation and a scale of another, we could iterate between two techniques. Find the rotation that seems to be best, then a scaling of the rotation that seems to be best, and keep iterating until the solution stabilises. The trouble is, we are searching in a two-dimensional space (the dimensions of rotation and scale) and we may find a solution that is optimal locally but not globally. We may be misled into finding a solution that isn't the best posible solution.

Hmmm... searching a 2-dimensional space. ImageMagick can do that, with "-subimage-search". All we need do is create a small image that is 360° wide and one scale factor high, and a larger image that is 720° wide and a greater number of scale factors high. A subimage search will find the rotation and scale of the globally best solution.

We create each image by making a depolar (as in What rotation?), and scaling this to a single row. Each pixel represents the average of the radial lines from the edge to the image centre. For the large image we repeat this at different scales (as in What scale?), then it is cloned and appended so it represents 720°.

IM's subimage-search locates one 2-D image within another, returning a 2-D coordinate. In normal usage, the two dimensions are the x- and y-coordinates of source images. This script transforms images so that the two dimensions are of scale and rotation.

Using the script

call %PICTBAT%whatRotScale wrs_src1.png wrs_src2.png
if ERRORLEVEL 1 exit /B 1

echo ANGLE=%wrsANGLE% ANGLE_ERR=%wrsANGLE_ERR% SCALE=%wrsSCALE% FACT=%wrsFACT% SCORE_SUB=%wrsSCORE_SUB% DODGY=%wrsDODGY% 
ANGLE=99.9 ANGLE_ERR=0.3 SCALE=1.30036546 FACT=1.01104669 SCORE_SUB=0.0339328 DODGY=0 

These are the two images that were compared:

Multi-scale version of the first image,
with a black line showing where the second image was found,
scaled down for the web:

%IM%convert ^
  %TEMP%\wrs_src1_wrs_0.5_1.5_100.png ^
  -resize "300x^!" ^
  -draw "rectangle 42,86 191,86" ^
  wrs_comp1.png
wrs_comp1.pngjpg

The second image, scaled down for the web,
scaled up vertically so we can see it:

%IM%convert ^
  %TEMP%\wrs_src2_wrs.png ^
  -resize "150x^!" ^
  -scale "x50^!" ^
  wrs_comp2.png
wrs_comp2.pngjpg

Image #3:

call %PICTBAT%whatRotScale wrs_src1.png wrs_src3.png
if ERRORLEVEL 1 exit /B 1

echo ANGLE=%wrsANGLE% ANGLE_ERR=%wrsANGLE_ERR% SCALE=%wrsSCALE% FACT=%wrsFACT% SCORE_SUB=%wrsSCORE_SUB% DODGY=%wrsDODGY% 
ANGLE=99.9 ANGLE_ERR=0.3 SCALE=0.784494101 FACT=1.01104669 SCORE_SUB=0.117731 DODGY=0 

Image #4:

call %PICTBAT%whatRotScale wrs_src1.png wrs_src4.png
if ERRORLEVEL 1 exit /B 1

echo ANGLE=%wrsANGLE% ANGLE_ERR=%wrsANGLE_ERR% SCALE=%wrsSCALE% FACT=%wrsFACT% SCORE_SUB=%wrsSCORE_SUB% DODGY=%wrsDODGY% 
ANGLE=260.1 ANGLE_ERR=0.3 SCALE=1.30036546 FACT=1.01104669 SCORE_SUB=0.0345223 DODGY=0 

Image #5:

call %PICTBAT%whatRotScale wrs_src1.png wrs_src5.png
if ERRORLEVEL 1 exit /B 1

echo ANGLE=%wrsANGLE% ANGLE_ERR=%wrsANGLE_ERR% SCALE=%wrsSCALE% FACT=%wrsFACT% SCORE_SUB=%wrsSCORE_SUB% DODGY=%wrsDODGY% 

set ANGLE_5=%wrsANGLE%
set SCALE_5=%wrsSCALE%
ANGLE=259.8 ANGLE_ERR=0.3 SCALE=0.767444996 FACT=1.01104669 SCORE_SUB=0.114684 DODGY=0 

The results are good, but the scales for images #3 and #5 are about 10% out, which isn't great. This error is well beyond the FACT value. We can try for greater precision by calling the script again with smaller gaps between the scale limits.

for /F "usebackq" %%L ^
in (`%IM%identify ^
  -format "MIN=%%[fx:%SCALE_5%/1.2]\nMAX=%%[fx:%SCALE_5%*1.2]" ^
  xc:`) ^
do set %%L

call %PICTBAT%whatRotScale wrs_src1.png wrs_src5.png %MIN% %MAX%
if ERRORLEVEL 1 exit /B 1

echo ANGLE=%wrsANGLE% ANGLE_ERR=%wrsANGLE_ERR% SCALE=%wrsSCALE% FACT=%wrsFACT% SCORE_SUB=%wrsSCORE_SUB% DODGY=%wrsDODGY% 
ANGLE=259.8 ANGLE_ERR=0.3 SCALE=0.761868348 FACT=1.0036531 SCORE_SUB=0.113469 DODGY=0 

This has slightly improved the result.

This script, whatRotScale.bat, found the scale from the average of radial lines, which naturally smears most data. We can rotate wrs_src1.png by the angle it found (ANGLE_5), and use the greater accuracy of whatScale.bat. After rotating, we crop by 50% to ensure we get no virtual pixels.

%IM%convert wrs_src1.png -distort SRT 1,%ANGLE_5% -gravity center -crop 50%%x50%%+0+0 +repage wrs_d1.png
%IM%convert wrs_src5.png -gravity center -crop 50%%x50%%+0+0 +repage wrs_d5.png

call %PICTBAT%whatScale wrs_d1.png wrs_d5.png

echo SCALE=%wsSCALE% FACT=%wsFACT% SCORE_SUB=%wsSCORE_SUB% DODGY=%wsDODGY% 
SCALE=0.702874139 FACT=1.01104669 SCORE_SUB=0.055862 DODGY=0 

That is better. The scale found is within 1% of the true result, and within the limit stated by FACT.

The debugging images show:

wrs_wrs_src1_wrs_src2_dbg.pngjpg wrs_wrs_src1_wrs_src3_dbg.pngjpg wrs_wrs_src1_wrs_src4_dbg.pngjpg wrs_wrs_src1_wrs_src5_dbg.pngjpg

We can also test the identity case, ie match an image against itself:

call %PICTBAT%whatRotScale wrs_src1.png wrs_src1.png
if ERRORLEVEL 1 exit /B 1

echo ANGLE=%wrsANGLE% ANGLE_ERR=%wrsANGLE_ERR% SCALE=%wrsSCALE% FACT=%wrsFACT% SCORE_SUB=%wrsSCORE_SUB% DODGY=%wrsDODGY% 
ANGLE=0 ANGLE_ERR=0.3 SCALE=0.998978955 FACT=1.01104669 SCORE_SUB=0.00585913 DODGY=0 

Conclusion

The script below, whatRotScale.bat, returns the aproximate scale and rotation of one image with respect to another. The angle is accurate, but the scale is less accurate. Greater accuracy may be obtained by then using whatScale.bat (see What scale?).

The script works for non-square images. However, it ignores all pixels outside the central inscribed circle.

The search might work faster if it used Searching an image. Watch this space.

Acknowledgements

This page was inspired by Grayscale Template-Matching Invariant to Rotation, Scale, Translation, Brightness and Contrast (pdf), by Hae Yong Kim and Sidnei Alves de Araújo.

See also:

Scripts

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

whatRotScale.bat

@rem Given same-size images %1 and %2,
@rem finds scale S and rotation angle R in "-distort SRT S,R" for %1 to best match %2, and a score.

@rem Parameters:
@rem   %3 min scale (default 0.5) OR "again" to iterate from previous run.
@rem   %4 max scale (default 1.5)
@rem   %5 number of scale steps (default 100)
@rem   %6
@rem   %7
@rem
@rem Also uses:
@rem   wrsDO_SCORE_SUB  if 0, wrsSCORE_SUB will not be found.
@rem   wrsMETRIC        default RMSE
@rem   wrsDO_SUPER      if 0, no supersampling will be done.
@rem   wrsDEBUG         if 1, creates images for debugging
@rem
@rem Returns:
@rem   wrsANGLE     (degrees)
@rem   wrsSCALE
@rem   wrsFACT      error margin, multiple of wrsSCALE
@rem   wrsSCORE     (0.0 to 1.0, more or less).
@rem   wrsSCORE_SUB (0.0 to 1.0, more or less).

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

@setlocal

@call echoOffSave


if "%wrsMETRIC%"=="" set wrsMETRIC=RMSE

if "%wrsDO_SCORE_SUB%"=="" set wrsDO_SCORE_SUB=1

set wrsMIN_SCALE=%3
if "%wrsMIN_SCALE%"=="." set wrsMIN_SCALE=
if "%wrsMIN_SCALE%"=="" set wrsMIN_SCALE=0.5

set wrsMAX_SCALE=%4
if "%wrsMAX_SCALE%"=="." set wrsMAX_SCALE=
if "%wrsMAX_SCALE%"=="" set wrsMAX_SCALE=1.5

set wrsnSTEPS=%5
if "%wrsnSTEPS%"=="." set wrsnSTEPS=
if "%wrsnSTEPS%"=="" set wrsnSTEPS=100

set wrsOFFS_X=%6
if "%wrsOFFS_X%"=="." set wrsOFFS_X=
if "%wrsOFFS_X%"=="" set wrsOFFS_X=0

set wrsOFFS_Y=%7
if "%wrsOFFS_Y%"=="." set wrsOFFS_Y=
if "%wrsOFFS_Y%"=="" set wrsOFFS_Y=0

if "%wrsDO_SUPER%"=="" set wrsDO_SUPER=1

set wrsDEPTH=+depth


if /I "%wrsMIN_SCALE%" EQU "again" (
  for /F "usebackq" %%L in (`%IM%identify ^
    -precision 9 ^
    -format "wrsMIN_SCALE=%%[fx:%wrsSCALE%/pow(%wrsFACT%,10)]\nwrsMAX_SCALE=%%[fx:%wrsSCALE%*pow(%wrsFACT%,10)]" ^
    xc:`) do set %%L
)

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

call %PICTBAT%setInOut %1 wrs
set IN_A=%INFILE%
set TEMP_A_BASE=%TEMP%\%~n1_wrs
rem FIXME: also offsets
set TEMP_A=%TEMP%\%~n1_wrs_%wrsMIN_SCALE%_%wrsMAX_SCALE%_%wrsnSTEPS%%EXT%

call %PICTBAT%setInOut %2 wrs
set IN_B=%INFILE%
set TEMP_B=%TEMP%\%~n2_wrs%EXT%
if %IN_B%==%IN_A% set TEMP_B=%TEMP%\%~n2_B_wrs%EXT%

set DEBUG_FILE=wrs_%~n1_%~n2_dbg%EXT%


for /F "usebackq" %%L ^
in (`%IM%convert -ping  %IN_A% ^
    -format "WW1=%%w\nHH1=%%h\nWW1_2=%%[fx:w/2]\nHH1_2=%%[fx:h/2]\nSRT_OFFS_X=%%[fx:w/2+(%wrsOFFS_X%)]\nSRT_OFFS_Y=%%[fx:h/2+(%wrsOFFS_Y%)]" ^
    INFO:`) ^
do set %%L

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

for /F "usebackq" %%L ^
in (`%IM%identify ^
    -precision 9 ^
    -format "FACT=%%[fx:pow(%wrsMAX_SCALE%/%wrsMIN_SCALE%,1/%wrsnSTEPS%)]" ^
    xc:`) ^
do set %%L


if %wrsDO_SUPER%==1 (
  set SUPER_UP=-set option:distort:scale 4
  set SUPER_FACT=4
) else (
  set SUPER_UP=
  set SUPER_FACT=1
)

if exist %TEMP_A% goto skipTempA

set SCALE=%wrsMIN_SCALE%
set NAMES_A=
for /L %%i in (1,1,%wrsnSTEPS%) do (
  @rem Maybe we should crop all scales so we never have virtual pixels.

  %IM%convert ^
  %IN_A% ^
  -distort SRT %WW1_2%,%HH1_2%,!SCALE!,0,%SRT_OFFS_X%,%SRT_OFFS_Y% ^
  %SUPER_UP% ^
  -distort DePolar 0 ^
  -scale "x1^!" ^
  ^( +clone ^) +append ^
  %wrsDEPTH% ^
  %TEMP_A_BASE%_%%i%EXT%

  set NAMES_A=!NAMES_A! %TEMP_A_BASE%_%%i%EXT%

  for /F "usebackq" %%L in (`%IM%identify ^
    -precision 9 -format "SCALE=%%[fx:!SCALE!*%FACT%]" ^
    xc:`) do set %%L
)

%IM%convert %NAMES_A% -append %TEMP_A%

:skipTempA

%IM%identify %TEMP_A%


if not exist %TEMP_B% %IM%convert ^
  %IN_B% ^
  %SUPER_UP% ^
  -distort DePolar 0 ^
  -scale "x1^!" ^
  %wrDEPTH% %TEMP_B%


for /F "usebackq tokens=1-4 delims=()@, " %%R ^
in (`%IM%compare ^
  %TEMP_A% %TEMP_B% ^
  -similarity-threshold 0 -dissimilarity-threshold 1 -subimage-search ^
  -metric %wrsMETRIC% -subimage-search ^
  NULL: 2^>^&1`) ^
do (
  set COMP_INT=%%R
  set COMP_FLT=%%S
  set COMP_XW=%%T
  set COMP_YW=%%U
)

if "%COMP_FLT%" GTR "9" exit /B 1

echo COMP_FLT=%COMP_FLT% COMP_XW=%COMP_XW% COMP_YW=%COMP_YW%

set DODGY=0
if %COMP_YW% EQU 0 set DODGY=1
if %COMP_YW% GEQ %wrsnSTEPS% set DODGY=1

for /F "usebackq" %%L ^
in (`%IM%identify ^
  -precision 9 ^
  -format "ANGLE=%%[fx:%COMP_XW%*360/(%SUPER_FACT%*%WW1%)]\nANGLE_ERR=%%[fx:360/(%SUPER_FACT%*%WW1%)]" ^
  xc:`) ^
do set %%L

rem What is the magnification here?
set SCALE=%wrsMIN_SCALE%
@for /L %%i in (1,1,%COMP_YW%) do @for /F "usebackq" %%L in (`%IM%identify ^
    -precision 9 -format "SCALE=%%[fx:!SCALE!*%FACT%]" ^
    xc:`) do @set %%L


echo SCALE=%SCALE%


rem Cleanup: remove most temporary files.
@for /L %%i in (1,1,%wrsnSTEPS%) do @del %TEMP_A_BASE%_%%i%EXT% 2>nul


if %wrsDO_SCORE_SUB%==1 (
  rem Test result.

  for /F "usebackq" %%L in (`%IM%identify ^
    -format "cropX=%%[fx:int(min(%WW1%,%WW1%*%SCALE%)/2)]\ncropY=%%[fx:int(min(%HH1%,%HH1%*%SCALE%)/2)]" ^
    xc:`) do set %%L

  for /F "usebackq" %%L in (`%IM%convert ^
    %IN_A% ^
    -distort SRT "%WW1_2%,%HH1_2%,%SCALE%,%ANGLE%,%SRT_OFFS_X%,%SRT_OFFS_Y%" ^
    %IN_B% ^
    -gravity Center ^
    -crop !cropX!x!cropY!+0+0 +repage ^
    -write r.png ^
    -metric %wrsMETRIC% -format "ScoreSub=%%[distortion]" -compare ^
    info:`) do set %%L
)


if "%wrsDEBUG%"=="1" (

  for /F "usebackq" %%L in (`%IM%identify ^
    -format "cropX=%%[fx:int(min(%WW1%,%WW1%*%SCALE%)/2)]\ncropY=%%[fx:int(min(%HH1%,%HH1%*%SCALE%)/2)]" ^
    xc:`) do set %%L

  %IM%convert ^
  %IN_A% ^
  ^( +clone -alpha Transparent ^
     -shave 1x1 ^
     -bordercolor None ^
     -mattecolor #f00 -frame 1x1 ^
     -channel A -evaluate Multiply 0.75 ^
  ^) ^
  -composite ^
  -virtual-pixel None ^
  +distort SRT "%WW1_2%,%HH1_2%,%SCALE%,%ANGLE%,%SRT_OFFS_X%,%SRT_OFFS_Y%" ^
  ^( %IN_B% ^
    ^( +clone -alpha Transparent ^
       -shave 1x1 ^
       -bordercolor None ^
       -mattecolor #0f0 -frame 1x1 ^
       -channel A -evaluate Multiply 0.75 ^
    ^) ^
    -composite ^
  ^) ^
  ^( -clone -1 ^
     -gravity Center ^
     -crop !cropX!x!cropY!+0+0 ^
     -alpha Transparent ^
     -shave 1x1 ^
     -bordercolor None ^
     -mattecolor #ff0 -frame 1x1 ^
     -channel A -evaluate Multiply 0.75 ^
  ^) ^
  -layers merge ^
  +repage ^
  %DEBUG_FILE%
)


call echoRestore

endlocal & set wrsANGLE=%ANGLE%& set wrsANGLE_ERR=%ANGLE_ERR%& set wrsSCALE=%SCALE%& set wrsFACT=%FACT%& set wrsSCORE=%COMP_FLT%& set wrsSCORE_SUB=%ScoreSub%& set wrsDODGY=%DODGY%

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

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 whatrotscale.h1. To re-create this web page, run "procH1 whatrotscale".


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 13-May-2014.

Page created 03-Jun-2016 13:37:26.

Copyright © 2016 Alan Gibson.