Take an image:
Cross-correlating it with impulse should yield itself, and cross-correlating with itself should peak at center. Key points:
- The operating kernel must be centered about $t=0$. For a discrete sequence $h$ of length $N$, under the FFT, this means $h$, and the second-half of samples are of negative time: $h[n > N/2]$
- Assuming inputs are normal images, this means time-centering the "template" image: note $x \star h \neq h \star x$.
fft2(x) == fft(fft(x, axis=0), axis=1)
cross correlation between 2 images which I read in 2 vectors, both of them uni-dimensional.
That's a problem since the time-centering step isn't straightforward to replicate on a flattened image, I'm unsure how it'd be done. This answer will assume a 2D array, so you can just reshape it into 2D and then back. Finally, you might want to look into padding and boundary effects.
Putting it together, here's cross-correlation of COVID with image-centered unit impulse, and with itself:
additionally, we move it and its flipped copy, and check that the more intense dot spots the unflipped version; note boundary effects:
Centering / performance note
Answer assumes we're after circular cross-correlation with no padding, and $x$ and $h$ are "normal" (non-DFT centered) images. With padding/unpadding, the most compute efficient route may be different.
Complete cross-correlation, with padding, is implemented here.
This answer was subject of controversy. If readers aren't sure which answer to use, I encourage reading responses to the followup, where I've shown further demos and offered 1000 bounty to invalidate this answer, instead of trusting the votes.
import numpy as np
import matplotlib.pyplot as plt
from numpy.fft import fft, ifft, fft2, ifft2, ifftshift
from PIL import Image
def cross_correlate_2d(x, h):
h = ifftshift(ifftshift(h, axes=0), axes=1)
return ifft2(fft2(x) * np.conj(fft2(h))).real
# load image as greyscale
x = np.array(Image.open("covid.png").convert("L")) / 255.
# make kernels
h0 = np.zeros(x.shape, dtype=x.dtype)
h0[h0.shape//2, h0.shape//2] = 1
h1 = x.copy()
out0 = cross_correlate_2d(x, h0)
out1 = cross_correlate_2d(x, h1)
plt.imshow(out0); plt.xticks(); plt.yticks(); plt.show()
plt.imshow(out1); plt.xticks(); plt.yticks(); plt.show()
second example, same imports:
x = np.array(Image.open("covid_target.png" ).convert("L")) / 255.
h = np.array(Image.open("covid_template.png").convert("L")) / 255.
# blank regions default to `1`, undo that
x[x==1] = 0
h[h==1] = 0
out = cross_correlate_2d(x, h)
plt.imshow(out, cmap='turbo'); plt.xticks(); plt.yticks(); plt.show()