计算机应用   2017, Vol. 37 Issue (1): 273-277  DOI: 10.11772/j.issn.1001-9081.2017.01.0273 0

### 引用本文

CAO Junli, LI Jufeng. Improved ellipse fitting algorithm based on Letts criterion[J]. JOURNAL OF COMPUTER APPLICATIONS, 2017, 37(1): 273-277. DOI: 10.11772/j.issn.1001-9081.2017.01.0273.

### 文章历史

Improved ellipse fitting algorithm based on Letts criterion
CAO Junli, LI Jufeng
School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China
Abstract: The commonly used Least Square (LS) ellipse fitting algorithm based on minimum algebraic distance is simple and easy to implement, but it has no choice to the sample points, which leads to the fitting results are easily inaccurate due to the error points. According to this case, an improved ellipse fitting algorithm based on Letts criterion was proposed to overcome the shortage of LS algorithm. Firstly, the ellipse was fitted from the fitting curve by using the LS ellipse fitting algorithm based on minimum algebraic distance. Then, the algebraic distance of ellipse fitted by LS algorithm from the point distance on the fitting curve was set as the fitting point set. After the point set was verified to be normal distribution, the points which were greater than |3σ| were determined to be outliers and eliminated by using Letts criterion. Then the steps above were repeated until all points were within the scope of [-3σ,]. Finally, the best fitting ellipse was obtained. The simulation experiment results show that the fitting error of the improved algorithm based on Letts criterion is within 1.0%, and its fitting accuracy is improved by at least 2 percentage points compared with the LS algorithm under the same condition. The simulation result and the practical application in roundness measurement of cigarette verify the effectiveness of the improved algorithm.
Key words: Letts criterion    ellipse fitting    Least Square(LS) algorithm    roundness measurement    vision detection system
0 引言

1 基于代数距离的最小二乘椭圆拟合

 \begin{align} & f(x,y)=(\sum\limits_{i=1}^{N}{(Ax_{i}^{2}+Bxy+Cy_{i}^{2}+D{{x}_{i}}}+E{{y}_{i}}+1){{)}^{2}} \\ & (i=1,2,...,N) \\ \end{align} (1)

 \begin{align} & \frac{\partial f(x,y)}{\partial A}=\frac{\partial f(x,y)}{\partial B}=\frac{\partial f(x,y)}{\partial C}= \\ & \frac{\partial f(x,y)}{\partial D}=\frac{\partial f(x,y)}{\partial E}=0,(F=1) \\ \end{align} (2)

 $\left[ {\matrix{ {\sum\limits_{i = 1}^N {x_i^4} } & {\sum\limits_{i = 1}^N {x_i^3{y_i}} } & {\sum\limits_{i = 1}^N {x_i^2y_i^2} } & {\sum\limits_{i = 1}^N {x_i^3} } & {\sum\limits_{i = 1}^N {x_i^2{y_i}} } \cr {\sum\limits_{i = 1}^N {x_i^3{y_i}} } & {\sum\limits_{i = 1}^N {x_i^2y_i^2} } & {\sum\limits_{i = 1}^N {{x_i}{y_i}^3} } & {\sum\limits_{i = 1}^N {x_i^2{y_i}} } & {\sum\limits_{i = 1}^N {{x_i}{y_i}^2} } \cr {\sum\limits_{i = 1}^N {x_i^2y_i^2} } & {\sum\limits_{i = 1}^N {{x_i}{y_i}^3} } & {\sum\limits_{i = 1}^N {y_i^4} } & {\sum\limits_{i = 1}^N {{x_i}{y_i}^2} } & {\sum\limits_{i = 1}^N {y_i^3} } \cr {\sum\limits_{i = 1}^N {x_i^3} } & {\sum\limits_{i = 1}^N {x_i^2{y_i}} } & {\sum\limits_{i = 1}^N {{x_i}{y_i}^2} } & {\sum\limits_{i = 1}^N {x_i^2} } & {\sum\limits_{i = 1}^N {{x_i}{y_i}} } \cr {\sum\limits_{i = 1}^N {x_i^2{y_i}} } & {\sum\limits_{i = 1}^N {{x_i}{y_i}^2} } & {\sum\limits_{i = 1}^N {y_i^3} } & {\sum\limits_{i = 1}^N {{x_i}{y_i}} } & {\sum\limits_{i = 1}^N {y_i^2} } \cr } } \right]\left[ {\matrix{ A \cr B \cr C \cr D \cr E \cr } } \right] + \left[ {\matrix{ {\sum\limits_{i = 1}^N {x_i^2} } \cr {\sum\limits_{i = 1}^N {{x_i}{y_i}} } \cr {\sum\limits_{i = 1}^N {y_i^2} } \cr {\sum\limits_{i = 1}^N {{y_i}} } \cr {\sum\limits_{i = 1}^N {{x_i}} } \cr } } \right] = 0$ (3)

 ${{a}^{2}}=\frac{2(Ax_{0}^{2}+Cy_{0}^{2}+B{{x}_{0}}y{}_{0}-1)}{A+C-\sqrt{{{(A-C)}^{2}}+{{B}^{2}}}}$ (4)

 ${{b}^{2}}=\frac{2(Ax_{0}^{2}+Cy_{0}^{2}+B{{x}_{0}}y{}_{0}-1)}{A+C+\sqrt{{{(A-C)}^{2}}+{{B}^{2}}}}$ (5)

 $\theta =\frac{1}{2}{{\tan }^{-1}}(\frac{B}{A-C})$ (6)

2 莱特准则优化椭圆拟合算法

2.1 采样点正态分析

 图 1 莱特准则数据样本点集 Figure 1 Data sample point set of Letts criterion

2.2 基于莱特准则进行椭圆优化

 $\frac{{{(x'\cos \theta -y'\sin \theta )}^{2}}}{{{a}^{2}}}+\frac{{{(x'\sin \theta +y'\cos \theta )}^{2}}}{{{b}^{2}}}=1$ (7)
 $x=x'+center.x$ (8)
 $y=y'+center.y$ (9)

 $y=\frac{{{y}_{i}}-center.y}{{{x}_{i}}-center.x}x,(1=1,2,...,N)$ (10)

 图 2 样本点正态分析结果 Figure 2 Normal distribution results of sample points

 \begin{align} & l(i)=\sqrt{{{({{x}_{ip'}}-center.x)}^{2}}+{{({{y}_{ip'}}-center.y)}^{2}}}- \\ & \sqrt{{{({{x}_{ip}}-center.x)}^{2}}+{{({{y}_{ip}}-center.y)}^{2}}};(i=1,2,...N) \\ \end{align} (11)

 $\bar{I}=\frac{1}{N}\sum\limits_{i=1}^{N}{l(i)};(i=1,2,...N)$ (12)

 $\sigma =\sqrt{\sum\limits_{i=1}^{N}{\frac{{{(l(i)-\bar{I})}^{2}}}{N-1}}};(i=1,2,...N)$ (13)

 ${{l}_{b}}(i)=l(i)-\bar{I};(i=1,2,...N)$ (14)

3 算法测试 3.1 仿真测试

 图 3 仿真测试椭圆拟合结果 Figure 3 Ellipse fitting results of simulation
3.2 仿真测试香烟圆度检测系统应用

 图 4 卷烟烟条的横截面示意图 Figure 4 Cross section of cigarette on production line

 图 5 香烟圆度检测系统示意图 Figure 5 System diagram for roundness measurement of cigarette

 图 6 优化算法拟合结果 Figure 6 Ellipse fitting results of improved algorithm

 $h=a\sin \theta =a\sin {{50}^{\circ }}$ (15)
 $Δh=b-h$ (16)

 图 7 圆度检测数据分析示意图 Figure 7 Analysis of roundness measurement data

4 结语

 [1] 赵光明.机器视觉系统中的椭圆检测算法研究[D].武汉:华中科技大学,2009:1-5. ( ZHAO G M. Study on ellipse detection algorithm in machine vision system[D]. Wuhan:Huazhong University of Science and Technology, 2009:1-5. ) [2] 闫蓓, 王斌, 李媛. 基于最小二乘法的椭圆拟合改进算法[J]. 北京航空航天大学学报, 2008, 34 (3) : 295-298. ( YAN B, WANG B, LI Y. Optimal ellipse fitting method based on least square[J]. Journal of Beijing University of Aeronautics and Astronautics, 2008, 34 (3) : 295-298. ) [3] 韩建栋, 杨红菊, 吕乃光. 视觉测量中椭圆自动检测与定位方法[J]. 计算机工程与应用, 2011, 47 (17) : 169-171. ( HAN J D, YANG H J, LYU N G. Automated ellipse detection and location method on 3D visual inspection[J]. Computer Engineering and Applications, 2011, 47 (17) : 169-171. ) [4] YANG D L, BAI Q C, ZHANG Y L, et al. Eye location based on Hough transform and direct least square ellipse fitting[J]. Journal of Software, 2014, 9 (2) : 319-323. [5] 夏菁.椭圆拟合方法的比较研究[D].广州:暨南大学,2007:1-7. ( XIA J. Research on ellipse fitting method[D]. Guangzhou:Jinan University, 2007:1-7. ) [6] 陈海峰, 雷华, 孔燕波, 等. 基于最小二乘法的改进的随机椭圆检测算法[J]. 浙江大学学报(工学版), 2008, 42 (8) : 1360-1364. ( CHEN H F, LEI H, SUN Y B, et al. An improved randomized algorithm for detecting ellipses based on least square approach[J]. Journal of Zhejiang University (Engineering Science), 2008, 42 (8) : 1360-1364. ) [7] 张维光, 韩军, 周翔. 线结构光多分辨率测量系统数据拼接方法[J]. 仪器仪表学报, 2013, 34 (7) : 1441-1447. ( ZHANG W G, HAN J, ZHOU X. Data registration method for multiresolution measurement system with line structured light[J]. Chinese Journal of Scientific Instrument, 2013, 34 (7) : 1441-1447. ) [8] KURT O, ARSLAN O. Geometric interpretation and precision analysis of algebraic ellipse fitting using least squares method[J]. Acta Geodaetica et Geophysica Hungarica, 2012, 47 (4) : 430-440. doi: 10.1556/AGeod.47.2012.4.4 [9] 邹益民, 汪渤. 一种基于最小二乘的不完整椭圆拟合算法[J]. 仪器仪表学报, 2006, 27 (7) : 808-812. ( ZHOU Y M, WANG B. Fragmental ellipse fitting based on least square algorithm[J]. Chinese Journal of Scientific Instrument, 2006, 27 (7) : 808-812. ) [10] FITZGIBBON A, PILU M, FISHER R B. Direct least square fitting of ellipses[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, 21 (5) : 476-480. doi: 10.1109/34.765658 [11] 朱新岩, 史忠科. 基于残差特性分析的野值检测与剔除方法[J]. 飞行力学, 2008, 26 (6) : 79-83. ( ZHU X Y, SHI Z K. Outlier detection method based on characteristic analyzing of residue[J]. Flight Dynamics, 2008, 26 (6) : 79-83. ) [12] LAGANIERE R. OpenCV2 Computer Vision Application Programming Cookbook[M]. Birmingham: Packt Publishing, 2011 : 143 -164. [13] Philipp Wagner. Machine learning with OpenCV2[EB/OL].[2016-03-10] . http://www.bytefish.de. [14] 章毓晋. 图像处理和分析[M]. 北京: 清华大学出版社, 1999 : 35 -36. ( ZHANG Y J. Image Processing and Analysis[M]. Beijing: Tsinghua University Press, 1999 : 35 -36. ) [15] 李龙, 何明一, 李娜. 椭圆拟合的圆环模板摄像机标[J]. 西安电子科技大学学报(自然科学版), 2010, 37 (6) : 1148-1154. ( LI L, HE M Y, LI N. Camera calibration based on the circular pattern and ellipse fitting[J]. Journal of Xidian University (Natural Science), 2010, 37 (6) : 1148-1154. )