The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
428 
another and with specific angular relations with one another 
need to interact. Using projected LiDAR roof contours and their 
error projections, the neighboring set of straight lines associated 
with each building roof can be further reduced. This paper is 
organized as follows. Section 2 presents the proposed 
methodology. The preliminary results are presented and 
discussed in Section 3. Finally, the paper is finalized in Section 
4 presenting some conclusions and outlook. 
2. METHODOLOGY 
The proposed methodology comprises preprocessing steps, the 
establishment of the energy function (U(x)) based on an MRF 
model, the solution of the energy function by applying a 
minimization algorithm, and the completion of the detected 
straight lines' groupings for reconstructing the refined image- 
space roof contours. In the following sub-sections, details on 
briefly described steps of the proposed methodology are 
described. However, it will be given considerable emphasis on 
basic MRF theory and on development of the energy function. 
2.1 Preprocessing 
The preprocessing steps mainly comprise the projection of the 
3D roof contours onto the image-space and the extraction of the 
image straight lines that are nearby the projected LiDAR roof 
contours. The techniques used in these steps are well-known 
and, as such, only more general details are presented. 
In order to project the 3D building roof contours onto the 
image-space, two basic steps are necessary. First, the 
collinearity equations are used, along with the exterior 
orientation parameters, to transform the roof contours into the 
photogrammetric reference system. Second, an internal camera 
model and the associated interior orientation parameters are 
used to add systematic errors and to transform the roof contours 
from the photogrammetric reference system to the LC-image 
coordinate system. The error projections are estimated in order 
to construct a registration error model. 
The registration error model is a simple bounding box 
constructed around each projected LiDAR straight line, which 
enables the straight line extraction process to be focused only 
on limited regions of the image, avoiding the extraction of 
irrelevant information. There is a large amount of research in 
the literature in the subject of straight line extraction. Examples 
of methods are the Bums line detector (Bums et al., 1984) and 
the Hough transform based methods (Balard and Brown, 1982). 
The algorithm for straight line extraction is based on standard 
image processing algorithms and seems to be effective for the 
present application. First, the Canny operator is used to 
generate a binary map with thinned edges. Next, an edge 
linking algorithm is applied to the edge map for organizing the 
pixels that lie along edges into sets of edge contours. In order to 
extract the straight lines, the edge contours are approximated by 
polylines through the recursive splitting method (Jain et al., 
1995). Very small straight lines (2-3 pixels length) and straight 
lines differing too much in orientation (e.g., 20°) from the 
projected LiDAR roof contour are removed, since they are 
unlikely to be valid candidates for constituting roof contours. In 
the last step, simple perceptual grouping rules (i.e., proximity 
and collinearity) are used to merge collinear straight lines and 
then to further reduce the number of candidates for representing 
the roof contours. 
2.2 MRF concepts and the energy function 
2.2.1 Basic concepts of the MRF theory 
MRF theory provides an efficient way to model context- 
dependent features such as straight lines forming a roof building 
contour. In an MRF, the sites in S= {1, ..., n} are related to one 
another through a neighborhood system defined as N= {N i; i G 
S}, where Nj is the set of sites neighboring i. A random field X 
is said to be an MRF on S with respect to a neighborhood 
system N if and only if, 
P(x) >0, V x e X 
p ( x i I x s-{i}) =p ( x i I x Nj ) 
(1) 
Note that x is a configuration of X and X is the set of all 
possible configurations. Also note that Xj e x and x s . {i j (or 
x N )cz x - As stated by the Hammersley-Clifford theorem, an 
MRF can also be characterized by a Gibbs distribution 
(Kopparapu and Desai, 2001), i. e., 
where: 
P(x)= 
exp(-U(x)) 
Z 
(2) 
Z= Z exp(-U(x)) 
xeX 
(3) 
is a normalizing constant and U(x) is an energy function, which 
can be expressed as: 
U(x) = Z V c (x) 
csC 
(4) 
Equation 4 shows that the energy function is a sum of clique 
potentials (V c (x)) over all possible cliques c G C. A clique c is a 
subset of sites in S in which every pair of distinct sites are 
neighbors. The value of V c (x) depends on the local 
configuration on clique c. For more detail on MRF and Gibbs 
distribution see e.g. Kopparapu and Desai (2001) and 
Modestino and Zhang (1992). 
2.2.2 The energy function: 
Straight lines resulting from the image processing techniques 
are used to construct an MRF model expressing the specific 
shapes of building roofs, having as reference the polygons 
resulted from the photogrammetric projection of LiDAR roof 
contours. The associated energy function is defined in such way 
that each straight line is associated with a discrete random 
variable (x;) assuming binary values according to the following 
rule: