ISPRS Commission II, Vol.34, Part 3A „Photogrammetric Computer Vision‘, Graz, 2002 
  
4.3.2 Minimum Description Length Criterion 
The minimum description length (MDL) criterion by Rissanen 
(1984) provides a generic method for comparing the optimality 
of different models fitted to particular observations (Cham, 
1999). In our terrain surface reconstruction process, this MDL 
criterion is employed in order to determine an optimised model 
T; out of the tetrahedron model candidates (77) generated for 
ÿ, - In Eq. (5), let us substitute the model candidate ¢° and its 
labelling observations f° for a tetrahedron model T and its 
new observations of the terrain polarity y, respectively. For 
simplifying the notation, let us describe a tetrahedron model 
candidate as T, and its set as {T,} . Then, Eq. (5) can be 
reformulated as follows: 
T° = argmax P(y, | T,,6)P(T)) (10) 
where y, is a set of labelling observations measured for all the 
three lateral facets of T, given, which is generated by Eq. (7) 
and (8). 
According to the MDL framework, when we take the minus 
logarithm based 2 on both sides of Eq. (10), maximizing the a 
posteriori probability density function of Eq. (10) in order to 
select the optimized model, 7' can be converted into 
minimizing the total coding length of describing observations 
y, using model 7, as follows: 
Ly ,T^)- min | -log; PG, |7,,3,) * LCT,) (11) 
where the first term of Eq. (11) is the description length to 
encode the closeness between the model T, and its observations 
y,» that is a degree of the terrain polarity and the last term 
L(T,) specifies the description length of the parameters of the 
tetrahedron model 7, as its length increases, when the model 
complexity gets larger. Thus, the MDL optimality in Eq. (11) 
can be achieved when the terrain polarity of plane terrain 
surface is augmented most strongly and the model 7, used is 
the simplest one of the candidates {7} . 
Li (1993) suggested that the description length of the entire 
observations y, can be efficiently encoded in the MDL 
framework, when given model 7, is divided into two parts, the 
inlier model part and the outlier part, i.e., T,= [T7 T 774] ; here 
I" is the inlier model fitted to the observations of “ons” and 
"bufs" generated by Eq. (8) and 77" is outlier part fitted to 
"offs" ones. Thus, given 7^, the total description length of y, is 
described as follows: 
Ly, T) Y | -log; PO (1,8) log; Ply% I7.) ] 
Vey, 
SI e IQ) 
(12) 
where y, is an observation generated by Eq. (7) and (8) when 
given T,; 77" and y" are labelling observations generated 
depending on which label is assigned to y, by Eq. (8), that is 
“ons” or “bufs”. 
In Eq. (12), the first term and second terms indicate lengths of a 
degree of the smoothness and discontinuity of the terrain 
polarity respectively, which are differently measured depending 
on the label of y,. Thus, when AQ, is measured for y. 
according to Eq. (9), the conditional probability for the model 
T, and an observation y, is given as follows: 
15 oa if R(A,)-ons 
P(y,|T,,0,) 7 1 
14e 444-5 if R(A, -bufs 
(13) 
where a and f are the parameters for the sigmoidal function 
which generates a normalized probability density function; its 
minimum and maximum probability is restricted up to 0 and 1 
respectively. In Eq (13), the probability is maximized when 
A0, of "ons" observation describing an intra-relationship of on- 
terrain points is measured close to 0°. Similarly, when “bufs” 
one of inter-relationship between on- and off-terrain points is 
measured close to 90°, the probability is also maximized. In this 
case, their description lengths in Eq. (12) get shortened. 
The last two terms in Eq. (12) are the description lengths for 
T?" and T" respectively. L(T7") is the description length of 
the number of outliers, that it L(T;")2-log, N, » which 
means that our objective function of Eq. (12) prefers a model 
which populates more off-terrain points when the strengths of 
the terrain polarity are comparable between model candidates. 
Likewise, La’) is the description length of a tetrahedron 
model used. Since the entire model candidates {T,} share the 
same base triangle, the only difference that can be characterized 
for an individual model is the size of volume of 7 which is 
proportional to its height 77,. Thus, the description length to 
encode T^ is generated as follows: L(T. 7.) * log, H,, which 
means that when the optimized model 7” is selected, we expect 
that the terrain surface is reconstructed smoothly, rather than 
abruptly. Thus, the model having a smaller volume is preferred 
in Eq. (12). 
When the upward divide-and-conquer triangulation is triggered 
over a local area, a set of the tetrahedron model candidates {7,} 
is generated and the description length of Eq. (12) is measured 
for all the three lateral facets of each T, when 6, is given. 
Finally, the model to have the minimum length of Eq. (12) is 
A - 342