„CD, 9 
Random 
(2), pp. 
ditional 
labeling 
nce on 
Lidar 
ditional 
1-710. 
y BFGS 
matical 
F. and 
n scene 
à. + «In: 
otes in 
erg, pp. 
ction of 
ata. In: 
Sensing 
4/W 19, 
abilistic 
midi 
). Non- 
fication. 
1-PCV 
Remote 
ISPRS, 
für die 
) 
ractical 
Morgan 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B3, 2012 
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia 
MIN-CUT BASED SEGMENTATION OF AIRBORNE LIDAR POINT CLOUDS 
Serkan Ural, Jie Shan 
School of Civil Engineering, Purdue University, West Lafayette, IN, U.S.A.- 
(sural, jshan)@ecn.purdue.edu 
Commission III, WG IIU2 
KEY WORDS: LIDAR, point clouds, segmentation, eigenvalue analysis, graph-cuts, min-cut 
ABSTRACT: 
Introducing an organization to the unstructured point cloud before extracting information from airborne lidar data is common in 
many applications. Aggregating the points with similar features into segments in 3-D which comply with the nature of actual objects 
is affected by the neighborhood, scale, features and noise among other aspects. In this study, we present a min-cut based method for 
segmenting the point cloud. We first assess the neighborhood of each point in 3-D by investigating the local geometric and statistical 
properties of the candidates. Neighborhood selection is essential since point features are calculated within their local neighborhood. 
Following neighborhood determination, we calculate point features and determine the clusters in the feature space. We adapt a graph 
representation from image processing which is especially used in pixel labeling problems and establish it for the unstructured 3-D 
point clouds. The edges of the graph that are connecting the points with each other and nodes representing feature clusters hold the 
smoothness costs in the spatial domain and data costs in the feature domain. Smoothness costs ensure spatial coherence, while data 
costs control the consistency with the representative feature clusters. This graph representation formalizes the segmentation task as 
an energy minimization problem. It allows the implementation of an approximate solution by min-cuts for a global minimum of this 
NP hard minimization problem in low order polynomial time. We test our method with airborne lidar point cloud acquired with 
maximum planned post spacing of 1.4 m and a vertical accuracy 10.5 cm as RMSE. We present the effects of neighborhood and 
feature determination in the segmentation results and assess the accuracy and efficiency of the implemented min-cut algorithm as 
well as its sensitivity to the parameters of the smoothness and data cost functions. We find that smoothness cost that only considers 
simple distance parameter does not strongly conform to the natural structure of the points. Including shape information within the 
energy function by assigning costs based on the local properties may help to achieve a better representation for segmentation. 
1. INTRODUCTION 
1.1. Motivation 
Lidar (light detection and ranging) is considered as one of the 
most important data acquisition technologies introduced for 
geospatial data acquisition lately (Petrie and Toth, 2009) and is 
progressively utilized for remote sensing of the Earth. This 
rapidly advancing technology quickly attracted interest for a 
variety of applications due to the dense point coverage (Filin 
and Pfeifer 2005). Pulse repetition rates, hence point densities 
have been increasing with new sensors and data acquisition 
techniques. However, the requirements of most applications go 
beyond the raw point locations. 
Applications usually require extensive processing of point 
cloud for extracting information on the features of interest to 
derive the final product (Biosca and Lerma, 2008; Vosselman et 
al., 2004). Analysis options with a set of unstructured 3D points 
are limited (Biosca and Lerma, 2008). Apart from the fact that 
the point data are noisy and not perfectly sampled, lidar 
acquisitions may also have poor sampling for almost vertical 
scans (Golovinsky and Funkhouser, 2009). The assumption of 
smooth surfaces and homogeneity does not perfectly hold for 
airborne lidar data as well as outdoor terrestrial and mobile 
acquisitions or their combinations. 
For effective extraction of required information from the 
unstructured 3D point cloud some level of organization is 
usually employed (Filin and Pfeifer, 2005). Such organization 
is usually achieved by labeling each point in the point cloud in 
a way that the points which are part of the same surface or 
region are labeled the same (Rabbani et al, 2006). Image 
segmentation methods have naturally been adapted to process 
2.5-D lidar range images. Convenience of implementing well 
studied algorithms established for image segmentation allowed 
lidar analysts and researchers to develop very useful methods 
and techniques for lidar range image analysis. However, 
analyzing lidar data as range images limits the possibilities of 
fully exploiting the 3-D nature of the lidar acquisition 
technology. We focus our efforts for the segmentation of point 
clouds following the track of algorithms which deal with 3-D 
point coordinates instead of 2.5-D range images. 
In a good segmentation, segments are expected to be in 
accordance with the actual objects. Several aspects of point 
cloud segmentation are of fundamental importance to achieve 
such conformance. These include to local neighborhood of the 
points, scale, and features that represent the properties of a 
point's local neighborhood. 
In this study, we adapt a graph representation from image 
processing which is used in pixel labeling problems and 
configure it for the unstructured point clouds. Particularly, we 
implement a min-cut based method of Boykov et. al. (2001) for 
the segmentation of the point cloud. We first determine a local 
neighborhood for each point by detecting the jumps in the 
change of surface variation as the neighborhood gets larger. 
Following neighborhood determination, we calculate point 
features that help to identify whether the point is from a 2-D or 
3-D manifold. Then we perform a segmentation of the point 
cloud with a min-cut algorithm using this feature vector and 
model the surface and scattered points. Once the data models 
are established for surface and scattered points, we label each 
point either as surface or scatter with the graph-cut optimization 
algorithm. We form a second feature vector and carry out a 
segmentation of the points labeled as surface.