在工業自動化檢測中經常需要偵測大量的圓形物件，雖然關於圓形偵測的演算法已經有非常多的研究，但其演算法的實作大部份是以個人電腦為發展平台；若要在嵌入式系統中實現即時圓形偵測，需要將演算法實現於FPGA或DSP中以降低功率消耗並提升系統可靠度。本論文使用以Altera Cyclone III FPGA為基礎的發展板做為開發平台，整合了影像輸入與輸出、影像前處理流程以及圓形偵測與定位之硬體模組於單顆FPGA晶片中，並搭配Nios II CPU與Avalon Bus進行軟硬體共同設計。在影像輸入的部份，實作完整的de-interlace架構，搭配後續的影像前處理模組可提供30fps去雜訊後的彩色影像與測邊後的二值化影像；在圓形偵測與定位的部份，我們實作重整邊點集的硬體架構，並設計基於隨機式測圓法的硬體加速模組以達成即時偵測的目標。本論文完成的系統整體時脈可運作於91.52MHz，偵測一張400x400的影像只需要4.1ms~4.7ms，並且能即時的將偵測結果標記於顯示畫面中；與其它圓形偵測硬體架構的研究相比較，本論文完成的系統不但在速度上有了明顯的改善，所偵測的影像大小也符合工業自動化中雙攝影機系統的需求。若研究上有需要，可來信向作者索取原始程式碼參考。

Circle Detection is commonly used in industrial automation. Although there are many researches of circle detection algorithm, these implementations are usually based on PC. In order to achieve real-time circle detection in the embedded system, we should implement the algorithm with FPGA or DSP to save power and to achieve reliability requirement. In this thesis, we use development board based on Altera Cyclone III FPGA to construct our system, integrating many hardware modules such as video input and output, image preprocessing, circle detection and location in a single FPGA chip. All cooperate with Nios II CPU and Avalon Bus to achieve HW/SW co-design. In the video input and output module, we implement complete de-interlace architecture, which can provide 30 fps de-noise color image and edge detected binary image to faciliate with follow image preprocessing module. In the circle detection and location module, we implement hardware architecture to compact edge point and design hardware acceleration module based on random circle detection algorithm to achieve real-time detection. Our system operate in 91.25MHz, takes 4.1ms~4.7ms to detect circles within video frame with size of 400x400 video size and mark detection result on monitor. Compare with circle deteciton hardware architectures, out system improve greatly in speed-up, also the video size is larger than previous hardware implementations. If you want to trace the souce code, mail to the author.

[1]蔡昇達，「以SoPC為基礎之自動化視覺檢測與定位系統」，碩士論文，國立台灣科技大學 (2009)。
[2]“Achieving Low Power in 65-nm Cyclone III FPGAs”, Altera Corporation White Paper (2007)
[3]Keith Jack , “Video Demystified: A Handbook for the Digital Engineer”, ELSEVIER, Burlington (2007)
[4]“High-Definition Video Deinterlacing Using FPGAs”, Altera Corporation White Paper (2009)
[5]Rafael C. Gonzalez, Richard E. Woods, “Digital Image Processing”, 2nd ed., Prentice Hall, New Jersey (2002)
[6]E. R. Davies, “Machine Vision - Theory, Algorithms, Practicalities”, 3rd ed., ELSEVIER, London (2005)
[7]Ramesh Jain, Randachar Kasturi, Brian G. Schunck, “Machine Vision”, 1st ed., McGRAW-HILL (1995)
[8]P. V. C. Hough, “Method and means for recognizing complex patterns” U.S. Patent 3,069,654 (1962)
[9]R. O. Duda and P. E. Hart, “Use of the Hough transformation to detect lines and curves in pictures” Commun, ACM, 15(1), pp. 11-15 (1972)
[10]X. Cao and F. Deravi, “An Efficient Method for Multiple-Circle Detection”, ICCV, Computer Vision, pp. 744-747 (1990)
[11]A. Goneid, S. El-Gindi and A. Sewisy, “A METHOD FOR THE HOUGH TRANSFORM DETECTION OF CIRCLES AND ELLIPSES USING A 1-DIMENSIONAL ARRAY”, 1997 IEEE International Conference on Volume 4, pp. 3154 – 3157 (1997)
[12]Dimitrios Ioannou, Walter Huda and Andrew F. Laine, “Circle recognistion through a 2D Hough Transform and radius histogrammig”, Image and Vision Computing 17, pp.15-26 (1999)
[13]鐘國亮, “影像處理與電腦視覺”, 3rd ed., 東華書局 (2006)
[14]M. Y. Chern and C. M. Dai, “Array Processor with Partitioned Memory for Hough Transform-based Circle Deteciton”, Proceedings of International Computer Symposium, Worshop on Computer Arcitecture, pp. 9-16 (2000)
[15]M. Y. Chern, “A Parallel Hardware and Associated Algorithm for Fast Detection of Circles and Symmetric Patterns”, Proceedings of International Computer Symposium, Worshop on Computer Systems, pp. 198-206 (2002)
[16]楊勝凱，「圓偵測並行處理機晶片系統設計實現：赫夫轉換與軌跡追蹤式之比較」，碩士論文，國立中正大學 (2005)
[17]詹祖懷，「快速圓形霍式轉換FPGA架構」，碩士論文，國立台灣科技大學 (2005)
[18]Priyadarshan Kolte, Roger Smith, Wen Su, “A Fast Median Filter Using AltiVec”, Proceedings of the 1999 IEEE International Conference on Computer Design, pp. 384-391 (1999)
[19]David A.Patterson, John L.Hennessy, “Computer Organization And Design - The Hardware/Software Interface”, 4th ed., ELSEVIER (2009)
[20]Clifford E. Cummings, “Synthesis and Scripting Techniques for Designing Multi-Asynchronous Clock Designs,” Synopsys Users Group , San Jose (2001)
[21]“Nios II System Architect Design Tutorial”, Altera Corporation Tutorial (2009)
[22]Fei Shang, Jinwei Liu, Xiao Zhang, Di Tian, "An Improved Circle Detection Method Based on Right Triangles Inscribed in a Circle," 2009 WRI World Congress on Computer Science and Information Engineering, csie, vol. 6, pp.382-387 ( 2009)
[23]T. C. Chen and K. L. Chung, “An efficient randomized algorithm for detecting circles”, Computer Vision and Image Understanding, 83, pp.172-191 (2001)
[24]蕭鴻森, “即時視訊處理架構之軟硬體共同設計”, 碩士論文, 國立台灣大學電機電信電子產業研發碩士專班(2009)
[25]“Cyclone II FPGA error data sheet”, Altera Corporation Error Data Sheet (2006)
[26]鄭子凡，「以多組CMOS感測器實現高速攝影系統之SOPC硬體架構」，碩士論文，國立台灣科技大學 (2007)
[27]陳首元，「基於SOPC平台之相機陣列式高速攝影系統軟體架構及影像校正設計」，碩士論文，國立台灣科技大學 (2007)