Fast MRF Optimization with Application to Depth Reconstruction

We describe a simple and fast algorithm for optimizing Markov random fields over images. The algorithm performs block coordinate descent by optimally updating a horizon-tal 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 pro-duces competitive results in a fraction of a second. As an application, we develop an approach to increasing the ac-curacy of consumer depth cameras. The presented algo-rithm enables high-resolution MRF optimization at multiple frames per second and substantially increases the accuracy of the produced range images. 1