In: Paparoditis N., Pierrot-Deseilligny M., Mallet C.. Tournaire O. (Eds), IAPRS. Vol. XXXVIII. Part 3A - Saint-Mandé, France, September 1-3, 2010 
Under the Markovian hypothesis, solve equation (5) with 
equation (5) and (7). The problem searching for the MAP 
configuration is equivalent to finding minimum global energy U 
as sum of data term U d and contextual term U c : 
U = aU d + (1 - a)U c (8) 
In our problem domain, we aim to model trees as objects in the 
ALS data and fit the detection of individual trees in a high-level 
MRF labeling problem. The problem representation of the 
model is specified below. 
4.1.1 Representation of trees: In our study, we represent a 
tree using a treetop point and a crown radius. Later, some other 
features are also extracted from the ALS image as properties of 
trees. The extraction process can be divided into two parts: local 
maxima extraction, and crown boundary' points and radius 
calculation. The second part will be described in next section 
4.1.2, which is related with the building of neighborhood 
system. As treetops are good representation of trees, after C'HM 
is reconstructed from ALS data, local maxima are over- 
populated using a variable circular window with relatively small 
size, to ensure in the set of local maxima contains all the 
treetops in the image as shown in Figure 1. So the goal of the 
MAP-MRF labeling is to label all local maxima which are true 
treetops as “true”, and all the otherwise as “false”. Initially, all 
the local maxima are assumed to be true treetops thus labeled as 
“true”. 
4.1.2 Neighborhood system: The sites in a configuration is 
related with each other via neighborhood system, which is 
another important task in the designing of a MRF model. A 
Delaunay TIN is used in our research to build up relationships 
between neighboring treetops, as shown in Figure 1. In this way, 
Delaunay TINs are built and updated during the optimization 
process using the local maxima label as “true”. And “false” 
local maxima will be pruned from the graph during the updating 
process. The neighbor system could then help us examine the 
interaction between two “true” treetops easily. 
Figure 1: The local maxima extracted using variable circular 
window size. Delaunay TIN is used to build the neighborhood 
system. 
The neighborhood system designed in such a manner is also 
advantageous for extracting some other properties for the 
treetops, namely crown boundary points and radius as 
mentioned in 4.1.1. A image profile between two adjacent “true” 
treetops is extracted from the CHM image. It is then reasonable 
to say the deepest valley point on the profile is the safest 
separation of the two trees, if the two treetops are “true”. From 
the treetop points to the separation points, we can find all the 
possible boundary points. Those boundary points are then used 
to determine the directional average boundary radius, average 
boundary radius and most possible boundary points on each 
profile. Those features extracted from the image are then used 
with the local maxima to represent a tree object in the MRF 
model. 
4.2 Energy Formulation 
Design of energy functions, or objective functions, is another 
critical issue in MRF. For energy functions will map a solution 
to a real number measuring the quality of the solution in terms 
of goodness or cost, the formulation has to carefully determine 
how various constrains to be encoded into the function, in order 
to get the optimal solution. According to equation (8), the 
global energy U of the model is comprised of data energy U d 
and contextual energy U c . 
4.2.1 Data Energy: The data energy indicates the likelihood 
of the objects of trees in relation with the features extracted 
from the ALS data, or how well those features support the 
treetop point as “true”. In the calculation of this term, we 
incorporate four kinds of constrains, w hich are specified below. 
Symmetric (U s d ) 
The “true” treetops are assumed to locate in the central part of 
the crown, whereas the “false” ones at the edge part of the 
crown. Therefore, the determined crown shapes of “true” 
treetops are expected to be more symmetric. This function (see 
Figure 2) is then used to penalize treetops with asymmetric 
crown given by equation (9). 
sin “ £ s)) '/ 0 ^ A/? ( s ) ^ 2e s (9) 
1 if Aft(s) > 2e s 
Where s is a treetop, AR(s) is the radius difference ratio of s, 
given by equation (10). 
A R(s) = /r s (10) 
Where R l s is the directional average boundary radius of treetop 
s, R s is the average radius of s and N the number of profiles of 
s. 
Boundary Radius Constrain (U d ) 
This scoring function w'as set to penalize the local maxima lo 
cated closely to the edge part of a crown according to the num 
ber of radius of most possible boundary points under certain 
threshold given by equation (11). 
f 1 ifn h (s) > 2 
Ud( s ) = ) 0 if n b (s) = 1 (11) 
1-1 ifn b (s) = 0 
Where s is a treetop and n b (s) is the number of radius of most 
possible boundary points under threshold, with is set as 
minl^B, 0.1 R).