将一组线段近似为一条最佳拟合直线

Question

假设我有一组线段，如这张图片中的红线（或绿线）

我想知道如何用最接近它们的线段替换它们。或者您可以建议要搜索的内容，因为这可能是统计中的常见问题。

问题背景：这其实来自于使用OpenCV的概率霍夫变换。我想检测一张纸的角。当我将它应用于图像时，我会在边缘处得到一组线条，我想将这些线条转换为单线连续段。

我想到的一种方法是从直线上取几个点，然后使用直线回归得到直线的方程。一旦我有了它，我应该把它剪成一段。

Answer 1

这是一个很好的问题。看待这个问题的正确方法是沿着每个线段对误差进行积分。而不是一个简单的术语(y[i] - y_hat)^2（其中y_hat是回归线的预测值），您应该使用integral((y[i](t) - y_hat)^2, t, 0, 1)其中y[i](t)是线段的参数化（将第 - 段y[i](t) = t * y[i, 1] + (1 - t)*y[i, 0]的端点表示为和）。我认为您会发现您可以精确地计算积分，因此您将获得仅涉及端点的平方误差之和的项。我遗漏了一些细节，但我认为这足以让您解决其余问题。编辑：误差项应该平方；我相应地调整了公式。iy[i, 0]y[i, 1]

第二次编辑：我制定了一些公式（使用Maxima）。对于由 表示的回归线，我得到和y = alpha*x + beta的最小二乘估计：alphabeta

alpha = (4*('sum(ll[k],k,1,n))*'sum(xx[k][2]*yy[k][2]*ll[k],k,1,n)
    +2*('sum(ll[k],k,1,n))*'sum(xx[k][1]*yy[k][2]*ll[k],k,1,n)
    +('sum(xx[k][2]*ll[k],k,1,n))*(-3*'sum(yy[k][2]*ll[k],k,1,n)
                                  -3*'sum(yy[k][1]*ll[k],k,1,n))
    +('sum(xx[k][1]*ll[k],k,1,n))*(-3*'sum(yy[k][2]*ll[k],k,1,n)
                                  -3*'sum(yy[k][1]*ll[k],k,1,n))
    +2*('sum(ll[k],k,1,n))*'sum(yy[k][1]*xx[k][2]*ll[k],k,1,n)
    +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]*yy[k][1]*ll[k],k,1,n))
    /(4*('sum(ll[k],k,1,n))*'sum(xx[k][2]^2*ll[k],k,1,n)
     +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]*xx[k][2]*ll[k],k,1,n)
     -3*('sum(xx[k][2]*ll[k],k,1,n))^2
     -6*('sum(xx[k][1]*ll[k],k,1,n))*'sum(xx[k][2]*ll[k],k,1,n)
     +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]^2*ll[k],k,1,n)
     -3*('sum(xx[k][1]*ll[k],k,1,n))^2)

  beta = -((2*'sum(xx[k][2]*ll[k],k,1,n)+2*'sum(xx[k][1]*ll[k],k,1,n))
   *'sum(xx[k][2]*yy[k][2]*ll[k],k,1,n)
   +('sum(xx[k][2]*ll[k],k,1,n)+'sum(xx[k][1]*ll[k],k,1,n))
    *'sum(xx[k][1]*yy[k][2]*ll[k],k,1,n)
   +('sum(xx[k][2]^2*ll[k],k,1,n))*(-2*'sum(yy[k][2]*ll[k],k,1,n)
                                   -2*'sum(yy[k][1]*ll[k],k,1,n))
   +('sum(xx[k][1]*xx[k][2]*ll[k],k,1,n))
    *(-2*'sum(yy[k][2]*ll[k],k,1,n)-2*'sum(yy[k][1]*ll[k],k,1,n))
   +('sum(xx[k][1]^2*ll[k],k,1,n))*(-2*'sum(yy[k][2]*ll[k],k,1,n)
                                   -2*'sum(yy[k][1]*ll[k],k,1,n))
   +('sum(xx[k][2]*ll[k],k,1,n)+'sum(xx[k][1]*ll[k],k,1,n))
    *'sum(yy[k][1]*xx[k][2]*ll[k],k,1,n)
   +2*('sum(xx[k][1]*yy[k][1]*ll[k],k,1,n))*'sum(xx[k][2]*ll[k],k,1,n)
   +2*('sum(xx[k][1]*ll[k],k,1,n))*'sum(xx[k][1]*yy[k][1]*ll[k],k,1,n))
   /(4*('sum(ll[k],k,1,n))*'sum(xx[k][2]^2*ll[k],k,1,n)
    +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]*xx[k][2]*ll[k],k,1,n)
    -3*('sum(xx[k][2]*ll[k],k,1,n))^2
    -6*('sum(xx[k][1]*ll[k],k,1,n))*'sum(xx[k][2]*ll[k],k,1,n)
    +4*('sum(ll[k],k,1,n))*'sum(xx[k][1]^2*ll[k],k,1,n)
    -3*('sum(xx[k][1]*ll[k],k,1,n))^2)

其中xx和yy是值对列表，每个线段一对。即，xx[k]是第 - 个线段的端点的 x 坐标k，yy[k]是第 - 个线段的端点的 y 坐标k，是第 - 个线段的ll[k]长度。sqrt((xx[k][2] - xx[k][1])^2 + (yy[k][2] - yy[k][1])^2)k

这是我的程序来推导这些公式。可能还有其他合理的方法来解决这个问题，产生相似但不同的公式。

y_hat[k](l) := alpha * x[k](l) + beta;
x[k](l) := (1 - l/ll[k]) * xx[k][1] + l/ll[k] * xx[k][2];
y[k](l) := (1 - l/ll[k]) * yy[k][1] + l/ll[k] * yy[k][2];
e[k]:= y[k](l) - y_hat[k](l);
foo : sum (integrate (e[k]^2, l, 0, ll[k]), k, 1, n);
declare (nounify (sum), linear);
[da, db] : [diff (foo, alpha), diff (foo, beta)];
map (expand, %);
bar : solve (%, [alpha, beta]);

这是一些示例数据和我得到的结果。我推迟了定义dx、dy、 和，因为它们都是常数项，所以我不希望它们在和 的ll解中展开。alphabeta

dx[k] := xx[k][2] - xx[k][1];
dy[k] := yy[k][2] - yy[k][1];
ll[k] := sqrt (dx[k]^2 + dy[k]^2);

xx : [[1,2],[1.5,3.5],[5.5,10.5]]$
yy : [[1,2.2],[1.5,3.3],[5,12]]$

''bar, nouns, n=length(xx);
  => [[alpha = 1.133149837130799, beta = - 0.4809409869515073]]