代表线的分组点
Grouping points that represent lines
我正在寻找能够解决这个问题的算法。
问题：
我有以下设置点：
我想将代表一条线（带有一些 epsilon）的点归为一组。
因此，最佳输出将类似于：
一些注意事项：
- 该点仅属于一条直线。
- 如果点可以属于两条线，则应该属于最强的。
- 当一条线拥有更多的归属点时，它被认为比另一条线更强。
- 算法不应涵盖所有点，因为它们可能是异常值。
- space 包含许多异常值，它可能达到总数的 50% space。
- 性能很关键，实时是必须的。
我目前找到的解决方案：
1）作为聚类问题处理：
这种方法的主要缺点是没有点之间的直接距离度量。距离度量在集群本身上（它是线性的）。所以，我不能使用传统的聚类方法，我必须（据我所知）使用某种方法，例如，聚类我们的遗传算法，其中评估发生在 while 聚类上，而不是在两点之间。我也不想在我瞄准实时解决方案时使用遗传算法之类的东西。
2) 累积对然后做聚类：
虽然很难直接在点上进行聚类，但我想到了提取点对然后尝试将它们与其他点聚类。所以，我有两对之间的距离可以代表线性度（两对是实数4点）。
这种方法的缺点是如何选择这些对？如果我依赖于它们之间的 Ecledian 距离，它可能不准确，因为两点可能彼此很近，但它们与其他点相距很远。
我感谢任何解决方案、建议、线索或注释。请您提出任何说明。
P.S。您可以在考虑任何解决方案时使用任何现成的 OpenCV 函数。
按照Micka的建议，我使用Sequential-RANSAC来解决我的问题。结果非常好，完全符合我的要求。
思路很简单：
- 在点上应用带拟合线模型的 RANSAC。
- 删除 RANSAC 输出的所有内点。
- 当有2个或更多点转到1.
我已经实现了自己的 fit-line RANSAC，但不幸的是我无法共享代码，因为它属于我工作的公司。但是，SO 上有一个出色的拟合线 RANSAC，由 Srinath Sridhar. The link of the post is : RANSAC-like implementation for arbitrary 2D sets.
实现
根据我上面提到的 3 个简单步骤，很容易制作 Sequential-RANSAC。
以下是一些结果：
我正在寻找能够解决这个问题的算法。
问题：
我有以下设置点：
我想将代表一条线（带有一些 epsilon）的点归为一组。 因此，最佳输出将类似于：
一些注意事项：
- 该点仅属于一条直线。
- 如果点可以属于两条线，则应该属于最强的。
- 当一条线拥有更多的归属点时，它被认为比另一条线更强。
- 算法不应涵盖所有点，因为它们可能是异常值。
- space 包含许多异常值，它可能达到总数的 50% space。
- 性能很关键，实时是必须的。
我目前找到的解决方案：
1）作为聚类问题处理：
这种方法的主要缺点是没有点之间的直接距离度量。距离度量在集群本身上（它是线性的）。所以，我不能使用传统的聚类方法，我必须（据我所知）使用某种方法，例如，聚类我们的遗传算法，其中评估发生在 while 聚类上，而不是在两点之间。我也不想在我瞄准实时解决方案时使用遗传算法之类的东西。
2) 累积对然后做聚类：
虽然很难直接在点上进行聚类，但我想到了提取点对然后尝试将它们与其他点聚类。所以，我有两对之间的距离可以代表线性度（两对是实数4点）。 这种方法的缺点是如何选择这些对？如果我依赖于它们之间的 Ecledian 距离，它可能不准确，因为两点可能彼此很近，但它们与其他点相距很远。
我感谢任何解决方案、建议、线索或注释。请您提出任何说明。
P.S。您可以在考虑任何解决方案时使用任何现成的 OpenCV 函数。
按照Micka的建议，我使用Sequential-RANSAC来解决我的问题。结果非常好，完全符合我的要求。 思路很简单：
- 在点上应用带拟合线模型的 RANSAC。
- 删除 RANSAC 输出的所有内点。
- 当有2个或更多点转到1.
我已经实现了自己的 fit-line RANSAC，但不幸的是我无法共享代码，因为它属于我工作的公司。但是，SO 上有一个出色的拟合线 RANSAC，由 Srinath Sridhar. The link of the post is : RANSAC-like implementation for arbitrary 2D sets.
实现根据我上面提到的 3 个简单步骤，很容易制作 Sequential-RANSAC。
以下是一些结果：