期刊論文

標題 Applying Multiple KD-Trees in High Dimensional Nearest Neighbor Searching
學年 99
學期 1
出版(發表)日期 2010/09/01
作品名稱 Applying Multiple KD-Trees in High Dimensional Nearest Neighbor Searching
作品名稱(其他語言)
著者 Yen, Shwu Huey; Shih, Chao Yu; Li, Tai Kuang; Chang, Hsiao Wei
單位 淡江大學資訊工程學系
出版者 Sofia: North Atlantic University Union
著錄名稱、卷期、頁數 International Journal of Circuits, Systems and Single Processing 4(4), pp.153-160
摘要 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
關鍵字 feature matching;nearest neighbor searching (NNS);kd-tree;backtracking;best-bin-first;projection.
語言 英文
ISSN 1998-4464
期刊性質 國外
收錄於
產學合作
通訊作者
審稿制度
國別 保加利亞
公開徵稿
出版型式 紙本