e. Recalage
Congres IS-
28 of Photo-
sion III, vo-
n line detec-
P, Adelaïde,
tches. Com-
1986.
AN IMAGE MATCHING SCHEME USING A HYBRID FEATURE- AND AREA BASED APPROACH
Nick van der Merwe and Heinz Rüther
Department of Surveying and Geodetic Engineering
University of Cape Town
South Africa
ruther@engfac.uct.ac.za
nvdmerwe@csir.co.za
Commision V, Working Group 3
KEY WORDS: Correlation, Extraction, Matching, Edge, Feature, Feature Matching Algorithms, Feature Extraction Algo-
rithms, Automatic Relative Orientation
ABSTRACT
This paper introduces a hybrid image matching scheme that combines aspects of Feature Based Matching (FBM) with Area
Based Matching (ABM). Line features are extracted from the images using edge detection followed by line following. These
line features are classified using a descriptor function, the dó(s) plot. The results of the feature classification determine
which features are considered to be suitable matching candidates. Matching feature candidates are matched in a novel, two-
step matching process. In the first step the matching probabilities are found by calculating the normalized cross-correlations
between the signature functions of the reference and candidate features. In the second step these matching probabilities are
used in conjunction with the feature topology to verify feature matches. The results of the feature matching process gives a
sparse point field of matching feature centre-of-mass points, which are used to calculate the initial relative orientation. This
orientation information is used to find more matching features and to subsequently update the relative orientation. The final,
high accuracy relative orientation is calculated from sub-pixel matched corners of matching feature pairs. In the final step the
matched features, matching corner points and the relative orientation information is combined to match points on the feature
boundaries.
1 INTRODUCTION
In the field of image matching, research has tended to treat
area-based and feature-based matching as alternate tech-
niques. In this paper, a hybrid image matching technique
is presented that incorporates aspects of both feature- and
area based matching without any prior knowledge of the im-
age orientation parameters. À coarse-to-fine approach is used
throughout the matching and subsequent relative orientation
calculation. Feature matching is used to drastically reduce
the search-space for corresponding points, and the results of
the feature matching stage are used to calculate an initial
estimate of the relative orientation. Once the initial relative
orientation has been determined the relative orientation is re-
fined using a combination of feature- and area based matching
and the epipolar conditions. The final point matches on the
matched feature outlines are also obtained in this way.
One of the major strengths of the feature matching algo-
rithm presented here is its use of not only the local structure
of a feature, but also the spatial relations between a feature
and its neighbours. Schenk et a/[17] presented a method for
matching line-features using ¢(s) plots. Horaud and Skordas
were one of the first groups to recognize the importance of
not only the local structure of a line feature but also the rela-
tionship between line features and their surrounding features
[13]. Hellwich and Faig improve on the relational matching
scheme presented by Horaud and Skordas by extending it to
curved lines and avoiding the use of epipolar constraints [11]
[12]. One of the first formulations of the image matching
solution as a combination between area based matching and
feature based matching was by Cochran and Medioni [3], who
use image pyramids that are resampled in epipolar geometry
to perform a coarse-to-fine match.
This paper will describe the image matching steps of feature
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
extraction, feature classification, feature matching, relative
orientation calculation and finally the matching of points on
the feature outlines. The main emphasis of this paper will be
on the feature matching step, which involves a novel, two-
stage matching algorithm that incorporates both the local
geometry and topology of line features.
2 FEATURE EXTRACTION
Line features are extracted from the original greyscale images
through edge detection with subsequent line following. Once
the pixel-level line features have been extracted, the feature
boundaries are recalculated to the sub-pixel level.
The edge detector used is the Canny edge detector [2], which
calculates the gradient of the input signal with Gaussian
smoothing as an integral part of the operator. The level of
smoothing is determined by the c of the Gaussian function.
Edge pixels (edgels) are linked together using an edge-linking
algorithm that is similar to chaincodes [6], with enhancements
to predict the locus of the next linking pixel and to handle
gaps in the edge chain.
The edgels of the pixel-level line features are recalculated
to the sub-pixel level using a preservation-of-moments-based
edge detector (Tabatabai et a/ [19]).
The steps of feature extraction and feature classification are
described in more detail in a previous paper by the authors
[20].
3 FEATURE CLASSIFICATION
Features are classified using a descriptor function, the dó(s)
function, which is the first-derivative of the ¢(s) function.
The @(s) function plots the tangential direction of a curve
