直线特征提取

问题概述

常见的直线特征提取算法是最小二乘法进行的直线拟合，但是线性二次拟合的效果容易受噪声影响，导致拟合效果较差。本文基于直线方程的另一种形式，详细给出最优直线的推导过程。

菊花展

直线方程可以表示为

$$r=\cos \theta \ast x+\sin \theta \ast y$$

几何关系如下图所示

几何关系

假设一组数据集合为

$$S_k=\{(x_0,y_0),...,(x_k,y_k)\}$$

该数据集符合直线分布，那么满足 $S_k$ 数据的最优直线 $L$ 为

$$\begin{array}{}\text{(1)}& r=\cos \theta \ast x+\sin \theta \ast y\end{array}$$

这组数据集与直线 $L$ 的误差值为

$$\begin{array}{}\text{(2)}& e_i=\Vert \cos \theta \ast x_i+\sin \theta \ast y_i-r\Vert \end{array}$$

方差值为

$$\begin{array}{}\text{(3)}& E_2=\sum _{S_k}{e}_i^2\end{array}$$

那么求取与数据点 $S_k$ 匹配度最优的线段 $L$ 问题，就可以转化为求取方差 $E_2$ 的最小值问题。

最值求解过程推导

函数定义

根据最值原理，求最小值的问题，可以转化为求解函数导数为零的解的问题。 假设函数

$$\begin{array}{}\text{(4)}& f(\theta ,r)=\sum _{S_k}(\cos \theta \ast x_i+\sin \theta \ast y_i-r{)}^2\end{array}$$

导数为

$$\begin{array}{}\text{(5)}& \dot{f}(\theta ,r)=2\sum _{S_k}(\cos \theta \ast x_i+\sin \theta \ast y_i-r{)}^{\prime }\end{array}$$

根据函数参数 $\theta$ 和 $r$，分别对其求偏导数得

$$\begin{array}{}\text{(6)}& \dot{f}(\theta ,r)=\frac{\partial f}{\partial \theta }+\frac{\partial f}{\partial r}\end{array}$$

故得

$$\begin{array}{}\text{(7)}& \dot{f}(\theta ,r)=2\sum _{S_k}(\cos \theta \ast x_i+\sin \theta \ast y_i-r)(\cos \theta \ast y_i-\sin \theta \ast x_i-1)\end{array}$$

当 $\dot{f}(\theta ,r)=0$ 得

$$\begin{array}{}\text{(8)}& \sum _{S_k}(\cos \theta \ast x_i+\sin \theta \ast y_i-r)(\cos \theta \ast y_i-\sin \theta \ast x_i-1)=0\end{array}$$

求解假设

假设

$$\begin{array}{}\text{(9)}& \begin{array}{r}\sum _{S_k}\cos \theta \ast x_i+\sin \theta \ast y_i-r=0\\ \cos \theta \sum _{i_0}^k{x}_i+\sin \theta \sum _{i_0}^k{y}_i-\sum _{i_0}^{k}r=0\end{array}\end{array}$$

由上述得

$$\begin{array}{}\text{(10)}& \begin{array}{ll}\sum _{i=0}^{k}r& =\cos \theta \sum _{i=0}^k{x}_i+\sin \theta \sum _{i=0}^k{y}_i\\ r& =\cos \theta \frac{\sum _{i=0}^k{x}_i}{k}+\sin \theta \frac{\sum _{i=0}^k{y}_i}{k}\end{array}\end{array}$$

令

$$\begin{array}{}\text{(11)}& \begin{array}{l}{V}_x=\frac{\sum _{i=0}^k{x}_i}{k}\\ V_y=\frac{\sum _{i=0}^k{y}_i}{k}\end{array}\end{array}$$

上述公式可以表述为

$$\begin{array}{}\text{(12)}& r=\cos \theta \ast V_x+\sin \theta \ast V_y\end{array}$$

函数导数化简

由公式 (8) 得

$$\begin{array}{}\text{(13)}& \sum _{i=0}^k(\cos \theta \ast x_i+\sin \theta \ast y_i)(\cos \theta \ast y_i-\sin \theta \ast x_i)-\sum _{i=0}^k(\cos \theta \ast x_i+\sin \theta \ast y_i)-\sum _{i=0}^{k}r(\cos \theta \ast y_i-\sin \theta \ast x_i)+\sum _{i=0}^{k}r=0\end{array}$$

将等式 (12) 带入等式 (13), 并将等式分解为一下 4 个部分

$$\begin{array}{}\text{(14)}& \begin{array}{l}A=\sum _{i=0}^k{\cos }^2\theta \ast x_i{y}_i-\sin \theta \cos \theta \ast x_i^2+\sin \theta \cos \theta \ast y_i^2-{\sin }^2\theta \ast x_i{y}_i\\ B=\sum _{i=0}^k(\cos \theta \ast x_i+\sin \theta \ast y_i)\\ C=\sum _{i=0}^k(\cos \theta \ast V_x+\sin \theta \ast V_y)(\cos \theta \ast y_i-\sin \theta \ast x_i)\\ D=\sum _{i=0}^k(\cos \theta \ast V_x+\sin \theta \ast V_y)\end{array}\end{array}$$

等式 (14) 的四个部分可化简为

• A

$$\begin{array}{}\text{(15)}& \begin{array}{l}A=\sum _{i=0}^k{\cos }^2\theta \ast x_i{y}_i-\sin \theta \cos \theta \ast x_i^2+\sin \theta \cos \theta \ast y_i^2-{\sin }^2\theta \ast x_i{y}_i\\ =({\cos }^2\theta -{\sin }^2\theta )\sum _{i=0}^k{x}_i{y}_i-\sin \theta \cos \theta (\sum _{i=0}^k{x}_i^2-\sum _{i=0}^k{y}_i^2)\\ =\cos 2\theta \sum _{i=0}^k{x}_i{y}_i-0.5\sin 2\theta (\sum _{i=0}^k{x}_i^2-\sum _{i=0}^k{y}_i^2)\end{array}\end{array}$$

• B

$$\begin{array}{}\text{(16)}& \begin{array}{l}B=\sum _{i=0}^k(\cos \theta \ast x_i+\sin \theta \ast y_i)\\ =\cos \theta \sum _{i=0}^k{x}_i+\sin \theta \sum _{i=0}^k{y}_i\end{array}\end{array}$$

• C

$$\begin{array}{}\text{(17)}& \begin{array}{l}C=\sum _{i=0}^k(\cos \theta \ast V_x+\sin \theta \ast V_y)(\cos \theta \ast y_i-\sin \theta \ast x_i)\\ ={\cos }^2\theta \ast V_x\sum _{i=0}^k{y}_i-\sin \theta \cos \theta \ast V_x\sum _{i=0}^k{x}_i+\sin \theta \cos \theta \ast V_y\sum _{i=0}^k{y}_i-{\sin }^2\theta \ast V_y\sum _{i=0}^k{x}_i\\ =({\cos }^2\theta -{\sin }^2\theta )\frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{y}_i}{k}-\sin \theta \cos \theta (V_x\sum _{i=0}^k{x}_i-V_y\sum _{i=0}^k{y}_i)\\ =\cos 2\theta \frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{y}_i}{k}-0.5\sin 2\theta (V_x\sum _{i=0}^k{x}_i-V_y\sum _{i=0}^k{y}_i)\end{array}\end{array}$$

• D

$$\begin{array}{}\text{(18)}& \begin{array}{l}D=\sum _{i=0}^k(\cos \theta \ast V_x+\sin \theta \ast V_y)\\ =\cos \theta \ast V_x\sum _{i=0}^k+\sin \theta \ast V_y\sum _{i=0}^k\\ =\cos \theta \sum _{i=0}^k{x}_i+\sin \theta \sum _{i=0}^k{y}_i\end{array}\end{array}$$

故等式 (13) 可以表示为

$$\begin{array}{}\text{(19)}& A-B-C+D=0\end{array}$$

根据等式 (16) 和 (18) 知，B 和 D 相等，故等式 (19) 可以进一步简化为

$$\begin{array}{}\text{(20)}& A-C=0\end{array}$$

等式 (20) 两端同时扩大两倍得

$$\begin{array}{}\text{(21)}& 2\cos 2\theta \sum _{i=0}^k{x}_i{y}_i-\sin 2\theta (\sum _{i=0}^k{x}_i^2-\sum _{i=0}^k{y}_i^2)-2\cos 2\theta \frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{y}_i}{k}+\sin 2\theta (V_x\sum _{i=0}^k{x}_i-V_y\sum _{i=0}^k{y}_i)=0\end{array}$$

合并同类项得

$$\begin{array}{}\text{(22)}& \cos 2\theta \ast 2\ast (\sum _{i=0}^k{x}_i{y}_i-\frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{y}_i}{k})+\sin 2\theta (V_x\sum _{i=0}^k{x}_i-V_y\sum _{i=0}^k{y}_i-\sum _{i=0}^k{x}_i^2+\sum _{i=0}^k{y}_i^2)=0\end{array}$$

令

• $V_{xy}$

$$\begin{array}{}\text{(23)}& \begin{array}{l}{V}_{xy}=\sum _{i=0}^k{x}_i{y}_i-\frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{y}_i}{k}\\ =\sum _{i=0}^k{x}_i{y}_i-\frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{y}_i}{k}-\frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{y}_i}{k}+\frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{y}_i}{k}\\ =\sum _{i=0}^k{x}_i{y}_i-\sum _{i=0}^k{x}_i{V}_y-\sum _{i=0}^k{y}_i{V}_x+\sum _{i=0}^k{V}_x{V}_y\\ =\sum _{i=0}^k(x_i-V_x)(y_i-V_y)\end{array}\end{array}$$

• $V_{xx}$

$$\begin{array}{}\text{(24)}& \begin{array}{l}{V}_{xx}=\sum _{i=0}^k{x}_i^2-V_x\sum _{i=0}^k{x}_i\\ =\sum _{i=0}^k{x}_i^2-2\frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{x}_i}{k}+\frac{\sum _{i=0}^k{x}_i\sum _{i=0}^k{x}_i}{k}\\ =\sum _{i=0}^k{x}_i^2-2V_x\sum _{i=0}^k{x}_i+\sum _{i=0}^k{V}_x{V}_x\\ =\sum _{i=0}^k(x_i-V_x{)}^2\end{array}\end{array}$$

• $V_{yy}$

$$\begin{array}{}\text{(25)}& V_{yy}=\sum _{i=0}^k(y_i-V_y{)}^2\end{array}$$

等式 (22) 可以表示为

$$\begin{array}{}\text{(26)}& \cos 2\theta \ast 2\ast V_{xy}+\sin 2\theta (V_{yy}-V_{xx})=0\end{array}$$

根据博客求解方程 Acos + Bsin = C 可知

$$\begin{array}{}\text{(27)}& \theta =\arctan \frac{(V_{yy}-V_{xx})-\sqrt{(V_{yy}-V_{xx}{)}^2+4V_{xy}^2}}{2V_{xy}}\end{array}$$

根据数据集 $S_k$ 和等式 (12)(27), 可以求出最优的 $\theta$ 和 $r$ 参数。