Revealing the skeleton from imperfect point clouds

Abstract

Quantifying our surrounding environment in terms of sizes and orders has always been of interest, because it enables us to visualize, describe and interpret our environment. In the last decade terrestrial laser scanners became available as a tool to measure objects in our surrounding environment. Terrestrial laser scanning samples surfaces with millions of 3D points to be stored as a point cloud. These point clouds contain information of sizes and orders of the sampled objects. Recently, trees became an object of high interest, because they contain a rich and complex structure, which is to be exploited in terms of branch length, branch diameter and branching hierarchy. Such information can be used for forestry, hydrology, ecology and visualization applications. This thesis introduces the SkelTre algorithm (Skeletonization of Trees) as a method to extract a structure description from point clouds. Such a structure description is a socalled skeleton which is similar to a collection of connected lines. A skeleton enables us to extract the branching hierarchy and the size parameters of tree branches from point clouds. Laser scanned point clouds contain only information about the surface of a scanned object and no information about its inside. One benefit of SkelTre is its ability to extract a skeleton purely from the surface samples represented in the point cloud. The SkelTre algorithm meets four main requirements explicitly: 1. Topological preservance - to enable the branching hierarchy extraction 2. Metric representation - to enable the measurement of sizes 3. Imperfect data handling - to address data characteristics such as noise, underampling and varying point density 4. Computational efficiency - to address the need for fast data processing on the given huge amount of data The SkelTre algorithm treats all four requirements based on one single characteristic, the local elongation direction. This elongation direction describes locally how an object surface is sizing in a 3D space. A local elongation direction can be extracted from the given imperfect data by analyzing small cubical cells subdividing the point cloud into a 3D raster. The cubical cells are derived from a so-called octree subdivision. For each cell it is analyzed which side of the cell is passed by the point cloud. The passed sides are representing the local elongations which are further represented by a graph. In this graph, each cell is corresponding to a vertex. If cells share a passed side, than the corresponding vertices are linked by an edge. The input point cloud is imperfect, because it contains noise, undersampling and varying point densities. Therefore, SkelTre treats these point cloud characteristics explicitly, to produce a result that is correctly representing the branching hierarchy. Therefore, before the graph is reduced to the skeleton a robustness criterion is applied. This criterion removes and adds edges to the graph. Edges are added on locations where data is missing because of undersampling or removed when noise causes unintended edges. At this stage the graph ideally represents the surface of an object and is to be reduced to a skeleton. This corrected graph is then reduced to a skeleton by a set of newly developed rules. The reduction uses two suited vertex configurations occurring in the graph, so-called E-Pairs and V-Pairs. Basically the reduction relies on the property, that whenever an E-Pair is found and reduced, one or more V-Pairs are generated. Processing of a V-Pair leads to either new V-Pairs or otherwise a new E-Pair has to be found in the graph. If neither an E-Pair or a V-Pair is present in the graph it is ensured that the result is a skeleton. The resulting skeleton is related to a known topological structure, the Reeb-Graph. During the reduction of the graph, the graph is embedded into the point cloud such that every vertex is locally centered within the point cloud. The correct branching order and centeredness enables the navigation to a chosen location in the point cloud to derive a branch diameter. A first implementation of the algorithm is given to demonstrate its efficiency on huge point cloud data. On many examples it is evaluated, that all four requirements are met. These examples include non-tree objects to emphasize the generality of the introduced skeletonization framework. The practical use of the SkelTre algorithm is demonstrated on two applications demanding automatic size measurements on trees. In contrast to older methods, both applications do not rely on pre-knowledge of the tree species. Hence, the assessment of trees in these applications is purely based on the point cloud data. Both applications use the newly developed HARPER method to estimate the diameter under support of the SkelTre skeleton. The HARPER method estimates the diameter of a branch on the basis of the double distance of the point cloud points to the skeleton. The length of branches is derived as the sum of the edge lengths in the skeleton of a branch. The first application is the automatic estimation of the tree parameters branch length and branch diameter from laser scanned orchard trees. The estimated parameters are a key to understand a number of physiological processes in the tree canopy. Furthermore, these parameters are useful to determine the vitality of a tree. Orchard trees are optimized by branch cuttings to maximize the crop load on the tree. These cuttings destroy the growth pattern of the tree. Therefore, assumptions about the growth pattern can not be made for the estimation of the branch sizes. For these orchard trees the branch length and diameter was derived with the HARPER method. High correlations above 0.9 between field and automatic measurement were found in the frequency distributions of the branch length and diameter classes. These results show that automatic measurement of tree parameters from terrestrial laser scans is possible. The second application demonstrates a possible future use of the SkelTre skeleton. Here, the skeletonization was applied to airborne obtained laser point clouds to estimate the trunk diameter at breast height (1,30m). The diameter at breast height is one key parameter for calculating hydrological roughness in flooding areas and to estimate the woody volume of a tree. The density of airborne obtained point clouds is only 75 points per square meter. Still, the trunk diameter at breast height could be extracted. On simulated airborne scanned trees a correlation of 0.97 was achieved between the diameter at breast height of the known simulated trees and the HARPER method. Furthermore, test cases were extracted from the airborne obtained point cloud of the recently updated Actual Height Model of the Netherlands, AHN2. On these test cases the estimated diameter with the HARPER method deviated less than a standard cylinder fitting method from manually measured diameters in the field. Still, the validation of a whole forest remains difficult, because not all trees of the forest are found back in the AHN2 point cloud. Such AHN2 point clouds will be available for the whole Netherlands in 2013 and other countries collect similar point clouds at this time. The wide availability of such point clouds in future underlines the relevance of this application.