detecting parallel lines in an image using Frequency domain

Question

I have an image with straight lines. I want to check if the lines are parallels using frequency domain. I'm doing fft on the image and i get the transform image.

Does anyone know how can i use the transform image for finding if the lines are parallel?

Answer 1

So here are the two cases, using either some random angle or the same angle, of 2 lines of variable lengths, and their absolute value ffts.

So there are many ways you can tell if they are parallel or not by looking on their fft, I'll give a hint in one of the easier directions, start from the center of the fft'ed image...

Answer 2

If you only have 2 lines than FFT is a bad idea. It is slow and complex.

The simplest implementation is to smooth the image. Calculate gradients angles (atan2(gradY,gradX)) and than just put them in histogram. If you have one clear peak - lines are parallel. Otherwise they are not. From the histogram you also know the angle of each line (local maximum represents a line).

The fastest running time would be using connected components style.

1. Search the black image in a loop until you find a white pixel. This is a beggining of a line
2. recursively traverse pixels neighbors until you find the most distant pixel. this is the end of the line
3. When you know the starting point and the ending point you can calculate the slope of each line by atan2(endY-startY,endX-startX). Now you compare analytically the lines. If their slopes have difference of more than, say 0.1 of radians (5 degrees) in difference than lines are not regarded as parallel. This solution works for any amount of lines and it also gives the the list of all the pixels of each line + mathematical equation of the line as AX+BY+C = 0.

If you still insist on FFT I advise to rotate the original image or the FFT image so at least one line would be parallel to Y axis (FFT's representation is on X axis). Than it would be easy to check if the second line is parallel. If they are parallel than they are both aligned to y axis and than means that entire FFT transform lies on X axis. Just check that all the pixels of FFT above the few center rows are zeros. If not that means that lines are not parallel since the first line lies on X axis in FFT image and the second one goes up and down. P.s. I didn't explain how to rotate the image so at least one line aligns with Y axis. If you do it on the original image, just calculate the orientation (angle) of gradients, find the maximal value and rotate the image by (minus maximal value in degrees). On FFT image you can do the same, since two lines in the image still look like 2 lines in FFT.

Important note: Your questions got many inaccurate answers from other people. Here are some corrections

1. Do not use Hough or Radon transform! It is relatively slow and is a complete overkill for your easy task of only 2 lines.
2. When you use FFT you actually can know the location of the lines. Until now we used the amplitude image of FFT but there is also the phase image and the location of the lines is encoded in the phase image.

In concludion: I advise you to implement the solution I denoted as the fastest running time. If an image has N pixels you will do on average O(N) steps while only the FFT takes at least O(N*log(N)) steps.