Automated Extraction of 3D Trees from Mobile LiDAR Point Clouds

Yongtao Yu, Jonathan Li, Haiyan Guan, Dawei Zai, Chunjin Wang2014 · DOI

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:

  1. 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.
  2. 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.
  3. 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.
Segmentation results demonstrating the separation of individual trees using voxel-based N-cut.

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 RIEGL VMX-450 mobile mapping system used for data acquisition.

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

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 blockbased 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.
BibTeX
@inproceedings{yu2014automated,
  author = {Yongtao Yu and Jonathan Li and Haiyan Guan and Dawei Zai and Chunjin Wang},
  title = {{Automated Extraction of 3D Trees from Mobile LiDAR Point Clouds}},
  booktitle = {˜The},
  year = {2014},
  doi = {10.5194/isprsarchives-xl-5-629-2014},
}
Figure