# Centering zero frequency for Discrete Fourier Transform

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

• 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 2 '13 at 2:15

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: . It's Fourier transform looks like:

If you take the Fourier transform of the alternating image (), it results in a single point right at the center of the Fourier transform: . (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: , while convolving the fourier transform image with the rotation kernel (in the frequency domain) gives you: .

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

• 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 9 '13 at 15:28
• 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 9 '13 at 16:55
• Oh right, it's a sign flip, not a real multiplication. – endolith May 9 '13 at 18:00
• 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 2 '13 at 2:12

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).