Figure 14. Comparison of execution time: Tests of (a) group 1, (b) group 2, and (c) group 3.
there are some slight differences. Specifically, for a too small
voxel size, over-segmented objects appear as individual iso-
lated voxels. This is because within some voxels, there are too
few points, so that the geometric features cannot be estimated
reliably enough to judge about the connectivity of voxels.
Thus, they are normally regarded as outliers and finally
become segments consisting of merely one voxel. On the con-
trary, a too large voxel size will cause errors when segmenting
the local graph, because each voxel contains too many points
related to more than one structure or object, so that the points
inside carry relatively general geometric information, namely
all the voxels have similar attributes with no distinction.
Therefore, as nodes in the local graph, such large voxels will
naturally lead to an incorrect partition of the graph.
Comparison of Execution Time
Efficiency is also an important criterion for assessing the per-
formance of an algorithm. To thoroughly explore the efficien-
cy of the proposed strategy, we carry out a set of execution
time tests with different sizes of datasets. As the granularity
of elements (e.g., voxels, supervoxels, and neighborhoods
of normal vectors) can significantly influence the computa-
tional cost, in these experiments, we also compare results of
using different granularities of elements. In detail, there are
three groups of tests using a different granularity of voxels
and supervoxels. Here, the voxel sizes used in
LCCP
,
VGS
, and
SVGS
are set to 0.05 m, 0.1 m, and 0.2 m for different groups of
tests, equaling the radius of normal estimation in
RG
and the
radius of small normal estimation in
DON
. The seed resolution
of supervoxel in
LCCP
and
SVGS
as well as the radius of large
normal estimation in
DON
are set to 0.125 m, 0.25 m, and 0.5
m for different groups of tests, respectively. Comparisons of
the execution time are given in Figure 14. Here, the execu-
tion time contains all processing steps, including the time
required for creating the octree structure.
As demonstrated in Figure 14, point-based methods (i.e.,
RG
and
DON
) require a much longer execution time than the
voxel-based methods, regardless of the size of neighborhood
for normal vector estimation, voxels, and supervoxels. As for
the proposed methods, for small datasets, the execution time
of
VGS
is approximately the same as that of
SVGS
, but with in-
creasing size of datasets, the execution time of
SVGS
becomes
longer than that of
VGS
. This is mainly due to the calcula-
tion of element attributes. Although the use of supervoxels
reduces the number of elements, larger elements (i.e., super-
voxel) include more points, requiring a longer computation
time for calculating the attributes. Moreover, the generation of
supervoxels also consumes additional time. Besides, the pro-
posed methods are inferior to the
LCCP
method with respect to
efficiency. This is because of the time consumed by the graph-
based segmentation step, used in the proposed methods.
Comparing results of using a different granularity of ele-
ments, we can also find that voxel-based methods have an
advantage over the point-based baseline methods, namely
our methods show stable execution time when using varying
granularity. Specifically, the proposed methods and
LCCP
are
not sensitive to increasing voxel and supervoxel size. In con-
trast, the execution time of
RG
and
DON
methods grows drasti-
cally when utilizing a larger neighborhood for estimating
normal vectors. This is because for the point-based methods,
the estimation of normal vectors is applied to every point in
the dataset. The larger the neighborhood selected, the longer
time is needed, whereas for voxel-based methods, the estima-
tion of normal vectors is applied to elements (i.e., voxels and
supervoxels), and all the points inside the element share the
same normal vector. Larger elements will decrease the number
of calculated normal vectors. However, using larger voxel or
supervoxel sizes may also blur the details of segments, and re-
sult in zigzag edges of segments. Thus, finding the appropriate
granularity of voxel structures for voxel-based segmentation
methods requires a trade-off between accuracy and speed.
Conclusions
In this paper, we proposed a strategy for point cloud segmen-
tation, using voxel structure and graph-based clustering with
perceptual grouping laws, which allows a learning-free and
completely automatic but parametric method for segmenting
3D point clouds of manmade infrastructures. For fully inves-
tigating and exploring the potential of the proposed strategy,
experiments, comparisons, and evaluations using different
datasets and parameters were conducted. The evaluation has
demonstrated that the proposed methods can achieve a good
balance between effectiveness and efficiency. Experiments
also validate the superior performance of the proposed meth-
ods, especially for complex scenes and nonplanar surfaces of
objects. The use of multiple perceptual grouping laws pro-
vides a purely geometric solution for the segmentation task,
avoiding the use of color or intensity information of points,
which are normally limited by the data collection techniques
and lighting conditions. From experimental results and analy-
sis, several essential conclusions are drawn as follows:
The quantitative comparison between the proposed meth-
ods and other representative segmentation methods confirms
the effectiveness and efficiency of the proposed methods,
with overall F1-measure better than 0.66 even for the most
complex dataset (i.e., construction site). Especially for the test
in the construction site, the stereo matching errors existing in
our photogrammetric point cloud can be suppressed, and the
unevenly distributed point density in lidar point cloud can be
alleviated by the use of the voxel-based representation.
The selection of the optimized voxel and supervoxel sizes,
namely the granularity of the entire voxel and super struc-
tures, is crucial to the quality of final segments. In this work,
an investigation of the influence of using different voxel
sizes is conducted. Theoretically, the larger the voxels and
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
June 2018
389
