最小二乘法圆拟合:kasa’s method

在圆拟合方法中,最常见的是一 种代数圆拟合方法,在我查阅的资料中,这种方法被称为“kasa’s method”。已知采样点集\( \{(x_1,y_1),(x_2,y_2),…,(x_n,y_n)\}\) 欲求圆$$(x-a)^2 + (y-b)^2 = r^2$$使得采样点到圆的距离的平方和最近。

即欲求\(a,b,r\)使$$f=\sum_{i=1}^n (\sqrt{(x_i-a) ^2+ (y-b)^2} – r)^2$$得到最小值。为了简化描述,可以令\(d=\sqrt{(x_i-a) ^2+ (y-b)^2}\)。因为d中带有根号,令问题称为非线性最小二乘问题,计算起来就没有线性问题那么快速了,所以kasa 方法提出了将求解 \((d-r)^2\)问题转换为\((d^2-r^2)^2\)最小值问题。看起来,\(d-r\)取最小值(接近为0时),\(d-r\)也能取最小值。我后面分析算法的正确性和适用范围。

$$g=\sum((x_i-a)^2+(y_i-b)^2-r^2)^2$$

若令\(B=-2a, C=-2b , D=a^2+b^2-r^2,g=\sum(x_i^2+y_i^2+Bx_i+Cy_i+D)^2 \)

求解B,C,D的值可以解出a,b,c。令 \(z_i = x_i^2 + y_i^2\)

\begin{equation}
\left\{
\begin{aligned}
\overset{.} {\frac {\partial g}{\partial D} =2(\sum z+ \sum x B + \sum y C + nD ) =0} \\
{\frac {\partial g}{\partial B} =2(\sum xz + \sum x^2 B + \sum xy C + \sum x D ) =0} \\{\frac {\partial g}{\partial C} =2(\sum yz+ \sum xy B + \sum y^2 C + \sum y D ) =0}
\end{aligned}
\right.
\end{equation}

写成矩阵形式

$$\begin{bmatrix} \sum x& \sum y& n\\\sum x^2 & \sum xy & \sum x \\ \sum xy & \sum y^2  & \sum y \end{bmatrix} \begin{bmatrix} B \\ C \\ D\end{bmatrix} = \begin{bmatrix} -\sum z \\ -\sum xz \\ -\sum yz  \end{bmatrix}  $$

采用Eigen可以解线性方程,求出B,C,D;

\( a = -\frac {B}{2} , b = -\frac {C}{2},r = \frac{\sqrt{B^2+C^2-4D}}{2}\)。

下面分析算法的正确性和使用范围。

\( d^2-r^2 = (d-r)(d+r) \)当 d-r较小,即采样点几乎都分布在同一个圆上时,算法效果良好,当d-r变大,即噪音较大时,\(min( d^2-r^2)\)会试图减小(d+r)项,使得算法得出的直径显著偏小。

其次,算法的效果还和采样点的分布有关系,如果采样点分布在整个圆上,kasa 方法的效果较好,如果分布在半圆上效果较差,如果是四分之一圆和八分之一圆,效果更差。如下图。

上图引用自Nikolai Chernov 教授的 《Circular and Linear Regression》,Chernov 教授是莫斯科大学数学系博士,长期任教于UAB(University of Alabama at Birmingham)。他的研究帮我们解决了生产中的实际问题。他于2014年逝世,May he rest in peace!

发表评论

电子邮件地址不会被公开。