Best fit for the intersection of multiple lines

Question

I'm trying to solve the following problem:

• I'm analyzing an image and I obtain from this analysis a set of segments
• I want to know the intersection of these lines (best fit)

I'm using for this opencv's function cvSolve. For reasonably good input everything works fine.

The problem that I have comes from the fact that when I have just a single bad segment as input the result is different from the one expected.

Details:

• Upper left image show the "lonely" purple lines influencing the result (all lines are used as input).

• Upper right image shows how a single purple line (one removed) can influence the result.

• Lower left image show what we want - the intersection of lines as expected (both purple lines eliminated).

• Lower right image show how the other purple line (the other is removed) can influence the result.

As you can see only two lines and the result is completely different from the one expected. Any ideas on how to avoid this are appreciated.

Thanks,

Iulian

Answer 1

The algorithm you are using finds, as described in the link, the least square error solution to the problem. This means that if there are more intersection points, the result will be an average (for a reasonable definition of average) of the real solutions.

I would try an iterative solution: if the error of the first solution is too large, remove from the set of segments the one farthest to the solution, and iterate until the error is acceptably small. This should remove one of the many intersection point, and converge on the one with most lines nearby.

Answer 2

A general answer to this kind of problems is the RANSAC algorithm (question dealing with this), however it has a few disadvantages, for example you need to estimate things like "the expected number of outliers" beforehand. Another Problem I see with your sample is that removing the two green lines also results in a pretty good fit, so that might be a more general problem.