Basic Search / Detailed Display

Author: 鄭名劭
Ming-shao Cheng
Thesis Title: 植基於曲率淘汰策略及半徑估計的快速圓偵測演算法
Curvature–Based Elimination Strategy and Radius Estimation for Fast Circle–Detection
Advisor: 鍾國亮
Kuo-liang Chung
Committee: 陳建中
Jiann-jone Chen
陳宏銘
Homer-H Chen
范國清
Kuo-chin Fan
廖弘源
Hong-yuan Liao
Degree: 碩士
Master
Department: 電資學院 - 資訊工程系
Department of Computer Science and Information Engineering
Thesis Publication Year: 2010
Graduation Academic Year: 98
Language: 中文
Pages: 46
Keywords (in Chinese): 圓偵測曲率淘汰策略哈克轉換半徑估計.
Keywords (in other languages): Circle detection, curvature, elimination strategy, Hough transform, radius estimation.
Reference times: Clicks: 492Downloads: 0
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  • 圓的偵測是影像處理領域中的一個基礎問題。一般來說,哈克轉
    換是一種最常見的圓偵測演算法。然而,針對輸入影像,哈克轉換需
    花費許多的執行時間在三維的累積陣列上完成投票程的程序。為了提
    高哈克轉換的時間效率,本篇論文首先提出一個植基於曲率的淘汰策
    略來減少參與投票程序的邊點數量。根據每個邊點的曲率,我們將較
    不可能位於圓周上的邊點濾除,只留下少量邊點參與投票程序。除此
    之外,利用邊點的曲率,本篇論文也提出了一個半徑估計的機制。根
    據估計的半徑及邊點的梯度方向,每個邊點只需要在一個變動的半徑
    範圍內進行投票,因此可降低哈克轉換的執行時間。實驗結果顯示,
    與其他四種已知的圓偵測演算法相比之下,本篇論文所提出的快速演
    算法可達到較佳的時間效率,其執行時間的平均改善率能達到
    87.67%。


    Circle-detection is an important issue in the image processing. In
    general, the Hough transform is most common method for detecting
    circles from digital images. However, given an input image, the Hough
    transform consumes a lot of time to perform the voting process on a 3-D
    accumulator array. To improve the execution-time performance of the
    Hough transform, we first present curvature-based elimination strategy to
    reduce the number of edge pixels considered in the voting process. Based
    on the curvatures of edge pixels, we discard those edge pixels which have
    lower probability of lying on circles and only a small amount of edge
    pixels will be considered in the voting process. Further, the curvature of
    each edge pixel is also considered in our proposed radius estimation
    scheme to estimate the radius of the circle. Based on the estimated radius
    and the gradient direction, each edge pixel only considers a range of
    radius rather than considers all possible centers and radiuses to perform
    the voting process. Combining the proposed curvature-based
    elimination strategy and radius estimation scheme, the proposed fast
    circle detection algorithm is presented. Experimental results demonstrate
    that the proposed algorithm has 87.67% average execution-time
    improvement ratio when compared to four currently published
    algorithms.

    目錄 ................................................................... i 圖目錄 ................................................................iii 表目錄 .................................... ............................vi 1. 緒論 ................................................................ 1 2. 相關研究 ............................................................ 3 3. 植基於曲率淘汰策略與半徑估計之測圓演算法 ........................... 14 3.1 邊點偵測 .......................................................... 15 3.2 平均曲率計算 ...................................................... 16 3.3 植基於曲率之邊點淘汰策略 .......................................... 18 3.4 植基於曲率淘汰策略與半徑估計之測圓演算法 .......................... 23 4. 實驗結果 ........................................................... 29 4.1 標準哈克測圓(SHT)實驗結果討論 ..................................... 30 4.2 CTEA 實驗結果討論 ................................................. 32 4.3 ACOD 實驗結果討論 ................................................. 35 4.4 EVCD 實驗結果討論 ..................................................36 4.5 CFHT 實驗結果討論 ................................................. 37 4.6 測圓演算法執行時間與準確度比較 .................................... 39 5. 結論 ............................................................... 43 參考文獻 .............................................................. 44

    [1] E. R. Davies, Machine Vision: Theory, Algorithms, Practicalities, Academic
    Press, London, 1990.
    [2] J. Illingworth and J. Kittler, “A survery of the hough transform,” Computer
    Vision, Graphics, and Image Processing, vol. 44, no. 1, pp. 87-116, Oct.1988.
    [3] V. F. Leavers, “Survey: Which hugh transform,” CVGIP: Image Understanding,
    vol. 58, no. 2, pp. 250-264, Sep. 1993.
    [4] R. K. K. Yip, P. K. S. Tam, and D. N. K. Leung, “Modification of Hough
    transform for circles and ellipses detection using a 2-dimensional array,"
    Pattern Recognition, vol. 25, no. 9, pp. 1007–1022, Sep. 1992.
    [5] D. H. Ballard, “ Generalizing the Hough Transform to detect arbitrary
    shapes," Pattern Recognition, vol. 13, no. 2, pp. 111–122, 1981.
    [6] E. R. Davies, “A modified Hough scheme for general circle location,"
    Pattern Recognition, vol. 7, no. 1, pp. 37–43, Jan. 1981.
    [7] C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of
    accumulators," Communication of the ACM, vol. 18, no. 2, pp. 120–122, Feb.
    1975.
    [8] N. Kiryati, Y. Eldar, and A. M. Bruckstein, “ A probabilistic Hough
    transform." Pattern Recognition, vol. 24, no. 4, pp. 303–316, 1981.
    [9] L. Xu, E. Oja, and P. Kultanan, “A new curve detection method: Randomized
    Hough transform (RHT)," Pattern Recognition, vol. 11, no. 5, pp. 331–338,
    May. 1990.
    45
    [10] L. Xu and E. Oja, “Randomized Hough transform (RHT): Basic mechanisms,
    algorithms, and computational complexities," CVGIP: Image Understanding,
    vol. 57, no. 2, pp. 131-154, Mar. 1993.
    [11] S. H. Chiu and J. J. Liaw, “An effective voting method for circle detection,”
    Pattern Recognition Letters, vol. 26, no. 2, pp. 121-133, Jan. 2005.
    [12] C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric
    symmetry," Pattern Recognition, vol. 28, no. 1, pp. 117–124, Jan. 1995.
    [13] C. T. Ho and L. H. Chen, “A high-speed algorithm for elliptical object
    detection," IEEE Transactions on Image Processing, vol. 5, no. 3, Mar. 1996.
    [14] C. Zhong, D. He, and W. Guoyou, “A new circle targets extraction algorithm,”
    IEEE International Conference on Multimedia Information Networking and
    Security, vol.1, pp. 301-304, 2009.
    [15] C. N. Young and J. J. Zou, “Adaptive circular object detection,” IEEE
    International Conference on Signal Processing and Communication Systems, pp.
    1-6,2008.
    [16] J. Illingworth and J. Kittler, “The adaptive hough transform,” IEEE Transactions
    on Pattern Analysis and Machine Intelligence, vol. PAMI-9, no. 5, pp. 690-698,
    1987.
    [17] H. Li, M. A. Lavin, and R. J. LeMaster, “Fast hough transform: A hierarchical
    approach, ” Computer Vision, Graphics, and Image Processing, vol. 36, no. 2-3,
    pp. 139-161, Dec.1986.
    [18] S. Y. Guo, X. F. Zhang, and F. Zhang, “ Adaptive randomized Hough
    transform for circle detection using moving window," IEEE International
    46
    Conference on Machine Learning and Cybernetics, pp. 3880-3885, Aug. 2006.
    [19] P. F. Zhang and Q. M. Li, “Research on iris image preprocessing algorithm,"
    IEEE International Conference on Machine Learning and Cybernetics, vol. 8, pp.
    5220-5224, 2005.
    [20] J. Canny, “A computational approach to edge detection," IEEE Transactions
    on Pattern Analysis and Machine Intelligence, vol. 8, No. 6, pp. 679-698, 1986.

    無法下載圖示 Full text public date 2015/06/07 (Intranet public)
    Full text public date This full text is not authorized to be published. (Internet public)
    Full text public date This full text is not authorized to be published. (National library)
    QR CODE