23
$\begingroup$

let b =

enter image description here

let c =

enter image description here

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.

Links to original images

Update

Here are the results so far:

enter image description here

Final Result (using Heike's answer)

enter image description here

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2012 at 14:15
  • $\begingroup$ @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. $\endgroup$ Commented Feb 17, 2012 at 14:33
  • $\begingroup$ I gave up on ImageAlign, and I rewrote the answer $\endgroup$ Commented Feb 17, 2012 at 15:01

4 Answers 4

Reset to default
12
$\begingroup$

Using ImageCorrelate, you can do something like

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

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, Padding -> None], "Graylevel"]])
Improve this answer
$\endgroup$
9
  • $\begingroup$ 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). $\endgroup$ Commented Feb 17, 2012 at 14:31
  • $\begingroup$ Could you explain the inner workings of bbox? $\endgroup$ Commented Feb 17, 2012 at 14:36
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2012 at 15:19
  • 1
    $\begingroup$ @Mr.Wizard It looks like in version 7, ImageCorrelate only accepts a 2 dimensional numerical matrix for the kernel. You could try to convert the both img and crop to grayscale and to use ImageCorrelate[img, ImageData[crop],...] on the converted images (although I don't know if you can specify the distance function in v7). $\endgroup$ Commented Feb 17, 2012 at 15:28
  • 1
    $\begingroup$ @Szabolcs I've added a new version of bbox using the minimum value $\endgroup$ Commented Feb 17, 2012 at 15:39
6
$\begingroup$

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]]

enter image description here

enter image description here

enter image description here

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ "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. $\endgroup$ Commented Feb 17, 2012 at 14:25
  • $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2012 at 14:27
  • $\begingroup$ @Mr.Wizard That's why I said "properly". Using patterns and Part will of course work, but it's pretty hacky. $\endgroup$ Commented Feb 17, 2012 at 14:40
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Feb 17, 2012 at 14:51
  • 1
    $\begingroup$ @David TransformationMatrix seems to be what you are looking for. $\endgroup$ Commented Feb 17, 2012 at 17:46
6
$\begingroup$

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.

You will find your answer here:

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

Mathematica graphics

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Feb 17, 2012 at 14:07
  • $\begingroup$ I got Position2D to work if a binarize the images beforehand. $\endgroup$ Commented Feb 17, 2012 at 17:47
  • $\begingroup$ @Cetin how does its speed compare to the ListCorrelate method? $\endgroup$ Commented Feb 17, 2012 at 17:49
6
$\begingroup$

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.

imagealign

and it seems to work.

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

returns row and column:

{187, 175}
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.