💻 computer science

Shortest-Path Decomposition for Foliage-Robust 3D Tree Modeling and Above-Ground Biomass Estimation from Point Clouds

This paper introduces a topology-driven shortest-path decomposition method that robustly reconstructs 3D tree structures and estimates above-ground biomass from point clouds under leaf-on conditions by directly recovering branching hierarchy without requiring explicit leaf-wood separation.

Original authors: Di Wang, Shi Li

Published 2026-08-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Di Wang, Shi Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out how much wood is inside a giant, living tree. You can't chop it down to weigh it, so you use a special laser scanner that takes millions of tiny 3D snapshots of the tree, creating a "point cloud"—a digital swarm of dots that looks like the tree made of stardust. Scientists use these dots to build a "Quantitative Structural Model" (QSM), which is basically a digital skeleton of the tree. By measuring the thickness and length of every branch in this digital model, they can calculate the tree's total weight, known as Above-Ground Biomass (AGB). This number is crucial for understanding how much carbon the forest is storing, which helps us fight climate change.

However, there is a massive problem: trees usually have leaves. When a tree is full of leaves, the laser scanner sees a fuzzy, green ball instead of a clear skeleton. The leaves hide the branches, and the scanner's dots get mixed up, making the tree look much fatter and heavier than it really is. For years, the standard way to fix this was to try to teach a computer to tell the difference between a "leaf dot" and a "wood dot" before building the model. But this is like trying to sort a pile of mixed-up Legos by color before you can build the castle; it's messy, prone to mistakes, and often throws away tiny, important branches along with the leaves.

This paper introduces a clever new way to solve the puzzle. Instead of trying to sort the dots by what they look like (green leaf vs. brown wood), the authors look at how the dots are connected. They treat the tree like a subway map. If you start at the bottom of the tree (the roots) and draw the shortest possible path to every single dot in the cloud, the main trunk and big branches become the busiest "subway lines." Thousands of paths have to travel through the trunk to reach the leaves, but only one or two paths go to the very tips of the leaves. By counting how many "passengers" (paths) travel through each dot, the computer can instantly know which dots are on the main highway and which are just dead-end stops, without ever needing to know if a dot is a leaf or a branch.

The authors tested this "shortest-path" method on 90 real trees, ranging from dense tropical forests in Cameroon to temperate forests in Germany, using both ground-based lasers and drone scanners. They found that their new method was incredibly accurate, even when the trees were covered in leaves. On the tropical trees, their model estimated the weight with an average error of just 17.2%, which is actually better than the best existing methods that try to remove the leaves first (which had an error of 21.2%). Even more impressively, when they used the method on low-quality data from drones, it still worked well, provided they knew the tree's diameter at the base.

The study shows that by focusing on the tree's "roadmap" rather than trying to clean up the picture, we can build accurate 3D models of trees without needing to strip off their leaves first. This means we can measure forest carbon much faster and more reliably, even in the middle of summer when the trees are at their leafiest. The authors suggest that this approach could become a standard tool for forest managers, removing the need for complex, error-prone steps to separate leaves from wood. While the method isn't perfect—it still struggles a bit if the drone data is too sparse to see the tree's trunk clearly—it represents a significant step forward in making forest monitoring robust and practical.

Technical Summary: Shortest-Path Decomposition for Foliage-Robust 3D Tree Modeling

Problem Statement
Estimating Above-Ground Biomass (AGB) from Terrestrial Laser Scanning (TLS) and UAV Laser Scanning (ULS) using Quantitative Structural Models (QSMs) is highly accurate under leaf-off conditions but degrades significantly when foliage is present. Existing QSM paradigms—primarily cylinder-fitting methods (e.g., TreeQSM) and skeleton-based methods (e.g., AdQSM)—suffer from a "foliage bottleneck." Cylinder-fitting approaches inflate volume by treating dense leaf clusters as woody material, while skeleton-based approaches generate spurious branches because the underlying graph must connect every input point, including leaves.

The standard remedy, a two-stage pipeline involving explicit leaf–wood separation prior to reconstruction, introduces its own limitations. Recent benchmarks indicate that separation algorithms often misclassify fine peripheral branches as leaves, leading to systematic AGB underestimation (2–46%). Furthermore, because the classifier and the reconstructor are optimized independently, classification errors propagate downstream with no guarantee of bounded effects, creating an architectural fragility that cannot be resolved by improving classifier accuracy alone.

Methodology: Topology-First Reconstruction
The authors propose a topology-driven approach that bypasses explicit leaf–wood classification entirely. Instead of relying on geometric features (e.g., intensity, curvature) to distinguish wood from leaves, the method exploits the topological signal inherent in the shortest-path structure of a point-cloud graph.

Theoretical Foundation: The method relies on a property of rooted tree graphs: the number of root-to-node paths traversing a specific node equals the size of the subtree rooted at that node. Consequently, path traversal frequency serves as an exact topological descriptor of branching hierarchy. Arterial woody edges are traversed by thousands of paths, while peripheral foliage points are reached by few paths. This frequency gap persists regardless of leaf shape, point density, or sensor platform.
Pipeline Overview: The algorithm executes a single Dijkstra run on a proximity graph (constructed via KNN and Delaunay triangulation) to extract a shortest-path tree rooted at the tree base. From this single run, three decompositions recover the branching hierarchy:
- Path Frequency Decomposition: Identifies arterial nodes based on the volume of paths traversing them.
- Farthest-Tip Decomposition: Partitions the point cloud into branch-level clusters by assigning each node to the terminal tip with the maximum root distance.
- Spatial Decomposition: Segments each branch along its length using a reverse-distance metric with adaptive exponential step sizes.
Adaptive Foliage Suppression: An adaptive frequency threshold is derived from the "elbow" point of frequency growth along each branch (the first instance where frequency doubles). This threshold suppresses leaf-level nodes without per-tree tuning or manual parameter specification.
QSM Assembly: The recovered skeleton nodes are used to construct a QSM. Branch diameters are estimated via allometric scaling (pipe model) rather than direct cylinder fitting, and tree volume is computed as the sum of truncated-cone volumes.

Key Contributions

Reformulation of QSM: The paper reframes QSM reconstruction as a topology recovery problem rather than a semantic segmentation problem, extracting branching hierarchy directly from graph connectivity.
Theoretical Basis: It establishes that path traversal frequency is an exact topological descriptor on rooted trees, providing a mechanism for foliage suppression that does not rely on geometric feature classification.
Unified Pipeline: The method utilizes three decompositions derived from a single Dijkstra run, employing an adaptive elbow threshold to replace manual parameter specification.
Cross-Platform Robustness: The approach demonstrates parameter consistency across sensor platforms (TLS and ULS) and biomes (tropical and temperate) without adjustment.

Experimental Results
The method was evaluated on 90 trees under exclusively leaf-on conditions across two datasets: 61 tropical trees from Cameroon (TLS) and 29 temperate trees from Germany (ULS).

Tropical TLS (Cameroon): The method achieved a Mean Absolute Percentage Deviation (MAPD) of 17.2% and an $R^2$ of 0.956. This outperformed the best separation-assisted TreeQSM pipeline (21.2% MAPD) and significantly reduced the error compared to unfiltered TreeQSM (169.3% MAPD).
Temperate ULS (Germany): With TLS-measured Diameter at Breast Height (DBH) provided as ground truth, the method achieved a MAPD of 6.4%. When using allometrically inferred DBH from tree height, the MAPD was 32.3%.
Structural Consistency: Analysis of the 61 Cameroon trees revealed that foliage introduces a mean geometric error of 2.6 cm (3.8 cm RMS) relative to leaf-off conditions. Crucially, the method preserved the hierarchical volume distribution, retaining 0.71% of volume in fine branch orders (Order 5+) under leaf-on conditions, whereas separation-assisted methods reduced this to 0.16%.

Significance and Claims
The paper claims that the primary barrier to operational QSM-based forest inventory under leaf-on conditions is architectural, not algorithmic. By replacing the two-stage "separate-then-reconstruct" paradigm with a "topology-first" approach, the method removes the need for explicit leaf–wood classification.

The authors assert that their topology-driven foliage suppression is robust because the frequency gap is a property of the whole tree's connectivity, making it invariant to leaf shape, point density, or sensor type. The results suggest that recovering branching hierarchy from shortest-path structure allows for accurate AGB estimation across diverse platforms and biomes without per-dataset parameter tuning, effectively bypassing the limitations of current separation-assisted pipelines. The paper concludes that while allometric diameter modeling introduces some error compared to direct cylinder fitting on clean data, the trade-off yields superior robustness in realistic, foliage-rich environments.

Technical Summary: Shortest-Path Decomposition for Foliage-Robust 3D Tree Modeling

More like this