•rance. September 1-3, 2010 
In: Paparoditis N., Pierrot-Deseilligny M. Mallet C.. Tournaire O. (Eds), 1APRS. Vol. XXXVIII. Part ЗА - Saint-Mandé, France. September 1-3, 2010 
27 
(*) 
:n, Germany, (c, d) the 
straight edge segments. 
Ithough non-maximum 
ige, this does not always 
images, since separate 
' combined during edge 
ge skeleton technique to 
' the binary edges. The 
shrink to a minimally 
irt. A different critical 
atne label (for example 
nts are connected with a 
is no more capable to 
lfortunately. this type of 
al images. To solve the 
to line (or multi-line) 
nnent. Thereafter, the 
are removed. 
straight object that is 
*2, y2). To accurately 
-he well-known Ransac 
1981; Zuliani et. al., 
edge segment may be 
line. For those cases, a 
i line segment from the 
trates the line segments 
lb. 
ling strategy is required 
le reference and search 
line matching strategy 
election of line pairs on 
ididate pair models on 
During the implementation, for the realization of the image-to- 
image relations (estimation of the epipolar lines, stereo intersection 
etc.), we utilized well-known photogrammetric techniques. For this 
study, we assumed that the processed stereo images are not 
significantly different (within ±5°) in terms of their kappa (k) 
angles. Thus, we do not apply any a priori rotation to the line 
segments for the calculation of their angle values in image space. 
2.3.1 Selection of Line Pairs on the Reference Image: In 
urban areas the number of extracted lines is quite large even for a 
small part of an aerial image. Our aim is to search for pairs of lines 
that have a connection in terms of their height values, and to discard 
those pair-wise relations that do not show any reasonable similarity. 
Since the height values of lines are not known at this stage, we 
assess three criteria, (i) proximity, (ii) angle of intersection in image 
space, (iii) similarity of the radiometric values in the flanking 
regions, during the selection of the line pairs. 
The first measure, proximity (T piox ), defines the minimum 2D 
Euclidean distance (djj) between two lines (1, and lj) (Fig. 2a). It can 
be defined as a joint minimum of two Euclidean distances; the 
minimum distance between the endpoints of the line segments in a 
pair, and the minimum of the orthogonal distances computed from 
one of the lines of any point on the other line segment. For example 
in Fig. 2a, the shortest 2D distance between the line segments 1| and 
1 4 is the du distance. 
The second measure is the angle enclosed by line segments 1, and lj 
(Fig. 2b). In this study, we only allow formations of line pairs that 
have a finite intersection point (not parallel) and an angle of 
intersection value larger than a specific threshold (> T ang ). In Fig. 
2b, the line segments, h and I3 have approximately similar 
orientation, therefore, the pair grouping off and I3 is not allowed. 
The third measure, similarity of flanking regions, is another metric 
to evaluate the selection of line pairs. Apparently, if the lines in a 
pair do not show any similarities within their flanking regions, 
those lines can be assumed to be part of different objects. In this 
study, for each line, left and right flanking regions are generated, 
and the robust radiometric mean values of the pixels within the 
flanking regions are estimated using the minimum covariance 
determinant (Meucci, 2005). The similarities can be computed in 
several ways and may involve different color spaces (Henricsson, 
1998; Zhang and Baltsavias, 2000); however; we utilized the 
multispectral bands directly for the computation of the similarities 
by taking the absolute differences of the norms of the mean values. 
One other important gain that we achieve at the end of this process 
is that, the comparison of the flanking regions gives us ability to 
leant which side(s) of a pair represents the most similarity. This 
information is also held in reserve to be used in the next stage, 
identifying candidate pair models on the search image. 
2.3.2 Identifying Candidate Pair Models on the Search 
Image: Once all line pairs are selected from the reference image, 
their corresponding matches on the other image is also searched 
using a pair-wise approach. To fulfil this objective, for each 
reference pair, all candidate pair models must be collected from the 
other image. With the knowledge of the exterior and interior 
orientation along with the user-specified minimum and maximum 
height values (or the approximated height information derived from 
a DSM data), for a single line, an epipolar quadrilateral region 
constraint can be employed to reduce the search space (Schmid and 
Zisserman, 1997; Zhang and Baltsavias, 2000). However, in a pair 
wise strategy, there are two lines in a pair; thus, we collect all 
candidates for a pair of lines using two different quadrilateral 
regions. For example, in Fig. 3b, two quadrilateral regions (defined 
by certain minimum and maximum height) are illustrated for the 
line pairs, f and 1 2 (Fig. 3a). However, even for a single line, the 
number of candidates in each quadrilateral region could be 
excessive. Here, we propose a constraint to construct the candidate 
pair model sets from the individual candidates. As a result, for each 
Fig. 2 Lines on the reference image, (a) the proximity measure, (b) 
the angle of intersection. 
line, we can reduce the number of candidates considerably. We 
first compute the intersection point of the reference pair (Fig. 
3c). Since, we restricted the formation of the reference pairs in 
the previous stage with a specific angle (> T an „, see section 
2.3.1); there is always an intersection point between the lines 
that form a reference pair. After that, we estimate the epipolar 
line segment (with the same minimum and maximum heights) 
of the intersection point on the search image (Fig. 3d). Next, for 
all candidate pair models, we computed their individual 
intersection points and tested the proximity of the points to the 
epipolar line segment by computing their orthogonal distances. If 
the distance value is computed to be less than a threshold (T ep j). the 
candidate pair is justified, otherwise deleted. For the threshold T ep „ 
rigorous experimental evaluations are performed, and we found that 
almost all the correct pair intersections are within the range of 5 
pixels distance to the epipolar line. Very similar results for the 
features of junctions are already verified by (Kim and Nevatia, 
2004), thus we fixed the parameter T ep , to 5 pixels. The intersection 
points of candidate pair models that are computed to be less than 
T ep j for the line pair f and I2 are shown in Fig. 3d. 
Although the epipolar line of intersection constraint is very 
successful if the lines in a pair actually intersect on the Earth 
surface (or intersect hypothetically), it does not hold for the pairs 
that are formed by the lines that do not intersect. Thus, the correct 
pair model (if it exists) on the other image might be missed. 
However, those kinds of pair formations are minimized through the 
selection step by imposing the flanking regions constraint (see 
section 2.3.1). One different aspect of this constraint is that, it also 
automatically eliminates the pairs in which two lines in one view 
(a) (b) 
(c) (d) 
Fig. 3 (a) reference line pairs, (b) the quadrilateral regions, (c) the 
intersection point of h and l 2 . (d) the epipolar line of intersection 
and the intersections of candidate pair models that are computed to 
be less than T ep j.