本論文係有關基於鏈結串列之霍夫轉換直線偵測演算處理器之軟/硬體整合設計與實現，研究工作包含四大部分：
第一部分為在分析演算法特性並考量嵌入式系統之記憶體資源限制後，發展出基於鏈結串列之霍夫轉換直線偵測演算法，並以C程式語言撰寫相關軟體，以驗證其功能之正確性。
第二部分為設計與開發基於鏈結串列之霍夫轉換直線偵測演算處理器，其組成包括控制單元、來源資料記憶體、有效像素邏輯、座標暨記憶體位址產生器、霍夫參數產生器和基於鏈結串列之霍夫轉換直線偵測演算副處理器。最後，將上述硬體設計整合於可程式系統單晶片中，並實現於Altera FPGA開發板上。
第三部分為實現與驗證基於鏈結串列之霍夫轉換直線偵測演算處理器軟/硬體整合設計，藉由NIOS II整合式開發環境撰寫相關軟體及驅動程式，並進行功能驗證與分析。
第四部分為演算法及演算處理器執行效能之評估。
整體而言，本論文的目標為研究基於鏈結串列之霍夫轉換直線偵測演算法及其演算處理器之軟硬體整合設計與實現，並將之實現於Altera FPGA開發板上，以證實其能顯著地改善原始演算法之執行及記憶體效能。

This thesis is related to the hardware/software codesign and implementation of a linked-list-based Hough-transform algorithmic processor for line detection. The research includes four parts:

The first part is to analyze the property of the algorithm and, after considering that the embedded systems have limited memory resources, a linked-list-based Hough-transform algorithm for line detection has been developed. Also the C language is used to write the program for implementing and verifying the proposed algorithm.

The second part is to design and develop a linked-list-based Hough-transform algorithmic processor for line detection. This algorithmic processor consists of a control unit, a source data buffer, a valid-pixel logic, a coordinate-and-address generator, a Hough-parameter generator, and a linked-list-based Hough-transform algorithmic subprocessor. The algorithmic processor is integrated onto a SOPC-based chip and implemented on an Altera FPGA development board.

The third part is about the hardware/software codesign of a linked-list-based Hough-transform algorithmic processor for line detection. Software and driver programs are developed by using the NIOS II integrated development environment to verify and analyze the function of this algorithmic processor.

The fourth part is to evaluate the performance of the algorithm and the algorithmic processor.
In conclusion, the goal of this thesis is: (1) to develop a linked-list-based Hough-transform algorithm for line detection; (2) to finish the hardware/software codesign and implementation of the HT-based algorithmic processor. Finally, by implementing this algorithmic processor on an FPGA development board, both the modified algorithm and the related algorithmic processor are proved to be more memory-efficient and have better performance.

[1] P. V. C. Hough, Method and means for recognizing complex patterns, U.S. Patent 3,069,654, 1962.
[2] P. V. C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959.
[3] R. O. Duda and P. E. Hart, Use of the Hough Transformation to Detect Lines and Curves in Pictures, Comm. ACM, Volume 15, pp.11-15, 1972.
[4] P. E. Hart, How the Hough Transform was Invented, IEEE Signal Processing Magazine, 2009.
[5] P. Mukhopadhyay and B. B. Chaudhuri, A survey of Hough Transform, Pattern Recognition, Volume 48, Issue 3, 2015.
[6] J. Illingworth and J. Kittler, A survey of the hough transform, Computer Vision, Graphics, and Image Processing, Volume 44, Issue 1, 1988.
[7] K. L. Chung, Z. W. Lin, S. T. Huang, Y. H. Huang, and H. Y. M. Liao, New orientation-based elimination approach for accurate line-detection, Pattern Recognition Letters, Volume 31, Issue 1, 2010.
[8] T. Petković and S. Lončarić, An Extension to Hough Transform Based on Gradient Orientation, Proceedings of the Croatian Computer Vision Workshop, 2015.
[9] R. C. Gonzalez and R. E. Woods, Digital Image Processing, Addison-Weslay Publishing Company, Inc, 1993.
[10] L. G. Shapiro and G. C. Stockman, Computer Vision, Pearson, 2001.
[11] M. D. Ciletti, Advanced Digital Design with the Verilog HDL, Pearson, 2011.
[12] E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamemtals of Data Structures in C, Silicon Press, 2008.
[13] M. Sonka, V. Hlavac, and R. Boyle, Image Processing, Analysis, amd Machine Vision, PWS Publishing, 1999.
[14] D. G. Bailey, Design for Embedded Image Processing on FPGAs, Wiley Publishing, 2011.
[15] Altera Corporation, NIOS Development Board Stratix II Editon Refrence Manual, 2007.
[16] Altera Corporation, Nios II Classic Processor Reference Guide, edition NII5V1, 2016.
[17] Altera Corporation, Quartus II Handbook, 2010.
[18] Altera Corporation, Avalon Bus Specification Reference Manual, Altera Corporation, 2002.
[19] Altera Corporation, SOPC Builder User Guide, 2010.
[20] IEEE, IEEE Standard for Verilog Hardware Description Language, IEEE Standard 1364-2005, 2006.
[21] 黃健軒，HT-based直線偵測兩階段演算處理器之軟/硬體整合設計與實現，國立臺灣科技大學碩士學位論文，民國100年。
[22] 陳鶴仁，SOPC-Based 演算處理器驗證系統之硬體設計，國立臺灣科技大學碩士學位論文，民國95年。
[23] 許博翔，多像素管線式單回合聯通物件標示演算處理器之軟/硬整合設計與實現，國立臺灣科技大學碩士學位論文，民國101年。
[24] 龔柏元，基於FPGA單次迭代平行細線化演算法處理系統之設計與實現，國立臺灣科技大學碩士學位論文，民國104年。
[25] 方毅瑋，兩階段區塊式圓形霍夫轉換演算處理系統之軟/硬整合設計與實現，國立臺灣科技大學碩士學位論文，民國107年。