分组表示线条的点

Question

我正在寻找能够解决这个问题的算法.

问题:

我有以下设定点:

我想将表示一行(带有一些epsilon)的点组合在一个组中.因此,最佳输出将是这样的:

一些说明:

1. 该点属于唯一的一条线.
2. 如果该点可以属于两条线,则它应属于最强线.
3. 当一条线具有更多的归属点时,该线被认为更强.
4. 该算法不应涵盖所有点,因为它们可能是异常值.
5. 该空间包含许多异常值,它可能达到总空间的50%.
6. 性能至关重要,实时是必须的.

我发现的解决方案到现在为止:

1)将其作为聚类问题处理:

该方法的主要缺点是点之间没有直接的距离度量.距离度量在群集本身上(线性多少).所以,我不能使用传统的聚类方法,我必须(据我所想)使用某种方式,例如,聚类我们的遗传算法,其中评估发生在while群集之间而不是两点之间.我也不想使用像遗传算法这样的东西我正在瞄准实时解决方案.

2)累积对然后进行聚类:

虽然很难直接对点进行聚类,但我想到了提取点对,然后尝试将它们与其他点聚类.所以,我有两对之间的距离,可以代表线性(两对在真正的4点).这种方法的缺点是如何选择这些对？如果我依赖它们之间的Ecledian-Distance,它可能不准确,因为两个点可能彼此如此接近,但它们远远没有与其他点形成一条线.

我感谢任何解决方案,建议,线索或说明.请您澄清一下.

PS您可以使用任何现成的OpenCV功能来考虑任何解决方案.

Answer 1

正如Micka建议的那样,我使用Sequential-RANSAC来解决我的问题.结果太棒了,完全符合我的要求.这个想法很简单:

1. 在点上应用RANSAC和拟合线模型.
2. 删除RANSAC输出的所有内容.
3. 虽然有2个或更多点去1.

我已经实现了自己的适配线RANSAC但不幸的是我无法共享代码,因为它属于我工作的公司.然而,SINEath Sridhar实施了一个优秀的RANSAC配件.帖子的链接是:任意2D集的RANSAC类实现.

根据我上面提到的3个简单步骤,很容易制作Sequential-RANSAC.

以下是一些结果: