Searching an image aggressively

Searching quickly for the location of a small sub-image inside a much larger image.

The method
Example usage
Dissmilarity threshold
Real photographs
Performance comparisons
Rotations
Conclusion
Cleanup
Scripts

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

This page follows from Searching an image, which showed a fast method of searching. The method shown on this page can be a hundred times faster.

The method

The goal is usually to find the best match of the small image (the "subimage") within the large image.

As described on the Searching an image page, the script srchImg.bat shrinks both images so the smaller is between 10 and 20 pixels on the smallest dimension. (If the script shrinks much further than this, it finds false matches.) So if the small image is 40x40 pixels, it shrinks both images by a factor of 2 in each dimension, which doesn't help very much if the large image has tens of millions of pixels.

So, we devise a new method for such cases.

The script srchImgAg.bat always performs two types of searches. The first search finds the most likely location(s) of the subimage. At each likely location, it then searches for the subimage within suitable crops of the large image.

For the first search, it aggressively resizes the input images: the subimage is shrunk to one pixel, and the large image is shrunk by the same proportion. It then searches for that single pixel in the shrunken large image.

IM's "-subimage-search" is very slow even when the subimage is only a single pixel, so the script doesn't use it. Instead, it scales the pixel up to the larger size, and finds the difference between the two images, and negates. In the result, the lightest is at the location of the closest match. (A white pixel would be an exact match.)

Multiplying this location by the size of the subimage should give the location within the full-size image, but the result is imprecise, by plus or minus one pixel in the shrunken image, or plus or minus the smaller image's dimensions in the full-size image. So the script crops an area three times the width and three times the height of the small image from the large image, and searches that for the small image.

We are only searching a crop, but that can still be large so a simple "-subimage-search" could be slow. So, for that search it uses srchImg.bat, which is fast when the subimage is one-third the dimension of the large image.

Thus, srchImgAg.bat is fast because the first search shrinks as much as possible, and subsequent searches use srchImg.bat in an effective way.

The cost is an increased chance of false matches in the first search. For example, a subimage that is half black and half white will match an area of mid-gray, missing a better solution that is nearly (but not quite) black and white. To overcome this problem, the script doesn't assume the best match in the first search necessarily corresponds to the best match in the final search. Instead, it finds the best (N) matches in the first search, and uses those all those results as the basis of multiple second searches. The final result is then the best of those second searches.

srchImgAg.bat is faster than srchImg.bat when the large image is many times larger than the subimage. When, in addition, the subimage is around ten pixels on the shorter dimension, the speed difference is more marked.

Example usage

First, we apply the method to an example from the Searching an image page.

%IMG7%magick ^
  -size 400x300 xc: ^
  -sparse-color barycentric "0,0 #88f 399,0 #44f 0,299 #2f2 399,299 #484" ^
  sia_large.png

%IMG7%magick ^
  -size 50x50 xc:#0aa ^
  -sparse-color barycentric "0,0 #0af 49,0 #28f 0,49 #2f2 49,49 #484" ^
  sia_sub.png

set siaDEBUG=1
call %PICTBAT%srchImgAg sia_large.png sia_sub.png

F:\pictures\srchImg: MinDim=50 Offset=(0,0)
:ResizeSrch: 20 5
:ResizeSrch: Creating TMPSRC_RES [C:\Users\Alan\AppData\Local\Temp\siSrc_siaSrc_sia_large_20.miff]
:ResizeSrch: 10701.9 0.1633 7 9
:ResizeSrch:   COMP_XW,YW = 35,45 IsDissim=0
:CropResizeSrch: 35,45 10 50 2
:CropResizeSrch: 10725.5 0.163661 6 5
:CropResizeSrch:   COMP_XW,YW = 37,45   IsDissim=0
:CropSrch: 37,45 2
:CropSrch: 10728.2 0.163701 0 1
:CropSrch:   COMP_XW,YW = 35,44   IsDissim=0
F:\pictures\srchImgAg: echo COMP_XW=135  COMP_YW=144  siCOMP_FLT=0.163701
F:\pictures\srchImgAg: echo BEST_XW=135  BEST_YW=144  BEST_FLT=0.163701

echo siCOMP_XW=%siCOMP_XW%  siCOMP_YW=%siCOMP_YW% ^
 siCOMP_FLT=%siCOMP_FLT%  siCOMP_CROP=%siCOMP_CROP%

siCOMP_XW=135  siCOMP_YW=144  siCOMP_FLT=0.163701  siCOMP_CROP=50x50+135+144

As we hope, this method gives the same result.

Dissmilarity threshold

The script will use a setting for -dissimilarity-threshold of siDISSIM_THR. By default, this is 1.0.

Any setting of siDISSIM_THR between 0 and 1 will stop the script early if any of the searches have a worse score. This can increase performance when we are looking for exact matches rather than more generally for the best match.

Beware of setting siDISSIM_THR too low. Even if the final search would yield a perfect score of zero, a previous search might not.

The returned variable siIS_DISSIM will be 0 if a match was found within the limit, and 1 if it wasn't.

Real photographs

Again, we apply the method to an example from the Searching an image page.

I took two hand-held photographs with a GoPro camera, pointing the camera in roughly the same direction for both. They are both 4000x3000 pixels. Here is the first, resized for the web, and a crop from the second.

The large image (shown resized for the web):

set WEB_SIZE=-resize 500x500

set SRC=%PICTLIB%20140430\GOPR0166.JPG
set SI_SRC=si_src.jpg
if not exist %SI_SRC% copy %SRC% %SI_SRC%

%IMG7%magick ^
  %SI_SRC% ^
  %WEB_SIZE% ^
  sia_photo_sm.jpg

Subimage, taken from the second photo:

%IMG7%magick ^
  %PICTLIB%20140430\GOPR0167.JPG ^
  -crop 200x200+2481+2493 +repage ^
  sia_photo_sub.png

We search for the sub-image, marking the location with a red square:

set siaDEBUG=1
set siaDEBUG_STROKE=-fill None -stroke #f00 -strokewidth 10
call StopWatch
call %PICTBAT%srchImgAg %SI_SRC% sia_photo_sub.png
call StopWatch 
set siaDEBUG=
set siaDEBUG_STROKE=

0 00:00:15

echo siCOMP_XW=%siCOMP_XW%  siCOMP_YW=%siCOMP_YW% 
echo siCOMP_FLT=%siCOMP_FLT%  siCOMP_CROP=%siCOMP_CROP%

siCOMP_XW=2407  siCOMP_YW=2377 
siCOMP_FLT=0.121981  siCOMP_CROP=200x200+2407+2377

%IMG7%magick ^
  si_src_sia_dbg.tiff ^
  %WEB_SIZE% ^
  si_src_sia_dbg_sm.jpg

Crop out what has been found, just to see what it looks like.

%IMG7%magick ^
  %SI_SRC% ^
  -crop %siCOMP_CROP% ^
  sia_fnd_crp.png

The difference with the sub-image:

%IMG7%magick ^
  sia_photo_sub.png ^
  sia_fnd_crp.png ^
  -compose Difference -composite ^
  -auto-level ^
  sia_fnd_diff.png

Again, this gives the same result as the non-aggressive search, but in 40% of the time.

For the next example, we use a smaller crop from the second photograph.

Subimage, taken from the second photo:

%IMG7%magick ^
  %PICTLIB%20140430\GOPR0167.JPG ^
  -crop 25x25+2548+2603 +repage ^
  sia_photo_sub2.png

We search for this small crop within the large image, the first photograph:

This is the wrong result.

call StopWatch
call %PICTBAT%srchImgAg %SI_SRC% sia_photo_sub2.png
call StopWatch

0 00:00:08

echo siCOMP_XW=%siCOMP_XW%  siCOMP_YW=%siCOMP_YW% 
echo siCOMP_FLT=%siCOMP_FLT%  siCOMP_CROP=%siCOMP_CROP%

siCOMP_XW=2473  siCOMP_YW=2486 
siCOMP_FLT=0.0619976  siCOMP_CROP=25x25+2473+2486

[No image]

What have we found?

%IMG7%magick ^
  %SI_SRC% ^
  -crop %siCOMP_CROP% +repage ^
  sia_fnd_crp2.png

Let's try again, setting siaN_BEST:

set siaN_BEST=4
call StopWatch
call %PICTBAT%srchImgAg %SI_SRC% sia_photo_sub2.png
call StopWatch

0 00:00:16

echo siCOMP_XW=%siCOMP_XW%  siCOMP_YW=%siCOMP_YW% 
echo siCOMP_FLT=%siCOMP_FLT%  siCOMP_CROP=%siCOMP_CROP%

siCOMP_XW=2473  siCOMP_YW=2486 
siCOMP_FLT=0.0619976  siCOMP_CROP=25x25+2473+2486

[No image]

What have we found?

%IMG7%magick ^
  %SI_SRC% ^
  -crop %siCOMP_CROP% +repage ^
  sia_fnd_crp3.png

This is the correct result. Note the value of siCOMP_FLT is improved.

Performance comparisons

For comparison, we do the same search with srchImg.bat:

call %PICTBAT%srchImg si_src.jpg sia_photo_sub2.png

Time and results:

0 00:06:29

siCENT_X=2485
siCENT_Y=2498
siCOMP_CROP=25x25+2473+2486
siCOMP_FLT=0.0619346
siCOMP_XW=2473
siCOMP_YW=2486
siIS_DISSIM=0
SI_SRC=\prose\pictures\si_src.jpg

And the same search with -subimage-search:

%IMG7%magick compare -metric RMSE -subimage-search si_src.jpg sia_photo_sub2.png NULL:

Time and results:

4058.89 (0.0619346) @ 2473,2486

0 00:21:28

For this combination of image sizes, srchImg.bat takes 30% of the time for -subimage-search, and srchImgAg.bat takes 0.7% of the time for srchImg.bat.

Rotations

This script copes with small rotations that are typically found with holding a camera in one's hand, up to around 10°. If the angle is large, eg 45°, it will find false positives. Smaller sub-images are more tolerant of rotations. Searching rotated images are the subject of another page, What rotation?.

Conclusion

The method shown on this page is useful when the sub-image is very much smaller than the large image, eg 1% of the linear dimensions. In these circumstances, the method shown in Searching an image doesn't resize by much, so the speed isn't a massive improvement on the IM "-subimage-search" method.

The speed on this page's aggressive method is always good, but the downside is an increased chance of finding a false positive on the first (reduced size) search. We reduce this problem by finding the (N) best matches from the first search, and examining those results in more detail.

This raises the question: how many best matches should we use? Experiments so far suggest that N=5 is a reasonable number.

Cleanup

We don't need to keep large tiff files, so delete them.

del si_*_*.tiff

Scripts

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

srchImgAg.bat

rem  Searches image %1 for smaller image %2.
@rem Aggressively resizes both images down by same factors so small image is 1x1.
@rem Finds best match by difference composition.
@rem This gives crop location(s) in large image for full search(es).
@rem
@rem  Also uses:
@rem
@rem    siaSIZE_METH    sizing method: resize or scale
@rem    siaN_BEST       for the second (full-size) search,
@rem                    try this number of results from the first search.
@rem                      Default = 1 = only try the best.
@rem    siaDEBUG        if 1, creates a marked-up copy of image.
@rem    siaDEBUG_STROKE eg "-fill None -stroke #f00 -strokewidth 10" to get thick strokes
@rem
@rem    siMETRIC        defaults to RMSE
@rem    siDELTEMPSRC    if not 0, will remove temporary source (%1) files.
@rem    siDELTEMPSUB    if not 0, will remove temporary subimage (%2) files.
@rem    siDIV_DIM       Divide min dim by this, for purpose of choosing resizes. [1]
@rem    siDISSIM_THR    Dissimilarity threshold. [1]
@rem
@rem  Returns:
@rem    siCOMP_XW, siCOMP_YW coord of top-left of found area
@rem    siCOMP_FLT  RMSE difference beween %2 and found area
@rem    siCOMP_CROP=%subW%x%subH%+%COMP_XW%+%COMP_YW%  crop spec of found area
@rem    siIS_DISSIM 1 if images too dissimilar; otherwise 0
@rem
@rem Updated:
@rem   27-August-2022 for IM v7.
@rem


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

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 sisc


set siERROR=0

if "%siaDEBUG%"=="1" (
  set DEBUG_OUT=%BASENAME%_sia_dbg%EXT%
  if "%siaDEBUG_STROKE%"=="" set siaDEBUG_STROKE=-fill None -stroke #f00
)

set SRCNAME=%~n1
set SRC=%INFILE%
set SUB=%2

if "%siMETRIC%"=="" set siMETRIC=RMSE

set TMPEXT=.miff
set TMPDIR=%TEMP%

set SRC_PREF=%TMPDIR%\siaSrc_%SRCNAME%
set TMPSRC=%SRC_PREF%%TMPEXT%
set TMPSUB=%TMPDIR%\siaSub%TMPEXT%
set TMPDIFF=%TMPDIR%\siaSub_diff%TMPEXT%

if "%siDISSIM_THR%"=="" set siDISSIM_THR=1

if "%siaN_BEST%"=="" set siaN_BEST=1

set subW=
for /F "usebackq" %%L in (`%IMG7%magick ^
  %SUB% ^
  -format "subW=%%w\nsubH=%%h" ^
  info:`) do set /A %%L

if "%subW%"=="" (
  echo Can't open SUB [%SUB%]
  exit /B 1
)

set srcW=
for /F "usebackq" %%L in (`%IMG7%magick ^
  %SRC% ^
  -format "srcW=%%w\nsrcH=%%h" ^
  info:`) do set /A %%L

if "%srcW%"=="" (
  echo Can't open SRC [%SRC%]
  exit /B 1
)

if not %srcW% GTR %subW% (
  echo Src width must be greater than sub width
  exit /B 1
)

if not %srcH% GTR %subH% (
  echo Src height must be greater than sub height
  exit /B 1
)

for /F "usebackq" %%L in (`%IMG7%magick identify ^
  -format "newSrcW=%%[fx:int(%srcW%/%subW%+0.5)]\nnewSrcH=%%[fx:int(%srcH%/%subH%+0.5)]" ^
  xc:`) do set /A %%L

for /F "usebackq" %%L in (`%IMG7%magick identify ^
  -format "factW=%%[fx:%srcW%/%newSrcW%]\nfactH=%%[fx:%srcH%/%newSrcH%]" ^
  xc:`) do set %%L

rem %0: echo newSrcW=%newSrcW% newSrcH=%newSrcH% factW=%factW% factH=%factH%

if "%siaN_BEST%"=="1" (
  set sSTRETCH=
) else (
  set sSTRETCH=-linear-stretch 0x%siaN_BEST%
)

%IMG7%magick ^
  %SRC% ^
  -resize "%newSrcW%x%newSrcH%^!" ^
  ( %SUB% ^
    -scale "1x1^!" ^
    -scale "%newSrcW%x%newSrcH%^!" ^
  ) ^
  -channel RGB ^
  -compose Difference -composite ^
  +channel ^
  -grayscale RMS ^
  -negate ^
  %sSTRETCH% ^
  -auto-level ^
  +depth ^
  %TMPDIFF%

if ERRORLEVEL 1 (
  echo %0: bad magick
  exit /B 1
)

set /A cropW=3*%subW%
set /A cropH=3*%subH%

:: Ensure srchImg.bat deletes resized images.
set siDELTEMPSRC=1
set siDELTEMPSUB=1

set BEST_XW=0
set BEST_YW=0
set BEST_FLT=999

for /F "usebackq skip=1 tokens=1-2 delims=, " %%X in (`%IM7DEV%magick ^
  %TMPDIFF% ^
  -process allwhite ^
  NULL: 2^>^&1`) do (

  for /F "usebackq" %%L in (`%IMG7%magick identify ^
    -format "COMP_XW=%%[fx:int(%%X*%factW%+0.5)]\nCOMP_YW=%%[fx:int(%%Y*%factH%+0.5)]" ^
    xc:`) do set /A %%L

  rem echo %0: COMP_XW=!COMP_XW! COMP_YW=!COMP_YW!

  rem Now do the crop search.

  set /A cropL=!COMP_XW!-%subW%
  set /A cropT=!COMP_YW!-%subH%
  if !cropL! LSS 0 set cropL=0
  if !cropT! LSS 0 set cropT=0

  %IMG7%magick ^
    %SRC% ^
    +repage ^
    -crop %cropW%x%cropH%+!cropL!+!cropT! ^
    +repage ^
    %TMPSRC%

  if ERRORLEVEL 1 (
    set siERROR=1
    exit /B 1
  )

  call %PICTBAT%srchImg %TMPSRC% %SUB%

  set /A COMP_XW=!siCOMP_XW!+!cropL!
  set /A COMP_YW=!siCOMP_YW!+!cropT!

echo %0: echo COMP_XW=!COMP_XW!  COMP_YW=!COMP_YW!  siCOMP_FLT=!siCOMP_FLT!

  for /F "usebackq" %%L in (`%IMG7%magick identify ^
    -format "IS_BETTER=%%[fx:!BEST_FLT!>!siCOMP_FLT!?1:0]" ^
    xc:`) do set /A %%L

  if !IS_BETTER!==1 (
    set BEST_XW=!COMP_XW!
    set BEST_YW=!COMP_YW!
    set BEST_FLT=!siCOMP_FLT!
  )

)

echo %0: echo BEST_XW=!BEST_XW!  BEST_YW=!BEST_YW!  BEST_FLT=!BEST_FLT!

if "%siaDEBUG%"=="1" (
  set /A endX=%BEST_XW%+%subW%-1
  set /A endY=%BEST_YW%+%subH%-1

  %IMG7%magick ^
    %SRC% ^
    +repage ^
    %siaDEBUG_STROKE% ^
    -draw "rectangle %BEST_XW%,%BEST_YW% !endX!,!endY!" ^
    %DEBUG_OUT%
)

call echoRestore

@endlocal & set siCOMP_XW=%BEST_XW%& set siCOMP_YW=%BEST_YW%& set siCOMP_FLT=%BEST_FLT%& set siIS_DISSIM=%siIS_DISSIM%& set siCOMP_CROP=%subW%x%subH%+%BEST_XW%+%BEST_YW%

@exit /B 0

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)

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

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 6-September-2016.

Page created 28-Aug-2022 00:03:26.