6.3 Matching lines and points
The forementioned selection algorithm can easıly be
generalised for the case of line and point matching.
We have to define new cost functions for the point at-
tributes, the relations point-point and point-line. We
present the case of two images to be matched, the ge-
neralisation for more than one image pair is possible.
For the attribute costs we propose to use the com-
planarity constraint and the correlation coefficient
between points. In the ideal case the correlation co-
efficient pi; between two points P; and Pj equals 1.0.
The spat product pi; of the base vector and the two
direction vectors from the centres of projection to the
points equals 0. Thus we define
2
Pij
2
Tp
2 I ms d
KA, Pm at (9)
a
p
For the costs of point-point relations we regard the
distances (daz), dy!) between the points in the first
image and the distances (dx) dy(?)) of the corre-
sponding points in the other images. Then we get the
relational costs for the point pair PY, pV matched
to pU, pi respectively:
mn
i dell) dD ns (df Ay jt. |
Kg) m ( : ) 4 (dy ; yh) (10)
C dz 0 dy
For the relation point-line again we regard the di-
stance of the point from a line. One can differentiate
between the ’right’ and the "left? side of the line by
using a signed distance.
7 Experimental Results
Practical tests with an image sequence taken on a Ger-
man highway have been perfomed. Figure 4 shows
four images with extracted straight lines. The line
detector furnishes 32, 32, 31 and 37 lines respectively.
'The initial line matching furnishes 20 possible assig-
nments. The orientation of the second image pair is
performed using 5 assignments. The final optimisa-
tion furnishes assignment sets with up to 8 assign-
ments. There is only one false match in the right
part of the images: a neighbouring line is assigned.
These lines are even for the human operator difficult
to match as they are quite similar.
8 Performace Analysis
We have performed the tests on a DEC Alpha
3000/600 (175 MHz). The process time for the exam-
ple described in the previous section is listed in table
1. The greatest part of the calculation time is con-
sumed in the standard image processing part. This
calculation could be performed with a special image
processing hardware which is up to 100 times faster
30
Table 1: Calculation time for the whole feature ex-
traction and matching process with the four example
images from section 7
Procedure process time (s)
Interest point calculation 148
Lines calculation 116
Initial matches 4
Camera orientation 8
Optimal matching 4
than a workstation. Thus, the construction of a sy-
stem working under operational conditions is possible.
9 Discussion
An algorithm for line matching based on the minimi-
sation of a cost function was presented. The mini-
mus is found by first applying heuristic means and
a branch-and-bound optimisation afterwards. Cur-
rently only a small part of the possible line matches
(= 2096) are found. We hope to enhance the num-
ber of matches found in an aditional stage where the
matches from the first stage are assumed to be correct
ones. The matched lines are then of course discarded
from the list of possible assignments.
References
[1] Aussems, Thomas, 1995. Fahrzeugortung mit-
tels GPS und Koppelnavigation. In: Benning
(Ed.), 125 Jahre Geodasie an der RWTH Aachen,
Veroffentlichung des Geodatischen Instituts Nr.
53. pp.71- 30.
[2] Christmas, W., Kittler, J., Petrou, M., 1995.
Structural Matching in Computer Vision Using
Probabilistic Relaxation, IEEE-PAMI, Vol. 17,
No.8, pp. 749-764.
[3] Deriche, R, 1985. Optical Edge Detection Using
Recursive Filtering. In: First International Con-
ference on Computer Vision.
[4] Forstner, W, 1991. Statistische Verfahren fur
die automatische Bildanalyse und ihre Bewer-
tung bei der Objekterkennung und -vermessung.
DGK, Reihe C.
[5] Melsa, J., Cohn, D., 1978. Decision and estima-
tion theory, McGraw-Hill, New York.
[6] Taylor, C., Kriegman, D., 1995. Structure and
. Motion from Line Segments in Multiple Images,
IEEE-PAMI, Vol. 17, No.11, pp. 1021-1032.
[7] Schwermann, R., 1994. Automatic image orienta-
tion and object reconstruction using straight lines
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B2. Vienna 1996
Figu
ima,
inc
tech
sion
