  Over-segmentation, or super-pixel generation, is a common preliminary stage
for many computer vision applications. New acquisition technologies enable the
capturing of 3D point clouds that contain color and geometrical information.
This 3D information introduces a new conceptual change that can be utilized to
improve the results of over-segmentation, which uses mainly color information,
and to generate clusters of points we call super-points. We consider a variety
of possible 3D extensions of the Local Variation (LV) graph based
over-segmentation algorithms, and compare them thoroughly. We consider
different alternatives for constructing the connectivity graph, for assigning
the edge weights, and for defining the merge criterion, which must now account
for the geometric information and not only color. Following this evaluation, we
derive a new generic algorithm for over-segmentation of 3D point clouds. We
call this new algorithm Point Cloud Local Variation (PCLV). The advantages of
the new over-segmentation algorithm are demonstrated on both outdoor and
cluttered indoor scenes. Performance analysis of the proposed approach compared
to state-of-the-art 2D and 3D over-segmentation algorithms shows significant
improvement according to the common performance measures.
