Sparse Reconstruction of Depth Data: Representation, Algorithm, and Sampling

Lee-Kang Liu, Stanley H. Chan, Truong Q. NguyenarXiv 2014 · OpenReview

TL;DR

This paper introduces a novel framework for reconstructing dense depth maps from sparse measurements, addressing the limitations of existing hardware and software methods. By leveraging the inherent sparsity of depth data in wavelet and contourlet domains, and employing an efficient ADMM-based reconstruction algorithm with a smart sampling strategy, the authors achieve high-quality depth maps with significantly reduced computational cost and sampling requirements.

What Problem Does This Paper Address?

Acquiring high-resolution, precise depth information is crucial for many 3D technologies and computer vision applications. Current methods either rely on expensive hardware (like LiDAR or time-of-flight cameras) with slow acquisition times and limited resolution, or use computational approaches like stereo matching that are sensitive to environmental factors and often require dense feature correspondences. This paper tackles the challenge of obtaining accurate dense depth maps efficiently, particularly when only sparse depth measurements are available, which is a common scenario in many real-world applications.

Methods

The paper presents three main contributions:

  1. Sparse Representation: They demonstrate that depth maps can be represented much more sparsely than natural images using wavelet and contourlet dictionaries. A combined wavelet-contourlet dictionary further enhances this representation. This sparsity is key to enabling reconstruction from limited data.
  2. Efficient Reconstruction Algorithm: The authors propose an Alternating Direction Method of Multipliers (ADMM) algorithm for depth map reconstruction. A novel multi-scale warm-start procedure is introduced to significantly speed up convergence. ADMM is chosen for its ability to handle the optimization problem efficiently.
  3. Optimal Sampling Scheme: A two-stage randomized sampling strategy is developed to intelligently select sampling locations. This scheme aims to maximize reconstruction performance for a given sampling budget by prioritizing areas with significant depth gradients. The first stage uses a uniform random sample, and the second stage uses the pilot estimate from the first stage to guide more informed sampling, further improved by PCA on color image gradients.

Datasets

The authors evaluate their method on:

  • Synthetic Data: A synthetic gray-scaled image with a triangle overlapping an ellipse was used to test dictionary performance.
  • Middlebury Dataset: This dataset, containing ground truth disparities, was used to compare reconstruction algorithms under various sampling ratios.
  • Real Data: A stereo video sequence from the "Newspaper" dataset and a sequence captured by a custom stereo system were used to demonstrate the algorithm's performance on real-world data.

Key Insights and Ideas

  • Depth Data is Inherently Sparse: Unlike natural images, depth maps exhibit a much sparser structure when represented in wavelet or contourlet domains. This fundamental property is the bedrock of their reconstruction approach.
  • Combined Dictionaries are Better: A combination of wavelet and contourlet dictionaries provides superior representation for depth maps compared to using either alone, especially for capturing edge information.
  • ADMM for Speed: The ADMM algorithm, coupled with a multi-scale warm-start, offers a significant speedup in convergence compared to traditional subgradient methods, making real-time or near-real-time reconstruction feasible.
  • Gradient-Guided Sampling is Crucial: Prioritizing sampling in regions with high depth gradients is vital for maximizing reconstruction quality from sparse data. Their two-stage randomized sampling scheme, especially when enhanced with PCA on color image gradients, effectively achieves this.
  • Robustness to Noise: The proposed method demonstrates robustness to additive Gaussian noise, suggesting its potential for real-world applications where sensor noise is a concern.

Key Results

  • Improved Reconstruction Quality: The proposed "Proposed WT+CT 2-Stage" method consistently outperforms other methods (including subgradient-based approaches and bicubic interpolation) in terms of PSNR and percentage of bad pixels across various datasets and sampling ratios.
  • Significant PSNR Gains: For example, on the "Art" dataset, increasing the sampling ratio from 5% to 25% resulted in an 18 dB PSNR improvement for their method, compared to only 3 dB for bicubic interpolation.
  • Faster Convergence: The ADMM algorithm with multiscale warm-start converges significantly faster than subgradient methods. For a 20% sampling ratio, their multiscale ADMM reached steady state in about 20 seconds, while the subgradient algorithm took over 90 seconds.
  • Sampling Strategy Impact: The proposed two-stage sampling strategy, especially when improved with PCA, yielded substantial PSNR gains (up to 3.76 dB) over simpler sampling methods like uniform grids.

Limitations and Future Work

  • Parameter Tuning: While the paper provides typical parameter values, optimal parameters can still vary for specific problems. The authors suggest that their chosen parameters are robust across a wide range of problems.
  • Oracle Sampling: The "Oracle Random Sampling Scheme" relies on knowing the ground truth gradients, which is not practical. This section serves to demonstrate the theoretical potential of gradient-guided sampling.
  • Future Work: The authors suggest extending their methods to space-time data volumes to further improve consistency and reconstruction quality, particularly for dynamic scenes. They also note that their framework is applicable to many depth data processing tasks, including acquisition, compression, and enhancement.

Summary updated

Abstract

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.
BibTeX
@misc{liu2014sparse,
  author = {Lee-Kang Liu and Stanley H. Chan and Truong Q. Nguyen},
  title = {{Sparse Reconstruction of Depth Data: Representation, Algorithm, and Sampling}},
  year = {2014},
  eprint = {1407.3840},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1407.3840},
}
Figure