淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0508200911093600
中文論文名稱 高維空間中使用多棵K-D Trees搜尋最近鄰居
英文論文名稱 Nearest Neighbor Searching in High Dimensions Using Multiple K-D Trees
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 97
學期 2
出版年 98
研究生中文姓名 石兆宇
研究生英文姓名 Chao-Yu Shih
學號 696410447
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2009-06-23
論文頁數 58頁
口試委員 指導教授-顏淑惠
委員-顏淑惠
委員-林慧珍
委員-徐道義
中文關鍵字 特徵比對  最近鄰居搜尋  K-D樹  回溯 
英文關鍵字 Feature matching  Nearest neighbor search (NNS)  K-D tree  Backtrack 
學科別分類 學科別應用科學資訊工程
中文摘要 特徵比對在許多影像處理的應用中扮演著一個重要的角色,例如全景影像的產生、影像縫合、物件追蹤…等等。所謂的特徵比對即是在兩張不同的影像中找出最相似的特徵點組合,也就相當於找特徵點的最近鄰居。

在本篇論文提出了一個尋找最近鄰居的方法,利用將資料投射到不同的平面進行粗分類,同時建構數棵互補的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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2009-08-11公開。
  • 同意授權瀏覽/列印電子全文服務,於2009-08-11起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信