直线特征提取

问题概述

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

直线方程可以表示为

r=cosθx+sinθy

几何关系如下图所示

假设一组数据集合为

Sk={(x0,y0),...,(xk,yk)}

该数据集符合直线分布,那么满足 Sk 数据的最优直线 L

(1)r=cosθx+sinθy

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

(2)ei=cosθxi+sinθyir

方差值为

(3)E2=Skei2

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

最值求解过程推导

函数定义

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

(4)f(θ,r)=Sk(cosθxi+sinθyir)2

导数为

(5)f˙(θ,r)=2Sk(cosθxi+sinθyir)

根据函数参数 θr,分别对其求偏导数得

(6)f˙(θ,r)=fθ+fr

故得

(7)f˙(θ,r)=2Sk(cosθxi+sinθyir)(cosθyisinθxi1)

f˙(θ,r)=0

(8)Sk(cosθxi+sinθyir)(cosθyisinθxi1)=0

求解假设

假设

(9)Skcosθxi+sinθyir=0cosθi0kxi+sinθi0kyii0kr=0

由上述得

(10)i=0kr=cosθi=0kxi+sinθi=0kyir=cosθi=0kxik+sinθi=0kyik

(11)Vx=i=0kxikVy=i=0kyik

上述公式可以表述为

(12)r=cosθVx+sinθVy

函数导数化简

由公式 (8) 得

(13)i=0k(cosθxi+sinθyi)(cosθyisinθxi)i=0k(cosθxi+sinθyi)i=0kr(cosθyisinθxi)+i=0kr=0

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

(14)A=i=0kcos2θxiyisinθcosθxi2+sinθcosθyi2sin2θxiyiB=i=0k(cosθxi+sinθyi)C=i=0k(cosθVx+sinθVy)(cosθyisinθxi)D=i=0k(cosθVx+sinθVy)

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

  • A

(15)A=i=0kcos2θxiyisinθcosθxi2+sinθcosθyi2sin2θxiyi=(cos2θsin2θ)i=0kxiyisinθcosθ(i=0kxi2i=0kyi2)=cos2θi=0kxiyi0.5sin2θ(i=0kxi2i=0kyi2)

  • B

(16)B=i=0k(cosθxi+sinθyi)=cosθi=0kxi+sinθi=0kyi

  • C

(17)C=i=0k(cosθVx+sinθVy)(cosθyisinθxi)=cos2θVxi=0kyisinθcosθVxi=0kxi+sinθcosθVyi=0kyisin2θVyi=0kxi=(cos2θsin2θ)i=0kxii=0kyiksinθcosθ(Vxi=0kxiVyi=0kyi)=cos2θi=0kxii=0kyik0.5sin2θ(Vxi=0kxiVyi=0kyi)

  • D

(18)D=i=0k(cosθVx+sinθVy)=cosθVxi=0k+sinθVyi=0k=cosθi=0kxi+sinθi=0kyi

故等式 (13) 可以表示为

(19)ABC+D=0

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

(20)AC=0

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

(21)2cos2θi=0kxiyisin2θ(i=0kxi2i=0kyi2)2cos2θi=0kxii=0kyik+sin2θ(Vxi=0kxiVyi=0kyi)=0

合并同类项得

(22)cos2θ2(i=0kxiyii=0kxii=0kyik)+sin2θ(Vxi=0kxiVyi=0kyii=0kxi2+i=0kyi2)=0

  • Vxy

(23)Vxy=i=0kxiyii=0kxii=0kyik=i=0kxiyii=0kxii=0kyiki=0kxii=0kyik+i=0kxii=0kyik=i=0kxiyii=0kxiVyi=0kyiVx+i=0kVxVy=i=0k(xiVx)(yiVy)

  • Vxx

(24)Vxx=i=0kxi2Vxi=0kxi=i=0kxi22i=0kxii=0kxik+i=0kxii=0kxik=i=0kxi22Vxi=0kxi+i=0kVxVx=i=0k(xiVx)2

  • Vyy

(25)Vyy=i=0k(yiVy)2

等式 (22) 可以表示为

(26)cos2θ2Vxy+sin2θ(VyyVxx)=0

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

(27)θ=arctan(VyyVxx)(VyyVxx)2+4Vxy22Vxy

根据数据集 Sk 和等式 (12)(27), 可以求出最优的 θ r 参数。