used, as density increases, after a certain limit error also starts to increase concomi-
tantly. Therefore, it is worth calculating a less dense, high-confidence disparity map
and afterwards increasing the density by propagating the correct disparity values. In
this way we achieve better accuracy vs density trade-off than by directly reducing the
reliability threshold and thus increasing density at the expense of higher error. Many
global, dense, disparity calculation methods have built-in mechanisms for propagat-
ing/diffusing disparity [1][17] but sparse methods usually lack this capacity. To the
best of our knowledge there are very few independent propagation methods, apart from
interpolation [14] and diffusion [22], that can be applied as a post-processing step. By
independent we mean that the propagation method does not depend upon the algorithm
used to derive the initial disparity map. This work proposes a new densification method
that is able to arrive at denser and more accurate results than the standard one-stage dis-
parity algorithms such as dynamic programming, block- matching and so on that only
slightly affects the error rate. Since the scheme is based on very simple operations,
it can be considered suitable for efficient implementation. Our method resembles im-
age driven anisotropic diffusion, used for instance by Alvarez et al. [1] in variational
disparity calculation, in the sense that the propagation direction is based on the image
gradient. Instead of using a set of equations for defining the diffusion model as it is
done in [1] our approach (VMP) uses a bank of predefined masks and a voting process
to define the local interactions driving the diffusion process.
2 Method
The first step is to calculate a sparse, high-confidence, stereo map. Many feature-based
disparity calculation methods match edges present in stereo-images, since these can be
considered relatively robust features [8][11]. For the reasons set out in the Introduc-
tion we use here a simplified dynamic programming technique based on image edges
[14]. The rational for using dynamic programming is that it has been shown to be both
computationally efficient [12] and capable of producing highly accurate results [3].
Nevertheless, as mentioned earlier, our densification approach does not depend upon
the method used for producing the initial sparse disparity map. The second step is to
apply voting mask propagation (VMP) for propagating disparity in the direction where
estimations are expected to be similar and to use voting for resolving ambiguities. Lo-
cal support of the voting process is based on directional masks: for each image position
for which disparity is known a mask from a pre-determined bank is chosen, depend-
ing upon the underlying image structure (gradient). The properties of the chosen filter
define how many votes each of the neighborhood positions will receive.
2.1 Propagation direction
Since without further image analysis we cannot be sure of which object an image pixel
for which the disparity is known belongs to, and since we assume that inside objects
disparity changes gradually, image gradient is used as a driving force of the propagation
direction. We assume that two different objects will almost certainly have two different
disparity levels. By propagating in a direction perpendicular to the image gradient we
reduce errors since different objects have varying disparities divided by an edge. This
assumption of local maximum gradient separating different objects is also the basis of
anisotropic diffusion, where diffusion direction is driven by the gradient [22][13]. In
this work we concentrate on the case where the disparities for the edges are known and
2