Xiunguang Zhou 
  
NON-LINEAR SCALE AND ORIENTATION FREE CORRELATION MATCHING ALGORITHM 
BASED ON EDGE CORRESPONDENCE 
Xiuguang Zhou’, Egon Dorrer 
“Environmental System Research Institute (ESRI) Inc. 
Redlands, Ca 92373, USA 
xzhou@esri.com 
"Munich Bundeswehr University 
Institute for Phototgrammetry and Cartography 
D-85577 Neubiberg, Germany 
egon.dorrer ? unibw-muenchen.de 
KEY WORDS: Photogrammetry, Remote Sensing, Image Matching, Image Stereo, DEM Generation 
ABSTRACT 
A novel image matching algorithm is presented in this paper. One significant property of this algorithm is: free of large 
non-linear scale difference and orientation difference between left and right. The algorithm tries to match every pixel in 
the image pair to provide a very detailed matched point set for generating a very good quality DEM. The matching 
approach, which combines feature based and area based matching methods, consists sub-algorithms of edge extraction, 
edge description, edge matching, edge geometry constraint cross-correlation matching and Least Square Matching. The 
well-known From-Coarse-to-Fine matching approach is adopted. A Wavelet Transform was applied to generate image 
pyramids, extract edges and improve the cross-correlation. 
1 INTRODUCTION 
Stereo image matching is the key problem of automatic DEM generation. It is also one of the basic objectives of 
computer vision, photogrammetry and remote sensing. A large number of digital image matching algorithms have been 
proposed in digital photogrammetry and its related areas. The matching algorithms are usually classified into three 
classes: 
- Signal matching (area based image matching); 
- Feature matching (attribute based image matching); 
- Combination of signal and feature matching. 
In signal matching (area based matching), intensity values of the pixels in the selected window are taken into account in 
order to measure the disparities between two overlapping images. The well known cross-correlation algorithm takes the 
minimized disparity of the search area as the corresponding match pairs by measuring the maximization of correlation 
coefficients (Barnea and Silverman, 1972; Hannah, 1989). Another well-known technique Least Squares Matching 
(LSM) attempts to match windows of pixels by minimizing the differences of their gray values (Fórstner, 1982; 
Ackermann, 1984; Grün, 1985; Rosenholm, 1986). 
In feature matching (attribute based image matching), the predefined common features or attributes (normally are 
points, lines and areas) are detected in the conjugate windows. Similarity check and additional techniques, such as 
relaxation or robust statistics and dynamic programming, are employed for matching (Fórstner, 1986; Papanikolaou and 
Derenyi, 1988; Ackermann and Hahn, 1991; Cucka and Rosenfeld, 1992; Murtagh, 1992). Also graph theory is used to 
describe the relations of the features in matching (Shapiro and Haralick, 1987). 
Both area based and feature based matching have their advantages and disadvantages. Though LSM takes the 
radiometric and geometric differences into account to obtain very accurate correlation, it also requires quite accurate 
approximations for the corresponding image patches (e. g., to be accurate within 1—2 pixels). Usually, it is not easy to 
meet such requirements. Cross-correlation is an often used algorithm to get these initial approximations. Unfortunately, 
cross-correlation does not work properly in case where the stereo images contain larger geometric differences (i. c., 
large and nonlinear scale difference or large and nonlinear orientation difference or both). In order to handle the 
  
1054 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 
gt 
SC 
to 
ar 
ar 
al 
a