equation is: 
Um g»(1 — di)(1 — d;)dzi,; + gadı(1 — d2)dzi j+1+ 
92(1 — di )dadxi+1,j + gad1d2dm 141,741 — Ag 
(2) 
where Ag = gı (x, y) — g2(x+x°,y) and 9° is the differential 
in z-direction in right epipolar line and dz;; is the correction 
of original parallax z°. 
Assuming all the matching points are located on a grid sized 
by n1 X n2 (ni is rows and nz is columns). The constraint 
smoothness between the grid nodes is required in MLSM (first 
or second order differentials of parallaxes). The observations, 
normals and solution of MLSM can be expressed in the matrix 
form: 
VzAdX-L,P 
(ATPA)dX = ATPL (3) 
dX = (ATPA)-‘ATPL 
where A is the design matrix, dX is the vector of correction 
parallaxes (ninz x 1) and P is the weight matrix. 
Likewise MLSM can be performed in object space using the 
similar equations as in image space [4, 5, 20]. 
The main reason for the very low computing efficiency of the 
conventional MLSM is the solution of the large size normals. 
For example, the rank of the normals is 10,000 if the matching 
grid is 100 by 100, it is hard to be solved for the general 
purpose computer. Some techniques are used for improving 
the speed of the conventional MLSM such as multiresolution, 
multigrid approach [6], the average CPU time improvement 
was 60%, corresponding 2 3 node points per second. Besides 
it, the Cholesky triangle decomposition technique is used, 
and the speed of image matching is about 6 node points per 
second (platform SGI 4D/25). In the next sections we will 
discuss the array relaxation algorithm which can be applied 
for MLSM to considerably improve the matching efficiency. 
3 ARMLSM UNDER THE UNIFORM WEIGHT 
MODEL 
3.1 Introduction of array algebra 
Array Algebra was established by Rauhala in 1968, and it has 
become the powerful tools to deal with multi-dimensional 
data since 1968. The basic theory of array algebra could 
be found in [9]. The application of array algebra in image 
matching can be traced back to 1977 [10], when Rauhala 
combined the array algebra with finite element method, and 
applied the array relaxation technique in global image cor- 
relation. This thought is actually different in approach but 
equally satisfactory in result combining with Helava, Wrobel, 
Rosenholm, Ebner, Heipke and Barnard's algorithms of global 
image matching. And the capability of array relaxation makes 
Rauhala's method more practicable. 
3.2 ARMLSM under the uniform weight model 
Assuming z? in equation 1 is the node point parallax and need 
not be interpolated from other node points. The linearised 
form of equation 1 is as follows: 
v=gdz—Ag Ag-2gm-g (4) 
The expression of the correction of z? parallax after nor- 
malling equation 4: 
de =) 0:09] 7 (5) 
Equation 5 is the simplest case of the single point LSM, where 
>; means the sum in a small window around the node point. 
If the matching grid is n; x n2, then three matrices dX, A, L 
denote the three array of all node points’ parallaxes cor- 
rections, grey differentials and reflection differences, respec- 
tively: 
dX11 dX12 +. dX1in, 
dX21 dX22 $ vs dX2n4 
dX = ; : ; 
dXn,1 dXn,2 1 s dXnına 
R gai 9212 us Gain, 
9221 9222 re go2n2 
A= ; ; | (6) 
L Gan, 1 J2n12 vt Dongs 
[.. gus A gia c nno; 
Agi Age ++ An, 
L= ; : : 
L Agn,1 Agn,2 s Agn, na 
  
and the array expression of MLSM is: 
V=AxdX-L (7) 
where * means elementwise array multiplication. 
In equation 7 the relationship between node points has not 
been considered yet, so fictitious equations are also needed 
here. Assuming z is the true parallaxes, its initial value is 
2°, the correction is dz. Firstly the second order differential 
constraint is considered: 
Tit1,j = 2%ij + Tit1,; = 0 (8) 
Tij-1 —2%ij + Tij4+1 =0 
The array expression of equation 12 is: 
Vy = (1 + BY(X° + dX), s 
Vz = (X? -- dX)(2I2 -- B3), pa 
where the matrix ranks of subscript 1 and 2 are n; and ny, 
respectively. I is an unit matrix, B is a Toeplitz matrix, and 
p1,p2 are the weights in y, directions. 
B-STAS,STS8 2 SST-[ 
S — {sis} = (~1)'sin(ijr/(n + 1))\/(n + 72 
À = {Au} = —2 cos(ix/(n +1)), 1, j = 1,2,---,n 
(10) 
The Toeplitz matrix B's feature and orthogonal matrix can 
be derived through the finite element transformation [11] (see 
equation 10), and an approximation is applied near the edges 
of the net grid inside the matrix B. 
The array expression of ARMLSM under the second order 
differential constraint is: 
VzA*dX-L 
V, zz (2f + B1)(X° + dX), p1 (11) 
V, — (X? c dX)(2I2 -- B2), p2 
978 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
    
    
    
    
    
   
   
   
      
  
      
    
     
  
   
   
  
   
    
   
   
  
  
    
    
  
   
  
  
  
  
  
   
   
   
  
    
   
   
     
    
     
    
In 
firs 
wh 
wh 
en 
Be 
tio 
art 
Af 
su 
int 
11 ml 
N; = 
th 
an