— 
ves, 199, 
sampling, 
— 1, with 
n of g(z) 
0 
d function 
transform 
ion of its 
() 
derivative 
(6) 
transform 
and higher 
te the leas 
ous signi 
model tk 
(8) 
0) 
Rob Reeves 
where gi (x, y) and g» (v, y) are the image patches to be matched, ho and ^, are radiometric transformation parameters, 
a; and b; are geometric transformation parameters, and ny (x, y) and n»(z, y) are additive noise. 
1 
Using Taylor's theorem to linearize each equation about an initial guess and then subtracting yields 
Ag(r,y) -— dho-dhig(z,y) 4- daog, (v, y) + daizg, (v, y) + dasyg,(x,y) + dbog, (x, y) 
+ dbixgy(x,y) + dbaygy(x, y) -- v(a, y) (10) 
where g, (4, y) and g,(z, y) denote the partial derivatives of 9 (v, y) with respect to x and y, and x and y take on a series of 
discrete values within a match window. This results in a system of equations for the perturbations to the initial radiometric 
and geometric transformation parameters. 
The system of equations can be expressed in matrix form 
L= Ax +v (11) 
with the solution given by in i 
$z(ATA)!A"r (12) 
where @ is the vector of perturbations to the initially chosen transformation parameters that result in a better match 
between the two image patches. Vector v is a vector of noise terms, and A is given by 
A= 11 9(x,94) g.(z,y) 29.(x,9) yg.(z,y) g,(z,y) z9,(z,y) y9,(z,y) (13) 
Since the solution is based around a linear approximation, it can be improved by linearizing around the new solution, and 
re-solving. This is repeated until the solution converges. 
4 LSM IN THE TRANSFORM DOMAIN 
By choosing a suitable ordering system, the images can be expressed as column vectors, and the 2D linear transform as a 
matrix. Equation 11 can then be expressed in the transform domain as, 
TAx +Tv=TL (14) 
where matrix T' is the 2D DCT transform. This can be viewed as defining transform domain .A and L matrices given by 
TA and TL. It has been shown previously that as long as T' is orthogonal, which is the case for the DCT, the solution 
of Equation 12 is unaffected by using the transform domain A and L matrices (Reeves and Kubik, 1998). For typical 
images, the DCT behaves in a similar manner to the Karhunen-Loeve transform, which constructs basis functions in 
order of decreasing variance. In image compression, this fact is used to justify discarding many of the high frequency 
(low variance) coefficients, while maintaining the information important to the structure of the image (Rabbini and Jones, 
1991). This same principle can be extended to image matching. Since the bulk of the image energy appears in the low 
order DCT coefficients, discarding the higher order coefficients should not impair image matching. We can significantly 
reduce the size of the A matrix by transforming each column into the DCT domain, and then omitting the same high 
frequency coefficients from each column. Since the computational effort in the solution of the least squares system 
depends on the size of matrix A” A, this should enable the solution to be computed more quickly, without detriment to 
the quality of the match result. An experimental transform domain algorithm was used to test this hypothesis as outlined 
in the following sections, using the method of Equation 7 to compute the transforms of the columns of the A matrix 
involving partial derivatives. 
5 EXPERIMENTAL PROCEDURE 
A pixel domain least squares matching algorithm was constructed as explained in Sections 3. Estimates for the partial 
derivatives with respect to z and y in constructing the .A matrix were obtained by taking the first differences along rows 
and columns. In resampling between iterations, a bi-linear interpolation (Wang, 1990) was used, using the combined 
Parameters from all iterations to transform the original right image. A transform domain least squares algorithm was then 
constructed. It differed from the previously described algorithm only in that the least squares solution at each iteration was 
conducted in the DCT domain, as described in Section 4. However, rather than using all available transform coefficients to 
construct the transform domain A and L matrices, a subset was selected by taking the first n coefficients, in zig-zag order. 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 763