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

1.5.2.1 Correlation-Based Blockmatching Stereo Vision Algorithms

Correlation-based blockmatching stereo algorithms rely on a determination of the
similarity S between image regions located on corresponding epipolar lines with

C I 1 V s (u, v) ,I 2 V s u d(u,v),v ,

= −

S(u 1 ,u 2 ) (1.102)

where I 1 is the intensity image 1, I 2 is the intensity image 2, d(u,v) is the dispar-
ity, and V s is a vector of pixels in a spatial neighbourhood of the pixel situated at
(u, v) in image 1 and of the pixel situated at (u − d(u,v),v) in image 2. An early
description of this basic principle is provided by Horn ( 1986 ). As examples of the
function C , Vincent and Laganière ( 2001 ) describe the variance-normalised cross-
correlation and the average squared difference correlation. Franke and Joos ( 2000 )
rely on the sum of squared differences and the sum of absolute differences to express
the similarity, which allows for a computationally efficient similarity estimation.
A broad overview of correlation-based stereo methods is provided by Faugeras et
al. ( 2012 ). Their presentation especially emphasises the aspect of real-time imple-
mentation of such algorithms using special hardware, allowing an integration into
mobile robotic systems.
According to the algorithm suggested by Franke and Joos ( 2000 ), the image re-
gions which display a sufficient amount of texture are extracted with an interest
operator, e.g. a Sobel detector for vertical edges. In a second step, point correspon-
dences are established at pixel accuracy along corresponding epipolar lines by deter-
mining the optimum of the similarity measure. A hierarchical correspondence anal-
ysis at different resolution levels may significantly decrease the processing time. In
a third step, the inferred integer disparity values can be refined to subpixel accuracy
based on an interpolation of the measured similarity values by fitting a parabola to
the local neighbourhood of the optimum.
Blockmatching algorithms are computationally efficient and thus favourably
used in real-time vision systems. However, it is pointed out by Horn ( 1986 ) that the
depth maps generated by such methods tend to be inaccurate for surfaces not orthog-
onal to the optical axes, where pixels with different associated depths comprise a
correlation window. Similarly, Hirschmüller et al. ( 2002 ) state that abrupt depth dis-
continuities at the borders of objects appear diffuse in the depth map. Hirschmüller
( 2001 ) and Hirschmüller et al. ( 2002 ) propose a method which aims at correct-
ing or decreasing the effects of depth discontinuities due to object borders. A large
correlation window is replaced by a configuration of smaller, possibly overlapping
windows, where windows that generate inconsistent similarity values are neglected.
The correlation windows are bisected, and the correlation values obtained from the
resulting partial windows are analysed in order to obtain refined disparity values
associated with object borders. Only correspondences which pass a left-right con-
sistency check are retained. It is shown experimentally by Hirschmüller et al. ( 2002 )
that the proposed method yields a clearly improved depth map when compared to
standard correlation-based stereo.