影像特徵描述子匹配是許多電腦視覺應用中重要的前處理工作，本文提出一種多重解析全域搜尋演算法與多重解析候選點移除方法，有效地解決這個議題。所提出的演算法首先會由一張輸入影像與一張參考影像，透過特徵點描述子演算法求得特徵點及特徵點描述子。接著，使用L1-norm計算方法將兩影像的特徵點描述子集合做降維(Dimensionality reduction)的運算，每個特徵點描述子都會得到一張多重解析表(multi-resolution tables)，其記錄著特徵描述子向量降維後的多層特徵點描述子向量。最後，利用所建立出的多重解析表，便可以利用距離函數計算兩描述子向量的低維度距離，加速篩選候選點的速度。另一方面，所提出的演算法實現於CPU上時，我們發現在執行建立多重解析表之步驟時運算動作較沒效率，而此步驟又很適合實現於GPU平行化技術上，所以本文亦提出了以GPU加速運算方式來實現所提出的影像特徵描述子匹配演算法。在實驗測試中，本文所提出之演算法與現有三種方法比較後，所提出之演算法無論在運算速度或匹配準確度上，都能達到不錯的效能。

Image feature descriptor matching is an important pre-processing task in various computer vision applications. This thesis presents a multi-resolution exhaustive search algorithm combined with a multi-resolution candidate elimination technique to address this issue efficiently. The proposed algorithm first uses a SIFT-like algorithm to extract image feature points and the corresponding feature descriptors of an input image and a reference image, respectively. A multi-resolution table of each feature descriptor is then computed by using a L1-norm based dimension reduction approach. Finally, a fast candidate elimination algorithm is developed based on the multi-resolution tables to remove all non-candidates from a candidate list by using a simple L1-norm computation. When the proposed algorithm was implemented on CPU, we observed that the step of multi-resolution table building is not computationally efficient on CPU, but it is very suitable for parallel implementation on GPU. Therefore, this thesis also presents a GPU acceleration method for the proposed image feature descriptor matching algorithm to achieve better real-time performance. Experimental results validate the computational efficiency and matching accuracy of the proposed algorithm by comparing with three existing methods.

中文摘要	I
Abstract	II
目錄	III
圖目錄	VI
表目錄	VIII
第一章	 序論	1
1.1	 研究背景	1
1.2	 研究動機與目的	4
1.3	 論文架構	6
第二章	實驗系統介紹	7
2.1	 軟硬體介紹	7
2.2	 GPGPU技術介紹	8
第三章	相關研究	17
3.1	線性搜尋法	17
3.2	k-d tree	17
3.3	BBF k-d tree(k-d tree with Best Bin First)	20
3.4	Randomized k-d tree	26
3.5	Multi-resolution search algorithm(MRSA)	27
第四章	多重解析全域搜尋之影像特徵點匹配演算法	30
4.1	特徵描述子、Lp空間與離群點移除演算法	31
4.1.1	特徵描述子	31
4.1.2	Lp空間	32
4.1.3	離群點移除演算法	33
4.2	多重解析全域搜尋之影像特徵點匹配演算法	35
4.2.1	描述子降維	35
4.2.2	決定閥值dmin	37
4.2.3	決定匹配點	38
第五章	實現即時多重解析全域搜尋之影像特徵描述子匹配演算法	39
5.1	以CPU實現所提出的演算法	39
5.1.1	描述子降維	39
5.1.2	決定閥值dmin	40
5.1.3	決定匹配點	41
5.2	以GPU實現所提出的演算法	44
5.2.1	描述子降維	45
5.2.2	決定閥值dmin	45
5.2.3	決定匹配點	47
第六章	 實驗結果與分析	52
6.1	 影像資料庫	52
6.2	 所提出演算法之參數選擇	52
6.2.1	選擇參數β	53
6.2.2	四種演算法之比較	53
6.2.3	所提出方法CPU與GPU版本比較	63
6.3	 實際應用之實驗結果	64
第七章	 結論與未來展望	71
參考文獻	72
附錄A	74
附錄B	75
附錄C	79

圖目錄
圖2.1、CPU與GPU硬體架構比較圖[14]	10
圖2.2、CPU與GPU之浮點數計算能力近年發展比較圖[14]	10
圖2.3、Grid、Block、Thread間的層次關係示意圖[14]	11
圖2.4、以C語言說明異質結合時的運算方式示意圖[14]	13
圖2.5、不同核心數目的GPU由Block指派工作示意圖[14]	14
圖2.6、記憶體的與各運算區塊間的對應關係示意圖[14]	16
圖3.1、建構好的k-d tree與其在二維平面上維度切割示意圖	24
圖3.2、第一次搜尋的k-d tree	25
圖3.3、利用BBF方法第一次回溯	25
圖3.4、利用BBF方法第二次回溯	25
圖4.1、多重解析全域搜尋之影像特徵描述子匹配演算法流程圖	31
圖4.2、SURF演算法流程圖	32
圖4.3、SURF描述子示意圖	33
圖4.4、特徵點匹配與離群點移除結果圖	35
圖4.5、特徵點描述子降維示意圖	36
圖5.1、特徵點描述子降維流程圖	40
圖5.2、決定閥值dmin流程圖	41
圖5.3、決定閥值dmin步驟程式虛擬碼	42
圖5.4、找出候選點並判斷是否為匹配點之虛擬程式碼	42
圖5.5、決定候選點流程圖	44
圖5.6、以GPU平行化程式實現描述子降維表示圖	46
圖5.7、以GPU平行化程式實現決定閥值dmin表示圖	46
圖5.8、每個Thread所執行的動作流程圖	49
圖5.9、以Thread Block提取兩個最小值演示圖(a)表示有Nq個Block進行資料排序分工(b)Block(0)要選出兩個最小值示意(c)第一輪Thread從八個值中選出兩個最小值示意(d)第二輪Thread從八個值中選出兩個最小值示意及最終匹配結果	51
圖6.1、線性搜尋法、Randomized k-d tree、所提出的演算法(CPU版本，不同參數)之實驗結果。(a)所有比較的演算法執行時間，(b)為5.1(a)放大圖，顯示所提出方法的執行時間，(c)所有演算法之群內點比率，(d)所有演算法之匹配點數量，(e)所有演算法內群點數量。	58
圖6.2、線性搜尋法、Randomized k-d tree、所提出的演算法(GPU版本，不同參數)之實驗結果。(a)所有比較的演算法執行時間，(b)為5.2(a)放大圖，顯示所提出方法的執行時間，(c)所有演算法之群內點比率，(d)所有演算法之匹配點數量，(e)所有演算法內群點數量。	60

表目錄
表2.1、電腦規格表	7
表2.2、攝影機規格表	8
表2.3、使用軟體版本	8
表6.1、參數β在不同設置下之實驗結果表(286組影像平均數據)	54
表6.2、四種演算法參數設置表	54
表6.3、四種演算法數據比較表(286組影像平均數據)	61
表6.4、四種演算法數據比較表(1)	61
表6.5、四種演算法數據比較表(2)	62
表6.6、四種演算法數據比較表(3)	62
表6.7、所提出的方法CPU與GPU版本數據比較表(輸入影像特徵點數510點與參考影像特徵點數509點)	63
表6.8、所提出的方法CPU與GPU版本數據比較表(輸入影像特徵點數794點與參考影像特徵點數764點)	63
表6.9、實驗用之參考影像表	65
表6.10、物體距離攝影機20公分下之準確度	67
表6.11、物體距離攝影機40公分下之準確度	67
表6.12、物體距離攝影機60公分下之準確度	67
表6.13、不同距離下攝影機影像與參考影像辨識結果表(1)	68
表6.14、不同距離下攝影機影像與參考影像辨識結果表(2)	69
表6.15、不同距離下攝影機影像與參考影像辨識結果表(3)	70

[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 , Issue 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, Issue 6, pp. 891-923, 1998.
[5]	J. S. Beis and D. G. Lowe, "Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces," IEEE International Conference on Computer Vision and Pattern Recognition, pp.1000, 1997.
[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 Issue 1, pp.117-122, 2008.
[7]	C. S. Anan, 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]	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.
[9]	D. Nister and H. Stewenius, "Scalable recognition with a vocabulary tree," IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 2, pp. 2161-2168, 2006.
[10]	M. A. Fischler and R. C. Bolles, "Random sample consensus : a paradigm for  model fitting with applications to image analysis and automated cartography," Communications of the ACM , Vol. 24, Issue 6, pp.381-395, 1981.
[11]	P. Torr and A. Zisserman, "Robust computation and parameterization of multiple view relations," IEEE International Conference on Computer Vision, pp.727 – 732, 1998.
[12]	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,  Issue 5, pp.673-678, 2001.
[13]	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, Issue 4, 2005.
[14]	NVIDIA CUDA C Programming Guide available at: http://docs.nvidia.com/cuda/cuda-c-programming-guide/#axzz37LFV6WUl
[15]	P. Indyk, R. Motwani, "Approximate Nearest Neighbors Towards Removing the Curse of Dimensionality," Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604-613, 1998
[16]	OpenSURF Computer Vision Library available at:  http://www.chrisevansdev.com/computer-vision-opensurf.html
[17]	FLANN(Fast Library for Approximate Nearest Neighbors)  available at: http://www.cs.ubc.ca/research/flann/