15

我正在寻找一种算法来将任意矩形与无序的点集进行最佳拟合。具体来说，我正在寻找一个矩形，其中点到任何一个矩形边缘的距离之和最小化。我发现了很多最适合的线、圆和椭圆算法，但没有一个适合矩形。理想情况下，我想要 C、C++ 或 Java 的东西，但对语言并不那么挑剔。

输入数据通常由位于或靠近矩形的大多数点组成，并带有一些异常值。数据的分布将是不均匀的，不太可能包括所有四个角。

4

4 回答 4

3

以下是一些可能对您有所帮助的想法。

我们可以估计一个点是在边上还是在角上，如下所示：

  1. 收集点的 n 个近邻
  2. 计算点的质心
  3. 计算点的协方差矩阵如下：
    1. 从...开始Covariance = ((0, 0), (0, 0))
    2. 对于每个点计算d = point - centroid
    3. Covariance += outer_product(d, d)
  4. 计算协方差的特征值。（例如使用 SVD）
  5. 分类点：
    • 如果一个特征值很大而另一个非常小，我们可能处于边缘
    • 否则我们应该在拐角处

提取所有角点并进行分割。选择条目最多的四个段。这些线段的质心是矩形角的候选对象。

计算两个相对侧的归一化方向向量并计算它们的平均值。计算另外两个对边的平均值。这些是平行四边形的方向向量。如果您想要一个矩形，请计算与其中一个方向的垂直向量，并使用另一个方向向量计算平均值。那么矩形的方向是平均向量和垂直向量。

为了计算角点，您可以将候选对象投射到它们的方向上并移动它们，使它们形成矩形的角点。

于 2013-07-03T09:27:19.607 回答
1

这是一个总体思路。用小单元格制作一个网格；为每个不太空的单元格计算最佳拟合线（计算立即为1，不涉及搜索）。连接相邻的单元格，同时确保标准偏差正在改善/不会恶化太多。因此，我们检测到四个边和四个角，并将我们的点分成四组，每组属于四个边之一。

接下来，我们扔掉角落的单元格，用真正的矩形代替四个近似线，然后做一些爬山（或其他什么）。对于这种情况，最佳拟合线的计算可能会增加，因为两条线是平行的，并且我们已经将我们的点分成四组（对于给定的矩形，我们知道两个相对边之间的 delta-y (暂时取水平面），所以我们只需将这个 delta-y 添加到y下一组点的 s 并进行计算）。

最初的矩形网格可以用条纹（比如垂直）代替。然后，至少一半的条纹将有两个明显的点分组（通过将每个条纹用水平分割线划分为单元格来找到它们）。

1对于一条线，最小化数据点 {x i ,y i } 到该线Y = a*X+b的垂直距离的平方和。这对于和是直接可解的。要获得更多垂直线，请翻转 X 和 Y。ab

PS我将问题解释为最小化每个点到矩形最近边的垂直距离的平方和，而不是最小化矩形的所有边。

于 2013-07-03T13:19:55.823 回答
1

最佳拟合线的想法是计算点与线 y=ax+b 之间的垂直距离。然后，您可以使用微积分找到最小化距离平方和的 a 和 b 的值。选择平方而不是绝对值的原因是因为前者在 0 处可微。

如果您要对矩形尝试相同的方法，您会遇到这样的问题，即到矩形边的距离的平方是具有 8 个不同部分的分段定义函数，并且当这些部分在长方形。
到矩形的距离不同的8个区域
为了继续，您需要决定一个函数，该函数测量一个点与一个处处可微的矩形的距离。

于 2013-07-03T14:47:40.483 回答
0

我不完全确定，但从你的观点来看，你可能会在 PCA 上玩前 2（3？）个维度。在大多数情况下，它的工作速度相当快。

于 2016-09-20T19:58:50.977 回答