ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision“, Graz, 2002 
  
3. STEREO MATCHING 
Stereo matching (Klette et al., 1998) is an important problem 
with a broad range of applications. Considerable efforts have 
been made to enhance the matching quality and to reduce the 
processing time. Fast algorithms (Gimel'farb, 1999) and also a 
few approaches to parallel and neural algorithms, e.g. 
(Goulermas, Liatsis, 2000), (Pajares, de la Cruz, 2001), exist for 
the case of epipolar geometry but these geometry often is 
fulfilled only approximately. Therefore, methods are needed 
which can be generalized to the non-epipolar case and which 
have real-time processing capability. Here an attempt is made to 
develop such a method basing on the discrete dynamical 
networks (1). To start that research again epipolar geometry is 
used but it is obvious how the algorithm can be generalized to 
the non-epipolar case. 
We consider a left image g;(i,j) and a right image gz(i,j) (i,j = 
0,...,N-1). Corresponding points (i,j) of g; and (ij) of gz on 
epipolar lines j are connected by i= i+s where s(i’yj) is the 
disparity. Here, s(i’y) is assigned to the coordinates of the right 
image, but it is also possible to assign it to the left image or to a 
centered (cyclopean) image. In corresponding points the 
following equation approximately holds: 
gj) ga s. J) (8) 
In most images there are points which are absent in the other 
image (occluded points). Those points (for which (1) of course 
does not hold) must be considered carefully in order to avoid 
mismatch. 
Now, to each pixel (i) of the right image a coordinate x(i ',j), a 
velocity v(i'j), and a mass m are assigned in order to describe 
the motion of such a point. Let (i.,/) be an edge point of the left 
image and (i,j) an edge point of the right image, respectively. 
Then, the edge point in the left image exerts a force K(i,, i, ') 
on the edge point in the right image in order to attract that 
point. We consider that force as an external force. Furthermore, 
on mass point (ij) there can be acting internal forces such as 
the spring type forces Ki, ing(i™-1, i’), Kopring(i +1, i’) and a 
force -yv(i’,j) describing the friction with the background. Other 
internal forces such as friction between neighboring image rows 
j, j£1 can also be included. More general, the forces, here 
denoted as K(i’j, jtk), can also depend on edges and grey 
values in other image rows jk of both images which means a 
coupling of different image rows. 
With those forces Newton's equations are: 
= RER) e 
mii. 
Introducing the velocities V — X , the system of differential 
equations (9) of second order can be converted into a system of 
first order equations 
Xj) w^, j) 
2 (10) 
m j)s -y: vj) KG ik) 
X 
Here, Z — is the state vector of the system. 
y 
: Z zZ 
Now, approximating Z, by fus Zn the system of 
differential equations turns into a system of difference equations 
or discrete time state equations: 
ae st PE v.(r. j) 
Has = (m — At): v (i, j) * K,(, j, j € Kk) 
(11) 
That system which is of type (1) allows to calculate the system 
state z, recursively. The initial conditions are: 
i. s i 
v,{,7)=0 
When that recursive system of equations has reached its final 
(12) 
sate X, i", j ) then the disparity can be calculated 
according to 
S. six (6. (13) 
which is the final shift of X, (i 7 ) from its initial position 
ST. 
The recursive calculation of the disparity according to (11) 
allows the incorporation of some countermeasures against 
ambiguities. In particular, the so-called ordering constraint 
(Klette et al., 1998) can be included: Let 
A,x(i', j) = At-v,(i', j) (14) 
be the increment of X, (i * J ) . Then, the initial order 
X, (+1, A 2X, i 7) of the pixels of the right image can be 
guaranteed if the following limitation of Ax, (i i j ) is used: 
d. 72 f At-v(@,j)>d,/2 
Ax, (i, j) 2 37 4.2 if AC v s j)«-d /2 
AC v, (i^, j) elsewhere 
(15) 
Here, d. — x (i 1j) - x ij), d. — x dj) - x (8-1). 
Conditions such as (15) can be checked easily in each 
step of recursion. 
We come now to the calculation of the forces K. First, it must 
be acknowledged that essential stereo information is only 
present in image regions with significant changes of grey level, 
and especially near edges. Furthermore, in the epipolar 
geometry assumed here only the x — dependence of the grey 
values, i. e. Vyg(i) = g(i,j) - g(i-1,j) is essential. Let's assume 
that there is a step edge between (i,j) and (i-1,j) with |V,g(i,))| 
> threshold. That means that (i,j) belongs to an image segment 
and (i-1,j) to another one. When e. g. such an edge is at the 
border of a roof of a building then often left or right of that edge 
we have occlusion. Then, if the pixel (i,j) has a corresponding 
pixel in the other stereo image this may be not the case for pixel 
(i-1,j) or vice versa. Therefore, both pixels (i.e. pixels left hand 
and right hand of an edge) must be considered separately. They 
can have different disparities or even worse: in one of them 
A - 177