snibgo's ImageMagick pages

What rotation?

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

The problem could be solved by trial and error, comparing one image with rotations of the other. This page shows a more direct method that is faster, though more complex.

This is a sub-problem of the more general problem: "What areas in image A match what areas in image B?"

See also By FFT, what rotation?, which applies the method on this page to FFT results, finding rotation that is invariant to other factors.

Sample inputs

We crop a photograph, rotate it, and crop both these images to 300x200. The method requires that the images are the same size, and assumes that the centres of the images align, that is, the rotation is around the centre.

set wrDEBUG=1

set ANG=100
set DEP=-depth 16

%IM%convert ^
  \pictures\20140430\GOPR0166.JPG ^
  -crop 600x400+2164+2240 +repage ^
  -gravity Center ^
  ( -clone 0 ^
    -crop 300x200+0+0 +repage ^
    %DEP% -write wr_src1.png ^
    +delete ) ^
  -rotate 100 +repage ^
  -crop 300x200+0+0 +repage ^
  %DEP% wr_src2.png
wr_src1.pngjpg wr_src2.pngjpg

The method

We de-polar both images. This is like taking foam pipe insulation and unrolling it. The image centre is spread out to the top of the new image, while pixels at the maximum radius are squished together and become the bottom of the new image. The corners of each source image won't appear in the new image.

%IM%convert ^
  wr_src1.png ^
  -distort DePolar 0 ^
  ( +clone ) +append ^
  %DEP% wr_src1_dp.png
wr_src1_dp.pngjpg
%IM%convert ^
  wr_src2.png ^
  -distort DePolar 0 ^
  %DEP% wr_src2_dp.png
wr_src2_dp.pngjpg

Aside: By distorting polar, we can see how much data we have lost:

%IM%convert ^
  wr_src2_dp.png ^
  -virtual-pixel Black ^
  -distort Polar 0 ^
  %DEP% wr_src2_dp_p.png
wr_src2_dp_p.pngjpg

Depolar 0 has discarded all pixels outside the inscribed circle.

Search for the second depolar within the first. As the two images are the same height, this doesn't take a massive length of time.

%IM%compare -metric RMSE -subimage-search wr_src1_dp.png wr_src2_dp.png NULL: 

cmd /c exit /B 0
1763.2 (0.0269047) @ 83,0

The best match is found at x-offset 83 pixels. As the width of the images (before doubling) is 300 pixels, which represent 360°, the subimage is found at 83/300 * 360° = 99.6°.

Subimage searches return integer results, so the margin of error is 0.5 pixels in either direction, so we know the true result is really between 82.5/300 * 360° = 99.0° and 83.5/300 * 360° = 100.2°.

We can supersample to increase quality (by reducing the squishing at the bottom). Multiplying by π (3.141..) would keep the pixels at the edge of the circle at the same scale. For simplicity, we scale by 4. Supersampling also increases precision of the result.

%IM%convert ^
  wr_src1.png ^
  -set option:distort:scale 4 ^
  -distort DePolar 0 ^
  ( +clone ) +append ^
  -resize 100x25%% ^
  %DEP% wr_src1_dp3.png
wr_src1_dp3.pngjpg
%IM%convert ^
  wr_src2.png ^
  -set option:distort:scale 4 ^
  -distort DePolar 0 ^
  -resize 100x25%% ^
  %DEP% wr_src2_dp3.png
wr_src2_dp3.pngjpg

Search for the second within the first.

%IM%compare -metric RMSE -subimage-search wr_src1_dp3.png wr_src2_dp3.png NULL: 

cmd /c exit /B 0
790.656 (0.0120646) @ 333,0

This has improved the RMSE score. The x-offset is 333, which is 99.9° (between 99.75° and 100.05°.)

Supersampling has a cost: there are four times as many image-by-image comparisons, and each image comparison has four times as many pixel-by-pixels comparisons, so the time is increased by a factor of 16. We could crop the supersampled large image to correspond to the first solution, plus of minus the margin of error.

Check the result

The score obtained from the depolar images isn't usually important. More useful for onward processing would be a score of the source images, after rotating the first.

If we rotate the first image by 99.9°, it should match the second image.

%IM%convert ^
  wr_src1.png ^
  -rotate 99.9 ^
  %DEP% wr_src1_rot.png
wr_src1_rot.pngjpg wr_src2.pngjpg

The match can be seen more readily if we crop both images to the same degree. We crop the second image by applying the reverse rotation and then the forward rotation, following each rotation by a crop. If the sources were square, this would result in identical shapes.

%IM%convert ^
  wr_src1.png ^
  -gravity Center ^
  -rotate 99.9 +repage ^
  -crop 200x200+0+0 +repage ^
  %DEP% wr_src1_rotB.png
wr_src1_rotB.pngjpg
%IM%convert ^
  wr_src2.png ^
  -gravity Center ^
  -rotate -99.9 +repage ^
  -crop 200x200+0+0 +repage ^
  -rotate 99.9 +repage ^
  -crop 200x200+0+0 +repage ^
  %DEP% wr_src2_rotB.png
wr_src2_rotB.pngjpg

We can compare these results in the usual way:

%IM%compare -metric RMSE wr_src1_rotB.png wr_src2_rotB.png NULL: 

cmd /c exit /B 0
6089.66 (0.0929222)

This score is slightly worse (higher) than the score reported for the depolar images above. The depolar version gives a greater weight to the pixels near the centre of the image. Conversly, this comparison is biased by the white triangles, which are virtual pixels. A fairer comparison may come from using mirror for virtual-pixels, which requires us to use "-distort SRT" for the rotation.

%IM%convert ^
  wr_src1.png ^
  -gravity Center ^
  -virtual-pixel Mirror ^
  +distort SRT 1,99.9 +repage ^
  -crop 200x200+0+0 +repage ^
  %DEP% wr_src1_rotC.png
wr_src1_rotC.pngjpg
%IM%convert ^
  wr_src2.png ^
  -gravity Center ^
  -rotate -99.9 +repage ^
  -crop 200x200+0+0 +repage ^
  -virtual-pixel Mirror ^
  +distort SRT 1,99.9 +repage ^
  -crop 200x200+0+0 +repage ^
  %DEP% wr_src2_rotC.png
wr_src2_rotC.pngjpg

The comparison is now:

%IM%compare -metric RMSE wr_src1_rotC.png wr_src2_rotC.png NULL: 

cmd /c exit /B 0
1721.56 (0.0262693)

Yet another comparison is to take a 50% crop from the centre of each image. This entirely avoids virtual-pixel problems, for all angles, which is particularly important if we need to rank comparisons for various image pairs.

%IM%convert ^
  wr_src1.png ^
  -rotate 99.9 +repage ^
  -gravity Center ^
  -crop 100x100+0+0 +repage ^
  %DEP% wr_src1_rotD.png
wr_src1_rotD.pngjpg
%IM%convert ^
  wr_src2.png ^
  -gravity Center ^
  -crop 100x100+0+0 +repage ^
  %DEP% wr_src2_rotD.png
wr_src2_rotD.pngjpg

The comparison is now:

%IM%compare -metric RMSE wr_src1_rotD.png wr_src2_rotD.png NULL: 

cmd /c exit /B 0
328.579 (0.0050138)

On the negative side, this method of comparison clearly ignores much data from both images. On the plus side, it ignores data that occurs in one image but not the other. It is, for some purposes, the fairest comparison. If requested, the script returns this value as wrSCORE_SUB.

Using the script

For convenience, we put all this in a script whatRot.bat, which we can use like this:

call %PICTBAT%whatRot wr_src1.png wr_src2.png
if ERRORLEVEL 1 exit /B 1

echo wrANGLE=%wrANGLE% wrANGLE_ERR=%wrANGLE_ERR% wrSCORE=%wrSCORE% wrSCORE_SUB=%wrSCORE_SUB% wrDODGY=%wrDODGY% 
wrANGLE=99.9 wrANGLE_ERR=0.3 wrSCORE=0.0120646 wrSCORE_SUB=0.0050138 wrDODGY=0 

If we don't want supersampling, set wrDO_SUPER=0 before calling the script. If this environment variable is not set, small images will be supersampled.

The true angle lies between wrANGLE - wrANGLE_ERR/2 and wrANGLE + wrANGLE_ERR/2.

If wrDODGY is returned as 1, this would mean the best scale found was either the specified minimum or maximum, so the actual best scale is probably outside these limits.

The value of wrSCORE is the comparison metric returned by the subimage-search of the unrolled images.

The value of wrSCORE_SUB is the fairer comparison between the first image rotated by the calculated amount and the second image, cropped to a square half the size of the smallest dimension. Calculating this takes extra effort.

Instead of using IM's compare directly, whatRot.bat calls the script srchImg.bat which does a series of searches at different resolutions. This is more complex but much quicker. In theory, it might give the wrong result: the best result found at a low resolution might not be the best at full resolution. I've never see this happen with ordinary photos or video frames. For details of srchImg.bat, see the page Searching an image.

The debugging image shows:

wr_wr_src1_wr_src2_dbg.pngjpg

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

call %PICTBAT%whatRot wr_src1.png wr_src1.png
if ERRORLEVEL 1 exit /B 1

echo wrANGLE=%wrANGLE% wrANGLE_ERR=%wrANGLE_ERR% wrSCORE=%wrSCORE% wrSCORE_SUB=%wrSCORE_SUB% wrDODGY=%wrDODGY% 
wrANGLE=0 wrANGLE_ERR=0.3 wrSCORE=0 wrSCORE_SUB=0 wrDODGY=0 

False results

As described above, the script srchImg.bat does subimage-searches through a series of image pairs, successively reducing the subsampling (by resize), using each result to make a crop for the next search. In theory it can latch onto the wrong result at a small scale and this can't be corrected at a larger scale, so the final result will be wrong. This leads to whatRot.bat returning a wrong angle.

I've never seen this happen for ordinary photographs or video frames.

However, it does happen for FFT spectrum images, because these contain very little low-frequency data so the initial shrinking to a small size can remove all useful data.

In such situations, siDIV_DIM can be used. For the purpose of deciding the degree of the first resizing, the minimum size is reduced by a factor of siDIV_DIM. For FFT spectrums of 250x250 images, I find that siDIV_DIM=40 works fine. For 7000x5000 images, siDIV_DIM=50 works fine. I generally use siDIV_DIM=100 to be on the safe side. Using a value larger than necessary will decrease performance but increase the probability of finding the correct answer. (I want to always find the correct answer.)

In addition, the whatRot.bat script will crop both inputs to wrCROP_PC percent before unrolling. When the inputs are FFT spectrums, the effect is to remove high-frequency data from the search. wrCROP_PC=25 seems to work well.

See the page By FFT, what rotation?

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.

whatRot.bat

rem Given same-size images %1 and %2,
rem finds angle of rotation for %1 to best match %2, and a score.
@rem
@rem Also uses:
@rem   wrDO_SUPER      if ==0, no supersampling will be done.
@rem   wrDO_SCORE_SUB  if ==0, wrSCORE_SUB will not be found.
@rem   wrMETRIC        default RMSE
@rem   wrDEBUG         if 1, creates images for debugging
@rem   wrDELTEMP       if not 0, will remove temporary file.
@rem   wrCROP_PC       percentage for central crops before unrolling [100].
@rem
@rem Returns:
@rem   wrANGLE     (degrees) rotate first image by this to match second.
@rem   wrANGLE_ERR (degrees) margin of error
@rem   wrSCORE     (0.0 to 1.0, more or less).
@rem   wrSCORE_SUB (0.0 to 1.0, more or less).
@rem   wrDODGY     0 or 1. 1 means the result is unreliable.
@rem
@rem Updated:
@rem   19-August-2016 Added wrCROP_PC.

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

@setlocal enabledelayedexpansion

@call echoOffSave


if "%wrCROP_PC%"=="" set wrCROP_PC=100

set TMPEXT=.miff

call %PICTBAT%setInOut %1 wr
set IN_A=%INFILE%
set TEMP_A=%TEMP%\%~n1_wr_x2%TMPEXT%

call %PICTBAT%setInOut %2 wr
set IN_B=%INFILE%
set TEMP_B=%TEMP%\%~n2_wr%TMPEXT%
if %IN_B%==%IN_A% set TEMP_B=%TEMP%\%~n2_B_wr%TMPEXT%

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

if not "%wrDELTEMP%"=="0" (
  del %TEMP_A% 2>nul
  del %TEMP_B% 2>nul
)

if "%wrMETRIC%"=="" set wrMETRIC=RMSE

for /F "usebackq" %%L in (`%IM%identify ^
  -format "WW1=%%[fx:w*%wrCROP_PC%/100]\nHH1=%%[fx:h*%wrCROP_PC%/100]\nIS_SMALL=%%[fx:max(w,h)*%wrCROP_PC%/100>1000?0:1]" ^
  %IN_A%`) do set %%L

if "%wrDO_SCORE_SUB%"=="" set wrDO_SCORE_SUB=%IS_SMALL%

if "%wrDO_SUPER%"=="" set wrDO_SUPER=%IS_SMALL%

if %wrDO_SUPER%==1 (
  set SUPER_UP=-set option:distort:scale 4
  set SUPER_DN=-resize 100x25%%
  set SUPER_FACT=4
) else (
  set SUPER_UP=
  set SUPER_DN=
  set SUPER_FACT=1
)

echo %0: SUPER_FACT=%SUPER_FACT% WW1=%WW1% HH1=%HH1%


if %wrCROP_PC%==100 (
  set sCROP=
) else (
  set sCROP=-gravity center -crop %wrCROP_PC%%%x%wrCROP_PC%%%+0+0 +repage
)

if not exist %TEMP_A% %IM%convert ^
  %IN_A% ^
  %sCROP% ^
  %SUPER_UP% ^
  -distort DePolar 0 ^
  %SUPER_DN% ^
  ^( +clone ^) +append ^
  +depth ^
  %TEMP_A%


if not exist %TEMP_B% %IM%convert ^
  %IN_B% ^
  %sCROP% ^
  %SUPER_UP% ^
  -distort DePolar 0 ^
  %SUPER_DN% ^
  +depth ^
  %TEMP_B%


call %PICTBAT%srchImg %TEMP_A% %TEMP_B%
if ERRORLEVEL 1 exit /B 1

set DODGY=0

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

if %ANGLE%==360 set ANGLE=0

if %wrDO_SCORE_SUB%==1 (

  for /F "usebackq" %%L in (`%IM%identify ^
    -format "DIM_2=%%[fx:int(%WW1%<%HH1%?%WW1%/2:%HH1%/2)]" ^
    xc:`) do set %%L

  for /F "usebackq" %%L in (`%IM%convert ^
    %IN_A% ^
    -rotate %ANGLE% +repage ^
    %IN_B% ^
    -gravity Center ^
    -crop !DIM_2!x!DIM_2!+0+0 +repage ^
    -metric %wrMETRIC% -format "ScoreSub=%%[distortion]" -compare ^
    info:`) do set %%L
)


if "%wrDEBUG%"=="1" (

  for /F "usebackq" %%L in (`%IM%identify ^
    -format "DIM_2=%%[fx:int(%WW1%<%HH1%?%WW1%/2:%HH1%/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 1,%ANGLE% ^
  ^( %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 !DIM_2!x!DIM_2!+0+0 ^
     -alpha Transparent ^
     -shave 1x1 ^
     -bordercolor None ^
     -mattecolor #ff0 -frame 1x1 ^
     -channel A -evaluate Multiply 0.75 ^
  ^) ^
  -layers merge ^
  +repage ^
  %DEBUG_FILE%
)

if not "%wrDELTEMP%"=="0" (
  del %TEMP_A% 2>nul
  del %TEMP_B% 2>nul
)

call echoRestore

endlocal & set wrANGLE=%ANGLE%& set wrANGLE_ERR=%ANGLE_ERR%& set wrSCORE=%siCOMP_FLT%& set wrSCORE_SUB=%ScoreSub%& set wrDODGY=%DODGY%

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
License: http://www.imagemagick.org/script/license.php
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

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


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 15-May-2017 19:53:44.

Copyright © 2017 Alan Gibson.