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

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/59873

Title:	Applying Multiple KD-Trees in High Dimensional Nearest Neighbor Searching
Authors:	Yen, Shwu Huey;Shih, Chao Yu;Li, Tai Kuang;Chang, Hsiao Wei
Contributors:	淡江大學資訊工程學系
Keywords:	feature matching;nearest neighbor searching (NNS);kd-tree;backtracking;best-bin-first;projection.
Date:	2010-09
Issue Date:	2013-06-07 10:47:39 (UTC+8)
Publisher:	Sofia: North Atlantic University Union
Abstract:	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
Relation:	International Journal of Circuits, Systems and Single Processing 4(4), pp.153-160
Appears in Collections:	[Graduate Institute & Department of Computer Science and Information Engineering] Journal Article

Files in This Item:

File	Size	Format
1998-4464_4(4)p153-160.pdf	1854Kb	Adobe PDF	181	View/Open

Loading...