2
$\begingroup$

dataset with multiple lines I am getting the pattern shown in the picture from an experiment. To my human brain it is evident that it consists of some 20 straight lines. I need to find position and slope of all these lines (perform a regression). But I need to do it completely automatically. If this were a a single sequence I would have used RLS(Recursive Least Squares) or Kalman filter. But how can I go about if I want to make 20 simultaneous regressions that do not conflict with each other?

What would be the most generic way to solve these kind of problems (say if I have an image of 20 overlapping boxes and need to find size, position and angle of all of them, at once)? I suppose the solution is more than well-known since this would be fundamental for any image recognition, but I cannot find a generic description of the method.

$\endgroup$
  • 1
    $\begingroup$ Though this is not a general case, I can accept straight lines as hypothesis and then proceed proving or disproving it. Do you have any reference to a simple implementation of a line detector? $\endgroup$ – the_regressor Oct 20 '17 at 19:33
1
$\begingroup$

There are many possible methods. In your picture, there aren't too many dots, so the following algorithm might be good enough:

  • For each pair of points, find the line through them. Count the number of points that are approximately on that line.

  • Choose the line that has the most number of points on it. Output that line. Delete all points that are approximately on that line from the figure.

  • Repeat until no points remain.

For fancier methods (e.g., if you have a huge number of points, or some prior model for what kinds of lines you expect to see), you can look at RANSAC and the expectation maximization (EM) algorithm, but given your sample picture, the above simple method might be adequate in your setting.

$\endgroup$
  • $\begingroup$ Thanks! RANSAC seems a more straightforward solution for a limited number of points like here, though it may require many attempts to "grip" into the first valid line. EM algorithm looks tougher, but perhaps more powerful in the end. I shall investigate both! $\endgroup$ – the_regressor Oct 20 '17 at 19:58
  • $\begingroup$ Found on the RANSAC wiki page a link to Hough transform, which seems to be specifically designed to solve exactly this problem! $\endgroup$ – the_regressor Oct 20 '17 at 20:18
  • $\begingroup$ @the_regressor, the Hough transform is going to be basically equivalent to the first method I describe. $\endgroup$ – D.W. Oct 20 '17 at 20:55
  • $\begingroup$ Well, it certainly worked :-) Here are the custom Hough transform of the dots and the identified lines overlapped with the original data. Close to perfect! $\endgroup$ – the_regressor Oct 20 '17 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.