This functions is meant to be used internally by methods of the
segment_tree_crowns generic.
segment_tree_crowns_core(
coordinate_table,
segment_crowns_only_above,
ground_height,
crown_diameter_to_tree_height,
crown_length_to_tree_height,
crown_diameter_constant,
crown_length_constant,
verbose,
centroid_convergence_distance,
max_iterations_per_point,
dbscan_neighborhood_radius,
min_num_points_per_crown,
also_return_terminal_centroids,
also_return_all_centroids
)A list with at most three elements:
A vector of IDs of segmented bodies.
If also_return_terminal_centroids was set to TRUE, a
data.table with mode coordinates as the
second list element.
The table has two additional columns:
Holds the IDs also returned with the first list element.
Holds row indices of the original points in the input
coordinate_table.
If also_return_all_centroids was set to TRUE, a
data.table with centroid coordinates as the
last list element.
The table has two additional columns:
Holds the IDs also returned with the first list element.
Holds row indices of the original points in the input
coordinate_table.
A data.frame or
data.table
which is a valid coordinate table according to validate_coordinate_table.
A single positive number denoting the minimum height above ground at which crown IDs will be calculated.
Note that points directly below this threshold will still be considered
during the segmentation if they are within reach of search kernels
constructed at the segment_crowns_only_above height. See "How the
algorithm works" to learn about the search kernels.
One of
NULL, indicating that the point cloud stored in
coordinate_table is normalized with ground height at zero.
A SpatRaster providing ground heights for
the area of the (not normalized) point cloud stored in
coordinate_table.
Single number or
SpatRasters covering the area of the point_cloud.
The diameter of the search kernel will be calculated by multiplying this
value and the height above ground of the kernel center, and adding the
crown_diameter_constant. For details see "How the algorithm works". Points
will not be segmented wherever a raster contains NA values.
Single number or
SpatRasters covering the area of the point_cloud.
The height of the search kernel will be calculated by multiplying this
value and the height above ground of the kernel center, and adding the
crown_length_constant. For details see "How the algorithm works". Points
will not be segmented wherever a raster contains NA values.
Single number >=0. Used to determine the dimensions of the search kernel, together with the respective ratios to tree height. For details see "How the algorithm works".
TRUE or FALSE. Should the function show a progress bar and
other runtime information in the console?
A single number. Distance at which it is assumed that subsequently calculated centroids have converged to the nearest mode. See "How the algorithm works" to learn about centroids and modes in the context of the AMS3D algorithm.
A single integer. Maximum number of centroids calculated before the search for the nearest mode stops. See "How the algorithm works" to learn about centroids and modes in the context of the AMS3D algorithm.
A single number. Radius for the spherical DBSCAN neighborhood around a mode. See "How the algorithm works" to learn about neighborhoods in the context of the DBSCAN algorithm.
A single integer. The minimum number of converged centroids within a DBSCAN neighborhood at which the centroid in the neighborhood's center will be treated as a core point. See "How the algorithm works" to learn about neighborhoods and core points in the context of the DBSCANb algorithm.
TRUE or FALSE. Should mode coordinates be
returned as well?
TRUE or FALSE. Should all centroid coordinates
be returned as well? This slows down processing by a little bit and will
return a data set which requires at least ~10 times more memory than the
input point cloud.
The basic assumption is that tree crowns form local maxima of point density and height within lidar point clouds. These local maxima are called modes. The algorithm tries to find the nearest mode for each point. This is done by looking at the surrounding points and moving into the direction of the highest point density until the nearest mode is (almost) reached.
The surrounding points are found with a search kernel (a three-dimensional
search window) which has the shape of a vertical cylinder. According to
literature, the algorithm works best if the search kernel has roughly the
size of the surrounding crowns. Therefore, the parameters controlling the
kernels dimension are simplistically called
crown_diameter_to_tree_height, crown_diameter_constant, and
crown_lenght... respectively. The diameter of the kernel is calculated
from the height above ground of the kernels center times the value for
crown_diameter_to_tree_height, plus the crown_diameter constant. The
height of the kernel is calculated respectively.
The direction of the highest point density is found by calculating the
average position of all points within the cylinder, the cylinder's so
called centroid. In order to move further into the direction of the
highest point density, a new cylinder is placed on the centroid and a new
centroid is calculated for that cylinder. This continues on until the
cylinders "stop moving", i.e. until two subsequently calculated centroids
are closer to each other than centroid_convergence_distance. At this
point, the most recently calculated centroid, hence called 'terminal
centroid', is assumed to be close enough to the mode, so that the
original point can be linked to the respective tree top.
It sometimes happens that centroids converge only after a lot of
iterations. In order to prevent situations where an excessive number of
centroids is calculated for just one point, the parameter
max_iterations_per_point is used to stop the centroid
calculations after a certain number of them has been performed.
Nonetheless, the last centroid found before stopping is still taken as
a good enough guess of the nearest mode's position.
After the terminal centroids of the individual points have been calculated, it can be seen that terminal centroids of points belonging to the same tree crown are positioned very close to each other, shortly below the crown's apex. These dense clusters of terminal centroids are identified with the DBSCAN algorithm which assigns a cluster ID to every one of them. The cluster IDs are then finally connected back to the points of the point cloud and used as crown IDs.
The DBSCAN clustering is explained nicely in Wikipedia but here is a quick sketch of what it does: The DBSCAN algorithm classifies points as either core points, border points, or noise and assigns core and border points to the same cluster if they are close enough to at least one other core point of the cluster.
In order to be core points, points need to have enough neighbors. The
parameter dbscan_neighborhood_radius determines the radius of the
neighborhood and the parameter min_num_points_per_crown
determines the minimum number of points in the neighborhood (including the
to-be-classified one), which are needed for a core point.
Border points are within the neighborhood of core points but don't have enough neighbors to be core points themselves. Noise points are not within the neighborhood of any core point and also don't have enough neighbors to be core points.
Clusters are identified by iterating over the points and classifying them one by one. For each point the neighborhood is scanned and the point is classified accordingly. If the point is a core or border point, the neighboring points are classified next. As long as it is possible to directly connect to new core or border points in this way, the same cluster ID is assigned to each encountered point.