尋找事先未經訓練的最近鄰居，有許多的應用，例如: 馬賽克圖片，影像匹配，影像檢索，影像縫合。當資料量是大量的而且資料的維度高，如何有效地找到最近的鄰居就顯得非常重要。在這篇文章中，我們比較若干KD-樹的變化型以搜索最近鄰居。基於合成資料的測試，我們得出的結論是 KD樹的方法運作在有相關性資料比運作在不相連性的隨機資料好。還有，利用影像產生SIFT特徵點的測試，我們得出本文所提出的方法KDA以演算法分析其計算複雜度，比傳統的KD-Tree省下不少執行效能。最後，我們結合本文所提出的方法加以應用到影像拼接上。

Finding nearest neighbors without training in advance has many applications, such as image mosaic, image matching, image retrieval, and image stitching. When the quantity of data is huge and dimension is high, how to efficiently find the nearest neighbor (NN) becomes very important. In this article, we propose a variation of the KD-tree, Arbitrary KD-tree (KDA) which build tree without evaluate variances. Multiple KDA not only can be built efficiently it also processes an independent tree structures when data is large. Tested by extended synthetic databases and real-world SIFT data, we concluded that KDA method has advantages of satisfying accuracy performance in NN problem as well as computation efficiency.

目錄
第一章 緒論 1 
1.1 研究動機與目的  1 
1.2 論文架構 6 
第二章 相關研究與理論基礎 7 
2.1 最近鄰居搜尋法相關研究 7 
2.2 理論基礎 12 
2.3 介紹Homography 與 RANSAC 14 
第三章 研究方法 17 
3.1.1 Randomized KD-Trees (KDR) 17 
3.1.2 Arbitrary KD-Tree (KDA) 18 
3.2 利用BBF搜尋最近鄰居 20 
3.3 計算量分析 21 
第四章 實驗結果與探討 26 
4.1 KDA & KDR在合成資料情況下，隨機產生資料來做效能分析 27 
4.2 KDA & KDR，利用實際影像的SIFT特徵點來做效能分析 36 
4.3 KDA & KDR分析其回溯次數與正確率之間的關係 40 
4.4 應用KDA實作影像拼接 43 
第五章 結論與探討未來的繼續方向 47 
參考文獻 48 
附錄：英文論文 50

圖目錄 
圖1 間隔取樣法的示意圖[5] 5 
圖2 利用LSH找出Approximate Nearest Neighbor[14] 9 
圖3 Random Fern分類器的例子[6] 10 
圖4 整個independent-feature Ferns classifier的過程圖[6] 10 
圖5 KD (traditional) 建構過程圖 14 
圖6 KDA建構過程圖 19 
圖7 二元樹的構造圖 22 
圖8 KDA & KDR，在合成資料的實驗結果 36 
圖9 KDA & KDR，利用實際影像的SIFT特徵點實驗結果 38 
圖10 KDA & KDR 分析其回溯次數與正確率之間的實驗(1) 41 
圖11 KDA & KDR 分析其回溯次數與正確率之間的實驗(2) 42 
圖12 如何從query_image選取出特徵點作為詢問點 44 
圖13-1 皇澤寺大佛窟裡的佛像其中2張，影像拼接 45 
圖13-2 皇澤寺大佛窟裡的佛像其中2張，影像拼接 45 
圖13-3 皇澤寺大佛窟裡的佛像其中2張，影像拼接 46 
圖13-4 皇澤寺大佛窟裡的佛像其中2張，影像拼接 46

表目錄 
表1 計算變異數的乘法與加法個數 21 
表2 計算KD-Tree在不同層的計算量，乘法與加法個數 23

[1] P. Jain, B. Kulis, and K. Grauman, “Fast Similarity Search for Learned Metrics,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 31, no. 12, pp. 2143-2157, 2009.
[2] D. Lowe, “Distinctive Image Features from Scale Invariant Keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91-110, 2004.
[3] M. Ozuysal, M. Calonder, V. Lepetit, and P. Fua, “Fast Keypoint Recognition using Random Ferns,” IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 99, no. 1 , pp. 448 - 461, 2009.
[4] M. Slaney and M. Casey, “Locality-Sensitive Hashing for Finding Nearest Neighbors,” IEEE Signal Processing Magazine, vol. 25, no. 2, pp. 128-131, 2008.
[5] H. - C. Hwang, SIFT演算法應用於航測影像拼接之研究 (The Study of Aerial Imageries Stitching Based on SIFT Algorithm )，黃漢哲，98年7月國立中山大學海洋環境及工程學系研究所碩士論文.
[6] C.- S. Fan, 快速特徵點比對運用於物體追蹤 (Fast Keypoint Matching for Visual Tracking )，范智勝，97年國立清華大學資訊系統與應用研究所碩士論文.
[7] A. Bosch, A. Zisserman, and X. Munoz, “Image Classification using Random Forests and Ferns,” IEEE International Conference on Computer Vision, pp. 1-8, 2007.
[8] S. Lazebnik, C. Schmid, and J. Ponce, “Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories,” IEEE Conference on Computer Vision and Pattern Recognition, 2006.
[9] http://cybertron.cg.tu-berlin.de/pdci08/imageflight/nn_search.html
[10] C. Silpa.- Anan and R. Hartley, “Optimised KD-trees for Fast Image Descriptor Matching,” IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8, 2008.
[11] V. Lepetit and P. Fua, “Keypoint Recognition using Randomized Trees,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 9, pp.1465-1479, 2006.
49
[12] A. Torralba, R. Fergus, and Y. Weiss, “Small Codes and Large Image Databases for Recognition,” IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8, 2008.
[13] M. Raginsky and S. Lazebnik, “Locality-Sensitive Binary Codes from Shift-Invariant Kernels,” Neural Information Processing Systems , pp. 1-9, 2009.
[14] http://cybertron.cg.tu-berlin.de/pdci08/imageflight/nn_search.html
[15] http://graphics.stanford.edu/courses/cs368-00-spring/TA/manuals/CGAL/ refmanual2/SearchStructures/Chapter_main.html
[16] http://www.vlfeat.org/index.html
[17] M. Muja and D. Lowe, “Fast approximate nearest neighbors with automatic algorithm configuration,” International Conference on Computer Vision Theory and Applications (VISAPP), Lisbon, Portugal, Feb. 2009.
[18] P. Wu, S. C.H. Hoi, N. D. Dung, and H. Ying, “Randomly Projected KD-Trees with Distance Metric Learning for Image Retrieval,” International Conference on MultiMedia Modeling , Taipei, Taiwan, pp. 371-382, 2011.
[19] J. S. Beis and D. Lowe, “Shape indexing using approximate nearest-neighbour search in high-dimensional spaces,” Conference on Computer Vision and Pattern Recognition, Puerto Rico, pp. 1000-1006, June 1997.
[20] S. H. Yen, C. Y. Shih, T.K. Li, and H. W. Chang, “Applying Multiple KD-Trees in High Dimensional Nearest Neighbor Searching,” International Journal of Circuits, Systems and Signal Processing, issue 4, vol. 4, pp. 153-160, 2010.
[21] M. A. Fischler and R. C. Bolles, “Random sample consensus: A paradigm for model fitting with application to image analysis and automated cartography,” Communications of the Association for Computing Machinery, vol. 24, pp. 381-395, 1981.