Fast MRF Optimization with Application to Depth Reconstruction

Qifeng Chen Vladlen Koltun
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014


We describe a simple and fast algorithm for optimizing Markov random fields over images. The algorithm performs block coordinate descent by optimally updating a horizontal or vertical line in each step. While the algorithm is not as accurate as state-of-the-art MRF solvers on traditional benchmark problems, it is trivially parallelizable and produces competitive results in a fraction of a second. As an application, we develop an approach to increasing the accuracy of consumer depth cameras. The presented algorithm enables high-resolution MRF optimization at multiple frames per second and substantially increases the accuracy of the produced range images.


Supplementary material
Code for fast MRF optimization (Section 2)
Code for depth reconstruction (Section 4)
Ground-truth 3D models (Section 5.1)
Ground-truth 3D models without holes (thanks to Benjamin Ummenhofer)
Test data for quantitative evaluation of depth reconstruction (Section 5.1)

Updated base pattern (updated on 10 March, 2019)
For the udpated data, there are three base speckle patterns I captured at different ranges, "base.mat" for short range, "base_mid.mat" for mid-range, and "base_long.mat" for long range. These patterns for the types of IR images without black rows. For the base speckle patterns I put on the project website, they are for the type with black rows. You can run test.m in Windows to get the cost volume stored in "table?.mat". I visualize a row of cost volume and it looks good to me (see table1_visualization.png). I did not notice there are two types of IR images at the beginning of the project, so I accumulate two types of IR images over time. Sorry for the confusion.

More data (updated on 10 March, 2019)
For each of the 5 objects, I captured totally 36 views. I also captured a few indoor images at Stanford. They are put in the folder "extra.There are totally 5*36+32=212 images.

After publication we discovered that block coordinate descent on the primal MRF objective was also discussed in the following paper:
Kelm, B.M.; Mueller, N.; Menze, B.H.; Hamprecht, F.A.,
"Bayesian Estimation of Smooth Parameter Maps for Dynamic Contrast-Enhanced MR Images with Block-ICM,"
Computer Vision and Pattern Recognition Workshop, 2006. CVPRW '06.