The following information was submitted:
Transactions: INTERNATIONAL JOURNAL of CIRCUITS, SYSTEMS and SIGNAL PROCESSING
Transactions ID Number: 19-435
Full Name: Hsiao-Wei Chang
Position: Lecturer
Age: ON
Sex: Male
Address: 245, Sec. 3, Academia Road, Taipei City 11581
Country: TAIWAN
Tel:
Tel prefix:
Fax:
E-mail address: changhw@cc.cust.edu.tw
Other E-mails:
Title of the Paper: applying multiple kd-trees in high dimensional nearest neighbor searching
Authors as they appear in the Paper: Shwu-Huey Yen, Chao-Yu Shih, Tai-Kuang Li, Hsiao-Wei Chang
Email addresses of all the authors: shyen@cs.tku.edu.tw,josh_shih@asus.com,695410141@s95.tku.edu.tw,changhw@cc.cust.edu.tw
Number of paper pages: 8
Abstract: Abstract¡XFeature 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 im!
proves 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.
Keywords: feature matching, nearest neighbor searching (NNS), kd-tree, backtracking, best-bin-first, projection
EXTENSION of the file: .doc
Special (Invited) Session: Nearest Neighbor Searching in High Dimensions Using Multiple KD-Trees
Organizer of the Session: 647-169
How Did you learn about congress:
IP ADDRESS: 211.72.236.67
