教師資料查詢 | 類別: 期刊論文 | 教師: 顏淑惠YEN SHWU-HUEY (瀏覽個人網頁)

標題: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.
語言英文
ISSN1998-4464
期刊性質國外
收錄於
產學合作
通訊作者
審稿制度
國別保加利亞
公開徵稿
出版型式紙本
相關連結
SDGs
Google+ 推薦功能,讓全世界都能看到您的推薦!