本文提出將SIFT影像辨識演算法實現於FPGA上，以解決影像辨識需要大量運算時間，而使得系統無法即時運算之問題。為了大幅減少邏輯單元之需求以及提升系統頻率，我們依照硬體適合之架構以及平行處理的優勢，針對SIFT演算法進行改良，如使用軟體預先計算高斯模板、使用數值方式避免反矩陣使用除法器以及將影像金字塔使用平行處理之架構實現等。除此之外，我們也使用CORDIC演算法進行三角函數、平方相加開根號以及反三角函數等實現，還有使用最佳化演算法找出高斯影像所需之最佳參數，並在硬體中進行連續高斯影像金字塔之近似，最後使用硬體實現影像梯度直方圖統計，如此一來就能於硬體中進行特徵主方向偵測以及特徵點描述之功能，而論文中會清楚介紹上述所提到之實現方法。而為了降低開發之困難性，首先以軟硬協同設計之架構對部分模組進行加速設計，完成後，再將整個系統以全硬體方式進行實現，值得一提的是，整個系統電路皆是由管線架構設計而成，因此可以大幅提升運算效率，進而達到即時運算之目標，從實驗結果證實，電路模組運算速度相較於軟體有大幅提升，而硬體實現結果相較於軟體之誤差也保有相當之精確度。

To solve the problem of image recognition, which requires plenty of computation time by software, we present a hardware implementation approach of SIFT recognition algorithm to achieve the goal of real time execution, through the use of offline calculation of the Gaussian kernel by software, a mathematical derivation to calculate inverse matrix without using any divisors, realization of image pyramid in parallel, etc. As a result, the system performs well in reducing a number of logic units required and the system frequency is significantly increased. In addition, the CORDIC algorithm is employed to implement not only mathematical functions such as trigonometric functions and square root computation, but also an image gradient histogram successfully by hardware. Consequently, the dominant orientation detection and key point descriptors can be implemented by image gradient histogram. To develop an applicable system, the first step is to apply the software and hardware co-design approach to accelerate functional modules and subsequenty implement the entire system in pure hardware. Besides, the structure of all modules is based on pipeline design. Experimental results demonstrated that the proposed approach has significantly reduced computation time required and efficiently increased maximum system frequency. Most importantly, the execution speed has achieved real time computation for practical applications.

[1] T. Emter, A. Stein, “Simultaneous Localization and Mapping with the Kinect sensor,” in Proc. of the 7th German Conference on ROBOTIK 2012, Munich, Germany, May. 2012, pp. 239–244.
[2] C. Mei, G. Sibley, M. Cummins, P. Newman, and I. Reid, “A constant time efficient stereo SLAM system,” in Proc. of the British Machine Vision Conference (BMVC), London, Dec. 2009.
[3] C. Harris and M. Stephens, “A Combined Corner and Edge Detector,” in Proc. of the Fourth Alvey Vision Conference, Manchester, UK, 1988, pp. 147–151.
[4] J. Canny, “A computational approach to edge detection,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no. 6, pp. 679–698, Nov. 1986.
[5] 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, pp. 11–15, Jan. 1972.
[6] D. G. Lowe, “Object recognition from local scale-invariant features,” in Proc. of the Seventh IEEE International Conference on Computer Vision, Kerkyra, Sep. 1999, vol. 2, pp. 1150–1157.
[7] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, Nov. 2004.
[8] H. Bay, A. Ess, T. Tuytelaars, and L. V. Gool, “SURF: Speeded Up Robust Features,” Computer Vision and Image Understanding, vol. 110, no. 3, pp. 309–432, June. 2008.
[9] Y. Ke, and R. Sukthankar, “PCA-SIFT: a more distinctive representation for local image descriptors,” in Proc. of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Washington, Jul. 2004, vol. 2, pp. 506–513.
[10] L. Juan, and O. Gwun, “A comparison of SIFT, PCA-SIFT and SURF”, International Journal of Image Processing (IJIP), vol. 3, no. 4, pp. 143–152, Oct. 2009.
[11] M. Calonder, V. Lepetit, M. Ozuysal, T. Trzcinski, C. Strecha, and P. Fua, “BRIEF: Computing a local binary descriptor very fast,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 34, no. 7, pp. 1281–1298, Jul. 2012.
[12] E. Rublee, W. Garage, M. Park, and California, “ORB: An efficient alternative to SIFT or SURF,” in Proc. of International Conference on Computer Vision, Barcelona, Nov. 2011, pp. 2564–2571.
[13] S. Leutenegger, M. Chli, and R. Y. Siegwart, “BRISK: Binary Robust invariant scalable keypoints,” in Proc. of International Conference on Computer Vision, Barcelona, Nov. 2011, pp. 2548–2555.
[14] A. A. K, and R. V. Babu, “ Speeding up SIFT using GPU,” in Proc. of National Computer Vision, Pattern Recognition, Image Processing and Graphics (NCVPRIPG), Jodhpur, Dec. 2013, pp. 1-4.
[15] H. Fassold, and J. Rosner, “A Real-time GPU Implementation of the SIFT Algorithm for Large-Scale Video Analysis Tasks,” in Proc. of Real-Time Image and Video Processing, Czech, Feb. 2015.
[16] V. Bonato, E. Marques, and G. A. Constantinides, “A parallel hardware architecture for scale and rotation invariant feature detection,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 18, no. 12, pp. 1703–1712, Dec. 2008.
[17] L. Yao, H. Feng, Y. Zhu, Z. Jiang, D. Zhao, and W. Feng, “An architecture of optimised SIFT feature detection for an FPGA implementation of an image matcher,” in Proc. of the International Conference on Field-Programmable Technology, Sydney, NSW, Dec. 2009, pp. 30–37.
[18] J. Wang, S. Zhong, L. Yan, and Z. Cao, “An embedded system-on-chip architecture for real-time visual detection and matching,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 24, no. 3, pp. 525–538, Mar. 2014.
[19] J. Jiang, X. Li, and G. Zhang, “SIFT hardware implementation for real-time image feature extraction,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 24, no. 7, pp. 1209–1220, Jul. 2014.
[20] http://store.irobot.com/irobot-roomba-780/product.jsp?productId=11305111
[21] http://www.neatorobotics.com/robot-vacuum/botvac/botvac-85/
[22] J. D. Volder, “The CORDIC Computing Technique,” in Proc. of the Western Joint Computer Conference (WJCC) , California, 1959, pp. 257–261.
[23] Altera多媒體發展平台DE2-70網址，URL: http://www.altera.com/education/univ/materials/boards/de2-70/unv-de2-70-board
[24] Terasic Corporation, URL:http://www.terasic.com.tw/tw/
[25] Terasic, THDB-D5M_Hardware specification, Document Version 1.0, 2008.
[26] Terasic Corporation, TRDB_D5M_UserGuide, Document Version 1.0, 2008.