期刊論文
| 學年 | 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. |
| 語言 | en |
| ISSN | 1998-4464 |
| 期刊性質 | 國外 |
| 收錄於 | |
| 產學合作 | |
| 通訊作者 | |
| 審稿制度 | |
| 國別 | BGR |
| 公開徵稿 | |
| 出版型式 | 紙本 |
| 相關連結 |
機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/59873 ) |