特徵比對在許多影像處理的應用中扮演著一個重要的角色，例如全景影像的產生、影像縫合、物件追蹤…等等。所謂的特徵比對即是在兩張不同的影像中找出最相似的特徵點組合，也就相當於找特徵點的最近鄰居。

在本篇論文提出了一個尋找最近鄰居的方法，利用將資料投射到不同的平面進行粗分類，同時建構數棵互補的K-D Tree進行最近鄰居的搜尋，且使用Best Bin First(BBF)的回溯機制平均的在各棵K-D Tree上搜尋以降低搜尋時間並提升正確率。文中以演算法分析時間複雜度，最後再以實驗證明我們的分析和執行的效能。

Feature matching plays an important role in many image processing applications. To match a feature point in the query image is to find a correspondent feature point (i.e., the nearest neighbor) extracted from the target image. Edges, corners and DoG (difference of Gaussian) are most common adopted features in recent year. How to represent features is also very important in which SIFT (Scale Invariant Feature Transform) is one of the state-of-art. SIFT, proposed by Lowe [1], usually results feature vectors with high dimension such as 128. Thus how to efficiently find the nearest neighbor of a query feature point in the target image becomes essential. Kd- tree is often used to find the nearest neighbor in dimension higher than two. However, kd- tree needs many backtrackings to find the nearest neighbor when dimension gets higher. In this paper, we propose a multiple kd-trees method to efficiently search the nearest neighbor for high dimension feature points. First, we project feature points to three hyper-planes which have greatest variances. Second, for points projected on each splitting hyper-plane, two kd-trees are built that one is the conventional kd-tree and the other has first split on the hyper-plane with second largest variance. So total of six kd-trees are built. By this way, these kd-trees are searched for the nearest neighbor through different hyper-planes to compensate the deficiency of projection. The experiment showed that our method, under the same number of backtracks, indeed improves the accuracy rate of searching the nearest neighbor.

目錄
目錄	IV
圖目錄	VI
表目錄	VIII
第一章 緒論	1
1.1 研究動機與目的	1
1.2 研究內容	4
1.3 論文架構	6
第二章 相關研究與理論基礎	7
2.1最近鄰居搜尋法相關研究	8
2.2理論基礎	10
2.2.1 K-D Tree	10
2.2.2 Adaptive K-D Tree	12
2.2.3 KD-BBF Tree (K-D tree with Best Bin First)	14
第三章 研究方法	16
3.1提出的方法	17
3.2演算法	24
第四章 實驗結果與探討	34
4.1效能比較	35
4.2回溯次數分析	39
4.3執行時間	41
第五章 結論與未來研究方向	43
參考文獻	44
附錄－英文論文	46
 
圖目錄
圖1. (a)原始k-d tree的分割情形。(b)為所建構的對應二元樹。	11
圖2. (a)使用可調整k-d tree分割後的結果(b)對應的二元樹。	13
圖3. 使用最大變異數選擇切割維度	15
圖4. 粗線代表詢問點走到葉子的路徑。	15
圖5. 資料點投射到x-y平面時的分割情形。	18
圖6. x-y平面經過粗分類後得到的相對應的樹結構。	19
圖7. (a)為資料經過分割後的情形。(b)為對應的樹狀結構。	21
圖8. (a)為以變異數第二大的維度作第一次分割產生的結果。(b)為對應的樹狀結構。	22
圖9. 本文章提出之演算法。	26
圖10. 變異數計算。	27
圖11. 計算中心點。	27
圖12. 建構初始樹。	28
圖13. 建構完整的k-d tree。	30
圖14. 時間複雜度。	32
圖15. 本篇提出的方法在不同維度下的正確率。	36
圖16. kd-BBF tree在不同維度下的正確率。	37
圖17. 維度40時本篇方法與kd-BBF tree正確率。	37
圖18. 維度50時本篇方法與kd-BBF tree正確率。	38
圖19. 不同權重值下正確率的變化。	40
 
表目錄
表1. 使用kd-BBF tree在不同維度下的正確率。	5
表2. 兩棵不同切割的樹之正確率與重複率(資料維度=50)。	35
表3. 不同權重值下實際回溯的平均次數。	40
表4. 資料點維度50且資料點個數500	42
表5. 資料點維度50且資料點個數1000	42

1.	M. Brown and D. G. Lowe, “Recognising Panoramas”, Proc. Ninth Int’l Conf. Computer Vision, pp. 1218-1227, 2003.
2.	F. Isgrό and M. Pilu, “A Fast and Robust Image Registration Method Based on An Early Consensus Paradigm”, Pattern Recognition Letters vol. 25, pp. 943–954, 2004.
3.	D. Comaniciu, V. Ramesh, and P. Meer, “Kernel-Based Object Tracking”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25 , pp. 567-577, 2003.
4.	D. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints”, Int’l J. Computer Vision, vol. 2, pp. 91-110, 2004.
5.	H. J. Wolfson and I. Rigoutsos, “Geometric Hashing: An Overview”, IEEE Computational Science and Engineering, vol. 4, pp. 10–21, 1997.
6.	A. Califano and R. Mohan, “Multidimensional Index for Recognizing Visual Shapes”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, pp. 373–392, 1994.
7.	J. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching”, Communications of the ACM, vol. 18, pp. 509–517, 1975.
8.	J. H. Friedman, J. Bentley, and R. Finkel, “An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software, vol. 3, pp. 209–226, 1977.
9.	K. Mikolajczyk, and C Schmid, “A Performance Evaluation of Local Descriptors”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, pp.1615-1630, 2005.
10.	C. Chen, S. Pramanik, Q. Zhu, and Gang Qian, “A Study of Indexing Strategies for Hybrid Data Spaces”, ICEIS 2009 LNBIP vol. 24, pp. 149–159, 2009.
11.	S. A. Nene and S. K. Nayar, “A Simple Algorithm for Nearest Neighbor Search in High Dimensions”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, pp. 989-1003, 1997.
12.	C. S. Anan and R. Hartley, "Optimised K-D-trees for Fast Image Descriptor Matching", 2008 IEEE Conference on Computer Vision and Pattern Recognition, cvpr, pp.1-8, 2008.
13.	J. B. and D. Lowe, “Shape Indexing Using Approximate Nearest-Neighbor Search in High-Dimensional Spaces”, In Proceedings of the Interational Conference on Computer Vision and Pattern Recognition, pp. 1000–1006, 1997.
14.	J. L. Bentley, “Multidimensional Binary Search Tree Used in Database Application”, IEEE Transactions on Software Engineering, vol. 4, pp. 333-340, 1979.