Find corner points of a Quadrilateral from set of points

Question

I try to get the corner points of a Quadrilateral from set of points.

• The set of points are ordered and describe an outline
• Sometimes the outline has some noise (see 2nd picture)
• The searched corner points don't have to be points out of the given set of points (see 3rd picture bottom left)
• The searched corner points describe a convex Quadrilateral, not necessarily a rectangle

The second picture is a bit extreme, but the "quality" of my set of points lay between the frist and the second picture.

First I thought of making an Histogram from over 1-360° and length, two following points describe. The four highest peaks would describe the length of each line. But with that iam losing the order points, just know about degree and length or a line and don't know which position a line belongs to.

Then i thought of merging two following lines if they have more or less the same degree, but i don't know how to handle the noise here or predicting a corner.

Does anyone know of an Algorithm which handle this problem or something similar?

Answer 1

You can treat this as a clustering problem, where the cluster "centers" are actually straight lines. To compute the clustering you can use a k-means algorithm:

1. Pick 4 random pairs of points. Fit a line to each, so you have 4 lines going through the point cloud.
2. Repeat until the solution seems to have converged:
   1. For each of the points, compute the distance to each of the 4 lines.
   2. Assign the point to a bucket that corresponds to the line it lies closest to.
   3. Fit 4 new lines to the points in each of the 4 buckets (you can use linear regression or SVD)

To improve the first step you could take your idea of taking a histogram over the angles, and assign each point initially to a bucket that corresponds to the closest peak. Then fit lines to the four buckets, and start iterating.

You can also treat this as an optimization problem: pick 4 points so that the area of the difference (white area inside and black area outside of the quadrilateral) is smallest possible. Generic optimization algorithms probably work, but to make it fast you need a reasonable algorithm to compute areas.