opencv - 代表线的分组点

Question

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

问题:

我有以下设置点:

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

一些注意事项:

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

我目前找到的解决方案:

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

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

2)累积对然后做聚类:

虽然很难直接在点上进行聚类，但我想到了提取点对，然后尝试将它们与其他点聚类。所以，我有两对之间的距离可以代表线性度(两对是实数4点)。这种方法的缺点是如何选择这些对？如果我依赖于它们之间的 Ecledian 距离，它可能不准确，因为两点可能彼此很近，但它们与其他点相距很远。

我感谢任何解决方案、建议、线索或注释。请您提出任何说明。

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

Answer 1

作为Micka建议，我使用Sequential-RANSAC 来解决我的问题。结果非常好，完全符合我的要求。这个想法很简单:

1. 在点上应用 RANSAC 和拟合线模型。
2. 删除 RANSAC 输出的所有内点。
3. 当有 2 点或更多点时转到 1。

我已经实现了自己的 fit-line RANSAC，但不幸的是我无法共享代码，因为它属于我工作的公司。但是，SO 上有一个出色的拟合线 RANSAC，由 Srinath Sridhar 实现.帖子的链接是:RANSAC-like implementation for arbitrary 2D sets .

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

以下是一些结果: