nfor- 
ture. 
plete 
often 
lable 
cess- 
and 
ider, 
10ge- 
eived 
y the 
here- 
s the 
blem 
nage. 
how 
ge in 
pany 
anta- 
ences 
nula- 
ion”, 
Vol. 
Sys- 
309- 
sated 
nical 
. Re- 
v Re- 
sure- 
; PP- 
GRAPH-BASED MATCHING OF STEREO IMAGE FEATURES 
Olaf Hellwich and Wolfgang Faig 
Department of Surveying Engineering 
University of New Brunswick 
Fredericton, N.B. 
Canada, E3B 1W4 
olaf@atlantic.cs.unb.ca 
Abstract: 
À feature-based stereo vision method was developed. It utilizes a neighbourhood graph in order to control the search 
for matching edge pairs. Information about neighbourhood relations supports the establishment and the reliability of 
matches. The matching method does not exploit any geometric constraints and is therefore applicable to a wide range of 
related problems, such as finding correspondence between images and maps. The most important advantages of the 
matching algorithm are its independence from human interaction and the use of curved edge segments. 
The proposed method was implemented in the form of a modular software package on a Sun workstation using the 
XWindow user interface. The complete software package forms a softcopy photogrammetric program package. Its 
modular nature provides the possibility to exchange parts in order to adjust it to future technological developments, and 
use it for further stereo vision research. The features, advantages and problems of the proposed method are discussed. 
Digitized stereo image pairs for the investigation of automobile accidents are used to illustrate the method. For objects 
with distinctive edges, 80 to 9096 of the resultant densely distributed feature pairs were found to be correct. 
Key Words: Feature Extraction, Image Matching, Stereoscopy 
empirically set weight. The algorithm allows the use of 
the epipolar constraint, but does not rely on it. 
Pong et al. (1989) developed a matching method for 
topographic structures consisting of edges and regions. 
Arc segments, i.e. long thin edge regions which are not 
1. Introduction 
Since computers are getting cheaper and faster, and 
computer vision research has made progress in various 
vision tasks, it appears to be feasible to solve the stereo 
vision problem of applied photogrammetry without the 
use of stereo plotters, based on digital image processing. necessarily straight, are extracted from the images and 
This goal is being approached with the development of linked by a region growing process. The regions, 
digital photogrammetric workstations which solve the separated from each other by the arc segments, are found 
stereo vision problem fully digitally, and to a varying by assigning a unique label to each maximally connected 
degree, automatically (Schenk and Toth, 1992; Dowman group of non-arc pixels. In both images, sequences of 
et al., 1992; Miller et al., 1992). edges and regions on an epipolar line are generated. The 
algorithm establishes a match between these sequences. 
The matching criteria are the orientation of the edges and 
the intensity of the regions. After the evaluation of all 
epipolar lines, the algorithm finds unique matches for the 
edge or region segments. 
Ayache and Faverjon (1987) proposed a method of 
prediction and propagation of hypotheses applied to a 
graph-based description of images. The images are first 
reduced to neighbourhood graphs of edge segments. The 
line segments are generated by a polygonal 
approximation of edge elements in the images. The 
neighbourhood relations between the edge segments are 
established with the help of a bucketing technique. An 
image is subdivided into rectangular grid meshes. All 
edges which belong partially or completely to the same 
grid mesh are considered neighbours. The constraints 
used by the stereo matching algorithm are: epipolar 
The proposed matching method for digitized stereo 
image pairs is mainly intended to be used in industrial 
close-range photogrammetry. As examples for non- 
metric imagery, images of cars which were involved in 
accidents were evaluated. 
In order to provide a user friendly tool which can 
be applied by non-specialists, the amount of user 
intervention during the matching process has to be 
limited. However, as it cannot yet be expected to solve all 
matching problems with the existing means of computer 
vision, the possibility for interactive verification and 
correction of the matching results has been provided. 
These two aspects secure the usefulness of the developed 
software for practical applications. 
1.1 Previous Work 
Originally feature-based approaches to the stereo constraint, geometric similarity constraint, continuity 
vision problem were considered for application. In the constraint and uniqueness constraint. The experimental 
following discussion the extraction and matching of edges results of Ayache and Faverjon show weaknesses where 
is reviewed. the objects or object parts have curved contours. 
McIntosh and Mutch (1988) developed a matching A graph-based matching approach more elaborate 
method for straight lines. The lines are extracted from than Ayache and Faverjon's technique was presented by 
line-support regions which provide parameters Horaud and Skordas (1989). An image is described in 
describing the edges. The matching algorithm compares form of a relational graph. In the matching process not 
the parameters of candidate edges for matching. A match only the features and their attributes are evaluated, but 
function results in a high similarity value, when the two also the relationships between nearby features are 
edges belong to a correct match. Each parameter of the considered. In order to find a mapping function between 
edges contributes to the similarity value according to an the images which considers relations between features in 
307