Introducing a new constraint reduces the number of tests to 
investigate. This constraint on the coplanarity of two object 
points involves two instead of three correspondences, 
reducing the order of the number of tests to n*. Further 
significant reduction of the number of tests is achieved by 
computing a number of attributes for each constructed image 
point. A correspondence hypothesis is only set up when the 
attributes of the two points match to a sufficient degree. 
The procedure for deriving relative position, epipole 
detection in short, consists of the following five steps: 
1 Compute points in each image through line 
intersection. 
2 Establish correspondence hypotheses between the 
computed points. 
3 Compute statistical tests for coplanarity of all 
combinations of two correspondences. 
4 Grouping of correspondences based on the test results 
and epipolar plane intersection constraints. 
5 Refinement of grouped correspondences by overall 
adjustment and testing. 
Each step is repeated for each of the four possible 
permutations of the rotation matrix of the second image. The 
exterior orientation of the first image determines the object 
co-ordinate system. 
3.3.1 From lines to points 
Points are created in each image as intersection of two image 
lines being projections of edges with a different 
(perpendicular) orientation in object space. This orientation 
is determined by the vanishing point detection procedure. 
Two lines are intersected when an endpoint of a line is within 
a preset distance (commonly set to 5 pixels) from the other 
line. Furthermore, the following attributes are computed and 
registered for each point: 
e The orientation of the plane passing through the object 
point (perpendicular to the orientations of the two 
intersected lines) 
e The type of junction (T-junction or L-junction) 
e The orientation of the junction (4 options: Figure 4) 
e The ratio of the lengths of the two edges 
These attributes are all evaluated in object space, i.e. after 
projecting the lines onto a plane of which the orientation is 
known, again through the vanishing point detection. 
n: 
LT 291] 
Figure 4: Four T-junctions (top) and four L-junctions 
3.3.2 The correspondence hypotheses 
In the next step of the procedure a list of possible 
correponding image points is set up. A correspondence is 
added to the list only when the attributes of points have been 
compared. Both points have to have the same (plane) 
orientation, the same junction type, and the same junction 
orientation. The ratio of the line lengths should be similar for 
both points with a typical maximum difference of 50%. The 
correspondence search turned out not to be sensitive to this 
criterion. 
The creation of image points, their attributes, and 
—230— 
consequently the correspondence hypotheses depend on the 
current permutation of the rotation matrix of the second 
image. With each permutation the vanishing point (i.e. object 
orientation) line labels for X and Y are exchanged. 
3.3.3 Statistical testing of coplanarity 
With the image orientations known, the epipole is defined by 
a minimum of only two correspondences (the intersection of 
the two related epipolar planes; Figure 3). Furthermore, 
because each image point is constructed from the intersection 
of two lines of which the spatial orientation is known from 
the vanishing point detection, the orientation of the object 
plane in that point is known. With the epipole derived from 
the two correspondences, the location of the two object 
points in model space can be computed by forward 
intersection, and thus the position of the two parallel planes 
through those points and the distance between the planes is 
known. The coplanarity constraint requires this distance to be 
Zero. 
For the formulation of the coplanarity constraint the ray of an 
image point is rotated to the object co-ordinate system. After 
replacement of equation (1) by 
x" zR'(x y-f) (6) 
in which i refers to one of the two images, equations (2) and 
(4) are used to compute the orientation vector of the epipole 
(v) from two correspondences. Knowing the epipole, forward 
intersection results in the distance (d) from the projection 
center to an object point. This distance is projected onto the 
normal n, of the object plane. For image 7 and 
correspondence J: 
=} i x! :n Dp 
djzd,-— t (7) 
i 
Normal n, is a unit vector in the object X or Y direction, 
dependent on the orientation of the façade. For the 
formulation of the coplanarity constraints the first image is 
used (in principle, using the second image would yield 
identical results). The constraint for coplanarity of the two 
object points can now be written as: 
— 1 — 
Qr did (8) 
The statistical testing of the hypothesis is explained in (van 
den Heuvel, 1998). The coefficients of the linearised form of 
equation (8) are derived numerically. 
3.3.4 Clustering of correspondences 
For all combinations of two possible correspondences the 
statistical test based on constraint (8) is evaluated. Each test 
links two correspondences that define an epipole. The 
clustering procedure aims at grouping of correspondences of 
which the inter-correspondence tests are accepted, and at the 
same time support the same epipole. In order to verify the 
latter, a statistical test is used that is based on the intersection 
of epipolar planes. This constraint is identical to the 
intersection of interpretation planes constraint (3). 
The clustering procedure includes the following steps: 
e For each accepted test (8) it is checked whether one of 
the two correspondences is present in an existing 
cluster. If this is not the case, a new cluster is 
established. 
e [fa correspondence of an accepted test is present in an 
existing cluster, the other correspondence becomes a 
  
= 0 rs 
tl 
Les 
c9 ds CS CN NT Rady 
a IA WE MA m AY A fn S — - ("79 CH PF CH ed