Abstract
Our work addresses the problem of extracting trees from mobile laser scanning data. The work is a two step-wise strategy, including terrain point removal and tree segmentation. First, a voxel-based upward growing filtering is proposed to remove terrain points from the mobile laser scanning data. Then, a tree segmentation is presented to extract individual trees via a Euclidean distance clustering approach and Voxel-based Normalized Cut (VNCut) segmentation approach. A road section data acquired by a RIEGL VMX-450 system are selected for evaluating the proposed tree segmentation method. Qualitative analysis shows that our algorithm achieves a good performance.
1. Introduction
Mobile Laser Scanning (MLS) has revolutionized urban mapping by providing dense 3D point clouds of street environments. However, segmenting individual trees from these datasets remains a significant challenge. Urban trees often have overlapping canopies, are situated on varying terrain, and are surrounded by man-made objects like light poles and traffic signs. Traditional point-based methods are often computationally expensive and struggle to separate intertwined vegetation. This paper proposes a robust, voxel-based workflow to efficiently remove terrain and segment individual trees in complex urban scenes.
2. Methodology
The proposed method follows a two-stage process: terrain removal followed by tree segmentation.
2.1 Terrain Point Removal
To handle large-scale datasets and varying topography, a voxel-based upward growing filter is employed. The scene is first divided into blocks ($D_j$). Within each block, points are organized into an octree structure of voxels. Starting from base voxels, the algorithm "grows" upward. If the maximum height of a connected region remains below a predefined terrain threshold ($H_{thresh}$), the region is classified as ground and removed. This approach is more resilient to slope variations than simple height-cutoff filters.
2.2 Tree Segmentation
After terrain removal, the remaining points (primarily vegetation and street furniture) are segmented:
- Euclidean Distance Clustering: An initial pass groups points based on spatial proximity. While effective for isolated trees, this step often groups overlapping trees into a single cluster.
- Voxel-based Normalized Cut (VNCut): To resolve overlapping clusters, the authors apply a graph-based segmentation technique. The cluster is treated as a graph where voxels are nodes ($V_i$). Edges between nodes are weighted based on spatial similarity. By solving a generalized eigenvalue problem, the algorithm identifies the optimal "cut" to separate individual tree crowns.
3. Experimental Evaluation
The method was tested on a real-world dataset acquired using a RIEGL VMX-450 mobile mapping system.
3.1 Dataset
The study area is a 60-meter section of Huandao Road in Xiamen, China. This tropical environment features high point densities (~286 points/$m^2$) and complex vegetation, including Sago cycas and dense roadside trees.
3.2 Results
Qualitative analysis demonstrates that the voxel-based upward growing filter effectively isolates the road surface. Subsequent segmentation successfully disentangles overlapping tree canopies that would typically be merged by standard clustering algorithms. The use of 5cm voxels provided a balance between geometric fidelity and computational efficiency.
4. Conclusion
The combination of voxel-based terrain filtering and VNCut segmentation provides a powerful framework for urban tree inventory. By shifting from raw points to voxels and leveraging graph theory, the system handles complex, overlapping vegetation more effectively than traditional methods. Future work will focus on automating parameter selection and conducting quantitative benchmarking against manually labeled ground truth data to further validate the method's accuracy across diverse tree species.
Summary updated