Octree
- Detto anche: sparse voxel octree
- Categoria: Sensing › 3D maps & reconstruction
- Tag: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds
Una struttura dati ad albero che suddivide ricorsivamente lo spazio 3D in otto cubi, allocando celle fini solo dove ci sono dati, per ottenere mappe compatte e interrogazioni spaziali rapide.
Definizione
Octree (albero ottale) è un albero in cui ogni nodo rappresenta un cubo di spazio e può avere fino a otto figli, uno per ciascun ottante ottenuto dimezzando il cubo lungo tutti e tre gli assi. La radice copre l'intero volume; ogni livello più in basso dimezza la dimensione della cella. I rami vengono suddivisi solo dove c'è qualcosa di interessante, come punti di superficie misurati, così che le grandi regioni vuote o non osservate restano singoli nodi grossolani. Gli octree furono descritti per la modellazione solida da Donald Meagher all'inizio degli anni Ottanta e oggi sono uno standard nella grafica, nell'elaborazione delle nuvole di punti e nella mappatura robotica.
Il principale vantaggio è la memoria. Una griglia di voxel densa a risoluzione fine su un grande edificio richiede spazio per ogni cella, mentre lo spazio occupato da un octree cresce all'incirca con l'area della superficie osservata. Offre inoltre un accesso multirisoluzione: un pianificatore può interrogare celle grossolane per un controllo rapido e scendere per ottenere il dettaglio. In OctoMap, una libreria molto diffusa di Hornung e colleghi, ogni foglia contiene un valore di occupazione probabilistico in forma di log-odds, aggiornato dalle misure di distanza, così che la mappa distingue spazio occupato, libero e sconosciuto. I figli con lo stesso stato vengono potati e riassorbiti nel genitore per risparmiare memoria.
Gli octree cedono un po' di velocità in cambio di questa compattezza: raggiungere una foglia significa scendere lungo l'albero, il che è più lento che indicizzare un array piatto. Alternative come il voxel hashing e la struttura VDB offrono un accesso più rapido in alcuni carichi di lavoro. Gli octree si usano anche per accelerare la ricerca dei vicini più prossimi e la verifica delle collisioni sulle nuvole di punti, e nei sistemi recenti di mappatura neurale organizzano voxel sparsi che memorizzano feature apprese, crescendo in modo incrementale man mano che arrivano nuovi fotogrammi di profondità.
Perché è importante
I robot hanno bisogno di mappe 3D che coprano grandi aree a una risoluzione utile senza esaurire la memoria. Gli octree lo rendono possibile, e sono alla base di strumenti comuni di mappatura dell'occupazione e di verifica delle collisioni usati nella manipolazione e nella navigazione aerea.
Applicazioni principali
- Mappatura probabilistica dell'occupazione 3D con OctoMap
- Verifica delle collisioni per manipolatori e droni
- Ricerca dei vicini più prossimi e ricerca per raggio sulle nuvole di punti
- Strutture a voxel sparsi per la mappatura implicita neurale e densa
- Compressione di nuvole di punti e rendering a livelli di dettaglio
In pratica
Un team che costruisce una mappa 3D per un drone che vola in un magazzino fornisce a OctoMap nuvole di punti da una telecamera di profondità o da un lidar, con le pose dalla propria odometria, a una risoluzione di pochi centimetri. Ogni raggio segna le celle che attraversa come più probabilmente libere e la cella in cui termina come più probabilmente occupata. Il pianificatore interroga l'octree sull'occupazione lungo i percorsi candidati, trattando lo spazio sconosciuto come un ostacolo. Su un manipolatore, MoveIt può ricevere lo stesso tipo di octree da un sensore di profondità per mantenere aggiornata la scena di pianificazione del braccio. Gli ingegneri regolano risoluzione, portata del sensore e probabilità di hit e miss per bilanciare dettaglio, memoria e rapidità con cui vengono cancellati gli oggetti in movimento.
Idee sbagliate comuni
- Un octree è la stessa cosa di una griglia di voxel — una griglia di voxel memorizza ogni cella, mentre un octree suddivide solo dove serve e accorpa le regioni uniformi
- Gli octree sono sempre più veloci delle griglie piatte — risparmiano memoria, ma ogni consultazione scende lungo l'albero, quindi le griglie dense o con hashing possono essere più rapide per alcune interrogazioni
- Lo spazio vuoto in un octree significa spazio libero — negli octree di occupazione lo spazio non osservato è sconosciuto, e di solito i pianificatori dovrebbero trattarlo in modo diverso dallo spazio libero
Chi dovrebbe saperlo
- Ingegneri di mappatura e SLAM
- Sviluppatori di pianificazione del movimento e verifica delle collisioni
- Ingegneri di autonomia dei droni che lavorano in ambienti 3D
- Sviluppatori di sistemi di mappatura neurale e densa
Tecnologie correlate
- OctoMap
- Voxel hashing (Voxel Hashing)
- OpenVDB
- Point Cloud Library (PCL)
- MoveIt
Termini correlati
Progetti correlati
- 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
Video
- Using Octrees and A* for Efficient Pathfinding: git-amend