Applying Multiple KD-Trees in High Dimensional Nearest Neighbor Searching

淡江大學機構典藏 > 工學院 > 資訊工程學系暨研究所 > 期刊論文 > Item 987654321/59873

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: 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
显示于类别:	[資訊工程學系暨研究所] 期刊論文

文件中的档案:

档案	大小	格式	浏览次数
1998-4464_4(4)p153-160.pdf	1854Kb	Adobe PDF	181	检视/开启

在機構典藏中所有的数据项都受到原著作权保护.

TAIR相关文章

数据加载中.....