从一组点中找到四边形的角点 [英] Find corner points of a Quadrilateral from set of points

问题描述

我尝试从一组点中获取四边形的角点.

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

• 这组点是有序的，并描述了轮廓
• 有时轮廓有些杂音(请参见第二张图片)
• 搜索的角点不必一定是给定点集中的点(请参见左下方的第三张图片)
• 搜索到的角点描述的是凸四边形，不一定是矩形

第二张图片有些极端，但我的观点集的质量"介于第一张图片和第二张图片之间.

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

首先，我想到了从1-360°和长度上制作直方图的方法，以下两点说明了这一点.四个最高峰将描述每条线的长度.但是由于失去顺序点，我只知道度数和长度或一条线，却不知道一条线属于哪个位置.

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?

推荐答案

您可以将其视为聚类问题，其中聚类的中心"实际上是直线.要计算聚类，您可以使用k-means算法:

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. 随机选择 4 对点.每条线都适合一条线，因此您有4条线穿过点云.
2. 重复进行，直到解决方案收敛为止:

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. 对于每个点，计算到 4 条线中每条线的距离.
2. 将点分配给与其距离最近的线相对应的桶.
3. 在4个桶中的每个点上添加4条新线(可以使用线性回归或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.

您也可以将其视为优化问题:选择4个点，以使差异的区域(四边形内部的白色区域和四边形外部的黑色区域)最小.通用优化算法可能会起作用，但是要使其快速运行，您需要一种合理的算法来计算面积.

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.

这篇关于从一组点中找到四边形的角点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！