ometry 
ccurate 
ometry 
orough 
ms in 
jay be 
of the 
widely 
iood of 
01S, or 
ylinder 
of the 
radius 
| to the 
timally 
orhood 
ns like 
(2004). 
yptimal 
Nguyen 
(2005) 
= et. al. 
lection 
d Suter 
ne the 
cation. 
local 
tion as 
study, 
)ptimal 
point's 
means 
ie local 
; West 
2007; 
et al, 
| while 
feature 
nearest 
atrix C 
joint p 
ith the 
(1) 
Q) 
ariance 
tect the 
yws the 
nber of 
nearest neighbors for a sample point. The neighborhood is fixed 
to the number of nearest neighbors just before the jump in 
surface variation occurs. 
  
0.2 
0.18 1 
eel f ved 
I 
/ | 
reed 1 1 1 1 1 
0 5 10 15 20 25 30 35 40 45 50 
n 
Surface Variation 
QU ooo o 
DOWD se 
RR = e © - sv 
TEE 
o 
T 
  
  
  
Figure 1. Change of surface variation with neighborhood size 
3. POINT LABELING 
3.1. Segmentation as a labeling problem 
Segmentation may be considered as a labeling problem. The 
labeling problem is concerned with assigning a label from a set 
L of labels to each of the sites in a set $ of sites. The goal is to 
find a labeling f — (fj, fm } by assigning each site in 5 a 
label from the label set £ which minimizes an objective 
function E(f) (Delong et. al., 2010). 
The objective function maps a solution to a measure of quality 
by means of goodness or cost (Li, 2009). When the 
segmentation is considered as such an optimization problem, 
identifying the lowest cost for a discrete labeling f gives the 
optimum segmentation based on the objective function that 
formulates the criteria for a good labeling. A natural 
representation of such labeling problems is with an energy 
function having two terms (Szeliski et. al., 2008). A common 
structure used for the energy function to solve this type of 
problems can be typically written as 
E(f) = Eaata (f) + Eprior (f) (3) 
where 
Eqata(f) = Zi D(fi), Eprior (f) = X Vi (fi, fi) (4) 
The first term of the function penalizes for inconsistency with 
the data while the second term ensures that the labels f; and f; 
are compatible. Data term is the sum of data costs measuring 
how well the labeling fits the site given the observations. Eprior 
is also commonly referred to as the smoothness energy. 
(Boykov et. al., 2001). Smoothness may be dependent on the 
specific pair of neighbors as well as the particular labels 
assigned to them (Veksler, 1999). 
3.2. Graph-cuts 
Most of the time, energy functions of the above form have 
many local minima. There is no algorithm that can find the 
global minimum of an arbitrary energy function without the 
exhaustive enumeration of the search space. Finding the global 
minimum of an arbitrary energy function is intractable 
(Felzenswalb and Zabih, 2011; Veksler, 1999). Graph cuts, 
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 
which may be geometrically interpreted as a hypersurface on 
N-D space, work as a powerful energy minimization tool for a 
class of energy functions and they are used as an optimization 
method in many vision problems based on global energy 
formulations (Boykov and Veksler, 2006). Graph-cut based 
methods gained popularity in pixel labeling problems in images 
and helped increasing the computational efficiency of solutions 
based on energy minimization framework for such problems. 
Before graph-cuts and similarly effective loopy belief 
propagation (LBP) algorithms, elegant and powerful 
representation of labeling problem in terms of energy 
minimization was limited by computational inefficiency 
(Szeliski et al., 2008). 
A graph G — (V(G), £(g), i5 (.)) is a pair of sets V(G) and £(g) 
and an incidence relation tç(.) that maps pairs of elements 
of V(G), to elements of £(g). The elements of V(G) are called 
vertices or nodes, and the elements of £(g) are called the edges 
of the graph G (Kropatsch et. al, 2007). Considering two 
special nodes, source (s) and sink (t) on a directed graph, the 
“minimum-cut problem" is to find a cut with minimum cost on 
the graph that will separate the graph into two subsets such that 
s is in one subset and t is in the other subset (Figure 2). The cost 
of a cut is the sum of all the weights of the graph edges with 
one node in one subset, and the other node in the other subset. 
Ford and Fulkerson (1962) show that considering the edge 
weights as capacities, finding the “maximum flow” from s tot 
on the same graph is equivalent to finding the “minimum cut” 
since a maximum flow will saturate a set of edges which will 
separate the graph into two disjoint parts. 
     
source 
Figure 2. Minimum-cut on a graph (reproduced from Boykov 
and Veksler, 2006) 
There are numerous algorithms for solving low-level vision 
problems that find minimum cuts on an appropriately defined 
graph. Each of these algorithms has specific requirements and 
conditions regarding the types of energy functions they can 
minimize or the number of labels they can handle 
simultaneously. Some algorithms compute optimal solutions 
under certain conditions. 
In this study, we adapt the fast approximate energy 
minimization algorithm introduced by Boykov et. al. (2001) via 
graph cuts and employ it for the labeling of point clouds. Their 
method finds a local minimum with respect to very large moves 
they define as a-expansion and a-f-swap which allow a large 
number of sites to change their labels simultaneously in 
contrast to standard moves which allow to change the label of 
one site at a time. They prove that the local minimum they find 
using a-expansion is within a known factor of the global 
minimum.