MATCHING IN 2-D AND 3-D 
R. Nevatia 
Institute for Robotics and Intelligent Systems 
University of Southern California 
Los Angeles, Ca 90089-0273 
KEY WORDS: Image Matching, Feature Matching, Scene Registration 
PURPOSE: 
This paper discusses issues and methods for matching in 2-D and 3-D. Several factors that affect the complexity of the task and 
the choice of the appropriate matching methodology . These factors include task characteristics such as whether the input is 
iconic or symbolic, 2-D or 3-D, the scene characteristics and the constraints from prior knowledge. Choices to be made consist 
of the representation level at which the matching is to be performed, whether it is in 2-D or 3-D, whether it is local or global, 
and the matching technique itself. The paper describes some general considerations which are then illustrated by two classes of 
specif problems, first being the problem of scene registration, the second being that of matching for depth estimation. 
1. INTRODUCTION 
Matching is of central importance for many image processing 
and understanding tasks. The process of object recognition 
essentially consists of matching stored object models with 
models derived from images. Process of change detection 
and map updating requires matching descriptions derived 
from new data with descriptions (maps or models) that have 
been constructed from analysis of earlier data. Extraction of 
3-D information from a pair (or sequence) of images requires 
matching of corresponding (conjugate) points. 
The complexity of the matching task and the appropriate 
strategy will depend on several factors listed below: 
a) Iconic or Symbolic: Is the task to match entities in the 
image domain ((it iconic]), such as in stereo analysis, or to 
match an image with abstract models/ maps symbolic such as 
for change detection, navigation or object recognition? 
Certain kinds of methods, such as area correlation have no 
direct analog for symbolic matching. Note that even iconic 
matching may be performed by first extracting symbolic 
descriptions from images. 
b) 2-D or 3-D input: The entities to be matched may 
represent 2-D or 3-D information, thus giving rise to four 
possible matching combinations. Images are usually 2-D 
567 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
though 3-D (or what some may call 2-1/2 D) is becoming 
increasingly available. Maps are often 2-D but more complex 
models of the scene as may be found in a GIS can be 3-D. 
When the objects to be matched are not of the same 
dimensionality, we need to compute a transformation 
between the two. Note that 3-D matching may be applicable 
even if we are trying to match 2-D images, as the underlying 
scene may be 3-D and and it may be necessary to make this 
3-D structure explicit (as in stereo analysis). 
€) Scene Characteristics: The observed scene content can 
vary from natural terrain to highly structured urban and 
suburban environments. Different matching techniques may 
be more appropriate for these different environments. In 
general, structured environments can be naturally described 
by abstract geometric shape whereas natural terrain may be 
better characterized by texture. 
d) Constraints from prior knowledge: Complexity of the 
matching task can depend greatly on what constraints can be 
placed, say from the knowledge of camera geometry. For 
example, in stereo analysis, we can think of the task of 
computing the epipolar geometry or of utilizing given 
epipolar geometry for depth extraction. 
In the following, we first examine some common issues 
related to matching under these varying conditions. Then, we 
IAM Med quit ie. X