0

Imagine I have an image with a rectangular canvas of three identical squares, all parallel with the side of the image canvas. None of the squares are overlapping. It is easy to find answers all over SO (How to find one image inside of another?) to the problem of finding images within an image that exactly match a given image.

However, sometimes the images are rotated within the image, and they are not matched because of this. Taking our initial example, and rotating one square 25 degrees and retaining that no square overlaps, how could I not only match the two non-rotated squares as well as the rotated square?

Community
  • 1
  • 1
Nick Bull
  • 9,518
  • 6
  • 36
  • 58

1 Answers1

0

You would take the same approach as finding one image within another, but run the search again with your coordinates rotated 90 degrees or however many degrees rotated you think the inner image might be. If you are doing a direct scan of the image, pixel by pixel, do your search right to left, or top to bottom, instead of left to right.

Unicorno Marley
  • 1,744
  • 1
  • 14
  • 17
  • But an angle is not a discrete value, unlike a pixel. How would I know how much to rotate to make sure I get all rotations? – Nick Bull Oct 18 '14 at 02:33
  • Imagine the larger image is a grid (it is, of pixels). Place a square on the grid. Then rotate it. Every pixel still within the square are the coordinates you have to search. Then you move along the image, row by row just like you would if you were searching for an unrotated image. You will have to figure out what those coordinates are for each degree of rotation. – Unicorno Marley Oct 18 '14 at 03:11
  • I believe your answer will work, but including the transformations the operation is O(n^3), and I'm not sure that would be practical in my application. Perhaps this is the only way - thank you for your answer. – Nick Bull Oct 18 '14 at 03:17