The International Archives of the Photogrammetry. Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B7. Beijing 2008 
1066 
Limited experience of experimental DEM generation using the gradient cross correlation with line search suggests that incorporating 
a quadratic line search with Model-I often improves the convergence and leads to a higher matching correlation, but requires some 
additional computing time. Given that editing a DEM requires considerable operator intervention, it may be desirable to ensure the 
best possible matching, at the expense of increased computing time. 
1. INTRODUCTION 
Matching pixels in two images is a fundamental operation in 
image rectification and DEM generation. 
The standard approach for area matching for two images to the 
nearest pixel maximises the cross-correlation coefficient when 
the second image is shifted systematically relative to the first 
over a regular grid (Ackermann, 1984). 
Ideally, the matching should allow for offsets in the target 
image, and scaling and rotation. Offsets allow for sub-pixel 
shifts in the two images, while scaling is necessary when 
matching images from different sensors (e.g. Landsat TM, 
Landsat MSS) and rotation allows the matching between 
rectified and un-rectified images. 
The need to carry out the correlation matching to sub-pixel 
accuracy lead to a number of authors considering so-called least 
squares matching, including Forstner, 1982; Ackermann, 1984; 
Gruen, 1985; Rosenholm; 1987; Norvelle, 1992 and Zhaltov 
and Sibiryakov, 1997. 
The essence of least squares matching is to determine offset, 
scaling and rotation parameters to produce interpolated grey- 
level values for the second image which match as closely as 
possible the grey-level values for the first image. This is 
achieved by choosing the parameters to minimise the sum of 
squared differences between the grey-level values for the first 
image and the interpolated grey-level values for the second 
image. The parameters are estimated by iterative least squares 
after linearising by a standard Taylor expansion (Gruen, 1985). 
An affine transformation is usually adopted to determine the 
predicted line and pixel coordinates for the second image 
(Gruen, 1985; Rosenholm, 1987). Rosenholm has also 
suggested including parameters to compensate for differences in 
the grey-level contrast between the two images. 
This paper gives details of an implementation of sub-pixel 
matching using the normalised cross-correlation coefficient 
formation as the objective function, and allowing for offsets, 
scaling and rotation. The adoption of cross-correlation as the 
objective function automatically allows for a possible linear 
radiometric transformation between the two images. The 
implementation uses first and second derivatives to estimate 
these parameters efficiently. 
gradient cross correlation and LSM for least squares cross 
matching. 
2. GRADIENT CROSS CORRELATION (GCC) 
The formulation of the cross correlation coefficient is as: 
_ C l2 
~gl) 2 y^.(g2 ~8 2 ) 2 Vc„C 2 2 
where g t ,g 2 denote the left and right image intensity values, 
g,,g 2 denote the left and right image average intensity values 
within the left and right patches, C n ,C 22 ,C l2 denote the left and 
right image variances and covariance, respectively. 
An affine transformation to calculate the line and pixel in the 
second image as a function of six parameters can be written as: 
[ x = x 0 + a + Sx ■ cos(Rx) ■ x + Sx • sin(/?;c) • y 
[y = y 0 +b-Sy- sin(Ry) ■ x + Sy • cos (Ry) ■ y 
where x 0 ,y 0 denote the pixel and line coordinates for the best 
whole-pixel match on the second image; a,b denote the pixel 
and line offset or shift; Sx,Sy denote the pixel and line 
scaling; Rx, Ry denote the pixel and line rotation angles. 
The full model in (1) involves six parameters, which are usually 
re-parameterised as: 
fa, = Sx ■ cos(/?Jc),a 2 = Sx ■ sin(/?x) 
\b t = Sy ■ sin (Ry),b 2 = Sy • cos (Ry) 
The formulation in (1) is adopted here, as it leads to a more 
natural interpretation of the resulting parameters, especially 
when matching un-rectified and rectified satellite images. 
In the approach adopted here, bilinear interpolation is used to 
calculate the grey values of the second image at the predicted 
line and pixel coordinates: 
f dx = x 0 + a + Sx ■ cos (Rx) ■ x + Sx ■ sin(/?jc) • y - int(x) 
[dy = y 0 + b - Sy ■ sin(Ry) ■ x + Sy ■ cos (Ry) ■ y - int(y) 
g = (1 - dx)( 1 - dy)g.j + dx( 1 - dy)g iJ+t 
+ (1 - dx)dyg MJ + dxdyg Mj+t 
Section 2 presents the details of the proposed gradient cross 
correlation method, including the gradient vector and the matrix 
of second derivatives. Section 2 also outlines the calculation of 
the interpolated grey-level values for the second image and how 
to estimate parameters. Section 3 shows the equivalence of 
least squares matching and gradient cross correlation. Sections 
4 and 5 discuss the implementation and present some results. 
Finally Section 6 gives some conclusions and discussions and 
future work. 
For the sake of convenience, the following abbreviations are 
used to represent the different matching methods: GCC for 
The first-order derivatives of the grey-level value g with respect 
to image coordinates (x, y) and the gradients are given as 
follows: 
k = 8,j«-8,j+dyg< 
'% = 8 M j-g,j +dx '8« 
8d 8ij 8 1 8M,j 8m.j 
The first-order derivatives of the grey-level value g with respect 
to a,Sx,Rx,b,Sy,Ry are given as follows: