4
$\begingroup$

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:

Full image with frame borders

Frames 1 and 2:

Frame 1 Frame 2

Correlation-based incorrect frame matching:

Correlation-based incorrect matching

$\endgroup$
  • $\begingroup$ If there's overlap, and no scaling or rotation, cross-correlation should work. I don't think it will match the edges of the image frames, as long as you pad with the mean value before doing the circular cross-correlation (pad with 128 for 8-bit unsigned images, or zero-pad for signed images(?)) I don't think windowing makes sense for this. Also you can find sub-pixel shifts by interpolating the peak of the cross-correlation output and its neighboring pixels. If you try it on sample images you will quickly figure out whether it can work or not. $\endgroup$ – endolith Jul 10 '13 at 14:32
  • $\begingroup$ I assume there is no scaling or rotation. I don't think that mean-padding solves the issue. Common images have horizon, so the top is light and the bottom is dark. Cross-correlation is only concerned with putting bright spots against the bright spots, so it naturally aligns the frames (by aligning the sky halves). I'll try to produce some images, but the article in my question has provided a good example of cross-correlation just putting the sub-image over the brightest spot of the image. $\endgroup$ – Ark-kun Jul 10 '13 at 15:18
  • $\begingroup$ Example images would be good. You could preprocess with a filter that emphasizes high frequencies like the Sobel operator? $\endgroup$ – endolith Jul 10 '13 at 17:24
  • $\begingroup$ @endolith I'll try to provide the images a bit later. Emphasizing high frequencies certainly helps (i'm using gradient right now). But I'm trying to solve the problem without discarding the low frequency information. $\endgroup$ – Ark-kun Jul 11 '13 at 12:48
  • 1
    $\begingroup$ @endolith I've added the images illustrating the problem. $\endgroup$ – Ark-kun Jul 18 '13 at 10:50
2
$\begingroup$

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.

weighted method

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.

windowed method

$\endgroup$
  • $\begingroup$ Windowing this way makes the problem worse as the edge snapping becomes more justified. I guess, I'll use the cross-correlation divided by the overlap area, as described in this answer and in my question. $\endgroup$ – Ark-kun Jul 24 '13 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.