Partial image detection with perceptual hashing

Question

I'm looking for advice on the best perceptual hashing algorithms/strategies to detect when a certain image has been used in part of another image.

For example, given the following source image-

How would I detect its use in this fake image-

I have done some research into the perceptual image hashing algorithms, but none seem to cover my use-case. Specifically, Image registration doesn't fit my need because (as far as I know) the full-size images must be used, not just their perceptual hashes.

Can anyone help me out, or at least point me in the right direction on Google?

Sample image sources:

• "How I Met Your Mother" by CBS via Getty Images
  http://www.gettyimages.com/detail/news-photo/alyson-hannigan-stars-in-how-i-met-your-mother-scheduled-to-news-photo/53467548

• "Look At Me: Friends" by Scott Shephard Photography
  http://www.scottshephard.com/blog/2009/12/look-at-me-friends/

Answer 1

One approach for doing this can be 1. Extract geometric markers (special points), for both input and output, for example by using the Harris corner detector. 2. Compare every possible pair of triangles on each image . If they have the same angles, they define a transformation (resize, rotate,shift, and mirror). Google "geometric hashing" 3 Count how many points in the target agree with the transformed source, and you have a score for the match. 4. Verify the best match by other means (histogram, edge-registration).

This approach is slow in theory (o(n^6) in the number of points) but I believe it can be practical using an appropriate choice of n and some tricks to speed it up.