WU Yao feng1,3, WANG Wen2, LU Ke qing2, WEI Yan ding1, CHEN Zi chen1
1.Key Lab of Advanced Manufacturing Technology of Zhejiang Province, School of Mechanical Engineering, Zhejiang University, Hangzhou 310027, China;2.School of Mechanical Engineering, Hangzhou Dianzi University, Hangzhou 310018, China; 3.College of Mechanical and Energy Engineering, Institute of Technology, Zhejiang University, Ningbo 315100, China
An improved ellipse detection method based on edge grouping was proposed due to the low detection efficiency of multiple, overlapping, occluded and nested ellipses. The method consisted of image preprocessing, edge grouping, elliptical fitting and removal of false alarms. First, the majority of non elliptic boundary pixels were removed in the process of image preprocessing through edge detection, edge thinning and redundant EELs (equivalent edge lists) elimination. Then, a series of candidate elliptic arcs and elliptic arc pairs were obtained in the edge following process through edge linking, line segment list extraction, neighborhood and global merging of arcs. Ellipse fitting was performed by using direct least squares method, and the false alarms were subsequently removed. Besides, combined with the existing forms of target ellipses, the algorithm was simplified and the threshold was also optimized. Finally, the proposed method was evaluated by using both synthetic and real world images. Results show that the edge grouping method can detect ellipses accurately and fast in different existing forms, with 14%～76% time shortened after optimization．
WU Yao feng, WANG Wen, LU Ke qing, WEI Yan ding, CHEN Zi chen. Fast ellipse detection based on edge grouping. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(3): 405-411.
［1］ 陈海峰, 雷华, 孔燕波, 等. 基于最小二乘法的改进的随机椭圆检测算法［J］. 浙江大学学报：工学版, 2008, 42(8): 1360-1364．
CHEN Hai feng, LEI Hua, KONG Yan bo, 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．
［2］ LIU H M, WANG Z H. Geometric property based ellipse detection method ［J］. Journal of Visual Communication and Image Representation, 2013, 24(7): 1075-1086．
［3］ ALVAREZ L, SALGADO A, SANCHEZ J. Robust detection and ordering of ellipses on a calibration pattern ［J］. Pattern Recognition and Image Analysis, 2007, 17(4): 508-522．
［4］ LEO M, MAZZEO P L, NITTI M, et al. Accurate ball detection in soccer images usin g probabilistic analysis of salient regions ［J］. Machine Vision and Applications, 2013, 24(8): 1561-1574．
［5］ USABIAGA J, EROL A, BEBIS G, et al. Global hand pose estimation by multiple camera ellipse tracking ［J］. Machine Vision and Applications, 2008, 21(1): 1-15．
［6］ HIROSE K, TORIU T, HAMA H. Estimation of vehicle wheelbase in a circular fisheye image using two step detection method of tire road contact points ［J］. International Journal of Innovative Computing,Information and Control, 2011, 7(8): 4717-4727．
［7］ CHEN K C, BOUGUILA N, ZIOU D. Quantization free parameter space reduction in ellipse detection ［J］. Expert Systems with Applications, 2011, 38(6): 7622-7632．
［8］ MEI B, ZHU W D, YAN G R, et al. A new elliptic contour extraction method for reference hole detection in robotic drilling ［J］. Pattern Analysis and Applications, 2014, 18(3): 695-712．
［9］ BAI X Z, SUN C M, ZHOU F G. Splitting touching cells based on concave points and ellipse fitting ［J］. Pattern Recognition, 2009, 42(11): 2434-2446．
［10］ NGUYEN T M, AHUJA S, WU Q M J. A real time ellipse detection based on edge grouping ［C］ ∥ International Conference on Systems,Man and Cybernetics, San Antonio: IEEE, 2009: 3280-3286．
［11］ MUKHOPADHYAY P, CHAUDHURI B B. A survey of Hough Transform ［J］. Pattern Recognition, 2015, 48(3): 993-1010．
［12］ MCLAUGHLIN R A. Randomized Hough transform: improved ellipse detection with comparison ［J］. Pattern Recognition Letters, 1998, 19(3/4): 299-305．
［13］ 屈稳太. 基于弦中点Hough变换的椭圆检测方法［J］. 浙江大学学报：工学版, 2005, 39(8): 1132-1135．
QU Wen tai. Chord midpoint Hough transform based ellipse detection method ［J］.Journal of Zhejiang University: Engineering Science, 2005, 39(8):1132-1135．
［14］ 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．
［15］ RAY A, SRIVASTAVA D C. Non linear least squares ellipse fitting usin g the genetic alg orithm with applications to strain analysis ［J］. Journal of Structural Geology, 2008, 30(12): 1593-1602．
［16］ PRASAD D K, LEUNG M K H, CHOS S. Edge curvature and convexity based ellipse detection method［J］. Pattern Recognition. 2012, 45(9): 3204-3221．
［17］ CHATBRI H, KAMEYAMA K. Using scale space filtering to make thinning algorithms robust against noise in sketch images ［J］. Pattern Recognition Letters, 2014, 42: 1-10．
［18］ ONIGA F, MIRON M, DANESCU R, et al. Automatic recognition of low earth orbit objects from image sequences ［C］ ∥ 7th International Conference on Intelligent Computer Communication and Processing. Cluj Napoca: IEEE, 2011: 335-338．
［19］ MATLAB and Octave Functions. ［EB/OL］. (2013 08 02)［2015 02 07］. http:∥www.csse.uwa.edu.au/～pk/research/matlabfns/．
［20］ GUO Y, SOHEL F, BENNAMOUN M, et al. A novel local surface feature for 3D object recognition under clutter and occlusion ［J］. Information Sciences, 2015, 293: 196-213．
