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 try this, I could imagine something like this:

• Iterate over all the lines and calculate the slopes.

• Sort the lines by their slopes

• If any 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 estimate, 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.

• Now compare each set of parallel lines with each other set, and calculate if they intersect (possibly off-screen).

• 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 little by considering only lines with a minimum length, playing with the threshold for which lines are considered parallel, etc.

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence(AI) Tutorial. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.