# What is the fastest way to locate an image inside a larger image?

let b =

let c =

How to do:

find[c,b]


that returns the bounding box of c in b?

Notes

• Original b is not scaled, this is only the case in this post.
• (Update: this may actually not be the case.) Because b contains an exact copy of c, this can be thought of as a problem of finding a submatrix in a larger matrix.

Update

Here are the results so far:

-
If your actual images are not scaled with respect to each other, can you post them? Allowing rescaling is significantly more difficult than searching for an exact image. –  Szabolcs Feb 17 '12 at 14:15
@Szabolcs I just posted the originals AND updated B once because the first B I posted was actually scaled so I updated B with a smaller image with no scaling between B and C. –  Cetin Sert Feb 17 '12 at 14:33
I gave up on ImageAlign, and I rewrote the answer –  Szabolcs Feb 17 '12 at 15:01

Using ImageCorrelate, you can do something like

bbox[img_, crop_] := {#, # + Reverse@ImageDimensions[crop] - 1} &@
Position[ImageData@
Binarize[
ImageCorrelate[img, crop, SquaredEuclideanDistance,


Example

img = ExampleData[{"TestImage", "Mandrill"}]
crop = ImageTake[img, {40, 80}, {141, 200}]

bbox[img, crop]

{{40, 141}, {80, 200}}


Edit

In response to the OP's question,here is an explanation of how bbox works.

ImageCorrelate in bbox creates a new image by calculating the Euclidean distance between crop and each of the sub images of img with the same dimensions as crop. The option Padding -> None is to make sure that the pixel at {i,j} in the result of ImageCorrelate corresponds to the sub image whose upper left corner is at position {i,j} in the original image.

The Euclidean distance between two images is zero only if they are the same, so to find the position of crop in img we just need to extract the position of the pixels with value {0.,0.,0.} from the image data of ImageCorrelate which is what Position[ImageData@Binarize[....]], 0] does.

This will give us the position of the upper left corner of crop. The lower right corner is then the upper-left corner plus the dimensions of crop (note that since ImageDimensions returns {number of cols, number of rows}, and the bounding box is given as {{rowMin, colMin}, {roxMaw, colMax}} we need to reverse ImageDimensions)

Edit 2

As Szabolcs pointed out, the cut off in Binarize is somewhat arbitrary, and might cause false positives. As an alternative you could do something like this instead, which would find the best fit in the image:

bbox[img_, crop_] := {#, # + Reverse@ImageDimensions[crop] - 1} &@
(Position[#, Min[#]][[1]] &@
ImageData[ColorConvert[
ImageCorrelate[img, crop, SquaredEuclideanDistance,

-
This is the only working solution so far :) and it is much much faster than ImageAlign (the result which even needs further processing to get to a bbox). –  Cetin Sert Feb 17 '12 at 14:31
Could you explain the inner workings of bbox? –  Cetin Sert Feb 17 '12 at 14:36
Oh nuts, I just spent half an hour on something like this. I thought you were out. ;-p –  Mr.Wizard Feb 17 '12 at 14:52
I don't like that Binarize. It is a point of failure because of the rather arbitrary threshold. Can you search for the minimum value instead, as I did in my (now deleted solution)? I am afraid someone might come up with an example on which this'll fail. –  Szabolcs Feb 17 '12 at 15:19
@Szabolcs I've added a new version of bbox using the minimum value –  Heike Feb 17 '12 at 15:39

For (not necessarily) more complicated cases, you may want to have a look at the geometric transformation functions in Mathematica.

img = Import["~/temp/geomtrafo.png"]; (* The image *)
crop = ImageCrop[img, {100, 100}]; (* Crop small portion *)
FindGeometricTransform[img, crop, Transformation -> "Similarity"][[2]]


Notice the two numbers in the TransformationFunction? These are the lower left coordinates of the cropped image in the large one. I used the parameter Transformation -> "Similarity" here, which considers rotations, translations, and scalings; there are more basic and more complicated ones available, refer to the help function of FindGeometricTransform.

I'm afraid I don't know how to extract these numbers properly from there, but that shouldn't be an issue.

-
"I'm afraid I don't know how to extract these numbers properly from there, but that shouldn't be an issue." post the output of FindGeometricTransform[. . .] // InputForm and we should be able to fix that. –  Mr.Wizard Feb 17 '12 at 14:25
When I do b = "http://portfusion.sourceforge.net/i/m1/B.png" // Import; c = "http://portfusion.sourceforge.net/i/m1/C.png" // Import; FindGeometricTransform[b, c, "Transformation" -> "Similarity"] I get the error: Images ### and ### do not share any corresponding points. –  Cetin Sert Feb 17 '12 at 14:27
@Mr.Wizard That's why I said "properly". Using patterns and Part will of course work, but it's pretty hacky. –  David Feb 17 '12 at 14:40
@CetinSert Yes, I'm able to reproduce that, but I don't know why it occurs, sorry. I'm not using image functions very often. Read my post as a helper until somebody can give you a decent solution. –  David Feb 17 '12 at 14:51
@David TransformationMatrix seems to be what you are looking for. –  Cetin Sert Feb 17 '12 at 17:46

If your final assertion is true:

Because b contains an exact copy of c, this can be thought of as a problem of finding a submatrix in a larger matrix.

A fast implementation in Mathematica for Position2D

Since your images are apparently not exact, you can find the position of the upper left corner of the sample with correlation:

b = Import["http://portfusion.sourceforge.net/i/m1/B.png"];
c = Import["http://portfusion.sourceforge.net/i/m1/C.png"];

full = ImageData[ColorConvert[b, "Grayscale"]];
sample = ImageData[ColorConvert[c, "Grayscale"]];

cor = ListCorrelate[1/(sample /. 0. -> 1.0*^-6), full];

Position[cor, Min@cor]


{{94, 88}}

The correlation looks like this:

cor // Rescale // Image


-
I just took a look at that post myself for some reason none of the examples seem to work as of now. I copy paste these images using the snapshot tool of Acrobat. Perhaps the internal data are not exactly the same (despite the appearance), rendering my final assertion actually false. –  Cetin Sert Feb 17 '12 at 14:07
I got Position2D to work if a binarize the images beforehand. –  Cetin Sert Feb 17 '12 at 17:47
@Cetin how does its speed compare to the ListCorrelate method? –  Mr.Wizard Feb 17 '12 at 17:49

As a footnote: I remember my problems with ImageAlign before were caused by the fact that the images were simply too small. So if we make them bigger, it should work better.

bin = Binarize[
ImageAlign[ImageResize[all, Scaled[2]],
ImageResize[part, Scaled[2]]]]


where 'all' and 'part' are the two images.

and it seems to work.

First[Position[ImageData[bin], 1]]


returns row and column:

{187, 175}

-