3. FAST ALGORITHM FOR STEREO CORRELATION 
BASED ON A “SLIDING WINDOW” METHOD 
In this part of the paper the problem of reduction of 
computational time is considered for. the automatic stereo 
matching based on the normalized correlation. 
Let we have two grayscale digital stereo images of 3D scene: 
g(x,y) and g (x,y). Let consider for each pixel from left 
image the rectangle O - [/eff, right]xtop,bottom] of size MxN. 
It is required to find the best corresponded pixels on the right 
image. Standard solution of stereo correspondence problem is 
obtained by means of normalized stereo correlation 
corr(x,y;x,y,) for pixels (x,y) and (x,.v,): 
c—d 
er 6 
e* f ( ) 
where 
a b 
em > » a; *tXypt ve 6x, FX, + y) > 
xz-d yz-b 
a b a b 
d S: Daily *Xx.yp y) SS RT +X,%, +v), 
xz-q yz-b Xz-qyz-b 
2 
a b a b 
2 
e S: > g(x +x, +y)— > > g(x +x, +y) 
xz-a yz-b x--a yz-b 
: 2 
a b a b 
2 
f= à, 3 (X, Xy. *y)- > S e. TX, y) 
|xe-a yz-b xz-ayz-b 
and where (2a+1)x(2b+1) — the size of correlation region. 
For the best matching it is necessary to find: 
| 7 
0 
corr((x,, y, (x, . y, ) 
, 
(x, Ce = argmax 
Ind | SA. 
The key idea of acceleration of calculation for expression (6) is 
the use the "sliding window" algorithm like analogous sliding 
window algorithms for sum accumulation described by Huang 
(Huang, 1983). The essence of this idea consists of storing the 
ready-made column sums and recursive subtracting and adding 
of the appropriate partial sums corresponding to the motion of a 
sliding window along the image row. 
In order to apply this idea to normalized stereo correlation 
computation, let rewrite the expression (6) with the following 
additional notation: 
a b 
$5(X,, 1) 7 X RAE À (x, t x,y, * y)? (8) 
X=-ay=- 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
a b 
C 
sS,(X,.y,) S: S Fix, +X, y, + y)> (9) 
x=-ay=-b 
a b 
5.(x..7 )= > S (x, + x, P, + F)* (10) 
x=-ay=-b 
a b . ( l l ) 
SX. Mo Xps > Ye X, Yı FE (X xy)? 
X=—ay=-h 
where (xj. yj) € [/eff, right] x[top, bottom], 
(*,., y.) left — Ax pax, Fight + Ax, ]x[top— 1, bottom]. 
Then 
corx,, yx, ) = S, (X Y5X Y) 5008 VS Qty.) (12) 
Nip Y) — = = 
Jis, (x, y) sry, )- s. (x.y. )-s (xy, )) 
It is easy to see, (ha s.v). Sn(Xy, Vı)s 
S, (x.y. ), 8 LGSVE,) can be previously computed by 
sliding window algorithm before the main loop is started. 
However, it is not enough for essential acceleration of stereo 
correlation because the computation of §,, jog dee d zz) 
still require Ola-b- Ax -M-N) of operation. To 
accelerate this stage, let transform the formula (11) as follows: 
max 
Sir (xj MI Ax, Ay) = Spy (x; VI XI + Ax, Jt Ay) = 
a b 
> aly +x, y+ V)8, (x; +Ax +x, y; + Ay + y) = 
x=-ay=-b 
a b 
= > uon *x,ypty)g,Qu tx yj t yix Ay), (13) 
xz-ay--b 
where 
SAX + XV, + Y3AX, Ay) = g,. (x, +x+Ax, y, + y + Ay) 
From (13) one can see, that under the fixed AX and Ay 
values 35.(Xj, yj; Ax, Ay). for (xj, yj) eO can be computed 
by the "sliding window" algorithm approximately by 
2(2 * ko - k«)-b- N- M (14) 
of operations. 
Thus, if we change the order of loops by (x,y) and (4x, Ay), and 
use the "sliding window" method, the complexity of this 
algorithm can be estimated as: 
A(2- k, Fk. )-b- NM - b (2k, k, + 1) +3+ dk. +k, +k | N-M -3-2Ax 
0 0 y 
max 
=12(2k, + k. +1)-6-N-M - Ax (15) 
max 
of operations (supposing that Ax. >>1). 
max 
   
    
  
    
   
     
    
    
   
      
    
   
    
   
     
   
     
    
  
    
    
   
   
    
  
   
    
Inter 
So, 
com 
It is 
imp! 
The 
ster 
pho! 
pape 
info 
ofc 
Botl 
of c 
typi 
for : 
REI 
Sibi 
spac 
Spa 
Sen. 
Hua 
Scei