Как рассчитать линию из ряда точек? - PullRequest
Новая
       20

Как рассчитать линию из ряда точек?

3 голосов
/ 19 апреля 2011

Вероятно, простой вопрос, но я не мог найти легкое решение до сих пор. Я работаю над простым программным обеспечением для распознавания изображений для очень конкретного случая использования.

Дано множество точек, которые предположительно находятся на прямой линии. Однако некоторые точки ошибочно размещены и удалены от линии. Особенно вблизи концов линии, точки могут быть более или менее неточными.

Пример: 

   X            // this guy is off
         X      // this one even more
 X              // looks fine
 X
  X
      X         // a mistake in the middle
  X
     X          // another mistake, not as bad as the previous
   X
    X
   X
    X
         X      // we're off the line again

Общее направление линии известно, в данном случае оно вертикальное. Фактическая линия в примере фактически вертикальная с небольшим диагональным наклоном.

Меня интересует только бесконечная линия (то есть ее наклон и смещение), положение конечных точек не имеет значения.

В качестве дополнительной информации (не уверен, что это важно) невозможно, чтобы 2 точки лежали рядом друг с другом горизонтально. Пример: 

   X
   X
    X
   X X   // cannot happen
    X
     X

Производительность не важна. Я работаю в C #, но я в порядке с любым языком или просто с общей идеей.

Ответы [ 3 ]

4 голосов
/ 19 апреля 2011
3 голосов
/ 20 апреля 2011

Линейная регрессия (как уже упоминалось) хороша, если вы знаете, что у вас нет выбросов.

Если у вас есть выбросы, то один из моих любимых методов - это метод срединной средней линии: http://education.uncc.edu/droyster/courses/spring00/maed3103/Median-Median_Line.htm

По сути, вы сортируете точки по значениям X, а затем разделяете точки на три группы одинакового размера (наименьшие значения, средние значения и самые большие значения). Последний наклон - это наклон линии, проходящей через медиану небольшой группы и через медиану большой группы. Медиана средней группы используется с другими медианами для расчета окончательного смещения / пересечения.

Это простой алгоритм, который можно найти в нескольких графических калькуляторах.

Принимая три медианы, вы полностью игнорируете любые выбросы (в крайнем левом, крайнем правом, дальнем или дальнем).

На рисунке ниже показаны линейная регрессия и срединно-срединные линии для набора данных с парой больших выбросов.

Linear Regression vs. Median-Median

3 голосов
/ 19 апреля 2011

Майк на месте!Используйте следующее: 

double[] xVals = {...};
double[] yVals = {...};

double xMean = 0;
double yMean = 0;
double Sxy = 0;
double Sxx = 0;
double beta0, beta1;
int i;

for (i = 0; i < xVals.Length; i++)
{
   xMean += xVals[i]/xVals.Length;
   yMean += yVals[i]/yVals.Length;
}

for (i = 0; i < xVals.Length; i++)
{
   Sxy += (xVals[i]-xMean)*(yVals[i]-yMean);
   Sxx += (xVals[i]-xMean)*(xVals[i]-xMean);
}

beta1 = Sxy/Sxx;
beta0 = yMean-beta1*xMean;

Используйте бета1 в качестве наклона и бета0 в качестве y-перехвата!

...