摘要
离群点可显著影响椭圆拟合的结果。针对这一问题,提出了一种基于截断最小二乘法和两种基于双点移除法的改进椭圆拟合算法。截断最小二乘法由随机采样开始,在每次迭代中选择当前拟合残差最小的数据点作为下一次迭代时的被拟合点集,并最终收敛于占据点集主体的非离群点的拟合结果;双点移除法则从完整的待拟合点集开始,每次移除拟合残差为正负最大值的一对数据点,直至剩余点的数量不超过给定比例。在实际零件的图像集上,对所提的3种算法及现有的对比算法进行了实验。结果表明,当所保留的椭圆点数较少时,两种基于双点移除法的算法的拟合精度最佳,但运行时间比基于截断最小二乘法的拟合方法长;就算法的最优性能而言,基于截断最小二乘法的改进椭圆拟合算法具有最佳的拟合精度与时间性能,其形状-位置匹配精度可达0.62像素,朝向角匹配精度可达0.6°,平均运行时间为6.5 ms。此外,所提3种算法均具有参数少、意义直观、算法性能对参数不敏感的优点。实验结果表明了所提改进椭圆拟合算法特别是基于截断最小二乘法的算法的有效性。
The results of ellipse fitting can be considerably distorted by outliers in the fitted point set.To tackle this problem,three improved ellipse fitting algorithms,one of which is based on least trimmed square,and the other two on dual point removal,are proposed.The least trimmed square algorithm starts from a random sample of the original complete fitted set,and then in each iteration,new fitted set is formed by points with the least residual errors,till the process converges to an ellipse fitting a subset whose members are mostly non-outliers.Dual point removal algorithms,on the other hand,starts from the whole fitted set,removes the two points respectively with the maximal positive and the minimal negative residual errors,and halts when the number of points in the remaining set does not exceeds a user-defined threshold.The two proposed algorithms and existing methods are compared on an image base of actual accessories.Experimental results show that when the number of reserved ellipse points is relatively small,the dual removal-based algorithms present the best fitting accuracies,but are slower than the least trimmed square fitting algorithm.When the best performance with parameter tuning is concerned,however,the least trimmed square algorithm achieves a shape-location matching accuracy of 0.62 pixels and an orientation matching accuracy of 0.6°,at an average execution time of 6.5 ms,outperforming other algorithms.Other advantages of the proposed algorithms include the small number of algorithm parameters,the intuitiveness of the parameters,and the insensitivity of the algorithm performance to the parameters.These experimental results provide solid evidences for the effectiveness of the proposed algorithms,especially the least trimmed square algorithm.
作者
郭斯羽
吴延冬
GUO Si-yu;WU Yan-dong(College of Electrical and Information Engineering,Hunan University,Changsha 410082,China)
出处
《计算机科学》
CSCD
北大核心
2022年第4期188-194,共7页
Computer Science
基金
国家自然科学基金(61471167)。
关键词
椭圆拟合
椭圆检测
截断最小二乘
双点移除法
视觉测量
Ellipse fitting
Ellipse detection
Least trimmed square
Dual point removal
Vision-based measurement
