Nyström-based spectral clustering using airborne LiDAR point cloud data for individual tree segmentation

ABSTRACT

The spectral clustering method has notable advantages in segmentation. But the high computational complexity and time consuming limit its application in large-scale and dense airborne Light Detection and Ranging (LiDAR) point cloud data. We proposed the Nyström-based spectral clustering (NSC) algorithm to decrease the computational burden. This novel NSC method showed accurate and rapid in individual tree segmentation using point cloud data. The K-nearest neighbour-based sampling (KNNS) was proposed for the Nyström approximation of voxels to improve the efficiency. The NSC algorithm showed good performance for 32 plots in China and Europe. The overall matching rate and extraction rate of proposed algorithm reached 69% and 103%. For all trees located by Global Navigation Satellite System (GNSS) calibrated tape-measures, the tree height regression of the matching results showed an value of 0.88 and a relative root mean square error (RMSE) of 5.97%. For all trees located by GNSS calibrated total-station measures, the values were 0.89 and 4.49%. The method also showed good performance in a benchmark dataset with an improvement of 7% for the average matching rate. The results demonstrate that the proposed NSC algorithm provides an accurate individual tree segmentation and parameter estimation using airborne LiDAR point cloud data.

KEYWORDS:

• Tree segmentation
• airborne LiDAR
• spectral clustering
• Nyström approximation
• sampling method

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The relevant code of this research is available at https://github.com/limingado/NSC/tree/v1.0.0.

Notes

Note: The stem density classes correspond to high (H), medium (M) and low (L) levels.

^a Only selected trees with total station location are included for these plots.

Note: Corresponding Latin names: spruce (Picea abies), fir (Abies alba), beech (Fagus sylvatica), Scots pine (Pinus sylvestris), larch (Larix decidua), sycamore (Acer pseudoplatanus), elm (Ulmus glabra), and poplar (Populus nigra). These plots include forests of single or multi-layered (SL or ML)/mixed or coniferous (M or C).

Note: ΔH and ΔD represent the height difference and 2D distance between detection and reference.

Note: $\mathrm{NS}{\mathrm{C}}_{\mathrm{vw}}$ and $\mathrm{NS}{\mathrm{C}}_0$ represent the Nyström-based spectral clustering with and without the voxel weights in the similarity function. $R_{\mathrm{match}}$ represents the overall performance and the $R_{\mathrm{match}}$ with H, M, L correspond to the stem density class in Table 1.

Additional information

Funding

This study was funded by the National Key Research and Development Program of China [grant number 2017YFD0600404] and Natural Science Foundation of China [grant number 41871278].