计算机科学 ›› 2022, Vol. 49 ›› Issue (4): 188-194.doi: 10.11896/jsjkx.210200040

• 计算机图形学&多媒体 • 上一篇    下一篇

去除离群点的改进椭圆拟合算法

郭斯羽, 吴延冬   

  1. 湖南大学电气与信息工程学院 长沙 410082
  • 收稿日期:2021-02-04 修回日期:2021-05-14 发布日期:2022-04-01
  • 通讯作者: 郭斯羽(syguo75@163.com)
  • 基金资助:
    国家自然科学基金(61471167)

Improved Ellipse Fitting Algorithm with Outlier Removal

GUO Si-yu, WU Yan-dong   

  1. College of Electrical and Information Engineering, Hunan University, Changsha 410082, China
  • Received:2021-02-04 Revised:2021-05-14 Published:2022-04-01
  • About author:GUO Si-yu,born in 1975,Ph.D,asso-ciate professor,is a member of China Computer Federation.His main research interests include image proces-sing,machine vision,signal processing and artificial intelligence.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61471167).

摘要: 离群点可显著影响椭圆拟合的结果。针对这一问题,提出了一种基于截断最小二乘法和两种基于双点移除法的改进椭圆拟合算法。截断最小二乘法由随机采样开始,在每次迭代中选择当前拟合残差最小的数据点作为下一次迭代时的被拟合点集,并最终收敛于占据点集主体的非离群点的拟合结果;双点移除法则从完整的待拟合点集开始,每次移除拟合残差为正负最大值的一对数据点,直至剩余点的数量不超过给定比例。在实际零件的图像集上,对所提的3种算法及现有的对比算法进行了实验。结果表明,当所保留的椭圆点数较少时,两种基于双点移除法的算法的拟合精度最佳,但运行时间比基于截断最小二乘法的拟合方法长;就算法的最优性能而言,基于截断最小二乘法的改进椭圆拟合算法具有最佳的拟合精度与时间性能,其形状-位置匹配精度可达0.62像素,朝向角匹配精度可达0.6°,平均运行时间为6.5ms。此外,所提3种算法均具有参数少、意义直观、算法性能对参数不敏感的优点。实验结果表明了所提改进椭圆拟合算法特别是基于截断最小二乘法的算法的有效性。

关键词: 截断最小二乘, 视觉测量, 双点移除法, 椭圆检测, 椭圆拟合

Abstract: 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.5ms, 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.

Key words: Dual point removal, Ellipse detection, Ellipse fitting, Least trimmed square, Vision-based measurement

中图分类号: 

  • TP391
[1] ZHANG J F,MEI X,XU S S,et al.Method of video peoplecounting based on double ellipse model[J].Computer Science,2012,39(S1):499-502.
[2] LIU N Q,ZHANG W S,LI L.Study of positioning tropical cyclone center based on ellipse fitting[J].Computer Science,2015,42(5):67-71.
[3] WU B,YE D,GUO Y B,et al.Multiple circle recognition and pose estimation for aerospace applications[J].Acta Optica Sinica,2017,37(9):216-226.
[4] WANG Z,DONG N,ROSARIO S D,et al.Ellipse detection of optic disc-and-cup boundary in fundus images[C]//16th International Symposium on Biomedical Imaging.IEEE,2019.
[5] LI H T,CAO C.Magnetometer correction based on improved algorithm of least square ellipse fitting[J].Electronic Measurement Technology,2019,42(18):65-68.
[6] GOVINDAN P,KASAEIFARD A,SANIIE J.Ultrasonic chirplet echo parameter estimation using time-frequency distributions[C]//2015 IEEE International Ultrasonics Symposium.2015.
[7] FITZGIBBON A,PILU M,FISHER R B.Direct least square fitting of ellipses[J].IEEE Trans.on Pattern Analysis and Machine Intelligence,1999,21(5):476-480.
[8] AHN S J,RAUH W,WARNECKE H J.Least-squares orthogo-nal distances fitting of circle,sphere,ellipse,hyperbola,and parabola[J].Pattern Recognition,2001,34(12):2283-2303.
[9] SZPAK Z L,CHOJNACKI W,VAN DEN HENGEL A.Gua-ranteed ellipse fitting with the Sampson distance[C]//2012 European Conference on Computer Vision.2012:87-100.
[10] YU J,KULKARNI S R,POOR H V.Robust ellipse and spheroid fitting[J].Pattern Recognition Letters,2012,33(5):492-499.
[11] LIANG J,WANG Y,ZENG X.Robust Ellipse Fitting via half-quadratic and semidefinite relaxation optimization[J].IEEE Trans.on Image Processing,2015,24(11):4276-4286.
[12] MUÑOZ-PÉREZ J,DE CÓZAR-MACÍAS O D,BLÁZQUEZ-PARRA E B,et al.Multicriteria robust fitting of elliptical pri-mitives[J].Journal of Mathematical Imaging and Vision,2014,49:492-509.
[13] LIANG J,LI P,ZHOU D,et al.Robust ellipse fitting via alternating direction method of multipliers[J].Signal Processing,2019,164:30-40.
[14] PRASAD D K,QUEK C,LEUNG M K H.A precise ellipse fitting method for noisy data[C]//9th International Conference Image Analysis and Recognition.2012:253-260.
[15] PRASAD D K,LEUNG M K H,QUEK C.ElliFit:An unconstrained,non-iterative,least squares based geometric Ellipse Fitting method[J].Pattern Recognition,2013,46(5):1449-1465.
[16] VAN DEUN K,GROENEN P J F.Majorization algorithms for inspecting circles,ellipses,squares,rectangles,and rhombi[J].Operations Research,2005,53(6):957-967.
[17] DE LA FRAGA L G,SILVA I V,CRUZ-CORTÉS N.Euclidean distance fit of ellipses with a genetic algorithm[C]//EvoWorkshops 2007.LNCS,2007,4448:359-366.
[18] MAINI E S.Enhanced direct least square fitting of ellipses[J].International Journal of Pattern Recognition and Artificial Intelligence,2006,20(6):939-953.
[19] LIANG J,YU G,LI P,et al.Ellipse fitting via low-rank genera-lized multidimensional scaling matrix recovery[J].Multidimensional Systems and Signal Processing,2018,29:49-75.
[20] CAO J L,LI J F.Improved ellipse fitting algorithm based on Letts criterion[J].Journal of Computer Applications,2017,37(1):273-277.
[21] LI H T,LIU K Q.Magnetometer correction based on improved algorithm of least square ellipse fitting[J].Electronic Measurement Technology,2018,41(15):145-148.
[22] HE Z Q,CAO B,ZHANG L X.A defect ellipse locating method based on least squares[J].Computer & Digital Engineering,2017,45(11):2113-2117.
[23] HU C L,WANG G,HO K C,et al.Robust ellipse fitting with Laplacian kernel based maximum correntropy criterion[J].IEEE Transactions on Image Processing,2021,30:3127-3141.
[24] YU J,ZHENG H,KULKARNI S R,et al.Two-stage outlier elimination for robust curve and surface fitting[J/OL].EURASIP Journal on Advances in Signal Processing.https://dl.acm.org/doi/10.1155/2010/154891.
[25] LIANG J,ZHANG M,LIU D,et al.Robust ellipse fitting based on sparse combination of data points[J].IEEE Trans.on Image Processing,2013,22(6):2207-2218.
[26] CHEN Y X,QI F H.A new ellipse detection method using randomized Hough transform[J].Journal of Infrared and Millimeter Waves,2000,19(1):43-47.
[27] LI Y D,XU X P,ZHONG Y.Application of RHT based oncharacter string constraint in ellipse detection[J].Chinese Journal of Scientific Instrument,2017,38(1):50-56.
[28] ZHANG X,MU R,CHEN K,et al.Intelligent Hough transform with Jaya to detect the diameter of red-hot circular workpiece[J].IEEE Sensors Journal,2021,21(1):560-567.
[29] CHEN H F,LEI H,KONG 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.
[30] LIU Z H,XIA Y.Ellipse detection method based on curve segment[J].Computer Technology and Development,2015,25(10):19-23,28.
[31] FORNACIARI M,PRATI A,CUCCHIARA R.A fast andeffective ellipse detector for embedded vision applications[J].Pattern Recognition,2014,47(11):3693-3708.
[32] DONG H,PRASAD D K,CHEN I M.Accurate detection of ellipses with false detection control at video rates using a gradient analysis[J].Pattern Recognition,2018,81:112-130.
[33] HUBERT M,ROUSSEEUW P J,VAN AELST S.High-breakdown robust multivariate methods[J].Statistical Science,2008,23(1):92-119.
[34] ZHU Y J,GUO S Y,ZHU Z J,et al.Line detection algorithm combining LTS with Hough transform[J].Computer Enginee-ring,2012,38(14):206-210.
[35] GUO S Y,ZHAI W J,TANG Q,et al.Combining the Hough transform and an improved least squares method for line detection[J].Computer Science,2012,39(4):196-200.
[1] 刘年庆,张文生,李 林.
基于椭圆拟合的热带气旋中心定位研究
Study of Positioning Tropical Cyclone Center Based on Ellipse Fitting
计算机科学, 2015, 42(5): 67-71. https://doi.org/10.11896/j.issn.1002-137X.2015.05.014
[2] 崔家礼,宫贺,王一丁,贾瑞明,肖珂.
基于代数距离的椭圆拟合的优化及应用研究
Optimization and Research on Ellipse Fitting and Application Based on Algebraic Distance
计算机科学, 2014, 41(Z11): 88-90.
[3] 张继法,梅 雪,许松松,胡 石.
一种基于双椭圆模型的视频人数统计方法
Method of Video People Counting Based on Double_ellipse Model
计算机科学, 2012, 39(Z6): 499-502.
[4] 韩建栋,杨红菊.
三维视觉测量中圆中心投影误差分析方法
Analysis Method for the Projection Error of Circle Center in 3D Vision Measurement
计算机科学, 2010, 37(12): 247-249.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!