如何将多条线拟合到数据点 [英] How to fit more than one line to data points

问题描述

我正在尝试将多条线拟合到2D点列表中.我的分数非常低(16或32).

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.

您将如何解决此问题?如果我查看所有可能性，例如针对所有32个点的5个点的组，那么它给出了32个选择5 = 201376可能性.我认为花太多时间尝试所有可能性并尝试将一条线适合所有5元组.

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.

推荐答案

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

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.

其次，众所周知，即使对于任意点集的两条线也能找到全局最优拟合是NP-Hard的，因为它可以简化为k-均值聚类，所以我不希望找到一种高效的算法来求解这.当我使用霍夫变换时，它是基于像素强度来查找拐角，理论上它可能适用于此类问题，但这只是一个近似值，可能需要花大量的工作来找出并实施

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.

我不愿意提出这个建议，但是看起来您可能会以稍微不同的方式看待问题而受益.当我使用激光测距仪进行自主导航时，我们通过将空间离散为占用栅格，这是默认方法.当然，这只是假设墙壁只是另一个对象，这不是IMO的特别离谱的想法.除此之外，您是否可以假设您有一堵墙的地图，并且只是在尝试寻找障碍物并定位(确定机器人的位置)?如果是这样，关于此问题的论文和技术报告将很多.

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.

这篇关于如何将多条线拟合到数据点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！