  The rapid development of 3D technology and computer vision applications have
motivated a thrust of methodologies for depth acquisition and estimation.
However, most existing hardware and software methods have limited performance
due to poor depth precision, low resolution and high computational cost. In
this paper, we present a computationally efficient method to recover dense
depth maps from sparse measurements. We make three contributions. First, we
provide empirical evidence that depth maps can be encoded much more sparsely
than natural images by using common dictionaries such as wavelets and
contourlets. We also show that a combined wavelet-contourlet dictionary
achieves better performance than using either dictionary alone. Second, we
propose an alternating direction method of multipliers (ADMM) to achieve fast
reconstruction. A multi-scale warm start procedure is proposed to speed up the
convergence. Third, we propose a two-stage randomized sampling scheme to
optimally choose the sampling locations, thus maximizing the reconstruction
performance for any given sampling budget. Experimental results show that the
proposed method produces high quality dense depth estimates, and is robust to
noisy measurements. Applications to real data in stereo matching are
demonstrated.
