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