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.

A radial search method for fast nearest neighbor search on range images / Tombari, Federico; Salti, Samuele; Puglia, Luca; Raiconi, Giancarlo; Di Stefano, Luigi. - ELETTRONICO. - 9915:(2016), pp. 563-577. (Intervento presentato al convegno 14th European Conference on Computer Vision, ECCV 2016 tenutosi a nld nel 2016) [10.1007/978-3-319-49409-8_49].

A radial search method for fast nearest neighbor search on range images

TOMBARI, FEDERICO;SALTI, SAMUELE;DI STEFANO, LUIGI
2016

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.
2016
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
563
577
A radial search method for fast nearest neighbor search on range images / Tombari, Federico; Salti, Samuele; Puglia, Luca; Raiconi, Giancarlo; Di Stefano, Luigi. - ELETTRONICO. - 9915:(2016), pp. 563-577. (Intervento presentato al convegno 14th European Conference on Computer Vision, ECCV 2016 tenutosi a nld nel 2016) [10.1007/978-3-319-49409-8_49].
Tombari, Federico; Salti, Samuele; Puglia, Luca; Raiconi, Giancarlo; Di Stefano, Luigi
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/589907
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact