Robust ellipse detection based on hierarchical image pyramid and Hough transform

被引:20
作者
Chien, Chung-Fang [1 ]
Cheng, Yu-Che [1 ]
Lin, Ta-Te [1 ]
机构
[1] Natl Taiwan Univ, Dept Bioind Mechatron Engn, Taipei 106, Taiwan
关键词
TRANSMISSION; SYMMETRY; EXTRACTION; ALGORITHM; LINES;
D O I
10.1364/JOSAA.28.000581
中图分类号
O43 [光学];
学科分类号
070207 ; 0803 ;
摘要
In this research we propose a fast and robust ellipse detection algorithm based on a multipass Hough transform and an image pyramid data structure. The algorithm starts with an exhaustive search on a low-resolution image in the image pyramid using elliptical Hough transform. Then the image resolution is iteratively increased while the candidate ellipses with higher resolution are updated at each step until the original image resolution is reached. After removing the detected ellipses, the Hough transform is repeatedly applied in multiple passes to search for remaining ellipses, and terminates when no more ellipses are found. This approach significantly reduces the false positive error of ellipse detection as compared with the conventional randomized Hough transform method. The analysis shows that the computing complexity of this algorithm is Theta(n(5/2)), and thus the computation time and memory requirement are significantly reduced. The developed algorithm was tested with images containing various numbers of ellipses. The effects of noise-to-signal ratio combined with various ellipse sizes on the detection accuracy were analyzed and discussed. Experimental results revealed that the algorithm is robust to noise. The average detection accuracies were all above 90% for images with less than seven ellipses, and slightly decreased to about 80% for images with more ellipses. The average false positive error was less than 2%. (C) 2011 Optical Society of America
引用
收藏
页码:581 / 589
页数:9
相关论文
共 36 条
[1]   GENERALIZING THE HOUGH TRANSFORM TO DETECT ARBITRARY SHAPES [J].
BALLARD, DH .
PATTERN RECOGNITION, 1981, 13 (02) :111-122
[2]  
Bongiovanni G., 1990, Machine Vision and Applications, V3, P117, DOI 10.1007/BF01212195
[3]  
Chien CF, 2002, T ASAE, V45, P1669
[4]  
CHIEN CW, 2003, THESIS NATL TAIWAN U
[6]   USE OF HOUGH TRANSFORMATION TO DETECT LINES AND CURVES IN PICTURES [J].
DUDA, RO ;
HART, PE .
COMMUNICATIONS OF THE ACM, 1972, 15 (01) :11-&
[7]  
ESPINOSA C, 1992, ELEVENTH ANNUAL INTERNATIONAL PHOENIX CONFERENCE ON COMPUTERS AND COMMUNICATIONS, P743, DOI 10.1109/PCCC.1992.200515
[8]   COMPARATIVE PERFORMANCE OF PYRAMID DATA-STRUCTURES FOR PROGRESSIVE IMAGE TRANSMISSION [J].
GOLDBERG, M ;
WANG, L .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1991, 39 (04) :540-548
[9]   Lower order circle and Ellipse Hough Transform [J].
Guil, N ;
Zapata, EL .
PATTERN RECOGNITION, 1997, 30 (10) :1729-1744
[10]  
Haralick Robert M, 1992, Computer and Robot Vision, V1, P4