Quadrilateral Shape Finding Algorithm

Question

I want to detect and COMPLETE all possible quadrilateral shapes from randomly located line segments!

The photo attached is an example, the lines might always appear in very different locations.

Anyone can point out any good algorithm for this?

• note the line segments are the output of Hough transform using opencv 2.4.2

The solution is to detect and predict the yellow quadrilateral

Answer 1

In the case of 11 line segments, you have 330 ways of choosing four segments. You could determine the likelihood of each combination making a quadrilateral, and grade that way.

It is possible to have a Hough transform detect forms other than lines, though it becomes harder to visualise as the accumulator space would require more than two dimensions. Circles can be found in three dimensions (midX, midY, radius), ellipses in four (I believe). I'm not sure exactly how few parameters you'd need to model a quadrilateral, and I believe that the performance of the Hough transform starts to drop off when you get higher than three dimensions. The accumulator space becomes so large that the noise ratio increases significantly.

Here's a related question that may have some interesting answers for you.

Let us know how you get on!

---

EDIT

I took a stab at this problem today, and uploaded my solution to GitHub. There is too much code to post here.

Here's a screenshot showing the output:

The solution I took is basically what I described above before this edit.

1. Find all combinations of four lines
2. Find all permutations of those four lines
3. Evaluate the likelihood that those four lines form a quadrilateral
4. Take the best match

The evaluation works by calculating a crude error score. This is the sum of two different types of error:

1. The deviation at each corner from 90 degrees (I use the sum of squared errors across all four corners)
2. When the line segments intersect within the line segment, it's likely not a valid corner

The second type of error could possibly be determined in a more robust way. It was necessary to find a solution for your sample data set.

I haven't experimented with other data sets. It may need some tweaking to make it more robust. I have tried to avoid using too many parameters so that it should be straightforward to adjust to a particular environment. For example to control sensitivity to occlusion, as seen in your sample image.

It finds the solution in about 160ms on my laptop. However I haven't made any performance optimisations. I expect that the methods of finding combinations/permutations could be significantly optimised if you needed this to run closer to real-time, as is often the case with computer vision experiments.

Answer 2

About any four lines can be completed to form a quadrilateral if you don't impose constraints on angles etc.

Image with potentially wrong quadrilaterals:

Probably you don't want to include quadrilaterals like the yellow one shown in my example. You should have constraints on angles, minimum/maximum size, aspect ratio and the degree of completion allowed. If 90 percent of the lines have to be added in order to form a complete quadrilateral this would probably not be a very good candidate.

I fear that you will have to test every possible combination of lines and apply a heuristic on them to give them points. Many points for angles close to 90 degrees (if what you want are rectangles), for completeness, for aspect ratios close to the expected one etc.

---

UPDATE

Using a point system has advantages over just applying strict rules.

• A point system allows you to evaluate the quality of quadrilaterals and to take the best one or to reject a quadrilateral completely.
• The good quality of one property can help outweigh the poor quality of another one.
• It allows you to give different weights to different properties.

Let's say you have a strict rule (in pseudo code):

(angles == 90 +/- 10 degrees) && (line_completeness>50%) 

This would work, can however lead to situations like angles == 90 +/- 1 degree) && (line_completeness == 45%). According to the rules this quadrilateral would not pass because of the poor line completeness; however, the quality of the angles is exceptional, still making it a very good candidate.

It is better to give points. Say 20 points for an angle of exactly 90 degrees, falling to 0 points for an angle of 90 +/-15 degrees and 10 points for complete lines towards 0 points for lines complete by only 25% for instance. This makes angles more important than line completeness and also creates softer conditions for a problem that does not have absolute rules.