Dynamic Graph Cuts for Efficient Inference in Markov Random Fields
December 2007 (vol. 29 no. 12)
pp. 2079-2088
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.
[1] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms and Applications. Prentice Hall, 1993.[2] A. Blake, C. Rother, M. Brown, P. Perez, and P.H.S. Torr, “Interactive Image Segmentation Using an Adaptive GMMRF Model,” Proc. European Conf. Computer Vision, vol. 1, pp. 428-441, 2004.[3] E. Boros and P.L. Hammer, “Pseudo-Boolean Optimization,” Discrete Applied Math., vol. 123, nos. 1-3, pp. 155-225, 2002.[4] Y. Boykov and M.P. Jolly, “Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images,” Proc. Int'l Conf. Computer Vision, pp. I: 105-I: 112, 2001.[5] Y. Boykov and V. Kolmogorov, “An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, Sept. 2004.[6] Y. Boykov, O. Veksler, and R. Zabih, “Markov Random Fields with Efficient Approximations,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp. 648-655, 1998.[7] M. Bray, P. Kohli, and P.H.S. Torr, “Posecut: Simultaneous Segmentation and 3D Pose Estimation of Humans Using Dynamic Graph Cuts,” Proc. European Conf. Computer Vision, pp. 642-655, 2006.[8] Y. Chiang and R. Tamassia, “Dynamic Algorithms in Computational Geometry,” Proc. IEEE, special issue on computational geometry, vol. 80, pp. 362-381, 1992.[9] R.F. Cohen and R. Tamassia, “Dynamic Expression Trees and Their Applications,” Proc. Symp. Discrete Algorithms, pp. 52-61, 1991.[10] E.A. Dinic, “Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation,” Soviet Math. Doklady, vol. 11, pp. 1277-1280, 1970.[11] L.R. Ford and D.R. Fulkerson, Flows in Networks. Princeton Univ. Press, 1962.[12] D. Freedman and P. Drineas, “Energy Minimization via Graph Cuts: Settling What Is Possible,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp. 939-946, 2005.[13] G. Gallo, M.D. Grigoriadis, and R.E. Tarjan, “A Fast Parametric Maximum Flow Algorithm and Applications,” SIAM J. Computing, vol. 18, no. 18, pp. 30-55, 1989.[14] D. Greig, B. Porteous, and A. Seheult, “Exact Maximum A Posteriori Estimation for Binary Images,” J. Royal Statistical Soc., B, vol. 51, no. 2, pp. 271-279, 1989.[15] A. Hengel, A. Dick, T. Thormählen, B. Ward, and P.H.S. Torr, “Rapid Interactive Modelling from Video with Graph Cuts,” Proc. Eurographics, 2006.[16] H. Ishikawa, “Exact Optimization for Markov Random Fields with Convex Priors,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1333-1336, Oct. 2003.[17] H. Ishikawa and D. Geiger, “Occlusions, Discontinuities and Epipolar Lines in Stereo,” Proc. European Conf. Computer Vision, pp.232-248, 1998.[18] H. Ishikawa and D. Geiger, “Segmentation by Grouping Junctions,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp.125-131, 1998.[19] O. Juan and Y. Boykov, “Active Graph Cuts,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp. 1023-1029, 2006.[20] P. Kohli and P.H.S. Torr, “Efficiently Solving Dynamic Markov Random Fields Using Graph Cuts,” Proc. Int'l Conf. Computer Vision, pp. 922-929, 2005.[21] P. Kohli and P.H.S. Torr, “Measuring Uncertainty in Graph Cut Solutions: Efficiently Computing Min-Marginal Energies Using Dynamic Graph Cuts,” Proc. European Conf. Computer Vision, pp.30-43, 2006.[22] V. Kolmogorov, “Convergent Tree-Reweighted Message Passing for Energy Minimization,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 28, no. 10, pp. 1568-1583, Oct. 2006.[23] V. Kolmogorov and Y. Boykov, “What Metrics Can Be Approximated by Geo-Cuts, or Global Optimization of Length/Area and Flux,” Proc. Int'l Conf. Computer Vision, pp. 564-571, 2005.[24] V. Kolmogorov and R. Zabih, “Multicamera Scene Reconstruction viaGraph Cuts,” Proc. European Conf. Computer Vision, 2002.[25] V. Kolmogorov and R. Zabih, “What Energy Functions Can Be Minimizedvia Graph Cuts?” IEEE Trans. Pattern Analysis Machine Intelligence, vol. 26, no. 2, pp. 147-159, Feb. 2004.[26] M.P. Kumar, P.H.S. Torr, and A. Zisserman, “Learning Layered Pictorial Structures from Video,” Proc. Indian Conf. Computer Vision, Graphics and Image Processing, pp. 158-163, 2004.[27] M.P. Kumar, P.H.S. Torr, and A. Zisserman, “Obj Cut,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp. 18-25, 2005.[28] A. Raj and R. Zabih, “A Graph Cut Algorithm for Generalized Image Deconvolution,” Proc. Int'l Conf. Computer Vision, 2005.[29] C. Rother, V. Kolmogorov, and A. Blake, “‘Grabcut:’ Interactive Foreground Extraction Using Iterated Graph Cuts,” ACM Trans. Graphics, vol. 23, no. 3, pp. 309-314, 2004.[30] S. Roy and I.J. Cox, “A Maximum-Flow Formulation of the N-Camera Stereo Correspondence Problem,” Proc. Int'l Conf. Computer Vision, pp. 492-502, 1998.[31] M.I. Schlesinger and B. Flach, “Some Solvable Subclasses of Structural Recognition Problems,” Proc. Czech Pattern Recognition Workshop, 2000.[32] D. Snow, P. Viola, and R. Zabih, Exact Voxel Occupancy with Graph Cuts, pp. I: 345-I: 352, 2000.[33] M. Thorup, “Fully-Dynamic Min-Cut,” Proc. Symp. Theory of Computing, pp. 224-230, 2001.[34] M.J. Wainwright, T.S. Jaakkola, and A.S. Willsky, “Map Estimation via Agreement on Trees: Message-Passing and Linear Programming,” Trans. Information Theory, vol. 51, no. 11, pp.3697-3717, 2005.[35] J. Wang, P. Bhat, A. Colburn, M. Agrawala, and M.F. Cohen, “Interactive Video Cutout,” ACM Trans. Graphics, vol. 24, no. 3, pp. 585-594, 2005.[36] J. Xiao and M. Shah, “Motion Layer Extraction in the Presence of Occlusion Using Graph Cut,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp. 972-979, 2004.[37] S.Z. Li, Markov Random Field Modeling in Computer Vision. Springer, 2001.[38] R. Zabih and V. Kolmogorov, “Spatially Coherent Clustering Using Graph Cuts,” Proc. Int'l Conf. Computer Vision and Pattern Recognition, pp. 437-444, 2004.
Index Terms:
Energy Minimization, Markov Random Fields, Dynamic graph cuts, Maximum flow, st-mincut, Video segmentation
Citation:
Pushmeet Kohli, Philip H. S. Torr, "Dynamic Graph Cuts for Efficient Inference in Markov Random Fields," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 12, pp. 2079-2088, June 2007, doi:10.1109/TPAMI.2007.1128
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb