Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration

Keywords

Computer science, Nearest neighbor search, k-nearest neighbors algorithm, Implementation, Iterative closest point

References

• MD-tree: a balanced hierarchical data structure for multidimensional data with highly efficient dynamic characteristicsYuichi Nakamura, Shigeo Abe, Yutaka Ohsawa — 1988
• ANN: library for approximate nearest neighbor searchingSunil Arya, DM Mount — 1998
• Simple and Efficient Traversal Methods for Quadtrees and OctreesSarah Frisken, Ronald N. Perry — 2002
• An empirical performance comparison of some variations of thek-d Tree andBD treeSivarama P. Dandamudi, Paul Sorenson — 1985
• A Method for Registration of 3-D ShapesPaul J. Besl, Neil David McKay — 1992
• Efficient processing of large 3D point cloudsJan Elseberg, Dorit Borrmann, Andreas Nüchter — 2011
• Approximate nearest neighbor queries in fixed dimensionsSunil Arya, David M. Mount — 1993
• Geometric modeling using octree encodingDonald J. Meagher — 1982
• Data structures and algorithms for nearest neighbor search in general metric spacesP.N. Yianilos — 1993
• Towards identification of best practice algorithms in 3D perception and modelingSebastian Blumenthal, Erwin Prassler, Jan Fischer — 2011
• R-trees: a dynamic index structure for spatial searchingA. Guttman — 1984
• Tracking a depth camera: Parameter exploration for fast ICPFrançois Pomerleau, Stéphane Magnenat, Francis Colas — 2011
• A data structure for orthogonal range queriesGeorge S. Lueker — 1978
• Memory Performance and Cache Coherency Effects on an Intel Nehalem Multiprocessor SystemDaniel Molka, Daniel Hackenberg, Robert Schöne — 2009
• The R*-tree: an efficient and robust access method for points and rectanglesNorbert Beckmann, Hans‐Peter Kriegel, Ralf Schneider — 1990
• Fast construction of k-nearest neighbor graphs for point cloudsMichael Connor, Piyush Kumar — 2010
• Multidimensional binary search trees used for associative searchingJon Bentley — 1975
• A nearest neighbor method for efficient ICPMichael Greenspan, Guy Godin — 2001
• An optimal algorithm for approximate nearest neighbor searching fixed dimensionsSunil Arya, David M. Mount, Nathan S. Netanyahu — 1998
• CGAL - The Computational Geometry Algorithms LibraryAndreas Fabri, Monique Teillaud — 2011

Cited by

• General Purpose Computing on Graphics Processing Units for Robotic ApplicationsB?Dkowski, Janusz, Karol Majek, Andreas Nüchter — 2013
• Advantages of exploiting projection structure for segmenting dense 3D point cloudsAlex Bewley, Ben Upcroft — 2013
• Three Dimensional Nonlinear Statistical Modeling Framework for Morphological AnalysisAbdel Fatah, Emam ElHak — 2012
• Continuous‐Time Three‐Dimensional Mapping for Micro Aerial Vehicles with a Passively Actuated Rotating Laser ScannerLukas Kaul, Robert Zlot, Michael Bosse — 2016
• Efficient radius neighbor search in three-dimensional point cloudsJens Behley, Volker Steinhage, Armin B. Cremers — 2015
• Representing 3D shape in sparse range images for urban object classificationA. Quadros — 2013
• Live Texturing of Augmented Reality Characters from Colored DrawingsStéphane Magnenat, Markus Groß, Robert W. Sumner — 2015
• Conservative decision-making and interference in uncertain dynamical systemsJan-Peter Calliess — 2014
• Simulating Lithic Raw Material Variability in Archaeological Contexts: A Re-evaluation and Revision of Brantingham’s Neutral ModelCornel Pop — 2016
• Efficient Large‐scale Three‐dimensional Mobile Mapping for Underground MinesRobert Zlot, Michael Bosse — 2014
• Toward a new approach for massive LiDAR data processingHung Cao, K-X. Chu, Nhien‐An Le‐Khac — 2015
• Comparing ICP variants on real-world data setsFrançois Pomerleau, Francis Colas, Roland Siegwart — 2013
• On real-time obstacle avoidance using 3-D point cloudsYiqun Fu, Guolai Jiang, Wei Feng — 2014
• Long-term 3D map maintenance in dynamic environmentsFrançois Pomerleau, Philipp Krüsi, Francis Colas — 2014
• Place recognition using keypoint voting in large 3D lidar datasetsMichael Bosse, Robert Zlot — 2013
• Fast in-place binning of laser range-scanned point setsBruce Merry, James Gain, Patrick Marais — 2013
• Collision detection between point clouds using an efficient k-d tree implementationJohannes Schauer, Andreas Nüchter — 2015
• Placeless Place-RecognitionSimon Lynen, Michael Bosse, Paul Furgale — 2014
• Calibration of an Outdoor Distributed Camera Network with a 3D Point CloudAgustín Ortega, Manuel F. Silva, Ernesto H. Teniente — 2014
• Efficient registration of 2D points to CAD models for real-time applicationsRubén Usamentiaga, Daniel F. García, Julio Molleda — 2018

Related papers

• A Method for Registration of 3-D ShapesPaul J. Besl, Neil David McKay — 1992
• Fast Approximate Nearest Neighbors with Automatic Algorithm ConfigurationMarius Muja, David Lowe — 2009
• 3D is here: Point Cloud Library (PCL)Radu Bogdan Rusu, Steve Cousins — 2011
• Multidimensional binary search trees used for associative searchingJon Bentley — 1975
• Efficient variants of the ICP algorithmSzymon Rusinkiewicz, Marc Levoy — 2001
• Comparing ICP variants on real-world data setsFrançois Pomerleau, Francis Colas, Roland Siegwart — 2013
• An optimal algorithm for approximate nearest neighbor searching fixed dimensionsSunil Arya, David M. Mount, Nathan S. Netanyahu — 1998
• Fast Point Feature Histograms (FPFH) for 3D registrationRadu Bogdan Rusu, Nico Blodow, Michael Beetz — 2009
• Closed-form solution of absolute orientation using unit quaternionsBerthold K. P. Horn — 1987
• LOAM: Lidar Odometry and Mapping in Real-timeJi Zhang, Sanjiv Singh — 2014