Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a set of points $(x, y)$ where each one comes from either one of two linear functions: \begin{align*} y &= m_1 x + b_1\\ y &= m_2 x + b_2 \end{align*} Is there a fitting method to find such functions, without knowing from which function each of the points come from?

PS. can somebody add fit (or fitting) to the existing tags

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Imagine that your data is presented as a binary two dimensional image (assuming a unit value whenever the point coordinate (x,y) is present in your data). Then the problem is equivalent to straight line detection in binary images. The equivalent problem can be solved using the Hough transform for straight line detection.

The basic idea of the hough transform is as follows:

  1. It transforms an array from the geometrical coordinates (x,y) to the space of initial points and slopes.
  2. Every point contributes a unit to all sets of slopes and initial points of straight lines passing through this point.
  3. The Hough transform of the whole array is the linear superposition of the transform of it's individual points.

The detected lines appear as peaks in the hough transform image

share|improve this answer
    
This sounds very good. I will give it a try. –  Hernan Mar 3 '11 at 21:27

Your question reminds me a robust model fitting method: RANSAC, which is widely used in computer vision to remove image feature outliers. Suppose the data are roughly located on two lines. If traditional fitting methods are employed, you may get a linear function that is very different to the ones you expected. But if you use RANSAC, at least it can give you one correct estimated line, and the points on the other line will be regarded as outliers.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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