Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (1): 273-277.DOI: 10.11772/j.issn.1001-9081.2017.01.0273

Previous Articles     Next Articles

Improved ellipse fitting algorithm based on Letts criterion

CAO Junli, LI Jufeng   

  1. School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China
  • Received:2016-06-12 Revised:2016-09-05 Online:2017-01-10 Published:2017-01-09

基于莱特准则的椭圆拟合优化算法

曹俊丽, 李居峰   

  1. 上海大学 机电工程与自动化学院, 上海 200072
  • 通讯作者: 曹俊丽
  • 作者简介:曹俊丽(1991-),女,内蒙古乌兰察布人,硕士研究生,主要研究方向:计算机图像处理、控制系统设计;李居峰(1956-),男,上海人,副教授,硕士,主要研究方向:机电一体化、控制系统设计。

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

摘要: 普遍使用的代数距离最小的最小二乘(LS)椭圆拟合算法简单、易实现,但对样本点无选择,导致拟合结果易受误差点影响,拟合不准确。针对此特性,提出了一种基于莱特准则的椭圆拟合优化算法。首先,由代数距离最小的LS法对待拟合曲线进行椭圆拟合;其次,将待拟合曲线上的点与LS法拟合的椭圆的代数距离作为样本点集,在验证该样本点集服从正态分布的情况下,采用莱特准则,将样本点中值大于|3σ|的点判定为野值并剔除,进行多次拟合,直至样本点中无野值;最后,得到椭圆最优拟合结果。仿真实验结果表明,优化算法的拟合误差在1.0%以下,相比同条件下的LS法,其拟合精度至少提高2个百分点。优化算法的仿真结果与其在香烟圆度在线检测中的实际应用验证了此算法的有效性。

关键词: 莱特准则, 椭圆拟合, 最小二乘法, 圆度检测, 视觉检测系统

CLC Number: