ematical Morphology. 
n Modeling and Error 
IS. PE & RS. Vol.60, 
on and Control, vol. 8, 
1a 1996 
RELATIONAL MATCHING FOR AUTOMATIC ORIENTATION 
Woosug Cho 
Department of Geodetic Science and Surveying 
The Ohio State University 
Columbus, Ohio 43210 
Commission III, Working Group 3 
KEY WORDS: Relational matching, A* search, Heuristics, Binary tree, Cost and Benefit function, Interest operator, Relative 
orientation. 
ABSTRACT 
The objective of this research is to investigate the potential of relational matching in one of the fundamental photogrammetric 
processes, the orientation of a stereopair. The automatic relative orientation procedures of aerial stereopairs have been investigated. 
The fact that the existing methods suffer from approximations, distortions (geometric and radiometric), occlusions, and breaklines is 
the motivation to investigate relational matching which appears to be a much more general solution. 
An elegant way of solving the initial approximation problem by using distinct (special) relationship from relational description is 
suggested and experimented. Two evaluation functions (cost and benefit function) with the same relational descriptions are 
investigated. Special attention is given to the solution for relational matching when a large number of features are involved. To 
speed up the relational matching procedure, unit ordering and modified forward checking are incorporated into the proposed 
relational matching scheme. In addition, an optimal way of constructing local binary relations is implemented. 
The detection of erroneous matching is incorporated as a part of proposed relational matching scheme. Experiments with real 
urban area images where large numbers of repetitive patterns, breaklines, and occluded areas are present prove the feasibility of 
implementation of the proposed relational matching scheme. 
The investigation of relational matching in the domain of image matching problem provides advantages and disadvantages over 
the existing image matching methods and shows the future area of development and implementation of relational matching in the 
field of digital photogrammetry. 
1. INTRODUCTION 
One of most fundamental tasks in photogrammetry is to find 
conjugate features in two or more images, which is commonly 
referred to as the matching problem. In conventional 
photogrammetry, the matching problem is solved by a human 
operator who identifies conjugate features in two or more 
images without conscious effort, in real time. The human visual 
system is easily able to form a stereo model and to describe the 
scene content in a highly symbolic fashion. In digital 
photogrammetry, the matching problem, which is called image 
matching problem in this study, is yet far from being solved 
fully automatically. The most persistent problems are 
occlusions, foreshortenings (relief distortions), breaklines 
(discontinuities in surface) and nonlinear radiometric 
differences among the images [Doorn et al. 1990, Zilberstein 
19921. 
The image matching problem can be described as comparing 
a specific feature in one image with a set of other features in the 
other image and selecting the best candidate, based on the 
similarity measure between feature descriptions. The feature 
description can be described at different levels of abstraction. 
Depending on the level of feature description, the image 
matching methods are usually divided into the three groups: 
area-based matching, feature-based matching, and relational 
matching. For a detailed description of the area-based and 
feature-based matchings, the reader is referred to the papers 
[Schenk 1992, Haralick and Shapiro 1992]. 
In computer vision, relational matching has been used for 
problems like object recognition and location, scene analysis, 
and navigation. Recently, relational matching began to gain 
attention in digital photogrammetry [Vosselman 1992, 
Zilberstein 1992, Shahin 1994, Tsingas 1994]. 
As the name suggests, relational matching seeks to find the 
best mapping between two relational descriptions. Relational 
description consists of not only features but also geometrical 
and topological relationships among the features. In order to 
find the best mapping, relational matching has to employ the 
measure of similarity while mapping one relational description 
into the other relational description. The measure of similarity 
between two relational descriptions can be achieved by an 
evaluation function which is usually defined as a cost function 
or benefit (merit) function. The cost function is to be minimized 
and is zero if two relational descriptions are identical. Unlike a 
cost function, the benefit function is to be maximized; and it 
achieves a maximum when two relational descriptions are best 
matched. 
The motivation for proposing a relational matching scheme in 
this paper stems from the fact that the method is much less 
sensitive to many factors which are limiting the existing image 
matching methods. Such factors include approximations, 
distortions (geometric and radiometric), and occlusions. 
Consequently, relational matching appears to be a much more 
general solution. 
2. FEATURE EXTRACTION 
Point features provide the most stable geometry for relative 
orientation. The extraction of distinct points such as corner 
points is a basic procedure in digital photogrammetry and 
computer vision. There has been much research in the field of 
distinct point detection [Moravec 1977, Forstner 1994, Tang 
111 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996