FFT for line detection

Question

I am trying use the FFT in a different way then most people ask about. I want to be able to take a picture of a graph with regular repeating vertical lines, and to process the image to determine how far in pixels the lines are apart on average. I have tried canny edge detection and hough line detection and I don't think I can optimize the images enough to accurately detect only the lines I am interested in.

So, my attempt is to scan 10 lines of the picture and to accumulate the pixel values into bins corresponding to the pixel column. What results when you graph it is a very nicely appearing waveform. When I perform a DFT or FFT on this, I can find a peak that I believe should be the frequency of the line repetition. (This may be a faulty assumption)

My question is, what does this number correspond to? i.e. I think I am confused with what my sampling rate would be because it is in pixels. I do think that this is a valid use of the FFT, but am falling right here at the point when i think I should be successful.

As an example. I created a picture that is 300 pixels in width. There are 1 pixel width lines drawn at exactly 30 pixel intervals. I found 2 peaks, one at 75 and one at 225 (which seem symmetrical) for the real component. (I do not believe that the imaginary component should play in??) I know the lines are 30 pixels apart. How does the 75 and or 225 relate?

I am trying really hard to get this, and I am grateful for any help you could recommend. At this point, I am giving up on edge detection, and want to try this approach.

Thank you in advance.

Answer 1

You might look at trying Autocorrelation for this. Here is an SO answer describing how to perform autocorrelation with Matlab using FFTs. This could be extended for two dimensions.

I implemented your test case in numpy as follows:

a = np.zeros(300)
a[::30] = 1
plt.acorr(a, maxlags=50)

This gives the following plot:

As you can see, the peaks pop up at +/- 30.

Answer 2

If there are 10 vertical lines in your image, then an FFT of a full horizontal scan line (300 pix) should show some magnitude content around bin 10 or bin 11. Bin 75 out of 300 would indicate something is happening every 4th pixel, or so.

You really need to look at the magnitude of the FFT result, not just the "real" component (really the even component) because, if your grid lines are off-centered, the spectral content could show up as odd (thus "imaginary" in the FFT result).

Given real input to an FFT, the result bins above N/2 (above 150 in your case) just contain repeats of the same data except complex conjugated. So you can ignore them.

Answer 3

I don't have a lot of idea, but to make the $FFT$ visually intuitive, you could try centering the $FFT$ (multiplying each value in the $FFT$ by $(-1)^{(x+y)})$. Once you've done this, your DC component appears at the center, with the whole $FFT$ being symmetric around it.

I'm not very sure about this, but something tells me that the distance (in pixels) between the peak and the center would then indicate the periodicity. Once you have the periodicity, you can easily arrive at the distance between each object.