IEEE Geoscience and Remote Sensing Magazine - December 2020 - 44

uneven-density point clouds. Moreover, [141] extracted close
contours from a binary edge map for fast segmentation. Reference [142] introduced a parallel edge-based segmentation algorithm extracting three types of edges. An algorithm optimization mechanism, named Reconfigurable MultiRing Network,
was applied in this algorithm to reduce its runtime.
The edge-based algorithms, because they are so simple, enable a fast PCS. However, this performance can be maintained
only when simple scenes with ideal points are provided (e.g.,
low noise, even density). Some are suitable for range images
only rather than 3D points. Thus, this approach is now rarely
applied for dense or large-area point cloud data sets. Besides,
in 3D space, such methods often deliver disconnected edges,
which cannot be used to identify closed segments directly
without a filling or interpretation procedure [17], [143].
REGION GROWING
Region growing, a classical PCS method, is still widely used. It
combines features from two points or two region units to measure the similarities among pixels (2D), points (3D), or voxels
(3D) and merges them if they are spatially close and have similar surface properties. Besl and Jain [144] introduced a two-step
initial algorithm: 1) coarse segmentation, in which seed pixels
are selected based on the mean and Gaussian curvature of each
point and its sign; and 2) region growing, in which interactive
region growing is used to refine the result of coarse segmentation based on a variable-order, bivariate surface fitting. Initially,
this method was primarily used in 2D segmentation. As in the
early stage of PCS research, most point clouds were actually
2.5D airborne lidar data, in which only one layer has a view in
the z direction and the general preprocessing step was to transform points from 3D space into a 2D raster domain [145]. With
the more easily available real 3D point clouds, region growing
was soon adopted directly in 3D space. This 3D region-growing technique has been widely applied in the segmentation of
building plane structures [75], [93], [94], [101], [104].
Similar to the 2D case, 3D region growing comprises two
steps: 1) selecting seed points or seed units; and 2) region
growing, driven by certain principles. To design a region-growing algorithm, three crucial factors should be considered: criteria (similarity measures), growth unit, and seed point selection. For the criteria factor, geometric features, e.g., Euclidean
distance or normal vectors, are commonly used. For example,
Ning et al. [106] employed the normal vector as the criterion,
so that the coplanar may share the same normal orientation.
Tovari et al. [146] applied normal vectors, the distance of the
neighboring points to the adjusting plane, and the distance between the current point and candidate points as the criteria for
merging a point to a seed region randomly picked from the
data set after manually filtering areas near edges. Dong et al.
[104] chose normal vectors and the distance between two units.
For the growth unit factor, one of three strategies is commonly applied. The first involves single points; the second
uses region units, e.g., voxel grids and octree structures; and the
third is based on hybrid units. Selecting single points as region
units was the main approach in the early stages [106], [138].
44

However, for massive point clouds, pointwise calculation is
time consuming. To reduce the data volume of the raw point
cloud and improve calculation efficiency, e.g., neighborhood
search with a k-d tree in raw data [147], the region unit is an alternative idea of direct points in 3D region growing. In a point
cloud scene, the number of voxelized units is smaller than the
number of points. In this way, the region-growing process can
be accelerated significantly. Guided by this strategy, Deschaud
et al. [147] presented a voxel-based region-growing algorithm
to improve efficiency by replacing points with voxels during the region-growing procedure. Vo et al. [93] proposed an
adaptive octree-based region-growing algorithm for fast surface patch segmentation by incrementally grouping adjacent
voxels with a similar saliency feature. In efforts to balance accuracy and efficiency, researchers proposed and tested hybrid
units. For example, Xiao et al. [101] combined single points
with subwindows as growth units to detect planes. Dong et al.
[104] used a hybrid region-growing algorithm based on units
of both single points and supervoxels to realize coarse segmentation before global energy optimization.
Since many region-growing algorithms aim at plane segmentation, the usual practice in seed point selection is to design a fitting plane for a certain point and its neighbor points
first and then choose the point with minimum residual to the
fitting plane as a seed point [106], [138]. The residual is usually estimated by the distance between one point and its fitting
plane [106], [138] or the curvature of the point [94], [104].
Nonuniversality is a significant problem for region growing
[93]. The accuracy of these algorithms depends on the growth
criteria and locations of the seeds, which should be predefined
and adjusted for different data sets. In addition, these algorithms
are computationally intensive and may require a reduction in
data volume for a tradeoff between accuracy and efficiency.
MODEL FITTING
The core idea of model fitting is matching the point clouds to
different primitive geometric shapes. Thus, model fitting has
been normally regarded as a shape-detection or -extraction
method. However, when dealing with scenes having parameter geometric shapes/models, e.g., planes, spheres, and cylinders, model fitting can also be regarded as a segmentation approach. Most widely used model-fitting methods are built on
two classical algorithms: Hough Transform (HT) and Random
Sample Consensus (RANSAC).
HT
HT is a classical feature-detection technique in digital image processing. It was initially presented in [148] for line detection in
2D images. The HT technique involves three main steps [149]:
1) mapping every sample (e.g., pixels in 2D images and points
in point clouds) of the original space into a discretized parameter space
2) laying an accumulator with a cell array on the parameter
space and then, for each input sample, casting a vote for
the basic geometric element representing the inliers in the
parameter space
IEEE GEOSCIENCE AND REMOTE SENSING MAGAZINE

DECEMBER 2020

IEEE Geoscience and Remote Sensing Magazine - December 2020

Table of Contents for the Digital Edition of IEEE Geoscience and Remote Sensing Magazine - December 2020