atppp's Blog

椭圆拟合

椭圆拟合最初是从计算机图形学发展起来的，比方模式识别中就经常要识别圆形，而非正投影下圆形是一个椭圆。椭圆拟合的基本思想很简单，给定一组数据点，找一个椭圆使得数据点到这个椭圆的距离和最小。不过这个东西说来简单，实现起来也不是非常简单，因为优化距离和是一个迭代优化问题，没有直接的代数算法。人们想到，一般的椭圆方程形式是：

A x² + B x y + C y² + D x + E y + F = 0

并且 B² – 4 A C < 0 （否则是双曲线或者抛物线）。在一级近似下，最小化

∑ (A x² + B x y + C y² + D x + E y + F)²

并强制

B² – 4 A C = -1

就可以得到拟合椭圆的参数。这个方法的好处是可以直接套用最小二乘拟合（Least square fitting）和拉格朗日乘子法（Lagrange multipliers）来解，只需要一次矩阵代数运算就可以得到结果，比迭代优化方法快无数倍。这个看似很没有技术含量的方法最早是在1999 年的一片论文中明确提出的。

后来，有物理学家注意到，两个同频率正弦信号的相位差可以用椭圆拟合得到：

φ = arccos(-B / (2 (AC)^1/2))

这个应用看似无聊，却不但发了论文还申请了专利（US 20050027489）。在这个基础上，又有人把这个技术应用在数字信号处理上，居然又去申请了一个新的专利（US 7224463）！最近，有物理学家注意到，由这个计算机图形学发展起来的椭圆拟合应用到物理信号处理上有着隐藏系统误差，精密测量不能容许这种误差，于是又有人提出了以物理模型为基础的无偏 Bayesian 信号处理方法。很可惜，Bayesian 方法计算量很大，和最早的迭代椭圆拟合法计算量差不多，感觉像是一夜又回到了解放前。科学的发展是螺旋式上升的，这个不知道是哪一位哲人最早提出来的，反正真的是不幸被他老人家言中了。

Kisstar 同学说，学术界真正有用的结果都是 top 10% 的牛校牛人搞出来的，大多数人都是陪练，跟着灌水而已。纵观椭圆拟合的发展，貌似每一次小小的进步都能在学术杂志上灌点水。在现在这个烂文章满天飞的年代里，写了文章就一定要选最牛鼻的杂志投起，投就是投个运气；您还别嫌烦，著作等身说的就是屁大点事儿就写篇文章投稿；所以我们灌水的口号就是：不求最好，但求最多。

Tags: elipse, kisstar, patent