Centering zero frequency for Discrete Fourier Transform

Question

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

Answer 1

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

Answer 2

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