IEEE Geoscience and Remote Sensing Magazine - December 2020 - 46

share a similar aim: grouping points with similar geometric features, spectral features, or spatial distribution into the same homogeneous pattern. Unlike region growing and model fitting,
these patterns usually are not defined in advance [166], and thus
clustering-based algorithms can be employed for irregular object
segmentation, e.g., vegetation. Moreover, in contrast to regiongrowing methods [109], seed points are not required by clustering-based approaches. Early on, K-means [45], [46], [76], [77],
[91], mean shift [47], [48], [80], [92], and fuzzy clustering [77],
[105] were the main algorithms in the clustering-based point
cloud segmentation family. For each clustering approach, several
similarity measures with different features can be selected, including Euclidean distance, density, and normal vector [109]. From
the perspective of mathematics and statistics, the clustering problem can be regarded as a graph-based optimization problem, so
several graph-based methods have been tried in experiments involving PCS [78], [79], [167].

research objectives (Figure 2). The figure, originally described in
[159], uses seven subclasses based on strategies. Venn diagrams
are used here to describe connections between methods and
strategies, since a method may use two strategies. For detailed
descriptions and explanations of those strategies, see [159]. Considering that [159] is obsolete, we added two recently published
methods, Extreme Value Sample Consensus [164] and GraphCut RANSAC [165], to the original figure to bring it up to date.
UNSUPERVISED CLUSTERING BASED
Clustering-based methods are widely used for unsupervised
PCS tasks. Strictly speaking, clustering-based methods are not
grounded in a specific mathematical theory. This methodology family is made up of a mixture of different methods that

K-MEANS
K-means is a basic and widely used unsupervised cluster analysis
algorithm. It separates the point cloud data set into K unlabeled
classes. The clustering centers of K-means are different from the
seed points of region growing. In K-means, every point should be
compared to every cluster center in each iteration step, and the
cluster centers change when absorbing a new point. The process
FIGURE 1. The black dots represent points in a point cloud. Two
of K-means is " clustering " rather than " growing. " It has been adwell-estimated hypothesis planes are indicated by the blue lines runopted for single tree crown segmentation on ALS data [91] and
ning through the blue squares. A spurious plane (dotted orange line)
planar structure extraction from roofs [76]. Shahzad et al. [45]
is generated using the same threshold [102]. (Reprinted from [102].)
and Zhu et  al. [46] used K-means for
building façade segmentation on TomoSAR point clouds.
Fast
Robust
K-means can be easily adapted to
RANSAC With Boil-Out Test
all kinds of feature attributes and can
Feng and Hung MAPSAC
R-RANSAC With SPRT
even be used in a multidimensional
feature space. The main drawback of
R-RANSAC With Td,d Test Adaptive Termination
K-means is that it is sometimes difficult
uMLESAC
Progressive RANSAC
AMLESAC
to predefine the value of K properly.
Adaptive Evaluation
Partial Evaluation

RANSAC

EVSAC PROSAC
NAPSAC GASAC
Guided MLESAC
Guided Sampling

MLESAC

pbM Estimator
GC-RANSAC
LO-RANSAC
Local Optimization

MAPSAC

MSAC
Loss Function

QDEGSAC
Model Selection
Accurate

FIGURE 2. The RANSAC family, with algorithms categorized according to their performance
and basic strategies [159], [164], [165]. SPRT: sequential probability ratio test; R-RANSAC:
randomized-RANSAC; MAPSAC: maximum a posterior estimation sample consensus; pbM:
projection-based M-estimator; EVSAC: extreme value sample consensus; GC-RANSAC: graphcut RANSAC; PROSAC: progressive sample consensus; NAPSAC: N adjacent points sample
consensus; GASAC: genetic algorithm sample consensus; MLESAC: maximum likelihood estimation sample consensus; AMLESAC: a new MLESAC; uMLESAC: user-independent MLESAC;
MSAC: M-estimator SAC; QDEGSAC: RANSAC for quasi-degenerate data; LO-RANSAC: locally
optimized RANSAC. (Used with permission from [159].)

46

FUZZY CLUSTERING
Fuzzy-clustering algorithms are improved versions of K-means. K-means is
a hard clustering method, which means
the weight of a sample point to a cluster
center is either 1 or 0. In contrast, fuzzy
methods use soft clustering, meaning a
sample point can belong to several clusters with certain nonzero weights.
In PCS, a no-initialization framework was proposed in [105] by combining two fuzzy algorithms, the fuzzy
C-means algorithm and the possibilistic C-means algorithm. This framework was tested on three point clouds
including a one-scan TLS outdoor data
set with building structures. Those experiments showed that fuzzy--clustering

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
