# Matching superimposed image

We are given two grayscale images, one of which contains a large, mostly contiguous patch from the other one. The patch can be altered with noise, its levels may be stretched, etc.

Here’s an example

We would like to determine the region of the image which was copied onto the other image.

My first instinct was to look at the local correlation. I first apply a little bit of blur to eliminate some of the noise. Then, around each point, I can subtract a gaussian average, then look at the covariance weighted by that same Gaussian kernel. I normalize by the variances, measured in the same way, to get a correlation. If $$G$$ is the Gaussian blur operator, this is:

$$\frac{G(A \times B) – G(A)G(B)}{\sqrt{(G(A^2)-G(A)^2)(G(B^2)-G(B)^2)}$$

The result is… not too bad, not great:

Playing with the width of the kernel can help a bit. I’ve also try correlating Laplacians instead of the images themselves, but it seems to hurt more than it helps. I’ve also tried using the watershed algorithm on the correlation, and it just didn’t give very good results.

I’m thinking part of my problem is not having a strong enough prior for what the patch should be like, perhaps a MRF would help here? Besides MRF, are there some other techniques, perhaps more lightweight that would apply? The other part is that correlation doesn’t seem to be all that great at measuring the distance. There are places where the correlation is very high despite the images being very visually distinct. What other metrics could be of use?