|
Published Articles >> Table of Contents >> Abstract
Fourth International Conference on 3-D Digital Imaging and Modeling (3DIM '03)
p. 79
Effective Nearest Neighbor Search for Aligning and Merging Range Images
Ryusuke Sagawa, Osaka University
Tomohito Masuda, University of Tokyo
Katsushi Ikeuchi, University of Tokyo
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IM.2003.1240235
Send link to a friend
| Abstract |
|
This paper describes a novel method which extends the
search algorithm of a k-d tree for aligning and merging
range images. If the nearest neighbor point is far from a
query, many of the leaf nodes must be examined during the
search, which actually will not finish in logarithmic time.
However, such a distant point is not as important as the
nearest neighbor in many applications, such as aligning
and merging range images; the reason for this is either because
it is not consequently used or because its weight becomes
very small. Thus, in this paper, we propose a new
algorithm that does not search strictly by pruning branches
if the nearest neighbor point lies beyond a certain threshold.
We call the technique the Bounds-Overlap-Threshold (BOT)
test. The BOT test can be applied without recreating the k-d
tree if the threshold value changes. Then, we describe how
we applied our new method to three applications in order to
analyze its performance. Finally, we discuss the method’s
effectiveness.
|
 Additional Information
|
Citation:
Ryusuke Sagawa, Tomohito Masuda, Katsushi Ikeuchi,
"Effective Nearest Neighbor Search for Aligning and Merging Range Images,"
3dim,
p. 79,
Fourth International Conference on 3-D Digital Imaging and Modeling (3DIM '03),
2003
|
|
