The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
The second term is a two-site click energy that favors straight 
lines that are nearer to the projected LiDAR roof contour. This 
term is called the proximity energy term and is formulated as 
follows, 
U 2 (x) 
X X Xj.Xj.POJ) 
i=ljljsN, J 
n n 
Xxj.CXxj -1) 
i=l i=l 
(10) 
The third term is also a two-site click energy and it supports 
straight lines that have similar orientations in relation to the 
projected LiDAR roof contour. This term is called the 
orientation energy term and is formulated as follows, 
X X Xj.X-.s^O,j) 
i=lj|jeN. J 
U-, (x) = 1 
3 V 7 n n 
XXj.(XXj -1) 
i=l i=l 
(11) 
The energy function can be finally expressed as follows: 
U(x)= <2 1 .U 1 (x) + a 2 -U2( x ) + C!; 3-Ll3( x ) (12) 
where: a 1 , a 2 , and a 3 are positive constants. 
The second and third terms of energy have in the denominator 
n 
the term Xx ; > 1. This means that each configuration needs to 
allow at least two correspondences. The optimal configuration 
(x opt ) is obtained by minimizing the energy function, i.e., x opt = 
argmin(U(x)). The minimization problem will be discussed in 
the next section. 
2) 
n 
Xxj < m , where m is the number of projected LiDAR 
straight lines. Let n 1; n 2 , ..., n m be the number of straight 
lines that are nearby the corresponding projected LiDAR 
straight lines. It is easily noted that n= n) + n 2 + ... + n m . 
The number of configurations that needs to be checked is 
C,= (n, + l).(n 2 + 1)... (n m + 1)« | X |= 2 n . 
Minimum-expected correspondences' constraint: It is 
reasonable to expect a minimum of correspondences for 
the problem in hand. Assuming a p percent rate, the 
configurations x to be checked need to respect the 
following restriction: int(m? < Xx ( < m , where 
i=l 
and int(a) means the near integer of a, such 
that int(a)< a. Now assuming for simplicity nj= n 2 = ...= 
n m = n', the number of configurations is C 2 = 
+... + 
« C|. 
The brute force search method modified with the two domain 
constraints described above is called constrained brute force 
search method. In order to demonstrate that the two domain 
constraints can reduce the search space to a tractable size, an 
example considering a relatively complex building with 20-side 
roof contour (m= 20) is analysed. Usually, the proposed 
preprocessing techniques extract 1-3 straight lines around each 
projected LiDAR straight line. Tanking into account an average 
extraction of two straight lines around each projected LiDAR 
straight line, the following holds: 1) n= 40; 2) n]= n 2 = ... = n 20 = 
n'= 2; 3) | X |= 2 n = 1,099,511,627,776; 4) C,= 3,486,784,401 
(~99,7% reduction); 5) C 2 = 1,048,786 (p= 90), which is a 
reduction of about 99,9996% when compared to the number of 
candidates resulted from the uniqueness constraint. In other 
words, it is true that C 2 << Q« | X |= 2 n . 
2.3 Solution of the energy function 
In order to obtain the optimal configuration (x opt ) it is 
necessary to find the global minimum of the energy function 
(U(x)). The global minimum can be found by the so-called 
brute force searching method. This method is a simple and 
general problem-solving technique, which consists of 
exhaustively searching for the best candidate among all possible 
configurations. It is simple to implement and, if a solution 
exists, it always finds it. The great problem of using the brute 
force method is that in many practical problems the number of 
candidates can be so large that the problem becomes intractable. 
In general, the brute force method can be used when the 
problem complexity is relatively simple or when there are 
problem-domain heuristics that can allow the search space size 
to be reduced properly. In the sequence, it will be showed that 
the problem in hand can be transformed into a tractable one, 
even when the complexity of the building is relatively high. 
In order to avoid the combinatorial explosion associated with 
the problem in hand, two constraints are used: 
1) Uniqueness constraint: each projected LiDAR straight line 
must have at most one correspondence, which is either an 
image straight line or no entity. This means that 
2.4 Building contour completion 
The optimisation method generates isolate image straight lines, 
whose one-to-one correspondences to the projected LiDAR 
straight lines are known. Projected LiDAR straight lines having 
no correspondences are kept together the matched image 
straight lines. Thus, the problem to be solved consists of the 
comer determination by line intersection. This is a simple 
problem because the topology of the projected LiDAR roof 
contour can be used to identify adjacent straight lines. 
3. EXPERIMENTAL RESULTS 
The test data consists of a high-resolution aerial image and a 3D 
bulding model generated automaticaly and previously by a 
preexisting methodology that processes LiDAR point clound. 
The test area is located in the city of Curitiba, Brazil. The 
image has 4500 pixels x 3000 pixels and the pixel footprint is 
about 20 cm. The interior orientation parameters of the camera 
and also the exterior orientation parameters of the images are 
known. Figure 2 shows the test building used in the preliminary 
experiment. This is an (inverted) E-shaped building, with a 19- 
side roof contour. Please note that some slight shadowed roof 
faces have low contrast with the background and, as a result, 
their edges are not well-defined.