Dynamic Graph Cuts for Efficient Inference in Markov Random Fields
- 5 November 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 29 (12) , 2079-2088
- https://doi.org/10.1109/tpami.2007.1128
Abstract
In this paper, we present a fast new fully dynamic algorithm for the st-mincut/max-flow problem. We show how this algorithm can be used to efficiently compute MAP solutions for certain dynamically changing MRF models in computer vision such as image segmentation. Specifically, given the solution of the max-flow problem on a graph, the dynamic algorithm efficiently computes the maximum flow in a modified version of the graph. The time taken by it is roughly proportional to the total amount of change in the edge weights of the graph. Our experiments show that, when the number of changes in the graph is small, the dynamic algorithm is significantly faster than the best known static graph cut algorithm. We test the performance of our algorithm on one particular problem: the object-background segmentation problem for video. It should be noted that the application of our algorithm is not limited to the above problem, the algorithm is generic and can be used to yield similar improvements in many other cases that involve dynamic change.Keywords
This publication has 24 references indexed in Scilit:
- Convergent Tree-Reweighted Message Passing for Energy MinimizationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2006
- OBJ CUTPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Efficiently solving dynamic Markov random fields using graph cutsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- What metrics can be approximated by geo-cuts, or global optimization of length/area and fluxPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- A graph cut algorithm for generalized image deconvolutionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Spatially coherent clustering using graph cutsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- "GrabCut"ACM Transactions on Graphics, 2004
- What energy functions can be minimized via graph cuts?Published by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Exact optimization for markov random fields with convex priorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A Fast Parametric Maximum Flow Algorithm and ApplicationsSIAM Journal on Computing, 1989