algorithm - 如何从一系列点计算一条线？

Question

可能是一个简单的问题，但到目前为止我找不到一个简单的解决方案。我正在为一个非常具体的用例开发一个简单的图像识别软件。

给定的是一堆应该在一条直线上的点。但是，有些点被错误地放置并远离线。尤其是在线的末端附近，点可能或多或少不准确。

例子：

   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# 中工作，但我对任何语言都很好，或者只是一个通用的想法。

Answer 1

我认为您正在寻找通过线性回归拟合的最小二乘

Answer 2

迈克很准！使用以下内容：

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;

使用 beta1 作为斜率，使用 beta0 作为 y 截距！

Answer 3

如果您知道自己没有异常值，则线性回归（正如其他人所提到的）很好。

如果您确实有异常值，那么我最喜欢的方法之一是中位数线法： http ://education.uncc.edu/droyster/courses/spring00/maed3103/Median-Median_Line.htm

基本上，您按 X 值对点进行排序，然后将这些点分成三个大小相等的组（最小值、中值和最大值）。最终斜率是通过小组中位数和大组中位数的线的斜率。中间组的中位数与其他中位数一起用于计算最终偏移/截距。

这是一个简单的算法，可以在几个图形计算器上找到。

通过取三个中位数，您完全忽略了任何异常值（在最左侧、最右侧、最上方或最下方）。

下图显示了一组具有几个大异常值的数据的线性回归和中位数线。