How to use a low-resolution, cropped photo as a guide to re-crop a higher resolution copy of the original?

Question

I have a square, low-resolution photo, which has been cropped (by the user) out of a high-resolution, non-square, original. The low-res photo has then been resized downwards into a thumbnail. I'd like to automatically (no user-intervention required) re-crop the original photo in the same way to achieve a higher-resolution copy of the square version. I do not have access to the original cropper coordinates. All I have are these two photos.

Here are some example images (from my Facebook profile) to illustrate what I mean:

Original, high-resolution photo - Cropped, then shrunk, square photo

Again, the goal is to use the small photo as a guide to get a much higher resolution square photo from the source.

The only constraints on the solution are:

1. Generality: I'm using this for profile pictures, so if it only works on faces that is perfectly acceptable! No need to generalize to all sorts of random images, pictures of people is a great place to start.
2. Platform: I'm using Node, but I'd be happy to run this process in Ruby, Python, Java, or C++ (with Node bindings). It would almost certainly run on Heroku or AWS.
3. Speed: It's going to need to be pretty speedy. For this to be useful, it would have to run in an on-line fashion, since I'd be blocking the user's interface waiting for this action.

Does anyone have any ideas? I don't know a lot about image processing, so I wouldn't really know where to start.

EDIT: For Facebook, specifically, there is a solution that is not nearly so hard. The original crop data is available for profile images: https://graph.facebook.com/bcherry/profile?fields=pic_crop

This is going to get me over my immediate hurdle, but may not be a long-term solution, so the answers provided below are still quite helpful to the more general problem.

Answer 1

While I will not comment to Javascript-ness of my solution - you're basically trying to perform Image Registration between the original and cropped, resized image.

There are many different methods to do something like this - for your particular purpose, I would start with a Phase-Correlation like approach.

EDIT: I just found a nice script using ImageMagick that does exactly what you need. NormCrossCorr "computes the normalized cross correlation surface to find where a small image best matches within a larger image."

Hope this helps!