Applying Multiple KD-Trees in High Dimensional Nearest Neighbor Searching

機構典藏 > College of Engineering > Graduate Institute & Department of Computer Science and Information Engineering > Journal Article > Item 987654321/59873

請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/59873

題名:	Applying Multiple KD-Trees in High Dimensional Nearest Neighbor Searching
作者:	Yen, Shwu Huey;Shih, Chao Yu;Li, Tai Kuang;Chang, Hsiao Wei
貢獻者:	淡江大學資訊工程學系
關鍵詞:	feature matching;nearest neighbor searching (NNS);kd-tree;backtracking;best-bin-first;projection.
日期:	2010-09
上傳時間:	2013-06-07 10:47:39 (UTC+8)
出版者:	Sofia: North Atlantic University Union
摘要:	Feature matching plays a key role in many image processing applications. To be robust and distinctive, feature vectors usually have high dimensions such as in SIFT (Scale Invariant Feature Transform) with dimension 64 or 128. Thus, accurately finding the nearest neighbor of a high-dimension query feature point in the target image becomes essential. The kd- tree is commonly adopted in organizing and indexing high dimensional data. However, in searching nearest neighbor, it needs many backtrackings and tends to make errors when dimension gets higher. In this paper, we propose a multiple kd-trees method to efficiently locate the nearest neighbor for high dimensional feature points. By constructing multiple kd-trees, the nearest neighbor is searched through different hyper-planes and this effectively compensates the deficiency of conventional kd-tree. Comparing to the well known algorithm of best bin first on kd-tree, the experiments showed that our method improves the precision of the nearest neighbor searching problem. When the dimension of data is 64 or 128 (on 2000 simulated data), the average improvement on precision can reach 28% (compared under the same dimension) and 53% (compared under the same number of backtrackings). Finally, we revise the stop criterion in backtracking. According to the preliminary experiments, this revision improves the precision of the proposed method in the searching result
關聯:	International Journal of Circuits, Systems and Single Processing 4(4), pp.153-160
顯示於類別:	[Graduate Institute & Department of Computer Science and Information Engineering] Journal Article

文件中的檔案:

檔案	大小	格式	瀏覽次數
1998-4464_4(4)p153-160.pdf	1854Kb	Adobe PDF	245	檢視/開啟

在機構典藏中所有的資料項目都受到原著作權保護.

TAIR相關文章

資料載入中.....