To solve this problem, the supervoxel strategy is introduced
and applied to the basic voxel structure, better preserving
the boundary features of segments and further improving the
computation efficiency (Stein
et al.
, 2014, Pham
et al.
, 2016a,
Ramiya
et al.
, 2016, Xu
et al.
, 2016). However, supervoxels
are merely an over-segmentation of points that need to be
further clustered into complete segments.
Contribution of the Paper
Based on our prior work (Xu
et al.
, 2017a), in this paper, the
emphasis is to carry out both qualitative and quantitative
experiments, in order to further investigate the performance
of the proposed strategy and compare the methods with the
state-of-the-art algorithms. The main contribution of this
paper are: (a) A bottom-up point cloud segmentation strategy,
combing the voxel structure and the graph-based clustering
procedures which encapsulates local contextual information.
Two novel segmentation methods (i.e.,
VGS
and
SVGS
) real-
izing this strategy are presented and shown to be effective as
well as efficient for 3D scene segmentation; (b) The adoption
of perceptual grouping laws for estimating geometric cues in
order to identify the connections between basic elements (i.e.,
voxels or supervoxels, enabling a purely geometric and un-
supervised solution for segmentation; (c) In thorough experi-
ments using both laser scanned and photogrammetric point
clouds of the same 3D scene, the performance of the proposed
methods dealing with datasets from different sources is ana-
lyzed. Influence factors of the granularity of voxelization and
the selection of thresholds and parameters are investigated
and analyzed.
Overview of the Strategy
The implementation of the proposed segmentation strategy
consists of three core steps: (i) the voxelization of the point
cloud, (ii) the calculation of geometric cues, and (iii) the
graph-based clustering. In the first step, the entire point cloud
is voxelized into a 3D grid. For the
VGS
method, voxels are
basic elements for segmentation. In contrast, for the
SVGS
method, voxels are further clustered into supervoxels char-
acterized by geometric and spatial consistency, which serve
as segmentation primitives. In the second step, for estimating
geometric cues of basic elements (i.e., voxels or supervoxels),
attributes of each element are calculated according to geo-
metric information of its constituent points. Geometric cues
reflect the relation of two adjacent basic elements, namely
they indicate whether two structural patches should be
connected or not. Three representative principles of the
perceptual grouping laws are selected as clustering criteria:
proximity, similarity, and continuity. Perceptual grouping
laws have a long history of use in the field of computer vision
for recognizing objects in a scene, namely for the determina-
tion of regions of the visual scene belonging to the same part
of higher level perceptual elements (Richtsfeld
et al.
, 2014).
The proximity principle states that elements are likely to be
categorized into the same group if they are close to each other,
whereas the similarity principle claims that elements tend to
be aggregated into a group when they resemble each other.
The continuity principle indicates that oriented elements
are considered to be integrated into one part in case that
they can be aligned with each other. In the last step, based
on the geometric cues, the homogeneity of basic elements is
assessed and used for weighting edges in graphical models.
Graph-based clustering is conducted to merge basic ele-
ments according to the edge weights in the graphical model
in a greedy process. A separate graph is constructed for each
basic element considering only adjacent elements. This graph
encodes the contextual information. By applying the graph
segmentation algorithm, the connectivity of each element to
its neighbors can be estimated. Then, all the connected ele-
ments can be aggregated into complete segments by a simple
clustering. A comparison between processing workflows of
VGS
and
SVGS
methods is given in Figure 2, with key steps and
sample results illustrated. Detailed explanations on
VGS
and
SVGS
methods are provided in the following sections.
VGS
: Voxeland Graph-Based Segmentation
The
VGS
method is the basic solution implementing the pro-
posed strategy, adopting voxels as basic elements and fully con-
nected local graphs for identifying connections of voxels, which
has been initially reported in our recent work (Xu
et al.
, 2017b)
Voxelization of Point Cloud
In this step, we use the octree-based voxelization to discretize
the entire point cloud with 3D voxels. The advantages of
using the octree-based voxel structure are as follows (Vo
et
al.
, 2015): (a) It allows indexing the unorganized point cloud
with octree structure, (b) it simplifies the dataset and sup-
presses the outliers and uneven density of point clouds with
Figure 2. Comparison of workflows of two voxeland graph-based segmentation methods.
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
June 2018
379
