本論文提出以多重解析全域搜尋之影像特徵描述子匹配演算法為基礎，以硬體描述語言實現影像特徵描述子匹配加速器，並應用於影像處理中的物件辨識及追蹤。在影像辨識與追蹤的研究中，常需要找出影像中物體模型的特徵點並做兩張影像的特徵點匹配運算。當特徵點的維度過高時，要比對兩邊的特徵資料需要花費較多的運算時間，而無法達到物件追蹤上的即時性。而多重解析全域搜尋之影像特徵描述子匹配演算法在這匹配議題上有著不錯的改善效果，此匹配演算法透過降維的方式將特徵描述子向量建立成一張多重解析表。其記錄著特徵描述子降維後的多層特徵點描述子向量。本文利用多重解析表計算兩特徵描述子向量的距離，以加速篩選候選點的速度。此演算法在運算上簡單且有許多重複的運算，所以其適合用硬體電路做平行化計算。故本文提出以硬體描述語言實現多重解析全域搜尋之影像特徵描述子匹配演算法硬體加速器。

This thesis proposes an image feature descriptor matching accelerator for multi-resolution exhaustive search algorithm by hardware description language. The accelerator can apply to image recognition and tracking. In the image recognition and tracking research, the computer usually finds keypoints of the object model in image and computes keypoints matching for object feature descriptor. When the feature descriptor dimension is too high, the image processing must take a lot of computing time. Therefore it can’t achieve real-time image recognition and tracking. The multi-resolution exhaustive search algorithm has a good improving effect on the matching subject. The matching algorithm establishes a table of multi-resolution by reducing keypoint dimension. The multi-resolution table records the vector of multi-layer feature descriptor after feature descriptor dimensionality reduction. In this paper, we use the multiple resolution table to compute the distance between two feature descriptor vectors, and filter quickly the candidate points speed. This matching algorithm is simple in operation and has many repeat operations, so it is suitable for parallel computing with hardware circuitry. Therefore, this paper proposes to hardware description language to achieve multiple video analytic features global search algorithm to match the descriptors hardware accelerators.

目錄
第 1 章 緒論	1
1.1 研究背景	1
1.2 研究動機	4
1.3 論文架構	5
第 2 章 多重解析全域搜尋之影像特徵描述子匹配演算法	6
2.1特徵描述子與Lp空間介紹	7
2.2多重解析全域搜尋之影像特徵描述子匹配演算法	10
第 3 章 硬體電路設計之系統架構介紹	15
3.1硬體電路設計介紹	15
3.2特徵描述子匹配加速器系統介紹	16
第 4 章 模擬與實驗結果	37
4.1影像的參考資料庫	37
4.2演算法的參數選擇	37
4.3模擬環境	40
4.4模擬結果	41
第 5 章 結論與未來展望	44
參考文獻	45

 
圖目錄
圖 2.1、多重解析全域搜尋之影像特徵描述子匹配演算法流程圖	7
圖 2.2、SURF流程圖	8
圖 2.3、SURF描述子示意圖	9
圖 2.4、特徵描述子降維示意圖	12
圖 2.5、篩選候選點流程圖	14
圖 3.1、系統架構示意圖	17
圖 3.2、第一版加速器系統流程圖	18
圖 3.3、第一版的篩選候選點流程圖	19
圖 3.4、第一版硬體加速器之系統架構示意圖	20
圖 3.5、第一版參數模組示意圖	21
圖 3.6、第一版降維模組示意圖	21
圖 3.7、第一版距離誤差模組示意圖	22
圖 3.8、第一版閥值計算模組示意圖	23
圖 3.9、第一版匹配模組示意圖	23
圖 3.10、第一版資料緩衝器模組示意圖	24
圖 3.11、第一版參考資料緩衝器模組示意圖	25
圖 3.12、第一版距離誤差緩衝器模組示意圖	25
圖 3.13、第一版匹配點緩衝器模組示意圖	26
圖 3.14、第一版特徵描述子匹配加速器之系統架構流程示意圖	26
圖 3.15、第二版加速器系統流程圖	28
圖 3.16、平行化流程示意圖	28
圖 3.17、第二版硬體加速器之系統架構示意圖	29
圖 3.18、第二版參數模組示意圖	30
圖 3.19、第二版降維模組示意圖	30
圖 3.20、第二版曼哈頓距離模組示意圖	31
圖 3.21、第二版閥值計算模組示意圖	32
圖 3.22、第二版匹配模組示意圖	32
圖 3.23、第二版歐基里德距離模組示意圖	33
圖 3.24、第二版資料緩衝器模組示意圖	34
圖 3.25、第二版參考資料緩衝器模組示意圖	34
圖 3.26、第二版距離誤差緩衝器模組示意圖	35
圖 3.27、第二版匹配點緩衝器模組示意圖	36
圖 3.28、第二版特徵描述子匹配加速器之系統架構流程示意圖	36
圖 4.1、實驗用參考原圖	38
圖 4.2、實驗用輸入原圖	39
圖 4.3、模擬環境示意圖	41

 
表目錄
表 4.1、參數 "β " 在不同設置下之實驗結果	39
表 4.2、參數t在不同設置下之實驗結果	40
表 4.3、特徵描述子匹配加速器之模擬實驗結果	42

參考文獻
[1]	D. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91-110, 2004.
[2]	H. Bay, T. Tuytelaars, and L. V. Gool, “SURF: Speeded up Robust Features,” International Conference on Computer Vision, pp. 404-417, 2006.
[3]	J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, vol. 18, no. 9, pp. 509-517, 1975. 
[4]	S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu, “An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions,” Journal of the ACM (JACM), vol. 45, no. 6, pp. 891-923, 1998.
[5]	M. Muja and D. G. Lowe, “Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration,” International Conference on Computer Vision Theory and Applications, pp. 331-340, 2009.
[6]	A. Andoni and P. Indyk, “Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions,” IEEE  International Conference on Foundations of Computer Science, vol. 51, no. 1, pp. 117-122, 2008.
[7]	C. S. Anan and R. Hartley, “Optimised K-D trees for Fast Image Descriptor Matching,” IEEE International Conference on Computer Vision and Pattern Recognition, pp. 1-8, 2008.
[8]	D. Nistér and H. Stewénius, “Scalable recognition with a vocabulary tree,” IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, pp. 2161-2168, 2006.
[9]	B. C. Song, M. J. Kim, and J. B. Ra, “A Fast Multiresolution Feature Matching Algorithm for Exhaustive Search in Large Image Databases,” IEEE International Conference on Circuits and Systems for Video Technology, vol. 11, no. 5, pp. 673-678, 2001.
[10]	B. C. Song and J. B. Ra, “Multiresolution Descriptor Matching Algorithm for Fast Exhaustive Search in Norm-Sorted Databases,” Journal of Electron Imaging, vol. 14, no. 4, 2005.
[11]	C. Y. Tsai, C. H. Huang, and A. H. Tsao, “Graphics Processing Unit-Accelerated Multi-Resolution Exhaustive Search Algorithm for Real-Time Keypoint Descriptor Matching in High-Dimensional Spaces,” The Institution of Engineering and Technology, vol. 10, no. 3, pp. 212-219, 2016.
[12]	曹安宏，以GPU運算技術實現即時多重解析全域搜尋之影像特徵描述子匹配演算法，淡江大學電機工程學系碩士論文（指導教授：蔡奇謚），2013。
[13]	余家潤，即時人臉偵測之軟硬體共同設計，淡江大學電機工程學系碩士論文（指導教授：翁慶昌），2010。
[14]	翁仲緯，軟硬體共同設計於取放作業之路徑規劃，淡江大學電機工程學系碩士論文（指導教授：李世安），2014。
[15]	影像資料庫, URL: http://vis.uky.edu/~stewe/ukbench/