以GPU運算技術實現即時多重解析全域搜尋之影像特徵描述子匹配演算法

Implementation of a Real-Time Multi-Resolution Exhaustive Search Algorithm for Image Feature Descriptor Matching by Using GPU Computing

曹安宏(An-Hung Tsao)

指導教授 ： 蔡奇謚

淡江大學/工學院/電機工程學系碩士班/碩士(2014年)

https://doi.org/10.6846/TKU.2014.00125

摘要

影像特徵描述子匹配是許多電腦視覺應用中重要的前處理工作，本文提出一種多重解析全域搜尋演算法與多重解析候選點移除方法，有效地解決這個議題。所提出的演算法首先會由一張輸入影像與一張參考影像，透過特徵點描述子演算法求得特徵點及特徵點描述子。接著，使用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.

並列關鍵字

Feature descriptor matching ； dimensionality reduction ； exhaustive search ； GPU

參考文獻

[1] D. G. Lowe, "Distinctive image features from scale-invariant keypoints," International Journal of Computer Vision, Vol. 60, No. 2, pp. 91-110, 2004.

[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.