在圆拟合方法中，最常见的是一 种代数圆拟合方法，在我查阅的资料中，这种方法被称为“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!