Scalable individual tree delineation in 3D point clouds

Manually monitoring and documenting trees is labour intensive. Lidar provides a possible solution for automatic tree-inventory generation. Existing approaches for segmenting trees from original point cloud data lack scalable and efficient methods that separate individual trees sampled by different laser-scanning systems with sufficient quality under all circumstances. In this study a new algorithm for efficient individual tree delineation from lidar point clouds is presented and validated. The proposed algorithm first resamples the points using cuboid (modified voxel) cells. Consecutively connected cells are accumulated by vertically traversing cell layers. Trees in close proximity are identified, based on a novel cell-adjacency analysis. The scalable performance of this algorithm is validated on airborne, mobile and terrestrial laser-scanning point clouds. Validation against ground truth demonstrates an improvement from 89% to 94% relative to a state-of-the-art method while computation time is similar. Resume La detection et la documentation manuelle des arbres est une tache fastidieuse. Le lidar offre une solution possible pour l'inventaire automatique des arbres. Les approches existantes pour la segmentation des arbres dans des nuages bruts de points ne proposent pas de methodes efficaces et adaptees a toutes les echelles pour separer des arbres individuels echantillonnes par differents systemes lidar avec une qualite acceptable en toute circonstance. Cette etude propose et valide un nouvel algorithme pour la delimitation efficace d'arbres individuels a partir de nuages de points lidar. L'algorithme propose commence par reechantillonner les points dans des cellules cubiques (voxels), puis regroupe les cellules connexes en traversant verticalement les couches de cellules. Les arbres proches sont identifies grace a une nouvelle analyse d'adjacence de cellules. La performance de cetalgorithme en termes d'adaptabilite au changement d'echelle est validee a partir de nuages de points issus de systemes laser a balayage aerien, mobile et terrestre. Une validation basee sur des donnees de terrain de reference fait etat d'une amelioration de 89% a 94% par rapport a des methodes connues pour un temps de calcul comparable. Zusammenfassung Eine uberwachung und Dokumentation von Baumen ist sehr arbeitsaufwandig. Lidar bietet das Potential fur automatische Bauminventur. Es gibt Ansatze zur Segmentierung von Baumen aus Punktwolken, die allerdings noch nicht in der Lage sind, einzelne Baume in Punktwolken verschiedener Lidar-Systeme zuverlassig und mit ausreichender Qualitat unter vielfaltigen realen Bedingungen zu separieren. Diese Studie stellt einen neuen Algorithmus zur effizienten Erfassung von Baumen in Lidar-Punktwolken dar. Der Algorithmus bildet Punkte mit Hilfe von quaderformigen (Voxel) Zellen um. Nacheinander verbundene Zellen werden durch vertikale Traverse der Zellschichten akkumuliert. Baume in nachster Nachbarschaft werden durch eine neuartige Zellanalyse identifiziert. Der Vorteil der Skalierbarkeit des Algorithmus wird an flugzeuggestutzten, mobilen und terrestrischen Laserscanpunktwolken validiert. Anhand von Solldaten ist festzustellen, dass bei gleicher Rechenzeit, eine Verbesserung von 89% bis 94% im Vergleich zu aktuellen Verfahren erzielt werden kann. Resumen Monitorizar y documentar manualmente arboles es un trabajo intensivo. El lidar proporciona una posible solucion para la generacion automatica del inventario de arboles. Los enfoques existentes para segmentar arboles a partir originalmente de nubes de puntos lidar carecen de metodos escalables y eficientes que separen arboles individuales muestreados por diferentes sistemas lidar con calidad suficiente bajo todas las circunstancias. En este estudio, se presenta y valida un algoritmo nuevo para la delimitacion eficiente de arboles individuales a partir de nubes de puntos lidar. El algoritmo propuesto primero remuestrea los puntos usando celulas cuboides (voxels). Los voxels adyacentes se acumulan atravesando verticalmente las capas de voxels. Basados en un nuevo analisis de adyacencia de voxels se identifican arboles que estan proximos. El rendimiento escalable de este algoritmo se valida con nubes de puntos lidar aerotransportados, moviles y terrestres. La validacion con verdad terreno demuestra una mejora del 89% al 94% en comparacion con un metodo de vanguardia, mientras que el tiempo de calculo es similar.