Previous 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


Journal of Information Science and Engineering, Vol. 24 No. 2, pp. 503-520 (March 2008)

A Pruning-and-Voting Strategy to Speed up the Detection for Lines, Circles, and Ellipses*

Kuo-Liang Chung+ and Yong-Huai Huang
Department of Computer Science and Information Engineering
National Taiwan University of Science and Technology
Taipei, 106 Taiwan

Shape analysis is a fundamental problem in image processing field. In shape analysis, lines, circles, and ellipses are three important features since they often occur in the image. Based on the determined windows on the edge map, this paper first presents a novel pruning-and-voting strategy to speed up the detection for lines, circles, and ellipses. Especially, our proposed strategy can be plugged into several existing randomized algorithms to reduce the required computation time while preserving the same robustness. In addition, some related time complexity analyses are provided to show the computational advantage of our proposed strategy. Under some real images, experimental results confirm our theoretic analyses.

Keywords: circles, ellipses, lines, pruning-and-voting strategy, randomized algorithms

Full Text () Retrieve PDF document (200803_12.pdf)

Received March 9, 2006; revised June 30, 2006; accepted August 3, 2006.
Communicated by Kuo-Chin Fan.
*This work was partially supported the National Science Council of Taiwan, R.O.C., under contracts No. NSC 91-2213-E011-049 and NSC94-2213-E-011-041.