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.
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
%IMG7%magick ^
%PICTLIB%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
|
|
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.
%IMG7%magick ^ wr_src1.png ^ -distort DePolar 0 ^ ( +clone ) +append +repage ^ %DEP% wr_src1_dp.png |
|
%IMG7%magick ^ wr_src2.png ^ -distort DePolar 0 ^ %DEP% wr_src2_dp.png |
|
Aside: By distorting polar, we can see how much data we have lost:
%IMG7%magick ^ wr_src2_dp.png ^ -virtual-pixel Black ^ -distort Polar 0 ^ %DEP% wr_src2_dp_p.png |
|
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.
%IMG7%magick compare -metric RMSE -subimage-search wr_src1_dp.png wr_src2_dp.png NULL: cmd /c exit /B 0
1763.05 (0.0269024) @ 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.
%IMG7%magick ^ wr_src1.png ^ -set option:distort:scale 4 ^ -distort DePolar 0 ^ ( +clone ) +append +repage ^ -resize 100x25%% ^ %DEP% wr_src1_dp3.png |
|
%IMG7%magick ^ wr_src2.png ^ -set option:distort:scale 4 ^ -distort DePolar 0 ^ -resize 100x25%% ^ %DEP% wr_src2_dp3.png |
|
Search for the second within the first.
%IMG7%magick compare -metric RMSE -subimage-search wr_src1_dp3.png wr_src2_dp3.png NULL: cmd /c exit /B 0
790.513 (0.0120625) @ 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.
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.
%IMG7%magick ^ wr_src1.png ^ -rotate 99.9 ^ %DEP% wr_src1_rot.png |
|
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.
%IMG7%magick ^ wr_src1.png ^ -gravity Center ^ -rotate 99.9 +repage ^ -crop 200x200+0+0 +repage ^ %DEP% wr_src1_rotB.png |
|
%IMG7%magick ^ 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 |
|
We can compare these results in the usual way:
%IMG7%magick compare -metric RMSE wr_src1_rotB.png wr_src2_rotB.png NULL: cmd /c exit /B 0
6089.44 (0.0929189)
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.
%IMG7%magick ^ wr_src1.png ^ -gravity Center ^ -virtual-pixel Mirror ^ +distort SRT 1,99.9 +repage ^ -crop 200x200+0+0 +repage ^ %DEP% wr_src1_rotC.png |
|
%IMG7%magick ^ 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 |
|
The comparison is now:
%IMG7%magick compare -metric RMSE wr_src1_rotC.png wr_src2_rotC.png NULL: cmd /c exit /B 0
1720.84 (0.0262583)
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.
%IMG7%magick ^ wr_src1.png ^ -rotate 99.9 +repage ^ -gravity Center ^ -crop 100x100+0+0 +repage ^ %DEP% wr_src1_rotD.png |
|
%IMG7%magick ^ wr_src2.png ^ -gravity Center ^ -crop 100x100+0+0 +repage ^ %DEP% wr_src2_rotD.png |
|
The comparison is now:
%IMG7%magick compare -metric RMSE wr_src1_rotD.png wr_src2_rotD.png NULL: cmd /c exit /B 0
328.637 (0.00501468)
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.
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.0120633 wrSCORE_SUB=0.00501468 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:
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
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?
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:
For convenience, .bat scripts are also available in a single zip file. See Zipped BAT files.
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.
@rem 10-August-2022 for IM v7.
@rem
@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 (`%IMG7%magick 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% %IMG7%magick ^
%IN_A% ^
%sCROP% ^
%SUPER_UP% ^
-distort DePolar 0 ^
%SUPER_DN% ^
^( +clone ^) +append +repage ^
+depth ^
%TEMP_A%
if not exist %TEMP_B% %IMG7%magick 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 (`%IMG7%magick 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 (`%IMG7%magick identify ^
-format "DIM_2=%%[fx:int(%WW1%<%HH1%?%WW1%/2:%HH1%/2)]" ^
xc:`) do set %%L
for /F "usebackq" %%L in (`%IMG7%magick ^
%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 (`%IMG7%magick identify ^
-format "DIM_2=%%[fx:int(%WW1%<%HH1%?%WW1%/2:%HH1%/2)]" ^
xc:`) do set %%L
%IMG7%magick ^
%IN_A% ^
^( +clone -alpha Transparent ^
-shave 1x1 ^
-bordercolor None ^
-mattecolor #f00 -frame 1x1 ^
-channel A -evaluate Multiply 0.75 ^
^) ^
-compose Over -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:
%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)
To improve internet download speeds, some images may have been automatically converted (by ImageMagick, of course) from PNG or TIFF or MIFF 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 11-Aug-2022 01:06:43.
Copyright © 2022 Alan Gibson.