Grouping points that represent lines

Question

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

The problem:

I have the following set points:

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

Some notes:

1. The point belong to one and only line.
2. If the point can be belong to two lines, it should belong to the strongest.
3. A line is considered stronger that another when it has more belonging points.
4. The algorithm should not cover all points because they may be outliers.
5. The space contains many outliers it may hit 50% of the the total space.
6. Performance is critical, Real-Time is a must.

The solutions I found till now:

1) Dealing with it as clustering problem:

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) accumulative pairs and then do clustering:

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. You may use any ready OpenCV function in thinking of any solution.

Answer 1

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

1. Apply RANSAC with fit-line model on the points.
2. Delete all points that are in-liers of the output of RANSAC.
3. While there are 2 or more points go to 1.

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.

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

Here are some results: