Abstract: Low-resolution depth maps captured by consumer-level depth cameras are usually highly contaminated by noise and quantization error. In this paper, we consider the captured depth values to be samples from a high-resolution depth map which is sparsely approximated by linear combinations of atoms from an over-complete dictionary. By further combining a high-resolution color image of the same scene with the corrupted depth samples, we divide the scene into regions with depths changing smoothly. For every such region, our method infers the sparse coefficients in a Bayesian optimization framework with the depth samples as constraints, and then reconstructs the high-resolution depth map. It was shown that our method outperforms previous approaches in both the quantifying assessment experiments on the Middlebury dataset and qualitative comparisons on real scene reconstructions.