Graph based algorithms for scene reconstruction from two and more views


Note that algorithms in [KZ1] and [KZ2] are special cases of a more general algorithm described in [KZG]. This general algorithm uses an energy function with two different smoothness terms. If the first term is set to zero, then the algorithm reduces to [KZ2]; if the second term is set to zero, then it reduces to [KZ1].


An implementation of three algorithms - [KZ1] (for two views), [KZ2] and [BVZ] is here.

Experimental Results

Below are results for several stereo algorithms on the famous "Head" dataset from the University of Tsukuba, Japan. Brigher intensities correspond to closer depths for objects in the scene. The algorithms included are two our methods (multicamera scene reconstruction [KZ1] and stereo with occlusions [KZ2]) and two other methods [BVZ,SSZ] used in the recent evaluation of stereo algorithms by Scharstein and Szeliski [SS]. According to this evaluation the belief propagation method [SSZ] is the best performer on this dataset in terms of error statistics (as of December 14, 2002). Note that this statistics does not include occluded pixels so it's not directly applicable to algorithms computing occlusions (e.g. [KZ1, KZ2]).

All results shown have been computed using two images, except for the last result of [KZ1] which has been computed using 5 images. Red pixels correspond to occluded pixels (which are visible in the left camera, but not in the right). Note that KZ1 algorithm can be used for computing occlusions as well since it produces depth maps for both the left and the right images.

Tsukuba dataset:

left image ground truth with occlusions ground truth
Left Image Ground Truth
(with occlusions)
Ground Truth

Our results:

KZ1 with occlusions KZ1 KZ1 - 5 cameras
KZ1 algorithm
(with occlusions computed)
KZ1 algorithm KZ1 algorithm
(computed from 5 views)
KZ2 with occlusions KZ2
KZ2 algorithm KZ2 algorithm
(with occlusions filled)

Other results from [SS]:

graph cuts [4] belief propagation [5]
Graph Cuts [BVZ] Belief Propagation [SSZ]


[SS] D. Scharstein and R. Szeliski. A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms. IJCV, April-June 2002.
[BVZ] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. PAMI, November 2001.
[SSZ] J. Sun, H. Y. Shum, and N. N. Zheng. Stereo matching using belief propagation. ECCV 2002.

Back to Main Page