logo标签列表

如何将多条线拟合到数据点

algorithmmatlabgeometrycomputer-visioncurve-fitting
11

我试图将多条线段拟合到2D点列表中。我的点数量非常少（16或32个）。这些点来自于带有激光测距仪的机器人模拟环境。如果这些点位于一条直线上，这意味着它们检测到了一堵墙；否则，它们检测到了一个障碍物。我正在尝试检测墙壁并计算它们的交点，为此我认为最好的想法是在数据集上拟合线段。

对一组点进行一次线性拟合不是问题，如果我们知道所有这些点都在一条线上或周围。

我的问题是我不知道如何检测应将哪些点集归类为适合在同一条线上拟合，以及每条线上的点数。此外，我甚至不知道线上的点数，而自然地，最好检测到最长可能的线段。

您会如何解决这个问题？例如，如果我查看所有32个点的5点组的所有可能性，则会得到32个选择5 = 201376种可能性。我认为尝试所有可能性并尝试将线条拟合到所有5元组需要太多时间。

那么什么样的更好的算法会运行得更快呢？我可以连接限制内的点并创建折线。但是即使连接这些点也很困难，因为边缘距离甚至在一条线上也会发生变化。

您是否认为可以对离散数据集进行Hough变换？请注意：如果此问题太难解决，我正在考虑使用传感器的顺序进行过滤。这样，算法可能会更简单，但是如果墙前有一个小障碍物，它将分散线条的连续性，从而将墙壁分成两半。

sensors

你会期望这个点集示例有多少行代码呢？我可以“看到”三堵墙：一面在左边（4个点），一面在底部（6个点），还有一面在右边（3个点）。我无法确定右侧墙壁的最低点是否也属于底部墙壁。我也无法确定顶部的2个点是否形成了一堵墙，或者左侧的一个点是否是左侧墙壁的一部分，右侧的一个点是否与中间的点形成了一堵墙。也许“在限制范围内连接点并创建折线”的方法可以解决问题，但对于这样一个小的点集来说，很难确定适当的限制。 - kol
我可以过滤至少三个点在一堵墙上。这将使此示例具有三面墙。 - hyperknot
这些墙壁是否总是平行或垂直于彼此？ - kol
是的，这是一个矩形房间。 - hyperknot
@zsero，你找到解决方案了吗？这就是我在寻找的。 - mudin
4个回答
6
2
我要指出的第一件事是，你似乎忽略了数据的一个重要方面，即你知道哪些传感器（或读数）相邻。如果你有N个激光传感器，你知道它们固定在机器人上的位置，如果你旋转传感器，你知道测量值被采取的顺序（和位置）。因此，将点连接起来形成分段线性拟合（折线）应该是微不足道的。一旦你有了这些对应关系，你可以取每组四个点，并确定它们是否可以通过只用两条线或其他方法有效地建模。

其次，众所周知，即使是对于任意一组点找到两条线的全局最优拟合，也是NP-难问题，因为它可以归约为k-means聚类，所以我不会指望找到这样一个高效的算法。当我使用Hough变换时，是为了根据像素强度找到角落，在理论上它可能适用于这种问题，但它只是一种近似方法，可能需要大量的工作来理解和实现。

我不太愿意这样建议，但似乎您可以从稍微不同的角度来看待这个问题。当我在使用激光测距仪进行自主导航时，我们通过将空间离散化为占据网格来解决了这个问题，这是默认的方法。当然，这只是假设墙壁只是另一个物体，这在我看来并不是一个特别荒谬的想法。除此之外，您能否假设您拥有墙壁的地图，并且只是试图找到障碍物和定位（找到机器人的姿态）？如果是这样，那么有大量关于这个问题的论文和技术报告。
你认为我应该使用SLAM吗？我知道房间的尺寸，而且它是矩形的。此外，我可以将虚拟1D LIDAR附加到虚拟机器人上。在这种情况下，你认为我应该使用什么？ - hyperknot
所以，如果你知道房间是矩形的，并且你有尺寸，你就有了一张地图。一旦你有了地图，你可以通过许多方式确定机器人的位置，最常见的是卡尔曼滤波器或蒙特卡罗定位（粒子滤波器）。详细信息请参阅标准教科书：（http://www.probabilistic-robotics.org/）。一旦你有了机器人相对于墙壁的位置，你可以通过找到不匹配地图的点来检测障碍物。 - fairidox
此外，SLAM 是用于无需地图进行定位的算法的通用术语，它们可以非常复杂。由于您已经拥有一张地图，我不建议选择这种方法。 - fairidox
寻找全局最优的拟合线，即使是对于任意一组点来说，也是NP-Hard问题，因为它可以归约为k-means聚类。请问您能解释一下您的推理吗？我不明白您所指的归约方式，也不确定您具体指的是哪种k-means聚类的表述。另外，您是指“从...归约”吗？ - D.W.
1
解决方案的一部分可能在于（这是我会开始的地方）调查机器人。例如以下问题：
  1. 机器人转动/移动的速度有多快？
  2. 机器人激光射击的间隔是多少？
  3. 当找到一个点时，机器人在哪里以及它的朝向如何？
这些问题的答案可能比仅仅依赖于点的算法更有用。特别是当点非常少的时候。
这些问题的答案为您提供更多的信息和点。例如，如果您知道机器人在检测到一个点时处于特定位置，则该位置和被检测到的点之间没有其他点。这是非常有价值的。
问题在于所有传感器都有很多噪音（即使在模拟世界中），轮子编码器也不能真正用于跟踪它行驶/旋转了多少。我正在尝试获取角落，因为那样我就会在房间里有一组固定点。 - hyperknot
我的回答的主要内容是，你应该利用你所拥有的每一个信息比特/字节，包括噪音、对房间形状的任何了解。如果有太多的噪音，你永远不会确定；事实上，你甚至无法根据数据控制机器人或知道它的位置。 - Emond
1

对于所有的三元组，拟合一条直线穿过它们，并计算该直线与点之间的偏差程度。

然后仅使用好的（偏差小的）三元组，如果它们有两个共同点，则将它们合并，并通过添加所有至少有两个点在集合中的三元组来扩展集合。

作为最后一步，您可以放弃那些没有与任何其他三元组合并但与结果集中至少有4个元素的某些公共元素的三元组（以避免交叉线），但保留那些没有与任何集合共享元素但也没有与任何集合共享元素的三元组（这将产生您示例中右侧的三个点作为其中一条线）。

我认为这将在第二步中找到左边和底部的线，第三步中找到右边的线。

如果“线”是一个轻微的曲线，这个过程也会找到那条曲线。这是一个问题，是否对您有益。如果不是，您可以在合并期间进行更多的测试。 - user1046334
关于“从哪里开始”，我认为你应该合并两个三角形，得到最短和最直的线（可以尝试不同参数来构建这两个属性的分数，因为你不能保证一开始就拥有它们），然后将其合并到这个集合中，直到无法再合并，然后用剩下的三角形重复这个过程。 - user1046334
我的问题是我不确定它是否过于计算密集。在MATLAB中测试所有这些成千上万的可能性可能不适合快速操作。 - hyperknot
这应该是O(n^3)，太多了吗（也许更多，但我认为它仍然可以是多项式的）？当然，你应该修剪...我说的第一步是修剪所有不够好的三元组。也许试一下，你会看到它的表现如何。 - user1046334
我不知道为什么，在MATLAB中这个程序可能无法实时运行。在C++中，由于计算相对简单，也许可以实时运行。我认为霍夫变换可能是一个更好的选择。 - hyperknot
如果你担心性能问题，可以制作一些变体...比如不需要先计算三角形，而是从最近的两个点开始，逐个添加点直到线条足够平滑。这应该会更快（但比用三角形更麻烦，我认为；如果我使用的两个点都失败了，那该往哪里继续；如果我删除所有点，可能会出现大型线路交叉但交叉点消失的问题...） - user1046334
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接