Octree
- Aussi appelé: sparse voxel octree
- Catégorie: Sensing › 3D maps & reconstruction
- Mots-clés: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds
Structure de données arborescente qui divise récursivement l'espace 3D en huit cubes, en n'allouant des cellules fines que là où il y a des données, pour des cartes compactes et des requêtes spatiales rapides.
Définition
Un octree est un arbre dans lequel chaque nœud représente un cube d'espace et peut avoir jusqu'à huit enfants, un pour chaque octant obtenu en coupant le cube en deux selon les trois axes. La racine couvre tout le volume ; chaque niveau inférieur divise par deux la taille des cellules. Les branches ne sont subdivisées que là où se trouve quelque chose d'intéressant, comme des points de surface mesurés, de sorte que les grandes régions vides ou non observées restent des nœuds grossiers uniques. Les octrees ont été décrits pour la modélisation des solides par Donald Meagher au début des années 1980 et sont aujourd'hui standard en infographie, en traitement de nuages de points et en cartographie robotique.
Leur principal attrait est la mémoire. Une grille de voxels dense à résolution fine sur un grand bâtiment exige un stockage pour chaque cellule, alors que le stockage d'un octree croît à peu près avec l'aire de surface observée. Il offre aussi un accès multirésolution : un planificateur peut interroger des cellules grossières pour une vérification rapide et descendre pour obtenir du détail. Dans OctoMap, une bibliothèque très utilisée de Hornung et de ses collègues, chaque feuille contient une valeur d'occupation probabiliste sous forme de log-odds, mise à jour à partir des mesures de distance, de sorte que la carte distingue l'espace occupé, libre et inconnu. Les enfants de même état sont fusionnés dans leur parent pour économiser la mémoire.
Les octrees sacrifient un peu de vitesse à cette compacité : atteindre une feuille suppose de descendre l'arbre, ce qui est plus lent que d'indexer un tableau plat. Des alternatives comme le hachage de voxels et la structure VDB offrent un accès plus rapide pour certaines charges de travail. Les octrees servent aussi à accélérer la recherche de plus proches voisins et la vérification de collision sur des nuages de points, et dans des systèmes récents de cartographie neuronale, ils organisent des voxels creux qui stockent des caractéristiques apprises, en croissant de manière incrémentale à l'arrivée de nouvelles images de profondeur.
Pourquoi c'est important
Les robots ont besoin de cartes 3D qui couvrent de grandes zones à une résolution utile sans épuiser la mémoire. Les octrees rendent cela possible, et ils sont à la base des outils courants de cartographie d'occupation et de vérification de collision utilisés en manipulation et en navigation aérienne.
Applications principales
- Cartographie 3D probabiliste de l'occupation avec OctoMap
- Vérification de collision pour manipulateurs et drones
- Recherche de plus proches voisins et recherche par rayon sur des nuages de points
- Structures de voxels creux pour la cartographie implicite neuronale et dense
- Compression de nuages de points et rendu à niveaux de détail
En pratique
Une équipe qui construit une carte 3D pour un drone volant dans un entrepôt fournit à OctoMap, à une résolution de quelques centimètres, des nuages de points de caméra de profondeur ou de LiDAR, avec les poses issues de son odométrie. Chaque rayon marque les cellules qu'il traverse comme plus probablement libres et la cellule à son extrémité comme plus probablement occupée. Le planificateur interroge l'octree sur l'occupation le long des chemins candidats, en traitant l'espace inconnu comme un obstacle. Sur un manipulateur, MoveIt peut recevoir le même type d'octree d'un capteur de profondeur pour tenir à jour la scène de planification du bras. Les ingénieurs règlent la résolution, la portée du capteur et les probabilités de touche et de manque pour équilibrer le détail, la mémoire et la vitesse à laquelle les objets en mouvement sont effacés.
Idées reçues
- Un octree est la même chose qu'une grille de voxels — une grille de voxels stocke chaque cellule, alors qu'un octree ne subdivise que là où c'est nécessaire et fusionne les régions uniformes
- Les octrees sont toujours plus rapides que les grilles plates — ils économisent de la mémoire, mais chaque consultation parcourt l'arbre, si bien que des grilles denses ou hachées peuvent être plus rapides pour certaines requêtes
- L'espace vide d'un octree signifie de l'espace libre — dans les octrees d'occupation, l'espace non observé est inconnu, ce que les planificateurs devraient généralement traiter différemment de l'espace libre
Qui devrait le savoir
- Ingénieurs en cartographie et en SLAM
- Développeurs de planification de mouvement et de vérification de collision
- Ingénieurs en autonomie de drones travaillant dans des environnements 3D
- Développeurs de systèmes de cartographie neuronale et dense
Technologies associées
- OctoMap
- Hachage de voxels (Voxel Hashing)
- OpenVDB
- Point Cloud Library (PCL)
- MoveIt
Termes associés
Projets associés
- 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
Vidéos
- Using Octrees and A* for Efficient Pathfinding: git-amend