最小二乘法拟合圆

有一系列的数据点 {xi,yi}$\{x_i,y_i\}$，我们知道这些数据点近似的落在一个圆上，根据这些数据估计这个圆的参数就是一个很有意义的问题。今天就来讲讲如何来做圆的拟合。圆拟合的方法有很多种，最小二乘法属于比较简单的一种。今天就先将这种。

我们知道圆方程可以写为：

(x−xc)2+(y−yc)2=R2$$(x-x_c{)}^2+(y-y_c{)}^2=R^2$$

通常的最小二乘拟合要求距离的平方和最小。也就是

f=∑((xi−xc)2+(yi−yc)2−−−−−−−−−−−−−−−−−−√−R)2$$f=\sum {\left(\sqrt{(x_i-x_c{)}^2+(y_i-y_c{)}^2}-R\right)}^2$$

最小。这个算起来会很麻烦。也得不到解析解。所以我们退而求其次。

f=∑((xi−xc)2+(yi−yc)2−R2)2$$f=\sum {\left((x_i-x_c{)}^2+(y_i-y_c{)}^2-R^2\right)}^2$$

这个式子要简单的多。我们定义一个辅助函数：

g(x,y)=(x−xc)2+(y−yc)2−R2$$g(x,y)=(x-x_c{)}^2+(y-y_c{)}^2-R^2$$

那么上面的式子可以表示为：

f=∑g(xi,yi)2$$f=\sum g(x_i,y_i{)}^2$$

按照最小二乘法的通常的步骤，可知f$f$ 取极值时对应下面的条件。

∂f∂xc=0∂f∂yc=0∂f∂R=0$$\begin{array}{r}\frac{\mathrm{\partial }f}{\mathrm{\partial }{x}_c}=0\\ \frac{\mathrm{\partial }f}{\mathrm{\partial }{y}_c}=0\\ \frac{\mathrm{\partial }f}{\mathrm{\partial }R}=0\end{array}$$

先来化简 ∂f∂R=0$\frac{\mathrm{\partial }f}{\mathrm{\partial }R}=0$

∂f∂R=−2R×∑((xi−xc)2+(yi−yc)2−R2)=−2R×∑g(xi,yi)=0$$\begin{array}{rl}\frac{\mathrm{\partial }f}{\mathrm{\partial }R}& =-2R\times \sum \left((x_i-x_c{)}^2+(y_i-y_c{)}^2-R^2\right)\\ & =-2R\times \sum g(x_i,y_i)=0\end{array}$$

我们知道半径 R$R$ 是不能为 0 的。所以必然有：

∑g(xi,yi)=0$$\sum g(x_i,y_i)=0$$

这是个非常有用的结论。剩下的两个式子：

∂f∂xc=−4∑((xi−xc)2+(yi−yc)2−R2)(xi−xc)=−4∑g(xi,yi)(xi−xc)=−4∑xig(xi,yi)=0∂f∂yc=−4∑((xi−xc)2+(yi−yc)2−R2)(yi−yc)=−4∑g(xi,yi)(yi−yc)=−4∑yig(xi,yi)=0$$\begin{array}{c}\begin{array}{rl}\frac{\mathrm{\partial }f}{\mathrm{\partial }{x}_c}& =-4\sum \left((x_i-x_c{)}^2+(y_i-y_c{)}^2-R^2\right)(x_i-x_c)\\ & =-4\sum g(x_i,y_i)(x_i-x_c)\\ & =-4\sum x_{i}g(x_i,y_i)=0\end{array}\\ \begin{array}{rl}\frac{\mathrm{\partial }f}{\mathrm{\partial }{y}_c}& =-4\sum \left((x_i-x_c{)}^2+(y_i-y_c{)}^2-R^2\right)(y_i-y_c)\\ & =-4\sum g(x_i,y_i)(y_i-y_c)\\ & =-4\sum y_{i}g(x_i,y_i)=0\end{array}\end{array}$$

也就是下面两个等式：

∑xig(xi,yi)=0∑yig(xi,yi)=0$$\begin{array}{c}\sum x_{i}g(x_i,y_i)=0\\ \sum y_{i}g(x_i,y_i)=0\end{array}$$

这里设：

ui=xi−x¯uc=xc−x¯vi=yi−y¯vc=yc−y¯$$\begin{gathered} u_i=x_i-\overline{x} \\ {u}_c=x_c-\overline{x} \\ {v}_i=y_i-\overline{y} \\ {v}_c=y_c-\overline{y} \end{gathered}$$

其中：

x¯=∑xi/Ny¯=∑yi/N$$\begin{gathered} \overline{x}=\sum x_i/N \\ \overline{y}=\sum y_i/N \end{gathered}$$

那么简单的推导一下，就会发现：

∑uig(ui,vi)=0∑vig(ui,vi)=0$$\begin{array}{c}\sum u_{i}g(u_i,v_i)=0\\ \sum v_{i}g(u_i,v_i)=0\end{array}$$

其实都不需要推导，这个变量替换只不过是修改了坐标原点的位置。而我们的等式根本就与坐标原点的具体位置无关。所以必然成立。

这两个式子展开写是这样的：

∑((ui−uc)2+(vi−vc)2−R2)ui=0∑((ui−uc)2+(vi−vc)2−R2)vi=0$$\begin{gathered} \sum \left((u_i-u_c{)}^2+(v_i-v_c{)}^2-R^2\right)u_i=0 \\ \sum \left((u_i-u_c{)}^2+(v_i-v_c{)}^2-R^2\right)v_i=0 \end{gathered}$$

进一步展开：

∑(u3i−2u2iuc+uiu2c+uiv2i−2uivivc+uiv2c−uiR2)=0∑(u2ivi−2uiviuc+viu2c+v3i−2v2ivc+viv2c−viR2)=0$$\begin{gathered} \sum \left(u_i^3-2u_i^2{u}_c+u_i{u}_c^2+u_i{v}_i^2-2u_i{v}_i{v}_c+u_i{v}_c^2-u_i{R}^2\right)=0 \\ \sum \left(u_i^2{v}_i-2u_i{v}_i{u}_c+v_i{u}_c^2+v_i^3-2v_i^2{v}_c+v_i{v}_c^2-v_i{R}^2\right)=0 \end{gathered}$$

我们知道 ∑ui=0$\sum u_i=0$, ∑vi=0$\sum v_i=0$。所以上面两个式子是可以化简的。

∑(u3i−2u2iuc+uiv2i−2uivivc)=0∑(u2ivi−2uiviuc+v3i−2v2ivc)=0$$\begin{gathered} \sum \left(u_i^3-2u_i^2{u}_c+u_i{v}_i^2-2u_i{v}_i{v}_c\right)=0 \\ \sum \left(u_i^2{v}_i-2u_i{v}_i{u}_c+v_i^3-2v_i^2{v}_c\right)=0 \end{gathered}$$

为了简化式子，我们定义几个参数：

Suuu=∑u3iSvvv=∑v3iSuu=∑u2iSvv=∑v2iSuv=∑uiviSuuv=∑u2iviSuvv=∑uiv2i$$\begin{gathered} S_{uuu}=\sum u_i^3 \\ {S}_{vvv}=\sum v_i^3 \\ {S}_{uu}=\sum u_i^2 \\ {S}_{vv}=\sum v_i^2 \\ {S}_{uv}=\sum u_i{v}_i \\ {S}_{uuv}=\sum u_i^2{v}_i \\ {S}_{uvv}=\sum u_i{v}_i^2 \end{gathered}$$

那么上面的式子可以写为：

Suuuc+Suvvc=Suuu+Suvv2Suvuc+Svvvc=Suuv+Svvv2$$\begin{gathered} S_{uu}{u}_c+S_{uv}{v}_c=\frac{S_{uuu}+S_{uvv}}{2} \\ {S}_{uv}{u}_c+S_{vv}{v}_c=\frac{S_{uuv}+S_{vvv}}{2} \end{gathered}$$

至此，就可以解出uc$u_c$ 和vc$v_c$ 了。

uc=SuuvSuv−SuuuSvv−SuvvSvv+SuvSvvv2(S2uv−SuuSvv)vc=−SuuSuuv+SuuuSuv+SuvSuvv−SuuSvvv2(S2uv−SuuSvv)$$\begin{gathered} u_c=\frac{S_{uuv}{S}_{uv}-S_{uuu}{S}_{vv}-S_{uvv}{S}_{vv}+S_{uv}{S}_{vvv}}{2(S_{uv}^2-S_{uu}{S}_{vv})} \\ {v}_c=\frac{-S_{uu}{S}_{uuv}+S_{uuu}{S}_{uv}+S_{uv}{S}_{uvv}-S_{uu}{S}_{vvv}}{2(S_{uv}^2-S_{uu}{S}_{vv})} \end{gathered}$$

那么：

xc=uc+x¯yc=vc+y¯$$\begin{gathered} x_c=u_c+\overline{x} \\ {y}_c=v_c+\overline{y} \end{gathered}$$

还剩下个 R$R$ 没求出来， 也很简单。

∑g(xi,yi)=0∑((xi−xc)2+(yi−yc)2−R2)=0$$\begin{gathered} \sum g(x_i,y_i)=0 \\ \sum \left((x_i-x_c{)}^2+(y_i-y_c{)}^2-R^2\right)=0 \end{gathered}$$

所以：

R2=∑((xi−xc)2+(yi−yc)2)$$R^2=\sum \left((x_i-x_c{)}^2+(y_i-y_c{)}^2\right)$$

好了。下面给出个代码，这个代码的具体公式和我这里给出的有一点小差异，但是原理是相同的。

/** * 最小二乘法拟合圆 * 拟合出的圆以圆心坐标和半径的形式表示 * 此代码改编自 newsmth.net 的 jingxing 在 Graphics 版贴出的代码。 * 版权归 jingxing， 我只是搬运工外加一些简单的修改工作。 */typedef complex<int> POINT;bool circleLeastFit(const std::vector<POINT> &points, double &center_x, double &center_y, double &radius){     center_x = 0.0f;     center_y = 0.0f;     radius = 0.0f;     if (points.size() < 3)     {         return false;     }     double sum_x = 0.0f, sum_y = 0.0f;     double sum_x2 = 0.0f, sum_y2 = 0.0f;     double sum_x3 = 0.0f, sum_y3 = 0.0f;     double sum_xy = 0.0f, sum_x1y2 = 0.0f, sum_x2y1 = 0.0f;     int N = points.size();     for (int i = 0; i < N; i++)     {         double x = points[i].real();         double y = points[i].imag();         double x2 = x * x;         double y2 = y * y;         sum_x += x;         sum_y += y;         sum_x2 += x2;         sum_y2 += y2;         sum_x3 += x2 * x;         sum_y3 += y2 * y;         sum_xy += x * y;         sum_x1y2 += x * y2;         sum_x2y1 += x2 * y;     }     double C, D, E, G, H;     double a, b, c;     C = N * sum_x2 - sum_x * sum_x;     D = N * sum_xy - sum_x * sum_y;     E = N * sum_x3 + N * sum_x1y2 - (sum_x2 + sum_y2) * sum_x;     G = N * sum_y2 - sum_y * sum_y;     H = N * sum_x2y1 + N * sum_y3 - (sum_x2 + sum_y2) * sum_y;     a = (H * D - E * G) / (C * G - D * D);     b = (H * C - E * D) / (D * D - G * C);     c = -(a * sum_x + b * sum_y + sum_x2 + sum_y2) / N;     center_x = a / (-2);     center_y = b / (-2);     radius = sqrt(a * a + b * b - 4 * c) / 2;     return true;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

下图是个实际测试的结果。对这种均匀分布的噪声数据计算的结果还是很准确的。

但是当数据中有部分偏向某一个方向的干扰数据时。结果就不那么乐观了。下图就很说明问题。

数据点中有 20% 是干扰数据。拟合出的圆就明显被拽偏了。

之所以出现这个问题就是因为最小二乘拟合的平方项对离群点非常敏感。解决这个问题就要用其他的拟合算法，比如用距离之和作为拟合判据。等我有空了再写一篇博客介绍其他几种方法。