Matching masked images

Question

Let's say I have two images that are parts of the same bigger image, cut using two masks (for simplicity, let's assume that the masks are just rectangles of the same size). The images are presumed to overlap. The concrete examples are: image stabilization (two different views of the same background) and object tracking (matching the object on two images).

I've read this excellent article http://werner.yellowcouch.org/Papers/subimg/, but it deals with finding the displacement of a small image which is a part of a large one, while I want to find displacement between the images of the same size. My images intersect, but don't contain each other.

I want to find the coefficients of the translation transform which correctly overlaps the matching parts of the images. I want to use something like FFT-based correlation matching. I have the following problems with simply using FFT-correlation:

1. The edges of the image frames are strong features. If the algorithm searches the displacement $[dx, dy]$ that maximizes something like $\sum_{x,y}{a[x, y]}b[x + dx, y + dy]$, it would just snap the images so that their frames match, disregarding the content. I heard about windowing, but I don't understand how to apply it here. If each image is tapered at the edges, the images would no longer match when positioned correctly.
2. If we use a correlation function that normalizes the result by dividing it by the area of intersection resulting from the displaced matching, the algorithm would just try to keep the intersection to a minimum (~1x1 pixel; the smaller the intersection area is, the easier it is to find a nearly perfect match.)

How to solve this matching problem using windowing or some other techniques?

Update: I know that the problem can be partially eliminated by discarding the low-frequency information (taking gradient or applying the Sobel operator). I'm trying to solve the problem without discarding the low frequency information. Also, leaving only high-frequency features still doesn't solve the outlined problem: Imagine an image with a bright thin horizontal beam and a bleak square. These features are high-frequency and thus will remain after the filter is applied. Cross-correlation will than match the bright beam parts ignoring the square.

Here is the example which shows the matching problem:

Full image with frame borders:

Frames 1 and 2:

Correlation-based incorrect frame matching:

Answer 1

Ok, here's the simple method illustrated in Python:

# Correlation is convolution with one input reversed
corr = fftconvolve(img1, img2[::-1, ::-1])

# Get coordinates of peak in x, y pixels
peak = unravel_index(corr.argmax(), corr.shape)
# peak = (199, 189)
# Calculate offset from center point
print array(peak) - 199 # Offset is [  0 -10]

So it finds the vertical offset (10 pixels), but not the horizontal, as you've shown (bottom left output below). This is because the cross-correlation output is stronger in the center when more of the input images are overlapping (gets dark toward the edges even if the inputs are identical). (The found peak is shown with the red cross.)

And here's the method I described in the comments. I have no idea if there's a mathematically rigorous foundation for this or if it has a name, but it produces the right results. It may or may not be the same thing as normalized cross-correlation (I haven't bothered to decipher what Wikipedia is saying):

weighting = fftconvolve(ones(shape(img1)), ones(shape(img2)))
corr = corr / weighting # Normalize
peak = unravel_index(corr.argmax(), corr.shape)[::-1]
# peak = (224, 189)
print array(peak)-199 # Offset of [ 25 -10]

So this method works. It normalizes every element of the output array by the number of overlapping pixels that were used to calculate that element, so that when only the thin edges of the images are overlapped, it still produces a strong output. Now the offset from the dim square is not swamped by the white bar (lower right of image).

Note that while this works perfectly with your example images, this method doesn't work as well for real images, since the edges of the output tend to vary wildly compared to the middle, and can produce spurious peaks, but if you know the offset is constrained to less than the image width, you can look for the peak only in realistic locations near the center, ignore the edges, and it works.

Wikipedia suggests a method using windowed images which I thought might improve on this, but unless I'm doing it wrong, it doesn't:

h = hamming(shape(img1)[0]) # 1D Hamming window
ham2d = outer(h, h) # 2D Hamming window

h1 = img1 * ham2d
h2 = img2 * ham2d

corr = fftconvolve(h1, h2[::-1,::-1])
peak = unravel_index(corr.argmax(), corr.shape)[::-1]
# peak = (216, 189)
print array(peak) - 199 # Offset is [ 17 -10]

The windowing does too much, and causes it to find an erroneous peak that's in between the previous two results.