2
$\begingroup$

I am working on an imagery registration problem via cross-correlation and am seeing a weird phenomena sometimes. First, I am pre-processing each image by subtracting the mean image brightness from every pixel and then applying a cosine window to deal with the fact that my images are not periodic across the edges.

Then I am doing a simple cross correlation in Fourier space and creating the correlation surface. I work in Python so here is some scratch code showing what I am doing:

import numpy as np
from scipy.signal.windows import cosine as wind

im1 = np.load(file1)
im2 = np.load(file2)

rows, cols = im1.shape
hr = np.reshape(wind(rows, sym = False), (rows, 1))
hc = np.reshape(wind(cols, sym = False), (cols, 1))

h2d = np.dot(hr, hc.T)

im1 = im1 - im1.mean()
im2 = im2 - im2.mean()

im1 = im1 * h2d
im2 = im2 * h2d

fft1 = np.fft.fft2(im1)
fft2 = np.fft.fft2(im2)

prod = fft1 * fft2.conj()
surface = np.abs(np.fft.ifft2(prod))

When the relative shifts between the two images are largish, the (0,0) pixel seems to be drowned out by the overall correlation surface peak structure. However, when the relative shift becomes smaller, the (0,0) pixel starts to dominate and is no longer a smooth part of the overall surface. This causes a simple peak finding algorithm like numpys argmax to latch onto a shift of (0,0) even though a faint correlation peak surface still exists.

I am curious what can cause something like this to happen? In general, what about a set of two shifted images can cause the (0,0) pixel to dominate?

Edit 4: I discovered a scipy function called match_template that incorporates a normalization to the correlation surface proposed by JP Lewis. This method requires that template dimensions be smaller than the reference image. I accomplished this by zero padding the reference image to 2x the original image size so that upon convolution of the template, the entirety of the image dimensions contain valid correlation results. I found that there is basically no difference between my code above and this match_template method and the (0,0) peak is still the strongest component when it shouldn't be in the some cases. I think a band-aide solution is to interpolate the (0,0) pixel so that it becomes part of the overall surface. I'm jotting all this down hoping this helps someone in the future since this question hasn't gained much traction.

Edit 3: After some intensive literature review, it has become clear that this method of cross correlation is at best an approximation of normalized cross correlation. It seems like the denominator in NCC has no easily computable equivalent in Fourier space. Additionally, doing cross-correlation for images of the same size, inevitably results in inaccuracies anywhere besides the (0,0) shift component. This is due to pixels in the two images that no longer overlap once they have been shifted relative to each other. Spatially, this can/has to be accounted for by padding the images so that the correlation is defined everywhere. This padding results in inaccuracies but is necessary to search all possible translations between the two. I have another question related to this point. When doing a cross correlation like in the code above, what "padding" is applied? How are the non-overlapping parts spatially handled in Fourier space? I never define a padding, yet the surface I get is the same size as the input images...so what is going on behind the scenes for every pixel except the (0,0) one?

Edit 2: I accidentally stumbled on the realization that the (0,0) pixel of the correlation surface is always equal to the mean of the fft product. That makes me feel like its sort of deterministic and that the (0,0) pixel in the surface doesn't really encode any information about what the actual shift?

Edit to add an example image, notice the underlying structure isn't centered on that central (0,0) pixel yet it is the largest component of the surface. Also this surface has been shifted with np.fft.fftshift() to make visualization easier.

Correlation Surface

$\endgroup$
  • $\begingroup$ Not an expert on 2D-FFTs and 2D cross-correlation, but don't you have to append zeros to your image if you want to use the FFT to compute the cross-correlation? $\endgroup$ – Ben Oct 3 at 22:33
  • $\begingroup$ Yeah I thought so too. I originally thought that you had to append zeros to avoid high frequency noise caused by non-periodic edges (sort of like trying to fit the edges of a square function). I thought the zeros were necessary so that you could tile the arrays without any obvious edges. Then I realized that spatially, the template has to be smaller than the reference, so to spatially convolve two images, one needs to be padded to 2x its size. The questions I have about that are 1) How is the correlation accuracy affected by padding, and what is the equivalent operation in Fourier space? $\endgroup$ – Will.Evo Oct 4 at 15:23
3
$\begingroup$

Figures that the same day I post a bounty I answer my own question.

The answer to this question is dead/speckle like pixels. For a fixed number of dead pixels of a given brightness, the smaller the relative shift between the two images, the fewer dead pixels that are needed to cause the (0,0) pixel to spike. It can take fewer brighter dead pixels to have the same effect as more dimmer ones. Lastly, the threshold between a strong (0,0) pixel and normal one is extremely tight in the number of dead pixels. Literally a change in just 10 dead pixels can massively increase the probability that the (0,0) pixel becomes a problem.

This problem can be solved by a combination of dead pixel finding/interpolation and applying a light Gaussian blur to the images to minimize speckle.

$\endgroup$

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.