Author: |
申希明 Hsi-ming Shen |
---|---|

Thesis Title: |
有效率的取樣策略和精煉策略用於隨機式測圓 Efficient Sampling Strategy and Refinement Strategy forRandomized Circle Detection |

Advisor: |
鍾國亮
Kuo-Liang Chung |

Committee: |
賴榮滄
Zone-Chang Lai 陳世旺 Sei-Wang Chen 曾定章 Din-Chang Tseng 楊傳凱 Chuan-Kai Yang |

Degree: |
碩士 Master |

Department: |
電資學院 - 資訊工程系 Department of Computer Science and Information Engineering |

Thesis Publication Year: | 2010 |

Graduation Academic Year: | 98 |

Language: | 英文 |

Pages: | 33 |

Keywords (in Chinese): | 取樣策略 、強健性 、精煉 、隨機式演算法 、查表法 、哈克轉換 、圓形偵測 |

Keywords (in other languages): | Sampling Strategy, Refinement, Randomized algorithms, Robustness, Lookup table, Hough transform, Circle detection |

Reference times: | Clicks: 295 Downloads: 1 |

Share: |

School Collection Retrieve National Library Collection Retrieve Error Report |

在影像處理和圖形識別領域，圓形偵測是很重要且基本的方法。本論文分為兩部份，第一部份提出了以法線為基礎的抽樣策略來決定候選圓，較傳統的隨機式測圓有更高的機率使得候選圓成為真圓，大大的降低了計算時間。為了提昇準確率，第二部份提出以重新投票為基礎的精煉策略。實驗結果顯示和先前有關的隨機式測圓相比，以我們提出的以法線為基礎的抽樣策略和以重新投票為基礎的精煉策略來測圓，大大的降低了計算時間且有更好的準確率。

Circle-detection is an important and fundamental operation in image

processing and pattern recognition. This thesis first presents a new

gradient line-based sampling strategy to determine a candidate

circle and the determined candidate circle has higher probability to

be promoted to a true circle when compared with the traditional

randomized strategy; it leads to significantly computational effect.

Further, for enhancing the detection accuracy, a new revoting-based

refinement strategy is presented. Experimental results demonstrated

that our proposed gradient line-based sampling strategy and

revoting-based refinement strategy can significantly improve

computing time performance and the detection accuracy for circle

detection when compared with previous randomized related algorithms.

1 Introduction 1
2 Problems in Past Sampling Strategy and Refinement Scheme 4
2.1 Sampling strategy in the RCD leads to bias and computational overhead
problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Lee et al.’s RCD–based refinement strategy leads to the time consuming
problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 The Proposed Gradient Line-Based Sampling Strategy 10
4 The Proposed New Refinement Scheme 16
5 Experimental results 21
6 Conclusion 30

[1] D. H. Ballard, “Generalizing the Hough transform to detect arbitrary shapes,” Pattern Recognition, Vol. 13, No. 2, 1981, pp. 111–122.

[2] J. E. Bresenham, “Algorithm for computer control of a digital plotter,” IBM System Journal, Vol. 4, No. 1, 1965, pp. 25–30.

[3] J. E. Bresenham, “A linear algorithm for incremental digital display of circular arcs,”Communications of the ACM, Vol. 20, No. 2, 1977, pp. 100–106.

[4] T. C. Chen and K. L. Chung, “An efficient randomized algorithm for detecting circles,”Computer Vision and Image Understanding, Vol. 83, No. 2, 2001, pp. 172–191.

[5] S. H. Chiu and J. J. Liaw, “An effective voting method for circle detection,” Pattern Recognition Letters, Vol. 26, No. 1, 2005, pp. 121–133.

[6] K. L. Chung and Y. H. Huang, “Speed up the computation of randomized algorithms for detecting lines, circles, and ellipses using novel tuning-and LUT-based voting platform,” Applied Mathematics and Computation, Vol. 190, No. 1, 2007, pp. 132–149.

[7] K. L. Chung and Y. H. Huang, “A pruning-and-voting strategy to speed up the detection for lines, circles, and ellipses,” Journal of Information Science and Engineering, Vol. 24, No. 2, 2008, pp. 503–520.

[8] E. R. Davies, “Truncating the Hough transform parameter space can be beneficial,”Pattern Recognition Letters, Vol. 24, No. 1–3, 2003, pp. 129–135.

[9] E. R. Davies, Machine Vision: Theory, Algorithms, Practicalities, third ed., Morgan Kaufmann, San Fransisco, CA, 2004.

[10] R. O. Duda and P. E. Hart, “Use of the Hough transformation to detect lines and curves in pictures,” Communications of the ACM, Vol. 15, No. 1, 1972, pp. 11–15.

[11] D. A. Forsyth, Computer Vision: A Modern Approach, Prentice-Hall, New Jersey, 2002.

[12] R. Gonzalez and R. Woods, Digital Image Processing, Addison Wesley, New York, 1992.

[13] C. T. Ho and L. H. Chen, “A fast ellipse/circle detector using geometric symmetry,”Pattern Recognition, Vol. 28, No. 1, 1995, pp. 117–124.

[14] P. V. C. Hough, “Method and means for recognizing complex patterns,” US Patent# 3,069,654, 1962.

[15] P. V. C. Hough, Method and means for recognizing complex patterns, Addison Wesley, New York, 1992.

[16] D. Hearn and M. P. Baker, Computer Graphics, third ed., Prentice-Hall, New Jersey, 1997.

[17] J. Illingworth and J. Kittler, “The adaptive Hough transform,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 9, No. 5, 1987, pp. 690–698.

[18] J. Illingworth and J. Kittler, “Survey: Survey of the Hough Transforms,” Computer Vision, Graphics, and Image Processing, Vol. 44, No. 1, 1988, pp. 87–116.

[19] D. Ioannou, W. Huda, and A. F. Laine, “Circle recognition through a 2D Hough transform and radius histogramming,” Image and Vision Computing, Vol. 17, No. 1, 1999, pp. 15–26.

[20] R. Jain, R. Kasturi, and B. G. Schunck, Machine Vision, McGraw-Hill, Columbus, OH, 1995.

[21] M. R. Kappel, “An ellipse-drawing algorithms for faster displays,” Fundamental Algorithms for Computer Graphics, 1985, pp. 257–280.

[22] H. S. Kim and J. H. Kim, “A two-step circle detection from the intersecting chords,”Pattern Recognition Letters, Vol. 22, No. 6–7, 2001, pp. 787–798.

[23] C. Kimme, D. Ballard, and J. Sklansky, “Finding circles by an array of accumulator,”Communications of the ACM, Vol. 18, No. 2, 1975, pp. 120–122.

[24] N. Kiryati, Y. Eldar, and A. M. Bruckstein, “A probabilistic Hough transform,”Pattern Recognition, Vol. 24, No. 4, 1991, pp. 303–316.

[25] J. R. J. Lee, M. L. Smith, L. N. Smith and P. S. Midha, “Robust and efficient automated detection of tooling defects in polished stone,” Computers in Industry, Vol. 56, No. 8, 2005, pp. 787–801.

[26] L. Xu, E. Oja, and P. Kultanan, “A new curve detection method: randomized Hough transform (RHT),” Pattern Recognition Letters, Vol. 11, No. 5, 1990, pp. 331–338.

[27] L. Xu and E. Oja, “Randomized Hough transform (RHT): basic mechanisms, algorithms, and computational complexities,” Computer Vision Graphic Image Process: Image Understanding, Vol. 57, No. 2, 1993, pp. 131–154.

[28] 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, 1992, pp. 1007–1022.

[29] A. Yl¨a-J¨a¨aski and N. Kiryati, “Adaptive termination of voting in probabilistic Hough transform,” IEEE Trans on Pattern Analysis and Machine Intelligence, Vol. 16, No. 9, 1994, pp. 911–915.

- Two-User MISO Broadcast Channel with Delayed CSIT and Unequal Received Signal-to-Noise Ratio
- Fast Randomized Algorithm for Center-Detection
- Lightweight and Robust Authentication Scheme Based on PUF Technology in Internet of Vehicles Environment
- Investigations of coordinating the conflict between the driver and a lane keeping assist controller
- New Orientation Elimination-Based Algorithms for Detecting Lines