如何将多条线拟合到数据点
我正在尝试将多条线拟合到二维点列表中。我的积分很少（16 或 32）。
这些点来自侧面附有激光测距仪的机器人的模拟环境。如果这些点位于一条线上，则意味着它们检测到墙壁，如果不是，则意味着它们检测到障碍物。我正在尝试检测墙壁并计算它们的交点，为此我认为最好的想法是在数据集上拟合线条。
如果我们知道所有这些点都位于一条线上或一条线上，那么将一条线拟合到一组点就不是问题。
我的问题是，我不知道如何检测每条线的哪些点集应该分类为拟合在同一条线上，哪些点不应该分类。另外，我现在甚至不知道一条线上的点数，而自然地检测最长的线段是最好的。
你会如何解决这个问题？如果我查看所有的可能性，例如对于所有 32 个点的 5 个点组，那么它给出 32 选择 5 = 201376 种可能性。我认为尝试所有可能性并尝试将一条线拟合到所有 5 元组需要太多时间。
那么什么是更好的算法什么会运行得更快呢？我可以连接限制内的点并创建折线。但即使连接这些点也是一项艰巨的任务，因为即使在一条线上，边缘距离也会发生变化。
您认为可以在条目数量如此少的情况下对离散数据集进行某种霍夫变换吗？
注意：如果这个问题太难解决，我正在考虑使用传感器的顺序并将其用于过滤。这样，算法可能会更容易，但如果墙前面有一个小障碍物，它会分散线路的连续性，从而将墙分成两半。
I am trying to fit more than one line to a list of points in 2D. My points are quite low in number (16 or 32).
These points are coming from a simulated environment of a robot with laser range finders attached to its side. If the points lie on a line it means that they detected a wall, if not, it means they detected an obstacle. I am trying to detect the walls and calculate their intersection, and for this I thought the best idea is to fit lines on the dataset.
Fitting one line to a set of points is not a problem, if we know all those points line on or around a line.
My problem is that I don't know how can I detect which sets of points should be classified for fitting on the same line and which should not be, for each line. Also, I don't even now the number of points on a line, while naturally it would be the best to detect the longest possible line segment.
How would you solve this problem? If I look at all the possibilities for example for groups of 5 points for all the 32 points then it gives 32 choose 5 = 201376 possibilities. I think it takes way too much time to try all the possibilities and try to fit a line to all 5-tuples.
So what would be a better algorithm what would run much faster? I could connect points within limit and create polylines. But even connecting the points is a hard task, as the edge distances change even within a single line.
Do you think it is possible to do some kind of Hough transform on a discrete dataset with such a low number of entries?
Note: if this problem is too hard to solve, I was thinking about using the order of the sensors and use it for filtering. This way the algorithm could be easier but if there is a small obstacle in front of a wall, it would distract the continuity of the line and thus break the wall into two halves.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
在这样的噪声点数据中查找直线的一个好方法是使用 RANSAC。标准 RANSAC 用法是选择最佳假设（=本例中的线），但您可以根据数据轻松选择最佳的 2 或 4 条线。看看这里的例子：
http://www.janeriksolem.net/2009/06/ransac-using -python.html
Python 代码可在此处获取
http://www.scipy.org/Cookbook/RANSAC
A good way to find lines in noisy point data like this is to use RANSAC. Standard RANSAC usage is to pick the best hypothesis (=line in this case) but you can just as easy pick the best 2 or 4 lines given your data. Have a look at the example here:
http://www.janeriksolem.net/2009/06/ransac-using-python.html
Python code is available here
http://www.scipy.org/Cookbook/RANSAC
我要指出的第一件事是，您似乎忽略了数据的一个重要方面，即您知道哪些传感器（或读数）彼此相邻。如果您有 N 个激光传感器，您就知道它们用螺栓固定在机器人上的位置；如果您正在旋转传感器，您就知道进行测量的顺序（和位置）。因此，将点连接在一起以形成分段线性拟合（折线）应该是微不足道的。一旦你有了这些对应关系，你就可以采用每组四个点，并确定它们是否可以仅通过 2 条线或其他东西来有效地建模。
其次，众所周知，即使两条线与任意点集找到全局最佳拟合也是 NP 困难的，因为它可以简化为 k 均值聚类，因此我不期望为此找到有效的算法。当我使用霍夫变换时，它是为了根据像素强度查找角点，理论上它可能适用于此类问题，但它只是一个近似值，可能需要相当多的工作来弄清楚和实现。
我不想建议它，但似乎您可以通过以稍微不同的方式看待问题而受益。当我使用激光测距仪进行自主导航时，我们通过将空间离散化为占用网格<来解决这个问题/a>，这是默认方法。当然，这只是假设墙壁只是另一个物体，在我看来这并不是一个特别离谱的想法。除此之外，您是否可以假设您有一张墙壁地图，并且您只是想找到障碍物并定位（找到机器人的姿势）？如果是这样，就有大量关于这个问题的论文和技术报告。
The first thing I would point out is that you seem to be ignoring a vital aspect of the data, which is you know which sensors (or readings) are adjacent to each other. If you have N laser sensors you know where they are bolted to the robot and if you are rotating a sensor you know the order (and position) in which the measurements are taken. So, connecting points together to form a piecewise linear fit (polylines) should be trivial. Once you had these correspondances you could take each set of four points and determine if they can be modeled effectively by only 2 lines, or something.
Secondly, it's well known that finding a globally optimal fit for even two lines to an arbitrary set of points is NP-Hard as it can be reduced to k-means clustering, so I would not expect to find an efficient algorithm for this. When I used the Hough transform it was for finding corners based on pixel intensities, in theory it is probably applicable to this sort of problem but it is just an approximation and it is probably going to take a fair bit of work to figure out and implement.
I hate to suggest it but it seems like you might benefit by looking at the problem in a slightly different way. When I was working in autonomous navigation with a laser range finder we solved this problem by discretizing the space into an occupancy grid, which is the default approach. Of course, this just assumes the walls are just another object, which is not a particularly outrageous idea IMO. Beyond that, can you assume you have a map of the walls and you are just trying to find the obstacles and localize (find the pose of) the robot? If so, there are a large number of papers and tech reports on this problem.
解决方案的一部分可能是（这是我要开始的地方）调查机器人。诸如以下问题：
这些问题的答案可能比试图找到一些仅依赖于点的算法更好地帮助您。尤其是当数量如此之少的时候。
这些问题的答案为您提供更多信息/要点。例如，如果您知道机器人在检测到一个点时处于特定位置，则机器人的位置和检测到的点之间不存在任何点。这是非常有价值的。
A part of the solution could be (it's where I would start) to investigate the robot. Questions such as:
The answers to these questions might help you better than trying to find some algorithm that relies on the points only. Especially when there are so very few.
The answers to these questions give you more information/points. E.g., if you know the robot was at a specific position when it detected a point, there are no points in between the position of the robot and the detected point. that is very valuable.
对于所有三元组，拟合一条穿过它们的线，并计算该线偏离这些点的程度。
然后仅使用好的（偏差较小）三元组，如果它们有两个共同点，则将它们合并，并通过附加集合中具有（至少）两个点的所有三元组来增长集合。
作为最后一步，您可以放弃尚未与任何其他合并但具有一些公共元素且结果集至少有 4 个元素的三元组（以摆脱交叉线），但保留那些未与任何其他人合并的三元组，但与集合没有任何共同元素（这将在示例右侧产生三个点作为其中一条线）。
我认为这会在第二步中找到左线和底线，在第三步中找到右线。
For all the triads, fit a line through them and compute how much the line is deviating or not from the points.
Then use only the good (little-deviating) triads and merge them if they have two points at common, and the grow the sets by appending all triads that have (at least) two points in the set.
As the last step you can ditch the triads that haven't been merged with any other but have some common element with result set of at least 4 elements (to get away with crossing lines) but keep those triads that did not merge with anyone but does not have any element in common with sets (this would yield three points on the right side of your example as one of the lines).
I presume this would find the left line and bottom line in the second step, and the right line the third.