A Radial Search Method for Fast Nearest Neighbor Search on Range Images
In this paper, we propose an efficient method for the problem of Nearest Neighbor Search (NNS) on 3D data provided in the form of range images. The proposed method exploits the organized structure of range images to speed up the neighborhood exploration b
- PDF / 1,052,315 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 18 Downloads / 182 Views
Dipartimento di Informatica - Scienza e Ingegneria, University of Bologna, Bologna, Italy {federico.tombari,samuele.salti,luigi.distefano}@unibo.it 2 Dipartimento di Informatica, University of Salerno, Salerno, Italy [email protected] 3 D.I.E.M., University of Salerno, Salerno, Italy [email protected]
Abstract. In this paper, we propose an efficient method for the problem of Nearest Neighbor Search (NNS) on 3D data provided in the form of range images. The proposed method exploits the organized structure of range images to speed up the neighborhood exploration by operating radially from the query point and terminating the search by evaluating adaptive stop conditions. Despite performing an approximate search, our method is able to yield results comparable to the exhaustive search in terms of accuracy of the retrieved neighbors. When tested against open source implementations of state-of-the-art NNS algorithms, radial search obtains better performance than the other algorithms in terms of speedup, while yielding the same level of accuracy. Additional experiments show how our algorithm improves the overall efficiency of a highly computational demanding application such as 3D keypoint detection and description.
1
Introduction and Related Work
In the past few years there has been a growing interest in processing 3D data for computer vision tasks such as 3D keypoint detection and description, surface matching and segmentation, 3D object recognition and categorization. The relevance of such applications has been fostered by the availability, in the consumer market, of new low-cost RGB-D cameras, which can simultaneously capture RGB and range images at a high frame rate. Such devices are either based on structured light (e.g. Microsoft Kinect, Asus Xtion) or Time-of-Flight (TOF) technology (e.g., Kinect II), and belong to the class of active acquisition methods. On the other hand, low-cost RGB-D sensors belonging to the class of passive acquisition technologies are mostly based on stereo cameras [13] or Structurefrom-Motion. Independently from the specific technology being used, each sensor acquires 3D data in the form of range images, a type of 3D representation that stores c Springer International Publishing Switzerland 2016 G. Hua and H. J´ egou (Eds.): ECCV 2016 Workshops, Part III, LNCS 9915, pp. 563–577, 2016. DOI: 10.1007/978-3-319-49409-8 49
564
F. Tombari et al.
depth measurements obtained from a specific point in 3D space (i.e., sensor viewpoint) — for this reason, it is sometimes referred to as 2.5D data. Such representation is organized, in the sense that each depth value is logically stored in a 2D array, so that spatially correlated points can be accessed by looking at nearby positions on such grid. By estimating the intrinsic parameters of the sensors, usually available via calibration, the (x, y, z) coordinates associated to each depth value can be directly obtained. Conversely, point clouds are unorganized 3D representation that simply stores 3D coordinates in an unordered list. Arguably the most ubiquit
Data Loading...
