12

I am working on a image processing application which uses a discrete fourier transform to implement blurring/sharpening. The application is more or less working, but something about the mechanics is still confusing to me.

In particular, it is how the process of centering the zero frequencies is being done.

The example I have seen preprocesses the input image (of greyscale intensities) by multiplying it with a matrix of size equal to the input image, whose values are $(-1)^{x+y}$, where $x$ is the row, $y$ is the column, so a pattern alternating $1$ and $-1$

According to the notes, this is equivalent of swapping the quadrants of matrix by flipping across the $x$ and $y$ axis.

I understand why this is done, and I would like to stress I understand I have my code/Fourier stuff working, I just don't understand why multiplying the input matrix by 1/-1 ends up centering the zero frequency component around 0.

Thanks

dizzy
  • 243
  • 1
  • 2
  • 6
  • You also can find some reference in Chapter 4, 4.6-Implementation from Digital Image Processing by Gonzalez( I have second edition). Hope it helps. – hakunami Nov 02 '13 at 02:15

2 Answers2

21

Oh! What a cool trick! It works because of the convolution theorem (i.e., multiplication in the spatial/time domain is equivalent to convolution in the frequency domain.)

It's not flipping across the $x$ and $y$ axis, it is rotating the image of the Fourier transform (think of shifting halfway around a cylinder). The trick here is that alternating -1,1 in the spatial domain is a signal with the highest frequency. So the Fourier transform of that image is a single point in the frequency domain. Convolving by a single point is equivalent to shifting (rotating) the image by the offset of the point from the zero frequency.

Here is a test image: test image. It's Fourier transform looks like: fourier transform of test image

If you take the Fourier transform of the alternating image (checkerboard image), it results in a single point right at the center of the Fourier transform: enter image description here. (Recall we haven't done our rotation yet, so the center of the fourier transform is the high frequencies and the low frequencies are at the corners still.) But this is the "rotation kernel!" Convolving with this rotation kernel moves everything down and to the right (but things that fall off the bottom right rotate into the top left.)

Convolving the original image with the rotation kernel (in the image domain) gives you: convolved image, while convolving the fourier transform image with the rotation kernel (in the frequency domain) gives you: rotated fourier transform.

And we can check that multiplying the testimage by the checkerboard in the image domain gives multiplication image, which has a fourier transform of: again rotated fourier transform.

Wandering Logic
  • 1,531
  • 11
  • 20
  • I'm confused. This is using convolution to implement an fftshift-like function? Isn't it computationally cheaper to just rearrange the 4 quadrants directly? – endolith May 09 '13 at 15:28
  • 2
    There is no direct convolution here. This is using pixel-wise multiplication in the image domain to get the equivalent of a convolution in the fourier domain. Yes, fftshift is not very expensive, but this trick might have better cache behavior. The pixelwise multiplication is actually just flipping the sign of every other pixel. So easy to vectorize, the write of the read-modify-write is a guaranteed cache hit, and it is easy for the processor to prefetch the reads. – Wandering Logic May 09 '13 at 16:55
  • Oh right, it's a sign flip, not a real multiplication. – endolith May 09 '13 at 18:00
  • 1
    Why the Fourier transform of test image(the second image) looks like that? I actually see two image, black one over the other. – hakunami Nov 02 '13 at 02:12
11

Wandering Logic's answer is correct and detailed. Just thought you'd want to see some math instead of pictures:

If you look at the 1D case, you are multiplying the input by $(-1)^k = e^{j\omega}$ where the frequency $\omega$ happens to be $2\pi (k/2)$. I.e., the multiplication shifts the spectrum of the signal by half the sampling frequency.

The effect is that the zero frequency - which was at index 0 before - is now at half the image width (or height, depending on whether you multiply the columns or the rows).

nimrodm
  • 886
  • 1
  • 6
  • 10