Triangulation-Based Approaches to Three-Dimensional Scene Reconstruction - 3D Computer Vision: Efficient Methods and Applications - page 64

pared to the correlation-based real-time stereo algorithm described by Franke and
Joos ( 2000 ), which does not make use of a reference image, the disparity values are
more accurate and less noisy (Fig. 1.21 b). In Fig. 1.21 a the CBS algorithm is ap-
plied to a scene displaying a ball of 10 cm diameter and painted in the same colour
as the floor, therefore appearing as a small circle only eight pixels in diameter in the
stereo images. This very difficult object is detected by means of its shading contrast
only.

1.5.2.3 Dense Stereo Vision Algorithms

Correlation-based blockmatching and feature-based stereo vision algorithms usu-
ally generate sparse depth maps, i.e. depth information is only derived for parts of
the scene in which a sufficient amount of texture is observed, such that enough in-
formation is available to achieve a meaningful comparison between image windows
along corresponding epipolar lines. In contrast, stereo vision algorithms which gen-
erate a depth value for each image pixel are termed dense stereo vision algorithms.
An early dense stereo vision approach by Horn ( 1986 ) relies on the direct compari-
son of pixel grey values along corresponding epipolar lines instead of a comparison
between image windows or local features. Since the intensity-based criterion alone
leads to a highly ambiguous solution, a smooth depth map is assumed, i.e. there are
no large differences between the disparity values assigned to neighbouring pixels.
This line of thought leads to the minimisation of the error term

∇

2 d(u,v) 2

λ I 1 u d(u,v)/ 2 ,v − I 2 u d(u,v)/ 2 ,v 2 ,

e = + + −

u,v

(1.115)

2 d(u,v) denotes the Laplace operator applied
to the disparity map—at this point, Horn ( 1986 ) states that using the first instead of
the second derivative of the disparity in the first term of ( 1.115 ) would lead to a too
smooth solution. Based on the Euler equation of ( 1.115 ), a differential equation for
d(u,v) of fourth order in u and v is derived and solved numerically.
Another stereo vision algorithm that constructs dense depth maps is based on
dynamic programming (Cox et al., 1996 ). It makes use of the ordering constraint
which requires that for opaque surfaces the order of neighbouring point correspon-
dences on two corresponding epipolar lines is always preserved. Cox et al. ( 1996 )
assume that if two pixels correspond to the same scene point, the distribution of the
intensity difference with respect to all mutually corresponding pixels is Gaussian.
A maximum likelihood criterion then defines an overall cost function which is min-
imised by the dynamic programming algorithm. While in the approach suggested
by Cox et al. ( 1996 ) each epipolar line is processed independently, the graph cut
or maximum flow method optimises the solution globally (Roy and Cox, 1998 ). In-
stead of the ordering constraint, a more general constraint termed 'local coherence
constraint' is introduced by Roy and Cox ( 1998 ), where it is assumed that the dis-
parity values are always similar in the neighbourhood of a given point independent

∇

where λ is a weight parameter and