文档介绍：案卷号
日期
模型算法说明文档
算法名称:拟合多边形为椭圆算法
作者:白舒扬
测试人:徐宏
完成日期:2010年6月19日
签收人:
签收日期:2010年月日
修改情况记录
版本号
修改批准人
修改人
安装日期
签收人
1算法简述
本算法将多边形拟合为椭圆。算法利用带约束的最小二乘法,由给定的若干顶点得到椭圆在平面直角坐标系的一般方程,继而求得椭圆各特征参数。算法特点为稳定和快速。
2算法输入
x:多边形顶点横坐标组成的列数组
y: 多边形顶点纵坐标组成的列数组
若给待拟合多边形顶点编上序号,则x和y的第i个元素分别是第i个顶点的横和纵坐
标。输入的点顺序不一定按多边形周边的绕行顺序。一个顶点仅输入一次,不能重复。
3数学原理
椭圆方程及其变换
在平面直角坐标系上,一般位置的椭圆可表示为关于的方程:
, (1)
的解。其中
通过旋转和平移,可将一般位置的椭圆方程变换为中心在原点、对称轴重合于坐标轴
标准椭圆方程,从而提取出椭圆的特征参数。
首先假设(1)中的各系数已知。现在把坐标轴逆时针转动角度,其中表示点在坐标轴变动后的新坐标:
(2) 把(2)代入(1),设新方程为:
(3)
容易求出:
为了使坐标轴变换后,方程不在出现一项,即,则有:
为了让项的系数为0,需令
(4)
在将(4)代入(3)中各系数确定它们的值。此时再对(3)进行配方得到
令
则有
其中,
(5)
((1)中的限制条件保证了根号下为正)
此时的和即椭圆的两半轴长,再利用(2)将目前的椭圆中心点坐标转变为坐标轴变换之前的。
于是,我们从椭圆一般方程的系数得到了椭圆的两半轴长,中心坐标以及半轴关于x坐标轴的角度(逆时针为正向)。
用现在得到的参数,椭圆在原坐标系下的参数()方程为:
带约束的最小二乘
首先考虑带约束的方程:
() (6)
之所以可以把约束换为,是因为若(6)中方程系数都乘以某个非零数,方程解没有变化,所以无妨预先假定。
而最小二乘拟合,实际上是求函数的最小值,其中为第i个待拟合顶点坐标,另外还带有的约束条件。为简化,记,。再令
,于是问题转化为
求,
其中,
由拉格朗日乘子法,转化为解方程组:
(7)
(8)
接下来通过矩阵分块和求特征向量的方式能解出上述方程组(详见参考文献1),从而得到所需的系数组。
现在只需要说明得到的此系数组满足约束。而实际上,方程(6)在实平面上有非单点解当且仅当(见参考文献2,P158),或者说仅需(6)有非单点解,则解一定为椭圆。我们又有以下结论:
【结论】有上述方法解出的必定使得方程(6)在实平面上有非单点解。
证明:记
此时,由拉格朗日乘子法,仅考虑(6)最后一行的那个方程有:
(9)
从而知道:对某个两个,有,。由连续性即知必定存在一组使得,即使得(6)有解。
此时,若(6)只有单点解,设为,则满足
而对,(或)恒成立。
这与(9)矛盾,因为我么至少有三个不同的待拟合点。
4算法流程
算法流程(伪代码由IDL语法书写)
计算椭圆一般方程系数
step1:读入顶点坐标列数组x,y
step2:解方程(5)