Octree

Auch genannt: sparse voxel octree
Kategorie: Sensing › 3D maps & reconstruction
Schlagwörter: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds

Eine Baumdatenstruktur, die den 3D-Raum rekursiv in acht Würfel teilt und feine Zellen nur dort anlegt, wo Daten vorhanden sind, für kompakte Karten und schnelle räumliche Abfragen.

Definition

Ein Octree ist ein Baum, in dem jeder Knoten einen Würfel des Raums darstellt und bis zu acht Kinder haben kann, eines für jeden Oktanten, der durch Halbieren des Würfels entlang aller drei Achsen entsteht. Die Wurzel deckt das ganze Volumen ab; jede Ebene tiefer halbiert die Zellgröße. Äste werden nur dort unterteilt, wo etwas Relevantes vorhanden ist, etwa gemessene Oberflächenpunkte, sodass große leere oder unbeobachtete Bereiche als einzelne grobe Knoten bleiben. Octrees wurden Anfang der 1980er-Jahre von Donald Meagher für die Festkörpermodellierung beschrieben und sind heute Standard in Grafik, Punktwolkenverarbeitung und Roboterkartierung.

Der Hauptvorteil ist der Speicher. Ein dichtes Voxelgitter mit feiner Auflösung über einem großen Gebäude braucht Speicher für jede Zelle, während der Speicher eines Octrees ungefähr mit der beobachteten Oberfläche wächst. Er bietet außerdem Zugriff in mehreren Auflösungen: Ein Planer kann grobe Zellen für eine schnelle Prüfung abfragen und für Details tiefer gehen. In OctoMap, einer weit verbreiteten Bibliothek von Hornung und Kollegen, enthält jedes Blatt einen probabilistischen Belegungswert in Log-Odds-Form, der aus Entfernungsmessungen aktualisiert wird, sodass die Karte belegten, freien und unbekannten Raum unterscheidet. Kinder mit gleichem Zustand werden in ihren Elternknoten zurückgefasst, um Speicher zu sparen.

Octrees tauschen etwas Geschwindigkeit gegen diese Kompaktheit: Ein Blatt zu erreichen bedeutet, den Baum hinabzulaufen, was langsamer ist als die Indizierung eines flachen Arrays. Alternativen wie Voxel-Hashing und die VDB-Struktur bieten bei manchen Lasten schnelleren Zugriff. Octrees werden auch genutzt, um Nächster-Nachbar-Suche und Kollisionsprüfung auf Punktwolken zu beschleunigen, und in neueren neuronalen Kartierungssystemen organisieren sie dünn besetzte Voxel, die gelernte Merkmale speichern, und wachsen inkrementell, wenn neue Tiefenbilder eintreffen.

Warum es wichtig ist

Roboter brauchen 3D-Karten, die große Bereiche mit nützlicher Auflösung abdecken, ohne den Speicher zu erschöpfen. Octrees machen das praktikabel, und sie sind die Grundlage gängiger Werkzeuge für Belegungskartierung und Kollisionsprüfung in der Manipulation und der Flugnavigation.

Wichtige Anwendungen

Probabilistische 3D-Belegungskartierung mit OctoMap
Kollisionsprüfung für Manipulatoren und Drohnen
Nächster-Nachbar- und Radiussuche auf Punktwolken
Dünn besetzte Voxelstrukturen für neuronal-implizite und dichte Kartierung
Punktwolkenkompression und Rendering mit Detailstufen (Level of Detail)

In der Praxis

Ein Team, das eine 3D-Karte für eine durch ein Lager fliegende Drohne erstellt, speist Punktwolken aus Tiefenkamera oder LiDAR mit Posen aus seiner Odometrie in OctoMap mit einer Auflösung von wenigen Zentimetern ein. Jeder Strahl markiert die Zellen, die er durchläuft, als wahrscheinlicher frei und die Zelle an seinem Ende als wahrscheinlicher belegt. Der Planer fragt den Octree entlang von Kandidatenpfaden nach Belegung ab und behandelt unbekannten Raum als Hindernis. Bei einem Manipulator kann MoveIt dieselbe Art von Octree von einem Tiefensensor übernehmen, um die Planungsszene des Arms aktuell zu halten. Ingenieure stimmen Auflösung, Sensorreichweite sowie Treffer- und Fehlwahrscheinlichkeiten ab, um Detail, Speicher und die Geschwindigkeit, mit der sich bewegende Objekte gelöscht werden, auszubalancieren.

Häufige Missverständnisse

Ein Octree ist dasselbe wie ein Voxelgitter — ein Voxelgitter speichert jede Zelle, während ein Octree nur dort unterteilt, wo es nötig ist, und gleichförmige Bereiche zusammenfasst
Octrees sind immer schneller als flache Gitter — sie sparen Speicher, aber jeder Zugriff läuft den Baum hinab, daher können dichte oder gehashte Gitter bei manchen Abfragen schneller sein
Leerer Raum in einem Octree bedeutet freien Raum — in Belegungs-Octrees ist unbeobachteter Raum unbekannt, was Planer in der Regel anders behandeln sollten als freien Raum

Wer das wissen sollte

Ingenieure für Kartierung und SLAM
Entwickler für Bewegungsplanung und Kollisionsprüfung
Ingenieure für Drohnenautonomie in 3D-Umgebungen
Entwickler neuronaler und dichter Kartierungssysteme

Videos

Using Octrees and A* for Efficient Pathfinding: git-amend

Wikipedia

Octree

Open Source Robotics