How does ImageMagick's '-subimage-search' operation work?

Question

I have used ImageMagick in my application. I used ImageMagick for comparing images using the compare command with the -subimage-search option.

But there is very little documentation of about how -subimage-search works.

Can anyon provide me more information on how it works? For example:

Does it compare using colormodel or does it image segmentation to achieve its task?

What I know right now is it searches for the second image in the first.

But how this is done? Please explain.

Answer 1

Warning: Conducting a subimage-search is slow -- extremely slow even.

Theory

This slowness is due to how the subimage searching is designed to work: it is carries out a compare of the small image at every possible position within the larger image (with that area it currently covers at this location).

The basic command to use -subimage-search is this:

compare -subimage-search largeimage.ext subimage.ext resultimage.ext

As a result of this command you should get not one, but two images:

• results-0.ext : this image should display the (best) matching location.
• results-1.ext : this should be a "heatmap" of potential top-left corner locations.

The second image (map of locations) displays how well the sub-image matches at the respective position: the brighter the pixel, the better the match.

The "map" image has smaller dimensions, because it contains only locations or each potential top-left corner of the sub-image while fitting completely into the larger one. Its dimensions are:

width  = width_of_largeimage  - width_of_subimage  + 1
height = height_of_largeimage - height_of_subimage + 1

The searching itself is conducted on the basis of differences of color vectors. Therefore it should result in fairly accurate color comparisons.

In order to improve efficiency and speed of searching, you could follow this strategical plan:

1. First, compare a very, very small sub-image of the sub-image with the larger image. This should find different possible locations faster.
2. Then use the results from step 1 to conduct a difference compare at each previously discovered potential location for more accurate matches.

Practical Example

Let's create two different images first:

convert rose: subimage.jpg

convert rose: -mattecolor blue -frame 20x5 largeimage.png

The first image, sub-image.jpg (on the left), being a JPEG, will have some lossiness in the color encodings, so sub-image can not possibly create an exact match.

The main difference of second image, largeimage.png (on the right), will be the blue frame around the main part:

Now time the compare-command:

time compare -subimage-search largeimage.png  subimage.jpg  resultimage.png
 @ 40,5
 real  0m17.092s
 user  0m17.015s
 sys   0m0.027s

Here are the results:

• resultimage-0.png (displaying best matching location) on the left;
• resultimage-1.png (displaying the "heatmap" of potential matches) on the right.

Conclusion: Incorrect result? Bug?

Looking at the resulting images, and knowing how the two images were constructed, it seems to me that the result is not correct:

1. The command should have returned @ 20,5 instead of @ 40,5.
2. The resultimage-0.png should have the red area moved to the left by 20 pixels.
3. The heatmap, resultimage-1.png seems to indicate the best matching location as the darkest pixel; maybe I was wrong about my above "the brighter the pixel the better the match" statement, and it should be "the darker the pixel..."?.

I'll submit a bug report to the ImageMagick developers and see what they have to say about it....

Update

As suggested by @dlemstra, a ImageMagick developer, I tested with adding a -metric operation to the subimage-search. This operation returns a numerical value indicating the closeness of a match. There are various metrics available, which can be listed with

convert -list metric

This returns the following list on my notebook (running ImageMagick v6.9.0-0 Q16 x86_64):

AE Fuzz MAE MEPP MSE NCC PAE PHASH PSNR RMSE

The meanings of these abbreviations are:

• AE : absolute error count, number of different pixels (-fuzz effected)
• Fuzz : mean color distance
• MAE : mean absolute error (normalized), average channel error distance
• MEPP : mean error per pixel (normalized mean error, normalized peak error)
• MSE : mean error squared, average of the channel error squared
• NCC : normalized cross correlation
• PAE : peak absolute (normalized peak absolute)
• PHASH : perceptual hash
• PSNR : peak signal to noise ratio
• RMSE : root mean squared (normalized root mean squared)

An interesting (and relatively recent) metric is phash ('perceptual hash'). It is the only one that does not require identical dimensions for comparing images directly (without the -subimage-search option). It normally is the best 'metric' to narrow down similarly looking images (or at least to reliably exclude these image pairs which look very different) without really "looking at them", on the command line and programatically.

I did run the subimage-search with all these metrics, using a loop like this:

for m in $(convert -list metric); do
    echo "METRIC $m";
    compare -metric "$m"            \
            -subimage-search        \
             largeimage.png         \
             sub-image.jpg          \
             resultimage---metric-${m}.png;
    echo;
done 

This was the command output:

METRIC AE
compare: images too dissimilar `largeimage.png' @ error/compare.c/CompareImageCommand/976.

METRIC Fuzz
1769.16 (0.0269957) @ 20,5

METRIC MAE
1271.96 (0.0194089) @ 20,5

METRIC MEPP
compare: images too dissimilar `largeimage.png' @ error/compare.c/CompareImageCommand/976.

METRIC MSE
47.7599 (0.000728769) @ 20,5

METRIC NCC
0.132653 @ 40,5

METRIC PAE
12850 (0.196078) @ 20,5

METRIC PHASH
compare: images too dissimilar `largeimage.png' @ error/compare.c/CompareImageCommand/976.

METRIC PSNR
compare: images too dissimilar `largeimage.png' @ error/compare.c/CompareImageCommand/976.

METRIC RMSE
1769.16 (0.0269957) @ 20,5

So the following metric settings did not work at all with -subimage-search, as also indicated by the "images too dissimilar" message:

PSNR, PHASH, MEPP, AE

(I'm actually a bit surprised that the failed metrics include the PHASH one here. This may require further investigations...)

The following resultimages looked largely correct:

1. resultimage---metric-RMSE.png
2. resultimage---metric-FUZZ.png
3. resultimage---metric-MAE.png
4. resultimage---metric-MSE.png
5. resultimage---metric-PAE.png

The following resultimages look similarly incorrect as my first run above where no -metric result was asked for:

• resultimage---metric-NCC.png (also returning the same incorrect coordinates as @ 40,5)

Here are the two resulting images for -metric RMSE (what Dirk Lemstra had suggested to use):