Octree
- También llamado: sparse voxel octree
- Categoría: Sensing › 3D maps & reconstruction
- Etiquetas: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds
Una estructura de datos en árbol que divide recursivamente el espacio 3D en ocho cubos y asigna celdas finas solo donde hay datos, para obtener mapas compactos y consultas espaciales rápidas.
Definición
Octree (árbol octal) es un árbol en el que cada nodo representa un cubo de espacio y puede tener hasta ocho hijos, uno por cada octante que se obtiene al dividir el cubo por la mitad a lo largo de los tres ejes. La raíz cubre todo el volumen; cada nivel hacia abajo divide por la mitad el tamaño de celda. Las ramas solo se subdividen donde hay algo de interés, como puntos de superficie medidos, de modo que las grandes regiones vacías o no observadas se quedan como nodos gruesos únicos. Donald Meagher describió los octrees para el modelado de sólidos a principios de la década de 1980, y hoy son estándar en gráficos, procesamiento de nubes de puntos y mapeo robótico.
Su principal atractivo es la memoria. Una rejilla de vóxeles densa a resolución fina sobre un edificio grande necesita almacenamiento para cada celda, mientras que el almacenamiento de un octree crece aproximadamente con el área de superficie observada. También ofrece acceso multirresolución: un planificador puede consultar celdas gruesas para una comprobación rápida y descender para obtener detalle. En OctoMap, una biblioteca muy utilizada de Hornung y sus colegas, cada hoja guarda un valor de ocupación probabilístico en forma de log-odds, actualizado a partir de medidas de distancia, de modo que el mapa distingue el espacio ocupado, libre y desconocido. Los hijos con el mismo estado se podan y se fusionan en su padre para ahorrar memoria.
Los octrees sacrifican algo de velocidad a cambio de esta compacidad: llegar a una hoja implica recorrer el árbol hacia abajo, lo que es más lento que indexar un array plano. Alternativas como el voxel hashing y la estructura VDB ofrecen un acceso más rápido en algunas cargas de trabajo. Los octrees también se usan para acelerar la búsqueda de vecinos más cercanos y la comprobación de colisiones en nubes de puntos, y en sistemas recientes de mapeo neuronal organizan vóxeles dispersos que almacenan características aprendidas, creciendo de forma incremental a medida que llegan nuevos fotogramas de profundidad.
Por qué importa
Los robots necesitan mapas 3D que cubran grandes áreas con una resolución útil sin agotar la memoria. Los octrees lo hacen viable, y son la base de herramientas habituales de mapeo de ocupación y de comprobación de colisiones que se usan en manipulación y en navegación aérea.
Aplicaciones clave
- Mapeo probabilístico de ocupación 3D con OctoMap
- Comprobación de colisiones para brazos robóticos y drones
- Búsqueda de vecinos más cercanos y por radio en nubes de puntos
- Estructuras de vóxeles dispersos para el mapeo implícito neuronal y denso
- Compresión de nubes de puntos y renderizado por niveles de detalle
En la práctica
Un equipo que construye un mapa 3D para un dron que vuela por un almacén introduce en OctoMap nubes de puntos de una cámara de profundidad o de un lidar, con las poses de su odometría, a una resolución de unos pocos centímetros. Cada rayo marca las celdas que atraviesa como más probablemente libres y la celda en la que termina como más probablemente ocupada. El planificador consulta en el octree la ocupación a lo largo de las trayectorias candidatas y trata el espacio desconocido como un obstáculo. En un brazo robótico, MoveIt puede tomar el mismo tipo de octree a partir de un sensor de profundidad para mantener actualizada la escena de planificación del brazo. Los ingenieros ajustan la resolución, el alcance del sensor y las probabilidades de acierto y de fallo para equilibrar el detalle, la memoria y la rapidez con que se borran los objetos en movimiento.
Ideas erróneas comunes
- Un octree es lo mismo que una rejilla de vóxeles — una rejilla de vóxeles almacena cada celda, mientras que un octree solo subdivide donde hace falta y fusiona las regiones uniformes
- Los octrees son siempre más rápidos que las rejillas planas — ahorran memoria, pero cada consulta recorre el árbol, así que las rejillas densas o con hashing pueden ser más rápidas para algunas consultas
- El espacio vacío en un octree significa espacio libre — en los octrees de ocupación, el espacio no observado es desconocido, y los planificadores normalmente deberían tratarlo de forma distinta del espacio libre
Quién debería saberlo
- Ingenieros de mapeo y de SLAM
- Desarrolladores de planificación de movimiento y de comprobación de colisiones
- Ingenieros de autonomía de drones que trabajan en entornos 3D
- Desarrolladores de sistemas de mapeo neuronal y denso
Tecnologías relacionadas
- OctoMap
- Voxel hashing (Voxel Hashing)
- OpenVDB
- Point Cloud Library (PCL)
- MoveIt
Términos relacionados
Proyectos relacionados
- LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
- RTAB-Map: Versatile graph-based SLAM supporting RGB-D, stereo, and LiDAR with real-time operation
- LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)
- GLIM: GPU-accelerated 3D lidar SLAM framework for any range sensor, from AIST
Vídeos
- Using Octrees and A* for Efficient Pathfinding: git-amend