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

Question

我正在尝试将多条线拟合到 2D 中的点列表中。我的分数很低（16 或 32）。

这些点来自机器人的模拟环境，机器人的侧面附有激光测距仪。如果这些点位于一条线上，则意味着它们检测到了墙壁，如果不是，则意味着它们检测到了障碍物。我正在尝试检测墙壁并计算它们的交点，为此我认为最好的办法是在数据集上拟合线。

如果我们知道所有这些点都在一条线上或一条线上，那么将一条线拟合到一组点不是问题。

我的问题是我不知道如何检测哪些点集应该被分类以适合在同一条线上，哪些不应该被分类，对于每条线。另外，我现在连一条线上的点数都不知道，当然最好检测出可能最长的线段。

你将如何解决这个问题？如果我查看所有可能性，例如所有 32 个点的 5 个点组，那么它给出了 32 个选择 5 = 201376 个可能性。我认为尝试所有可能性并尝试为所有 5 元组拟合一条线需要太多时间。

那么什么会是一个更好的算法，它会运行得更快呢？我可以连接限制内的点并创建折线。但即使连接点也是一项艰巨的任务，因为即使在一条直线内边缘距离也会发生变化。

您是否认为可以对具有如此少条目数的离散数据集进行某种霍夫变换？

注意：如果这个问题太难解决，我正在考虑使用传感器的顺序并将其用于过滤。这样算法可能更容易，但如果墙前有一个小障碍物，它会分散线条的连续性，从而将墙分成两半。

Answer 1

像这样在嘈杂的点数据中查找线的一个好方法是使用 RANSAC。标准 RANSAC 用法是选择最佳假设（在本例中为 = 行），但您可以根据数据轻松选择最佳 2 或 4 行。看看这里的例子： http ://www.janeriksolem.net/2009/06/ransac-using-python.html Python 代码在这里 http://www.scipy.org/Cookbook/RANSAC

Answer 2

我要指出的第一件事是，您似乎忽略了数据的一个重要方面，即您知道哪些传感器（或读数）彼此相邻。如果您有 N 个激光传感器，您就知道它们用螺栓固定在机器人上的位置，如果您正在旋转传感器，您就知道进行测量的顺序（和位置）。因此，将点连接在一起以形成分段线性拟合（折线）应该是微不足道的。一旦有了这些对应关系，您就可以获取每组四个点，并确定它们是否可以仅通过 2 条线或其他东西有效地建模。

其次，众所周知，即使两条线与任意一组点找到全局最优拟合是 NP-Hard，因为它可以简化为 k-means 聚类，所以我不希望找到一个有效的算法。当我使用霍夫变换时，它是为了根据像素强度找到角点，理论上它可能适用于这类问题，但它只是一个近似值，可能需要大量工作才能弄清楚和实现.

我不想建议它，但看起来你可能会通过以稍微不同的方式看待问题而受益。当我使用激光测距仪进行自主导航时，我们通过将空间离散化为占用网格来解决这个问题，这是默认方法。当然，这只是假设墙壁只是另一个物体，这在 IMO 中并不是一个特别离谱的想法。除此之外，你能假设你有一张墙壁地图，而你只是试图找到障碍物并定位（找到机器人的姿势）吗？如果是这样，有大量关于这个问题的论文和技术报告。

Answer 3

解决方案的一部分可能是（这是我要开始的地方）调查机器人。诸如以下的问题：

1. 机器人转动/移动的速度有多快？
2. 机器人以什么间隔发射激光？
3. 当一个点被发现时，机器人在哪里？它的方向是什么？

这些问题的答案可能比试图找到一些仅依赖于点的算法更好地帮助你。尤其是当人数很少的时候。

这些问题的答案为您提供更多信息/要点。例如，如果您知道机器人在检测到一个点时处于特定位置，那么在机器人的位置和检测到的点之间没有任何点。这是非常有价值的。

Answer 4

对于所有的三元组，拟合一条穿过它们的线并计算该线偏离或不偏离这些点的程度。

然后只使用好的（小偏差）三元组，如果它们有两个共同点，则合并它们，并通过附加集合中（至少）两个点的所有三元组来增长集合。

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

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