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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1103201218381900
中文論文名稱 基於KD-TREE的高資料量最近鄰居搜尋法
英文論文名稱 KD-Tree Based Nearest Neighbor Search for Large Quantity Data
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 100
學期 1
出版年 101
研究生中文姓名 謝雅如
研究生英文姓名 Ya-Ju Hsieh
電子信箱 rong5433@gmail.com
學號 698410122
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2012-01-11
論文頁數 62頁
口試委員 指導教授-顏淑惠
委員-顏淑惠
委員-林慧珍
委員-施國琛
委員-許秋婷
中文關鍵字 特徵點  KD-樹  KDA  最近鄰居搜尋  影像拼接 
英文關鍵字 Feature Point  KD-Tree  Arbitrary KD-tree (KDA)  Nearest Neighbor (NN)  Image Stitching 
學科別分類 學科別應用科學資訊工程
中文摘要 尋找事先未經訓練的最近鄰居,有許多的應用,例如: 馬賽克圖片,影像匹配,影像檢索,影像縫合。當資料量是大量的而且資料的維度高,如何有效地找到最近的鄰居就顯得非常重要。在這篇文章中,我們比較若干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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-03-13公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-03-13起公開。


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