如何将多条线放入数据点
hyp*_*not 11 algorithm matlab geometry curve-fitting computer-vision
我试图将多行匹配到2D中的点列表.我的分数很低(16或32).
这些点来自机器人的模拟环境,其侧面附有激光测距仪.如果点位于一条线上,则表示它们检测到一堵墙,如果不是,则表示它们检测到一个障碍物.我试图检测墙壁并计算它们的交点,为此我认为最好的想法是在数据集上拟合线条.
如果我们知道线上或线周围的所有点,则将一条线拟合到一组点不是问题.
我的问题是,我不知道如何检测哪些点应该被分类以适合同一行,哪些不应该为每一行.此外,我现在甚至没有一条线上的点数,而自然地,最好是检测最长的线段.
你会如何解决这个问题？如果我查看所有可能性,例如对于所有32个点的5个点的组,则它给出32个选择5 = 201376的可能性.我认为这需要花费太多时间来尝试所有可能性,并尝试在所有5元组中使用一条线.
那么什么是更好的算法会运行得更快？我可以在极限内连接点并创建折线.但即使连接点也是一项艰巨的任务,因为即使在一条线内边缘距离也会发生变化.
您是否认为可以对具有如此少数量条目的离散数据集进行某种Hough变换？
注意:如果这个问题太难解决,我正在考虑使用传感器的顺序并将其用于过滤.这样算法可以更容易,但如果墙前有一个小障碍物,它会分散线的连续性,从而将墙分成两半.
小智 6
在这样的噪声点数据中查找直线的一个好方法是使用 RANSAC。标准 RANSAC 用法是选择最佳假设（=本例中的线），但您可以根据数据轻松选择最佳的 2 或 4 条线。看看这里的例子： http://www.janeriksolem.net/2009/06/ransac-using-python.html Python代码可以在这里找到 http://www.scipy.org/Cookbook/RANSAC
我要指出的第一件事是，您似乎忽略了数据的一个重要方面，即您知道哪些传感器（或读数）彼此相邻。如果您有 N 个激光传感器，您就知道它们用螺栓固定在机器人上的位置；如果您正在旋转传感器，您就知道进行测量的顺序（和位置）。因此，将点连接在一起以形成分段线性拟合（折线）应该是微不足道的。一旦你有了这些对应关系，你就可以采用每组四个点，并确定它们是否可以仅通过 2 条线或其他东西来有效地建模。
其次，众所周知，即使两条线与任意点集找到全局最佳拟合也是 NP 困难的，因为它可以简化为 k 均值聚类，因此我不期望为此找到有效的算法。当我使用霍夫变换时，它是为了根据像素强度查找角点，理论上它可能适用于此类问题，但它只是一个近似值，可能需要相当多的工作来弄清楚和实现。
我不想建议它，但似乎您可以通过以稍微不同的方式看待问题而受益。当我使用激光测距仪进行自主导航时，我们通过将空间离散化为占用网格（这是默认方法）来解决这个问题。当然，这只是假设墙壁只是另一个物体，在我看来这并不是一个特别离谱的想法。除此之外，您是否可以假设您有一张墙壁地图，并且您只是想找到障碍物并定位（找到机器人的姿势）？如果是这样，就有大量关于这个问题的论文和技术报告。