• Open Source Computer Vision Library

最小二乘法拟合直线

Wikipedia,自由的百科全书

本说明用于解释blobtrack程序的DetectNewBlob()函数中的直线拟合部分

目录

问题

假设已知时间序列上的点集(x_t, y_t), t=0,1,\cdots, N-1,需要拟合直线\begin{pmatrix}x \\ y\end{pmatrix}=\begin{pmatrix}a_x \\ a_y \end{pmatrix}\cdot t+\begin{pmatrix}b_x \\ b_y \end{pmatrix},也就是分别拟合直线\left\{ \begin{matrix}x =  a_x\cdot t+b_x \\ y  =  a_y\cdot t+b_y\end{matrix}\right .

该问题可以分解为两个完全相同的子问题:

  • 使用点集(x_t, t),  t=0,1,\cdots, N-1,来拟合(x, t)平面上的直线x =  a_x\cdot t+b_x
  • 使用点集(y_t, t),  t=0,1,\cdots, N-1,来拟合(y, t)平面上的直线y =  a_y\cdot t+b_y

下面以拟合(x, t)平面上的直线x =  a \cdot t+b为例说明问题的求解。

解答

所有的点到拟合出的直线x =  a \cdot t+b的误差应该为最小,也就是(a,b)分别取什么值的时候,下面这个方程的值(误差)最小:

\min_{a,b}\left\|\begin{pmatrix}0 & 1 \\ 1 & 1 \\ \vdots & \vdots \\ N-1 & 1  \end{pmatrix}  \begin{pmatrix} a\\ b\end{pmatrix} - \begin{pmatrix} x_0 \\ x_1 \\ \vdots \\ x_{N-1}\end{pmatrix}\right\|_{2} = \min_{a,b} \left\|A \begin{pmatrix}a\\b\end{pmatrix} -\mathbf{x} \right\|_2.

直接给出该式的参数解:

a = \frac{\sum_{t=0}^{N-1} t\cdot x_i - N \cdot \bar t \bar x}{\sum_{t=0}^{N-1} t^2- N \cdot (\bar t)^2}
b = \bar x - a \bar t

其中

\bar t = \frac{1}{N} \sum_{t=0}^{N-1}t = \frac{N-1}{2}
\bar x = \frac{1}{N} \sum_{t=0}^{N-1}x_t
\sum_{t=0}^{N-1} t^2 = \frac{(N-1)N(2N-1)}{6}

代入整理后,可得

a=6 \frac{  (1-N) \sum_{t=0}^{N-1}x_t + 2\sum_{t=0}^{N-1}t\cdot x_t }{N (N^2-1)}
b=-2\frac{(1-2N)\sum_{t=0}^{N-1} x_t   + 3 \sum_{t=0}^{N-1}t\cdot x_t}{N(N+1)}

误差

点集(x_t, t),  t=0,1,\cdots, N-1到直线x = a\cdot t +b的拟合误差为:

|a\cdot t +b - x_t |

blobtrack代码

blobtrack程序的DetectNewBlob()函数中的直线拟合部分

sum[0/1]对应上面的\sum_{t=0}^{N-1}x_t
jsum[0/1]对应上面的\sum_{t=0}^{N-1}t \cdot x_t
a[0/1]对应上面的a
b[0/1]对应上面的b
pBL[j]->x 对应上面的 xt
pBL[j]->y 对应上面的 yt
Views
Personal tools