of structural components, for example, planar segments cor-
responding to wall surfaces, frame structures representing
windows in the facade, and curved surfaces denoting the roof
facet of a building. Our strategy combines the voxel structure
and graph-based clustering using the perceptual grouping
laws. The voxel structure is designed for suppressing nega-
tive influences of outliers and unevenly distributed densi-
ties. We adopt the octree-based voxelization to organize the
point cloud, facilitating the traversing of neighborhoods and
improving the efficiency of processing as well. Graph-based
clustering is applied to aggregate voxels into complete seg-
ments. The connectivity relations between voxels are identi-
fied via the partition of a graphical model encapsulating local
information about a voxel’s neighborhood, which suppresses
the negative influence caused by the voxelization process
discretizing the 3D space. In the graph model, perceptual
grouping laws, which are also termed as gestalt principles, are
adopted to encode weights of graph edges.
Based on this strategy, we present two different seg-
mentation methods, namely a method termed as voxel and
graph-based segmentation (
VGS
) and the other one referred
to as supervoxel and graph-based segmentation (
SVGS
). Both
methods have been initially reported in our prior work (Xu
et al.
, 2017a). Our experiments are conducted using various
datasets, namely laser scanning and photogrammetric point
clouds representing the same scene. Particularly, influential
factors such as the granularity of voxelization and the thresh-
old for graph-based segmentation are fully investigated, with
corresponding results analyzed and discussed.
Related Work
Generally, popular point cloud segmentation approaches
can be grouped into three major categories (Vo
et al.
, 2015):
model-based, region growing-based, and clustering-based
methods.
Model-based methods examine points by their spatial posi-
tions and normal vectors at a local or global scale according to
a parametric model. Parametric models are fitted to points in
the spatial or parametric domain, and the inliers are extracted
from the entire point cloud as one individual segment. In this
category, 3D Hough Transform (
HT
) (Ballard, 1981) and
RANSAC
(Schnabel
et al.
, 2007) are two kinds of typical algorithms
(Vosselman, 2013). The
HT
and its variations build upon a
voting strategy and extract planes (Vosselman
et al.
, 2004),
cylinders and spheres (Rabbani
et al.
, 2006) from the point
cloud in the parameter domain. In contrast,
RANSAC
and its
extensions directly optimize parameters of geometric models
with an iteration process in the spatial domain (Schnabel
et al.
, 2007). Generally, model-based methods are regarded
as robust to noise and outliers (Nurunnabi
et al.
, 2015) and
can simultaneously yield optimized parameters for surface
modeling. However, when processing large-scale datasets, they
normally suffer from high computational cost resulting from
the iteration process of robust estimators or the voting proce-
dure (Vo
et al.
, 2015), the latter leading to excessive memory
consumption if a raster representation of high-dimensional
feature spaces is used. Additionally, segmenting objects with
no simple parametric representation, such as, irregular curved
surfaces, is also challenging. Region growing-based methods
repetitively evaluate points in the vicinity of initial seeds, and
check if they belong to the group of the seed according to giv-
en criteria. Growing criteria and the selection of seeds are two
influential factors impacting the quality of results. Coherence
between normal vectors (Tóvári and Pfeifer, 2005), smoothness
of surfaces (Rabbani
et al.
, 2006), and curvatures (Besl and
Jain, 1988) of points are popular growing criteria. Geometric
features extracted using Principal Component Analysis (
PCA
)
or local shape descriptors are also introduced as growing cri-
teria owning to their distinctiveness (Nurunnabi
et al.
, 2016).
For the selection of seeds, the density of seeds determines the
granularity of segments, while the position and distribution of
seeds significantly affect the correctness of segments. Points
with the smallest curvature (Nurunnabi
et al.
, 2012) or the
surface with the minimal residual from plane fitting (Rabbani
et al.
, 2006) are usually selected as seeds, because in this way,
no seed points will be generated near segment boundaries
and surface discontinuities. Region growing-based methods
can preserve the boundaries of surfaces well, but they are
easily influenced by noise and outliers. For instance, over-
segmentation can easily occur for objects with large curvatures
(e.g., pipes with a long radius elbow joint), despite the fact
that these surfaces are smoothly connected (Su
et al.
, 2016).
Spilling, i.e., under-segmentation occurs due to poor local
contrast at a small part of the object boundaries, is also a major
disadvantage of region growing. Clustering-based methods
consider neighboring points in a defined neighborhood by
their consistency in the attribute or spatial domain according
to geometric characteristics and spatial coordinates. Points
having characteristics in common are aggregated into one clus-
ter. Euclidean distance (Aldoma
et al.
, 2012), density (Lu
et
al.
, 2016; Aljumaily
et al.
, 2017), and normal vector deviation
(Vo
et al.
, 2015) are representative criteria used for clustering.
With respect to clustering algorithms, k-means (Morsdorf
et
al.
, 2003), mean-shift (Yao
et al.
, 2009), and analysis of local
configurations (Stein
et al.
, 2014) are used most frequently.
In contrast to region growing-based methods, the clustering-
based ones require no selection of seeds. Besides, the compu-
tational cost of clustering-based methods lies in the compu-
tational complexity of estimating the homogeneity between
points. Complex clustering criteria will greatly increase the
computational cost. Moreover, clustering thresholds also have
an influence on the granularity of the obtained segments.
The clustering of points can also be formulated as a graph
construction and partitioning problem. A graphical model
explicitly organizes elements (e.g., pixels or points) with a
mathematically sound structure (Peng
et al.
, 2013), encoding
the contextual information for deducing hidden information
from given observations. In recent work, graph-based ap-
proaches are frequently applied, such as Min Cuts (Golovin-
skiy and Funkhouser, 2009), Graph segmentation (Green and
Grobler, 2015) and Markov-based approaches like Markov
Random Field (MRF) (Hackel
et al.
, 2016), Conditional Ran-
dom Field (
CRF
) (Rusu
et al.
, 2009), or global energy model
(Landrieu and Simonovsky, 2017). With regard to graph-based
methods, a large topology radius of constructed graphs usu-
ally gives better results in segmentation, but it yields a higher
computational cost simultaneously (Cour
et al.
, 2005).
The use of pre-clustered patches in the segmentation has
attracted increasing attention recently. Instead of using points,
super points (i.e., sets of points) (Landrieu and Simonovsky,
2017), 3D regular cubes (Wang and Tseng, 2011, Truong-Hong
et al.
, 2013, Boerner
et al.
, 2017, Wang
et al.
, 2017), slices
(Zolanvari and Laefer, 2016), and planar facets (Vosselman
et al.
, 2017, Lin
et al.
, 2017) are used as basic elements. The
octree-structured voxelization is one of the most commonly
used strategy. In (Vo
et al.
, 2015), an octree structure and
region growing are integrated for fast building facade segmen-
tation. Similarly, an octree-based voxel structure combined
with graph-based sub-splitting is applied to segment cylindri-
cal objects in industrial scenes (Su
et al.
, 2016). Using voxel
structures instead of the original point cloud apparently
reduces the computation cost and can overcome outliers and
varying point densities to some extent. Nevertheless, select-
ing an appropriate voxel resolution is a crucial problem for
ensuring the accuracy of segments and preservation of details.
378
June 2018
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
