Detecting quadrilateral shapes from random set of lines segments

Question

the image attached is the output of Hough Transform of Opencv 2.4.2

Could you please advise me with the best algorithm to detect the best Quadrilateral (not always rectangular) shape from these line segments

even though some corners will reside outside the image boundaries, I still need to detect them

Many Thanks

Answer 1

Without having time to actually try this, I could image something like this:

1. Iterate over all the lines and calculate the slopes.
2. Sort the lines by their slopes
3. If two lines have a roughly similar slope, they are either parallel or the same line with a gap in it (e.g. the almost vertical lines on the left). To figure out which, calculate where they will intercept the x or y axis. If they intercept at the same point, they are the same line and should be merged into one line. If not, put them in a set of (roughly) parallel lines.
4. Compare each set of parallel lines with each other set, and calculate if they intersect (possibly off screen).
5. Apply some application-dependent criterium to pick the best.

The running time of this depends a lot on the number of detected lines and the number of sets of parallel lines. You could improve a bit by considering only lines with a minimum length, playing with the threshold for which lines are considered parallel, etc.