圆拟合算法
⽂章⽬录
最⼩⼆乘法拟合(least square fitting)
使⽤最⼩⼆乘法，对⼏何特征进⾏拟合，主要有两⼤类⽅式：代数拟合和⼏何拟合，这两种⽅式的区别，在于它们对误差距离的定义⽅式。代数距离：为要进⾏拟合的⼏何特征(直线、圆、椭圆等)写下隐式⽅程，然后将点的坐标带⼊此隐式⽅程就得到了点到该⼏何特征的距离。这种⽅法对于直线拟合、圆拟合，返回的就是到其的真实距离。⽽对于椭圆拟合，它返回的值是与距离有类似的属性，但不是⼀个真正的距离值。因此这个距离被称为 代数距离。 代数拟合 (algebraic fitting)
代数拟合的⼏何特征是通过带有参数向量 的隐式⽅程 来表⽰的。其误差距离是由隐式⽅程与每个给定点的期望值(即零)的偏差定义。但⽅程的不确定性导致给出的点会出现不位于图形上的现象(即存在⼀些拟合误差)。关于圆的最⼩⼆乘法拟合，⼤多数论⽂给出的其代数距离平⽅和及其修正公式，如下所⽰：
尽管代数拟合在实现和计算成本⽅⾯具有优势，但在精度⽅⾯以及与拟合参数和误差的物理解释相关⽅⾯都存在缺陷。其中，已知的代数拟合的缺点，有以下⼏点：
误差距离的定义与测量准则不符；拟合参数的可靠性，难以检验；
拟合参数对坐标变换来说是可变的(如，椭圆拟合过程中，对给定点进⾏⼀个简单的平移变换，不仅会造成中⼼点的坐标发⽣变化，⽽且还会造成椭圆轴的长度及⾓度的变化)；预估的拟合参数存在偏差；拟合误差存在不合理的加权；
拟合过程有时会以意外的⼏何特征结束(如，可能会以双曲线代替椭圆的拟合)；
Kåsa Fit
注：⽹络上查到的⼤多数最⼩⼆乘法求拟合圆的算法，均是该算法的实现。
以下是 K åsa Fit 的求解过程：
=a (a ,⋯,a )1q F (X ,a )=0e =i =1∑
m
i
2[(x −i =1∑
m
i x )+c 2(y −i y )−c 2r ]22
(1)
⾸先，根据圆的公式 可得，
令：
可得圆的⽅程的另⼀种形式：
根据公式，只要求出参数 a, b, c 即可得到圆⼼及半径的参数；
[外链图⽚转存失败，源站可能有防盗链机制，建议将图⽚保存下来直接上传(img-HoQMhYw6-1584789138214)(图1.png)]样本集 中，点到圆⼼的距离为 ：
令，点到圆边缘的距离的平⽅与半径的平⽅差为:
令， 为 的平⽅和:
求参数 使得 的值最⼩。
(x −A )+2(y −B )=2R 2R =2x −22Ax +A +2y −22By +B ;
2a =−2A ,b =−2B ,c =A +2B −2R 2
x +2y +2ax +by +c =0
(1)
(1)A =−，B =2a −，R =
2b
2
a +
b −4c
22(X ,Y ),i ∈i i (1,2,3,⋯,n d i d =i 2
(X −i A )+2(Y −i B )2
(X ,Y )i i δ=d −i 2R =2(X −i A )+2(Y −i B )−2R =2X +i 2Y +i 2
aX +i bY +i c
Q (a ,b ,c )δ2Q (a ,b ,c )=
δ=i =1∑
n
i
2[(X +i =1∑
n
i 2Y +i 2
aX +i bY +i c )]2
(a ,b ,c )Q (a ,b ,c )
解：平⽅差 ⼤于等于 ，因此，函数存在⼤于或等于 的极⼩值，其最⼤值为⽆穷⼤；
对 ，令偏导等于 ，则得到极值点，⽐较所有的极值点函数，即可得到极⼩值；
令，常数 ，则上式可转化为：
则，
将 代⼊上式，得:
同理，可得 的偏导数：
将上述等式，改写成⽅程的形式：
根据 运算法则，将常数提出，并且因为等式等于，所以，可以直接省略，得下式；
Q (a ,b ,c )00F (a ,b ,c )(a ,b ,c )0=∂a
∂Q (a ,b ,c )∂([(X +Y +aX +bY +c )])i =1∑
n
i 2i 2
i i 2D =(X +i 2Y +i 2
bY +i c )=∂a
∂Q (a ,b ,c )∂([(D +aX )])i =1∑
n
i 2=∂a
∂Q (a ,b ,c )∂([(D +2DaX +X a )])=i =1∑n 2
i i 22(2X a +2DX )=i =1∑n i 2i 2(aX +i =1∑n
i D )X i D =∂a
∂Q (a ,b ,c )2(X +i =1∑
n
i 2Y +i 2
aX +i bY +i c )X =i 0(2)
b ,
c =∂b
∂Q (a ,b ,c )2(X +i =1∑
n
i 2Y +i 2
aX +i bY +i c )Y =i 0(3)
=∂c
∂Q (a ,b ,c )2(X +i =1∑
n
i 2Y +i 2
aX +i bY +i c )=0(4)
⎩
⎪⎨⎪⎧=2(X +Y +aX +bY +c )X =0∂
a ∂Q (a ,
b ,
c )
∑i =1n
i 2
i 2
i i i =2(X +Y +aX +bY +c )Y =0∂b ∂Q (a ,b ,c )∑i =1n i 2i 2
i i i =2(X +Y +aX +bY +c )=0∂c ∂Q (a ,b ,c )∑i =1n i 2i 2i i
∑0
将上式展开，成下列形式：
根据求和公式，得，代⼊⽅程得：
所以，解⽅程组，消去 ，式 得
，得
⎩
⎪⎨⎪⎧=(X +X Y +aX +bX Y +cX )=0∂
a ∂Q (a ,
b ,
c )
∑i =1n
i 3
i i 2
i 2
i i i =(X Y +Y +aX Y +bY +cY )=0
∂b ∂Q (a ,b ,c )∑i =1n i 2i i 3i i i 2
i =(X +Y +aX +bY +c )=0∂c ∂Q (a ,b ,c )∑i =1n i 2i 2i i
⎩
⎪⎨⎪⎧X +X Y +a X +b X Y +c X =0∑i
=1n
i 3
∑i =1n
i i 2
∑i =1n
i 2
∑i =1n
i i ∑i =1n
i X Y +Y +a X Y +b Y +c Y =0
∑i =1n i 2i ∑i =1n i 3∑i =1n i i ∑i =1n i 2
∑i =1n i X +Y +a X +b Y +c =0
∑i =1n i 2∑i =1n i 2∑i =1n i ∑i =1n i ∑i =1n c =∑i =1n
Nc ⎩
⎪⎨⎪⎧X +X Y +a X +b X Y +c X =0∑i
=1n
i 3
∑i =1n
i i 2
∑i =1n
i 2
∑i =1n
i i ∑i =1n
i X Y +Y +a X Y +b Y +c Y =0
∑i =1n i 2i ∑i =1n i 3∑i =1n i i ∑i =1n i 2
∑i =1n i X +Y +a X +b Y +Nc =0
∑i =1n i 2∑i =1n i 2∑i =1n i ∑i =1n i c (2)∗N −(4)∗X ∑i =1n
i (N
X −
i =1
∑
n
i 2
X X )a +i =1
∑
n
i i =1∑
n
i N (X Y −
i =1∑
n
i i X Y )b +
i =1
∑
n
i i =1∑
n
i N
X +i =1
∑
n
3
N
拟合直线
X Y −i =1∑
n
i i 2(X +
i =1∑
n
i 2
Y )X =i 2
i =1
∑
n
i 0
(5)
(3)∗N −(4)∗Y ∑i =1n
i N (X Y −
i =1∑
n
i i X Y )a +i =1
∑
n
i i =1∑
n
i (N
Y −
i =1
∑
n
i 2
Y Y )b +
i =1
∑
n
i i =1∑
n
i N
X Y +i =1∑
n
i 2
i
N
Y −i =1∑
i 3(X +
i =1∑
n
i 2
Y )Y =i 2
i =1
∑
n
i 0
(6)
令：
则，得⽅程：解得：
C=(N X−
i=1
∑n
i
2X X),
i=1
∑n
i i=1
∑n
i
D=N(X Y−
i=1
∑n
i i X Y),
i=1
∑n
i i=1
∑n
i
E=N X+
i=1
∑n
i
3
N X Y−
i=1
∑n
i i
2(X+
i=1
∑n
i
2
Y)X
i
2
i=1
∑n
i G=(N Y−
i=1
∑n
i
2Y Y)
i=1
∑n
i i=1
∑n
i
H=N X Y+
i=1
∑n
i
2
i N Y−
i=1
∑
i
3(X+
i=1
∑n
i
2
Y)Y
i
2
i=1
∑n
i
{Ca+Db+E=0
Da+Gb+H=0
a=CG−D2
HD−EG
b=D−CG
2
HC−ED
c=−N
(X+Y)+a X+b Y ∑i=1
n
i
2
i
2
∑i=1
n
i∑i=1
n
i
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议