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: