title: Cross Correlation in numpy, with FFT - strange result?
body: <p>I'm attempting to perform a cross-correlation of two images using numpy's FFT. </p>
  
  <p>As far as I'm aware, we have that the cross-correlation of two images is equal to the inverseFFT of the multiplication of - Fourier transform of image A, and the complex conjugate of the Fourier transform of image B.</p>
  
  <p>Thus, I have the following code:</p>
  
  <pre><code>img1 = cv2.imread("...jpg")
  img1 = cv2.cvtColor(img1, cv2.COLOR_RGB2GRAY)
  fft1 = numpy.fft.fft2(img1)
  
  # I'm cross correlating the same image with itself
  fft2 = fft1.copy()           
  fft2 = numpy.conj(fft2)
  
  #Element wise multiplication
  result = fft1*fft2           
  result_img = numpy.fft.ifft2(result)
  result_img = numpy.abs(result_img) #Remove complex values
  
  #Following images are attached
  image_shifted = normalize(numpy.fft.fftshift(result_img))
  image_nonshifted = normalize(result_img)
  </code></pre>
  
  <p>However, my results are rather strange. In order to obtain what I believe to be the actual correlation-result I have to fftshift the result. Here are some example images:</p>
  
  <p><a href="http://i.stack.imgur.com/rxFte.png" rel="nofollow">Image, not shifted, you can see bright parts at each corner</a></p>
  
  <p><a href="http://i.stack.imgur.com/4aJu8.png" rel="nofollow">Image, shifted, looks much more like what an auto-correlation result should look like (centre point is maximal)</a></p>
  
  <p>I'm not sure if my code, or expected mathematics is wrong, but I can't quite figure out what's going on!</p>
  
  <p>Any help would be greatly appreciated, thanks.</p>