Real-Time Indexing of Arbitrarily Attributed Point Clouds

The demand for up-to-date airborne or terrestrial Light Detection and Ranging (LiDAR) data sets is increasing. This works by emitting a laser beam from a scanner. Based on the time of flight, the distance between each reflection point and scanner can be calculated, resulting in 3D point clouds. These point clouds are typically stored unindexed during acquisition. After acquisition, processing and indexing algorithms have to be run as time-consuming batch processes. To avoid this post-processing, the necessary processing steps can be implemented in real-time pipelines to further process and store data during acquisition. Not only spatial indexing but also indexing of many possible attributes of LiDAR points play an important role in applications such as data quality assurance or real-time preview. In this thesis, a real-time approach for attribute indexing of LiDAR point clouds is presented, which extends the spatial index structure of Modifiable Nested Octrees with attribute indexing. The attribute index is implemented by storing attribute ranges contained in each subtree. In addition to spatial restrictions, attribute filters can be defined in the form of attribute-value ranges for queries. Nodes whose ranges do not overlap with the attribute filters can then be sorted using the attribute ranges stored in the octree nodes. An implementation of the approach is presented and measured using a terrestrially acquired dataset of 365 million points. Indexing speeds of over 400 000 points per second can be achieved, and the time for queries with attribute filters can be reduced to 1%-50% of the time required for linear filtering of all indexed points, while on average 33% of all unwanted points can be discarded. These values are achievable on simple consumer hardware, provided a fast hard disk is available.

Der Bedarf an aktuellen luftgestützten oder terrestrischen LiDAR-Datensätzen steigt. Um diese Datensätze zu erfassen, werden Laserstrahlen von einem Scanner ausgesandt. Anhand der Lichtlaufzeit kann die Entfernung zwischen jedem Reflexionspunkt und dem Scanner berechnet werden, woraus 3D-Punktwolken hervorgehen. Die resultierenden Punktwolken werden in der Regel während der Erfassung unindexiert gespeichert. Nach der Erfassung müssen die Verarbeitungs- und Indexierungsalgorithmen als zeitaufwändige Batch-Prozesse ausgeführt werden. Um diese Nachbearbeitung zu vermeiden, können die notwendigen Verarbeitungsschritte in Echtzeit-Pipelines implementiert werden, um die Daten während der Erfassung weiter zu verarbeiten und zu speichern. Nicht nur die räumliche Indexierung, sondern auch die Indexierung der vielen möglichen Attribute von LiDAR-Punkten spielen eine wichtige Rolle in Anwendungen wie der Datenqualitätssicherung oder der Echtzeitvorschau. In dieser Arbeit wird ein Echtzeit-Ansatz zur Attribut-Indexierung von LiDAR-Punktwolken vorgestellt, der die räumliche Indexstruktur von Modifiable Nested Octrees um die Attribut-Indexierung erweitert. Die Attribut-Indexstruktur wird durch die Speicherung der in jedem Teilbaum enthaltenen Attributbereiche implementiert. Zusätzlich zu den räumlichen Einschränkungen können Attributfilter in Form von Attributwertbereichen für Abfragen definiert werden. Knoten, deren Bereiche sich nicht mit den Attributfiltern überschneiden, können dann anhand der in den Octree-Knoten gespeicherten Attributbereiche sortiert werden. Eine Implementierung des Ansatzes wird vorgestellt und anhand eines terrestrisch erfassten Datensatzes von 365 Millionen Punkten gemessen. Es können Indexierungsgeschwindigkeiten von über 400.000 Punkten pro Sekunde erreicht werden, und die Zeit für Abfragen mit Attributfiltern kann auf 1%-50% der Zeit reduziert werden, die für die lineare Filterung aller indexierten Punkte benötigt wird, während im Durchschnitt 33% aller unerwünschten Punkte verworfen werden können. Diese Werte sind auf einfacher Consumer-Hardware erreichbar, sofern eine schnelle Festplatte vorhanden ist.