opencv - 代表线的分组点

我正在寻找一种能够解决此问题的算法。

问题:

我有以下设定点:



我想将代表一条线(带有一些epsilon)的点归为一组。
因此，最佳输出将类似于:



一些注意事项:

该点属于一条且仅一条线。

如果该点可以属于两条线，则它应该属于最强线。

当一条线具有更多的归属点时，它被认为比另一条线更强。

该算法不应涵盖所有点，因为它们可能是异常值。

该空间包含许多离群值，可能占到总空间的50％。

性能至关重要，实时是必须的。

我到目前为止找到的解决方案:

1)作为聚类问题处理:

这种方法的主要缺点是点之间没有没有直接距离度量。距离度量标准在群集本身上(线性程度)。因此，我不能使用传统的聚类方法，而(我认为)必须使用某种类型的聚类方法，例如，对遗传算法进行聚类，其中评估发生在while聚类上而不是在两点之间。我也想在寻求实时解决方案时不使用遗传算法之类的方法。

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

虽然很难直接在点上进行聚类，但我想到了要提取成对的点，然后尝试将它们与其他点聚类。因此，我在两对线之间有一个可以表示线性度的距离(两对线在实际4点中)。
这种方法的缺点是如何选择这些对？如果我依靠它们之间的距离，这可能并不准确，因为两个点可能彼此距离很近，但距离彼此却还很遥远。

我感谢任何解决方案，建议，线索或笔记。请您询问任何澄清。

附言您可以在考虑任何解决方案时使用任何可用的OpenCV函数。

最佳答案

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

在点上应用带有拟合线模型的RANSAC。

删除位于RANSAC输出中的所有点。

如果有2点或更多，请转到1。

我已经实现了自己的生产线RANSAC，但是很遗憾，我不能共享代码，因为它属于我工作的公司。但是，SO上有一个非常棒的拟合线RANSAC，由Srinath Sridhar实现。帖子的链接是:RANSAC-like implementation for arbitrary 2D sets。

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

结果如下:

关于opencv - 代表线的分组点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33629842/