代表线的分组点 [英] Grouping points that represent lines

问题描述

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

I am looking for an Algorithm that is able to solve this problem.

问题:

我有以下设定点:

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

I want to group the points that represents a line (with some epsilon) in one group. So, the optimal output will be something like:

一些注意事项:

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

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

1)作为聚类问题来处理:

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

The main drawback of this method is that there is no direct distance metric between points. The distance metric is on the cluster itself (how much it is linear). So, I can not use traditional clustering methods and I have to (as far as I thought) use some kind of, for example, clustering us genetic algorithm where the evaluation occurs on the while cluster not between two points. I also do not want to use something like Genetic Algorithm While I am aiming real-time solution.

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

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

While It is hard to make clustering on points directly, I thought of extracting pairs of points and then try to cluster them with others. So, I have a distance between two pairs that can represents the linearity (two pairs are in real 4 points). The draw-back of this method is how to choose these pairs? If I depend on the Ecledian-Distance between them, it may not be accurate because two points may be so near to each other but they are so far from making a line with others.

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

I appreciate any solution, suggest, clue or note. Please you may ask about any clarification.

P.S.您可以使用任何可用的OpenCV函数来考虑任何解决方案.

P.S. You may use any ready OpenCV function in thinking of any solution.

推荐答案

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

As Micka advised, I used Sequential-RANSAC to solve my problem. Results were fantastic and exactly as I want. The idea is simple:

1. 在点上应用带有拟合线模型的RANSAC.
2. 删除所有位于RANSAC输出中的点.
3. 当有2点或更多点进入1时.

我已经实现了自己的生产线RANSAC，但是很遗憾，我不能共享代码，因为它属于我工作的公司.但是，SO上有一个非常棒的拟合线RANSAC，由 Srinath Sridhar 实现.该文章的链接为:针对任意2D集的类似于RANSAC的实现.

I have implemented my own fit-line RANSAC but unfortnantly I can not share code because it belongs to the company I work for. However, there is an excellent fit-line RANSAC here on SO that was implemented by Srinath Sridhar. The link of the post is : RANSAC-like implementation for arbitrary 2D sets.

根据我上面提到的3个简单步骤，很容易进行Sequential-RANSAC.

It is easy to make a Sequential-RANSAC depending on the 3 simple steps I mentioned above.

以下是一些结果:

这篇关于代表线的分组点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！