Abstract
This paper presents an automated algorithm for extracting 3D trees directly from 3D mobile light detection and ranging (LiDAR) data. To reduce both computational and spatial complexities, ground points are first filtered out from a raw 3D point cloud via block-based elevation filtering. Off-ground points are then grouped into clusters representing individual objects through Euclidean distance clustering and voxel-based normalized cut segmentation. Finally, a model-driven method is proposed to achieve the extraction of 3D trees based on a pairwise 3D shape descriptor. The proposed algorithm is tested using a set of mobile LiDAR point clouds acquired by a RIEGL VMX-450 system. The results demonstrate the feasibility and effectiveness of the proposed algorithm.
Introduction
Mobile LiDAR systems generate dense 3D point clouds of urban environments, providing a wealth of geometric information. However, the automated extraction of specific objects like trees remains a challenge due to massive data volumes, complex urban scenes where trees overlap with other structures, and the irregular geometry of vegetation. Unlike man-made objects with predictable planar surfaces, trees require specialized 3D processing to preserve their structural integrity. This study proposes a fully automated pipeline to isolate individual trees directly from 3D point clouds.
Methodology
The proposed workflow consists of three primary stages:
- Ground Filtering: To streamline processing, the algorithm removes road and sidewalk points using block-based elevation filtering. The scene is partitioned into 3m blocks, and points below a 0.4m threshold relative to the local minimum are discarded.
- Object Segmentation: Initial grouping is performed via Euclidean distance clustering. To handle overlapping or touching trees, a voxel-based Normalized Cut (N-cut) algorithm is applied. This graph-based approach partitions merged clusters into individual objects by analyzing connectivity within an octree structure.
- Model-Driven Extraction: Segmented objects are classified using a pairwise 3D shape descriptor. By comparing the spatial relationships of points within an object to a mathematical tree template, the system calculates a dissimilarity score to identify and extract trees.
Experimental Setup and Datasets
The algorithm was evaluated using point clouds collected along Ring Road South in Xiamen, China. The data was acquired using a RIEGL VMX-450 mobile mapping system, which integrates dual scanners, high-resolution cameras, GNSS, and IMU sensors to achieve high precision (5mm) and accuracy (8mm).
The test datasets featured varying tree species and planting densities, with a point density of approximately 7,000 points/m², providing a rigorous test for the segmentation and extraction logic.
Key Insights and Results
The study highlights several critical advantages of the 3D-centric approach:
- Geometric Fidelity: By avoiding 2D rasterization, the method preserves vertical structural details, which are essential for distinguishing trees from other tall urban features.
- Robust Segmentation: The N-cut algorithm effectively resolves "merged" clusters that simple distance-based methods fail to separate.
- Shape Context Robustness: The pairwise shape descriptor maintains performance despite varying point densities, a common issue in mobile LiDAR where distance from the scanner affects sampling.
The results across three distinct datasets confirmed high precision in tree extraction. Stable parameters, such as a 3m block size and 0.15m clustering distance, proved effective across different environments.
Conclusion and Future Work
The proposed automated pipeline demonstrates a robust solution for 3D tree extraction in complex urban settings. While highly effective, the model-driven nature of the extraction phase suggests that future work could benefit from integrating machine learning to accommodate a wider variety of tree morphologies. Additionally, optimizing the computational efficiency of the N-cut and shape matching steps will be vital for scaling the system to city-wide datasets.
Summary updated