Graph based algorithms for scene reconstruction from two and more views

• [KZG] Generalized Multi-camera Scene Reconstruction Using Graph Cuts. ([abstract] [.pdf])
  Vladimir Kolmogorov, Ramin Zabih and Steven Gortler.
  To appear in Fourth International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), July 2003.
  
• [KZ1] Multi-camera Scene Reconstruction via Graph Cuts. ([abstract] [.pdf] [.ps.gz])
  Vladimir Kolmogorov and Ramin Zabih.
  In European Conference on Computer Vision (ECCV), May 2002 (best paper award).
  
• [KZ2] Computing Visual Correspondence with Occlusions using Graph Cuts. ([abstract] [.ps.gz])
  Vladimir Kolmogorov and Ramin Zabih.
  In International Conference on Computer Vision (ICCV), July 2001.
  Also available as Cornell Technical Report.
  

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.

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

Our results:

KZ1 algorithm (with occlusions computed)	KZ1 algorithm	KZ1 algorithm (computed from 5 views)

KZ2 algorithm	KZ2 algorithm (with occlusions filled)

Other results from [SS]:

Graph Cuts [BVZ]	Belief Propagation [SSZ]

References: