Jn) 
7 / 
HN 
HE 
AA 
  
he classes 
illustrated 
n 
| points in 
given the 
model. A 
ribution in 
ns out of 
(C|x) can 
2, 6j) |, 
(1) 
1 constant. 
)babilities. 
ssociation 
i» Cj) over 
  
the neighbourhood N and the data set S (Kumar and Hebert, 
2006). 
The association potential A; indicates how likely a node ; 
belongs to a class C given the observations x. For example, 
Kumar and Hebert (2006) use a generalized linear model. In 
general, any discriminative classifier resulting in a probability 
P(C|x) can be implemented as association potential. 
The interaction potential I;; is a function of all data x and 
measures how the classes of neighbouring points interact. It is 
computed for each edge, for example by the difference of 
adjacent point feature vectors. Depending on the representation 
of these features, the interaction potential acts as smoothing 
term with various degree of smoothing. 
Since we are dealing with a supervised classification approach, 
weights for node and edge features have to be learnt in a 
training step first. The best discrimination of the classes is 
obtained iteratively in an optimization framework by 
minimizing a cost function which depends on both of the weight 
factors. The optimal label configuration is determined in an 
inference step. Thereby, P(C|x) is maximized for given 
parameters based on an iterative message passing algorithm. In 
regard to the large dataset and loops in the graph, an 
approximation has to be chosen for this, e.g. Loopy Belief 
Propagation (Frey and MacKey, 1998). The result of training 
and inference is a probability value per class for each data point. 
Finally, a label is assign to the point based on maximum a 
posteriori (MAP) criterion. In this process, the class labels of all 
nodes are determined simultaneously. 
3. METHODOLOGY 
We classify LIDAR data from Wadden Sea areas. In order to 
preserve small objects, especially small mussel bed areas, we 
classify point-based without a preceding segmentation. An 
overview of the proposed processing chain is given in Figure 2. 
It can be subdivided into five steps: 1) feature extraction, 2) 
implementation of the graph, 3) training, 4) inference and 5) 
labelling of the point cloud. 
  
  
Training data Test data 
  
Feature extraction Feature extraction 
   
  
  
  
  
  
  
  
  
  
  
      
    
  
  
Graph generated for Graph generated for 
training data test data 
Training 
Y 
Parameter b Inference 
  
  
Labels 
  
Figure 2: Flowchart of the processing chain for the 
classification task 
The classification task results in two crucial aspects which are 
explained in more detail in the following. On the one hand, the 
CRF framework has to be implemented for the irregular point 
    
   
  
  
  
  
   
  
  
   
  
  
   
  
   
   
    
    
   
  
   
  
   
  
   
  
   
  
  
  
   
  
   
   
    
  
  
  
  
  
   
   
    
     
  
  
  
   
  
  
  
   
  
   
      
    
    
    
cloud. The structuring of the graph as well as the choice of 
parameters and functions for the training and inference are 
described in Section 3.1. On the other hand, we need 
appropriate classification features for the distinction of water, 
mudflat, and mussel bed. Due to the special test data - flat areas 
with hardly any objects - this becomes a challenging task. The 
feature extraction is investigated in Section 3.2. 
3.1 Classification of point clouds using CRFs 
In a first step, the data are converted to a graphical model. As 
we use LiDAR data, the nodes of the graph are represented by 
the points where adjacent nodes are linked by an edge. Thereby, 
a fast access to the nearest neighbours of each LiDAR points is 
obtained by indexing the point cloud by a k-d tree with a 
dimension of two. Although we apply three dimensional data, 
the reduction to a two dimensional search is justified by the 
appearance of the data. In Wadden Sea nearly no objects with a 
significant extension in direction of z-axis occur. Nevertheless, 
it is an irregular data structure. Each point is linked with its N 
nearest neighbours. 
According to the basic equation (1) of the CRFs, the two main 
terms A;(x, C;) and l;j(x, Ci, C) have to be defined. Closely 
related to Kumar & Hebert (2006) we consider a log-linear 
formulation to model both potentials. Then, the association 
potential A;(x, C;) can be expressed as 
Ai(x, C; » 0) = exp(w, "h;(æ)), (2) 
where vector w,; contains the weights of features for a certain 
class /. For each class a weight vector is determined in a training 
process. Vector h; (x) is the feature vector of each node i. In our 
case we use the features described in Section 3.2 which are 
normalized to unit one to get a robust inference. 
To model the interaction potential I; j (x, C Cj) we use a 
generalized linear model again: 
I(x. Ci = LG - k) » exp (vf ny). 3) 
where the vector v;, indicates the weights of features p;;(x) 
and are learnt in a training process depending on the 
combination of classes | and k. For each label configuration a 
weight vector is determined. The feature vector p;;(x) is 
calculated for each point by the absolute difference of feature 
vectors for each point of neighbouring nodes i and j 
wij) = abs (h(x) = hy). (4) 
For the training and inference, we apply the optimization 
method Limited Memory Broyden-Fletcher-Goldfarb-Shanno 
(Liu and Nocedal, 1989) and the Loopy Belief Propagation 
(Frey and MacKay, 1998) as message passing algorithm as 
implemented in M. Schmidt's Matlab Toolbox (Schmidt, 2011). 
Thus, a probability value for each label is determined. The 
optimal label configuration based on maximizing P(C|x) is 
provided via maximum a posterior (MAP) probability estimate. 
3.2 Feature extraction 
For each laser pulse, information about 3D coordinates and 
intensity are available for the backscattered signal. We do not 
use full waveform laser scanner data and, thus, do not have 
additional signal waveform information. Nevertheless, several 
features can be calculated from the point cloud. We use the 
features described in Chehata et al. (2009). Most of these