Global interactions in random field models: A potential function ensuring connectedness

S. Nowozin, C. Lampert, SIAM Journal on Imaging Sciences 3 (2010) 1048–1074.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Nowozin, Sebastian; Lampert, ChristophIST Austria
Abstract
Markov random field (MRF) models, including conditional random field models, are popular in computer vision. However, in order to be computationally tractable, they are limited to incorporating only local interactions and cannot model global properties such as connectedness, which is a potentially useful high-level prior for object segmentation. In this work, we overcome this limitation by deriving a potential function that forces the output labeling to be connected and that can naturally be used in the framework of recent maximum a posteriori (MAP)-MRF linear program (LP) relaxations. Using techniques from polyhedral combinatorics, we show that a provably strong approximation to the MAP solution of the resulting MRF can still be found efficiently by solving a sequence of max-flow problems. The efficiency of the inference procedure also allows us to learn the parameters of an MRF with global connectivity potentials by means of a cutting plane algorithm. We experimentally evaluate our algorithm on both synthetic data and on the challenging image segmentation task of the PASCAL Visual Object Classes 2008 data set. We show that in both cases the addition of a connectedness prior significantly reduces the segmentation error.
Publishing Year
Date Published
2010-12-21
Journal Title
SIAM Journal on Imaging Sciences
Acknowledgement
This work was funded in part by the EU CLASS project, IST 027978. This work was also supported in part by the IST Programme of the European Community under the PASCAL Network of Excellence, IST-2002-506778.
Volume
3
Issue
4 (Special Section on Optimization in Imaging Sciences)
Page
1048 - 1074
IST-REx-ID

Cite this

Nowozin S, Lampert C. Global interactions in random field models: A potential function ensuring connectedness. SIAM Journal on Imaging Sciences. 2010;3(4 (Special Section on Optimization in Imaging Sciences)):1048-1074. doi:10.1137/090752614
Nowozin, S., & Lampert, C. (2010). Global interactions in random field models: A potential function ensuring connectedness. SIAM Journal on Imaging Sciences, 3(4 (Special Section on Optimization in Imaging Sciences)), 1048–1074. https://doi.org/10.1137/090752614
Nowozin, Sebastian, and Christoph Lampert. “Global Interactions in Random Field Models: A Potential Function Ensuring Connectedness.” SIAM Journal on Imaging Sciences 3, no. 4 (Special Section on Optimization in Imaging Sciences) (2010): 1048–74. https://doi.org/10.1137/090752614.
S. Nowozin and C. Lampert, “Global interactions in random field models: A potential function ensuring connectedness,” SIAM Journal on Imaging Sciences, vol. 3, no. 4 (Special Section on Optimization in Imaging Sciences), pp. 1048–1074, 2010.
Nowozin S, Lampert C. 2010. Global interactions in random field models: A potential function ensuring connectedness. SIAM Journal on Imaging Sciences. 3(4 (Special Section on Optimization in Imaging Sciences)), 1048–1074.
Nowozin, Sebastian, and Christoph Lampert. “Global Interactions in Random Field Models: A Potential Function Ensuring Connectedness.” SIAM Journal on Imaging Sciences, vol. 3, no. 4 (Special Section on Optimization in Imaging Sciences), Society for Industrial and Applied Mathematics , 2010, pp. 1048–74, doi:10.1137/090752614.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar