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