The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008 
fundamental matrix F may be chosen 
as P = [I | 0] and P' = [[e'] x F | e ] (Hartley, 2000). The 
reconstructed points will be shown in Figure.8 in the next 
section. 
3. LINE MATCHING AND RECONSTRUCTION 
When line features are extracted by a detection operator like 
Canny, many variant methods can be used for matching. A fast 
and stable matching method should satisfy two critical 
requirements: appropriate search range and distinct dissimilar 
measurement. Usually, epipolar line geometry and intensity 
information are two effective constraints. So first we try to use 
these two constraints to match lines. 
3.1 Epipolar line constraint and degeneracy 
Figure.4shows the geometric constraint described as epipolar 
line. The two end-points of a line segment generate two 
epipolar lines in the other image. These two lines intersect at 
epipole 6 . The corresponding line segment should be 
necessarily intersected or contained in the shadow range of the 
right figure in Figure.4. Perhaps more than one line are 
contained in this range. These lines are all regarded as 
candidate corresponding lines. Then we compare the similarity 
of the intensity neighbourhood of the each candidate line with 
respect to the intensity neighbourhood of the original line to 
match them uniquely. 
¡magel 
Image2 / 
• *1 
/ / \ 
1 / 
j AV ! \ 
x 2 • 
e 
e* 
Figure.4 Applying the epipolar line to reduce the search space 
of candidate lines. 
Figure.5 Top row pictures show the epipolar line constraint for 
a vertical line, while bottom row pictures show this 
constraint for a horizontal line. In four pictures, red 
lines represent extracted feature lines and blue lines 
represent epipolar lines. 
However, there might be degeneracy, that as described in 
(Hartley, 2000), lines in 3-space lying on epipolar planes cannot 
be determined from their images in two views. The degeneracy 
usually occurs when we get images what are almost parallel to 
the space object surface. For example, in the first row of 
Figure.5, the search range is clear and doubtless for the vertical 
lines, but for the horizontal lines in the second row, the search 
range becomes narrower and is difficult to confirm. This is a 
big problem when use eoipolar line as constraint condition for 
line matching. Therefore, we need to find a better solution. 
3.2 Homography constraint 
The projective geometry of two cameras is described 
as 171 ~ Hm , where H is the homography plane. Although the 
object building is not a plane, when compared to the distance 
between the camera center and the object, we can regard a 
facade as an approximate plane. Since we just need 
homography condition to restrict the matching search range, we 
don’t need very high precision. Figure.6illustrates the relation 
between homography and epipolar geometry. From the figure, 
we can see that, if the space point is out of the homography 
plane 7T, then m ^ Hm , where m and m are a pair of points 
corresponding to a same space point M . We try to determine 
H in two different ways. The first way is using redundant 
corresponding points to find an optimal solution with a least- 
squares approach. The second one is featureless based on a 
global optimization method inspired by the differential 
evolution (DE) algorithm (Price, 2005). This method has been 
successfully used for image registration (Karimi, 2008). 
Figure.6 Relation between homography and epipolar geometry. 
Any space point M mapped by the homography 
plane 71 lies on its corresponding epipolar line l' e . 
Using redundant corresponding points, a least-squares approach 
minimizes the energy function in equation (2) 
e - min ^ d(Hm, m) 2 (2) 
The DE algorithm performs a global search in the parameter 
space, using N vectors {jc,. G \i = 0,1,2, — — l} as a 
population for each generation G, 
where X = [x 0 ,X l ,X 2 ,“ 'X D _j] 7 is a D-dimensional 
parameter vector. The initial population of DE is chosen 
randomly. DE generates new parameter vectors by adding the 
weighted difference between two population vectors to a third 
vector according to 
V (,G+1 ~ X r t ,G + F( X r 2 ,G ~ X r 3 ,G~) (3)