derivadas.dev

Pablo Díaz Viñambres

MSc Informatics @ TUM

Efficient Neighbourhood Search in 3D Point Clouds Through Space-Filling Curves and Linear Octrees

C++ OpenMP LiDAR Investigación


Este es mi primer artículo de investigación, escrito en colaboración con Miguel Yermo, Ph.D., Silvia R. Alcaráz, Ph.D., Óscar G. Lorenzo, Ph.D., Francisco F. Rivera, Prof. y José C. Cabaleiro, Prof., y disponible como preprint en arXiv. Se desarrolló como una continuación y ampliación de mi TFG en Ingeniería Informática. La librería desarrollada en C++ también está disponible como código abierto en GitHub.

Octree construido sobre una nueva ordenada mediante la SFC de Hilbert.

Abstract (traducido del original)

Este trabajo presenta un enfoque eficiente para la búsqueda de vecindades en nubes de puntos 3D, combinando una reordenación espacial basada en Space-Filling Curves (SFC), concretamente en las curvas de Morton y Hilbert, con una implementación de octree lineal. También proponemos algoritmos de búsqueda especializados para consultas de radio fijo y kNN, basados en octrees lineales. Además, introducimos el concepto de histograma de localidad kNN, que puede emplearse para caracterizar la localidad en los accesos a datos, y que observamos que está directamente relacionado con los fallos caché y el rendimiento de las búsquedas. Nuestros experimentos revelan que la reordenación mediante SFC mejora significativamente el acceso a datos espaciales, reduciendo el número de fallos caché entre un 25% y un 75% y el tiempo de ejecución hasta en un 50%. Asimismo, comparamos nuestra propuesta con varias implementaciones de octree y KDTree ampliamente utilizadas. Nuestro método logra una reducción significativa del tiempo de búsqueda, siendo hasta 10 veces más rápido que las soluciones existentes. Además, analizamos el rendimiento de nuestras búsquedas de vecindad (paralelizadas con OpenMP), demostrando alta escalabilidad con el número de núcleos y el tamaño del problema. En particular, observamos un speedup de hasta 36x al ejecutar búsquedas de radio fijo en un sistema con 40 núcleos. Los resultados obtenidos indican que nuestros métodos proporcionan una solución robusta y eficiente para aplicaciones que requieren acceso rápido a conjuntos de vecinos 3D a gran escala.

Histograma de localidad kNN en la nube 5080_54400.Gráfica log-log mostrando la eficiencia de los algoritmos desarrollados.