Steve on Image Processing

Concepts, algorithms & MATLAB

This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English version of the page.

Fourier transforms, vertical lines, and horizontal lines 13

Posted by Steve Eddins,

A reader asked in a blog comment recently why a vertical line (or edge) shows up in the Fourier transform of an image as a horizontal line. I thought I would try to explain this using the simplest example I could think of.

I'll start with an image that is a constant black except for a single vertical line through the middle of it.

x = zeros(200, 200);
x(:, 100) = 1;
imshow(x)

Next I'll compute and display the log magnitude of the 2-D Fourier transform.

X = fft2(x);
imshow(fftshift(log(abs(X) + 1)), [])

There's the question in black and white, so to speak: Why is there a horizontal line in the 2-D Fourier transform?

Although I'm going to avoid equations and other complicated mumbo-jumbo in my answer, I do have to explain a couple of things about 1-D and 2-D Fourier transforms.

First, the magnitude of the 1-D Fourier transform an "impulse sequence" is a constant. An "impulse sequence" is a sequence that is nonzero only at one place, like this one:

x1 = [0 0 1 0 0]
x1 =

     0     0     1     0     0

The magnitude of the 1-D Fourier transform of x is constant:

abs(fft(x1))
ans =

    1.0000    1.0000    1.0000    1.0000    1.0000

Second, the magnitude of the 1-D Fourier transform of a constant sequence is an impulse. That is, the Fourier transform is nonzero only at one place.

x2 = [1 1 1 1 1]
x2 =

     1     1     1     1     1

abs(fft(x2))
ans =

     5     0     0     0     0

Finally, computing the 2-D Fourier transform is mathematically equivalent to computing the 1-D Fourier transform of all the rows and then computing the 1-D Fourier transforms of all the columns of the result. The order (row-first or column-first) doesn't actually matter.

Now let's go back to x, our 200-by-200 matrix with a vertical line down the middle of it. Each row of x is an impulse sequence:

plot(x(50,:))

So if we compute the Fourier transform of all the rows, they'll all be constant (in magnitude):

X_rows = fft(x, [], 2);
plot(abs(X_rows(50, :)))
ylim([0 2])

The next step in computing the 2-D Fourier transform is to compute the 1-D Fourier transforms of the columns of X_rows. But those columns are constant. Here's the 100th column of X_rows:

plot(abs(X_rows(:, 100)))
ylim([0 2])

As I said above, the Fourier transform of a constant sequence is an impulse. If you stack up all the resulting columns containing impulse sequences, the result looks like a horizontal line.

X = fft(X_rows, [], 1);
imshow(fftshift(log(abs(X) + 1)), [])

That's a step-by-step computational explanation. Let me leave you with more of a conceptual (that is, hand-wavy) explanation. Let's look at the input image and the 2-D Fourier transform side by side.

subplot(1,2,1)
imshow(x)
title('x')
subplot(1,2,2)
imshow(fftshift(log(abs(X) + 1)), [])
title('Log magnitude of fft2(x)')

You can think in terms of horizontal and vertical cross-sections. Each horizontal cross-section of x is an impulse sequence. The Fourier transform of an impulse sequence is constant, so horizontal cross-sections of the Fourier transform are constant.

Similarly, each vertical cross-section of x is a constant sequence. The Fourier transform of a constant sequence is an impulse sequence, so the vertical cross-sections of the Fourier transform are impulses. The impulses all line up each other, resulting in the appearance of a horizontal line.

Do these explanations work for you? Do you know of another way to think about it that makes a better explanation? Post your thoughts as comments below.


Get the MATLAB code

Published with MATLAB® 7.11

Note

Comments are closed.

13 CommentsOldest to Newest

Philipp replied on : 1 of 13
Maybe this is a little pedantic and doesn't matter for this example, but if you put a line at this position
x = zeros(200, 200);
x(:, 100) = 1;
you'll get a linear phase from -pi to pi after performing the fft2 - that's why you need abs() in this case. If you instead put the line at position 101 (center of image/k-space by convention), fftshift(fft2(x)) will produce a nice horizontal line with a positive real value of 200 - no need for abs() anymore.
Matteo replied on : 3 of 13
And this one is even better as it includes the topic of the day specifically, among other things: http://cns-alumni.bu.edu/~slehar/fourier/fourier.html
Alan B replied on : 4 of 13
I like to think about it in terms of directional energy content: the original image has no variation in the vertical direction, so you expect no energy in any of the nonzero vertical frequencies. More specifically, the vertical line is an impulse in a purely horizontal direction, so you expect a lot of energy in purely horizontal frequencies, and nowhere else. This does an equally decent job of explaining the transform of a line at an arbitrary orientation. Thinking about cascading two sets of 1D transforms, for an input of a diagonal line, is less than enlightening for me.
Steve replied on : 5 of 13
Alan—I like that. I agree that my explanation in terms of dimensional separability doesn't do much to help with intuition for lines at other angles. The "nice" thing about Fourier transforms is that there are approximately 1.6 million ways to interpret and explain every phenomenon. :-)
Rick replied on : 6 of 13
I'm a bit puzzled trying to remove some low frequency periodic noise from an image(s). It's caused by the power supply of fluorescent lighting, and so is 60 (120) Hz. The "waves" are horizontal, I guess caused by an out of sync scanning of the CCD. I can find the peaks, but when I mask them out with lines of various thicknesses and lengths I never get what seems to be an optimal result - there seems to be some higher frequency distortion after I do the inverse transform. In this case the highest peaks are around 8 pixels above and below the DC center (after fftshift) ; It seems like this would be a common problem - has anyone else found a good way to get rid of this signal? It seems straightforward - perhaps I'm missing something...?
Matteo replied on : 7 of 13
Hi Steve, Can you think of a similarly intuitive way to explain the uncertainty principle for Fourier pairs, i.e.: https://ccrma.stanford.edu/~jos/st/Uncertainty_Principle.html Or maybe recommend some readings. This is the best I found: http://www.ams.org/samplings/feature-column/fcarc-uncertainty Thank you
Steve replied on : 8 of 13
Matteo—This is a concept that I learned about 25 years ago. So it is already very familiar to me and therefore "intuitive." I haven't thought very much about how to explain it to others and do not have any immediate suggestions for you.
Teemu replied on : 9 of 13
I found the Fourier slice theorem especially insightful http://en.wikipedia.org/wiki/Projection-slice_theorem As discrete fourier transform is cyclical it can be 'easily' seen that all other angles except the angle perpendicular to the line have a constant function as their projection and thus their fourier transforms have amplitude only on DC.
Mehreen replied on : 10 of 13
Hi Steve, What kind of pre-processing techniques in the spatial domain do you think can make the DFT more useful, that is, more easy to interpret?
Steve replied on : 11 of 13
Mehreen—More useful for what? What information are you trying to get by looking at the Fourier transform?
Mehreen replied on : 12 of 13
I'm trying to determine the direction of text in an image, and I want to reduce the horizontal discontinuities(or vertical for vertical text), so that I can understand from the DFT what the text direction is..