Global minimization of Markov random fields with applications to optical flow

Tom Goldstein; Xavier Bresson; Stan Osher

doi:10.3934/ipi.2012.6.623

Article Contents

2012, Volume 6, Issue 4: 623-644. Doi: 10.3934/ipi.2012.6.623

This issue Previous Article Inverse problems for Jacobi operators III: Mass-spring perturbations of semi-infinite systems Next Article Efficient and accurate computation of spherical mean values at scattered center points

Global minimization of Markov random fields with applications to optical flow

1.
Rice University, Department of Electrical and Computer Engineering, Houston, 77251
2.
City University of Hong Kong, Department of Computer Science, Hong Kong
3.
UCLA, Department of Mathematics, Los Angeles, 90095

Received: August 31, 2011

Revised: May 31, 2012

Published: October 2012

Abstract Related Papers Cited by

Abstract

Many problems in image processing can be posed as non-convex minimization problems. For certain classes of non-convex problems involving scalar-valued functions, it is possible to recast the problem in a convex form using a ``functional lifting'' technique. In this paper, we present a variational functional lifting technique that can be viewed as a generalization of previous works by Pock et. al and Ishikawa. We then generalize this technique to the case of minimization over vector-valued problems, and discuss a condition which allows us to determine when the solution to the convex problem corresponds to a global minimizer. This generalization allows functional lifting to be applied to a wider range of problems then previously considered. Finally, we present a numerical method for solving the convexified problems, and apply the technique to find global minimizers for optical flow image registration.

Keywords:

Mathematics Subject Classification: 46N10, 68U10, 90C26.

Citation:

Related Papers

Cited by

References

[1]	Jean-François Aujol and Antonin Chambolle, Dual norms and image decomposition models, Int. J. Comput. Vision, 63 (2005), 85-104.doi: 10.1007/s11263-005-4948-3.
[2]	S. Baker, D. Scharstein, J. P. Lewis, S. Roth, M. J. Black and R. Szeliski, A database and evaluation methodology for optical flow, in "IEEE 11th International Conference on Computer Vision," Miami, Florida, 2007.
[3]	Rodney J. Baxter, "Exactly Solved Models in Statistical Mechanics," Dover Publications, December, 2007.
[4]	Julian Besag, Spatial interaction and the statistical analysis of lattice systems, Journal of the Royal Statistical Society Series B, 36 (1974), 192-236.
[5]	Julian Besag, On the statistical analysis of dirty pictures, Journal of the Royal Statistical Society Series B, 48 (1986), 259-302.
[6]	Andrew Blake and Andrew Zisserman, "Visual Reconstruction," MIT Press Series in Artificial Intelligence, MIT Press, Cambridge, MA, 1987.
[7]	Yuri Boykov and Gareth Funka-Lea, Graph cuts and efficient N-D image segmentation, Int. J. Comput. Vision, 70 (2006), 109-131.doi: 10.1007/s11263-006-7934-5.
[8]	Yuri Boykov and Vladimir Kolmogorov, An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, IEEE Trans. Pattern Anal. Mach. Intell., 26 (2004), 1124-1137.doi: 10.1109/TPAMI.2004.60.
[9]	Yuri Boykov, Olga Veksler and Ramin Zabih, Fast approximate energy minimization via graph cuts, IEEE Trans. Pattern Anal. Mach. Intell., 23 (2001), 1222-1239.doi: 10.1109/34.969114.
[10]	Y. Y. Boykov and M.-P. Jolly, Interactive graph cuts for optimal boundary region segmentation of objects in N-D images, in "Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference," Vol. 1, (2001), 105-112.
[11]	Xavier Bresson, Selim Esedoġlu, Pierre Vandergheynst, Jean-Philippe Thiran and Stanley Osher, Fast global minimization of the active contour/snake model, Journal of Mathematical Imaging and Vision, 28 (2007), 151-167.doi: 10.1007/s10851-007-0002-0.
[12]	Ethan S. Brown, Tony F. Chan and Xavier Bresson, A Convex Approach for Multi-phase Piecewise Constant Mumford-Shah Image Segmentation, UCLA CAM Report 09-66, July, 2009.
[13]	Andr Bruhn, Joachim Weickert, Timo Kohlberger and Christoph Schnr, Discontinuity-preserving computation of variational optic flow in real-time, in "Scale-Space and PDE Methods in Computer Vision," Lecture Notes in Computer Science, 3459, Springer, (2005), 279-290.
[14]	Antonin Chambolle, An algorithm for mean curvature motion, Interfaces Free Bound, 6 (2004), 195-218.doi: 10.4171/IFB/97.
[15]	Antonin Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20 (2004), 89-97.
[16]	Antonin Chambolle and Thomas Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40 (2011), 120-145.doi: 10.1007/s10851-010-0251-1.
[17]	Tony Chan, Selim Esedoġlu and Mila Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models, SIAM Journal on Applied Mathematics, 66 (2006), 1632-1648.
[18]	Tony F. Chan, Gene H. Golub and Pep Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20 (1999), 1964-1977.doi: 10.1137/S1064827596299767.
[19]	Isaac Cohen, Nonlinear variational method for optical flow computation, in "Proc. Eighth Scandinavian Conference on Image Analysis," Vol. 1, Tromso, Norway, May, (1993), 523-530.
[20]	J Darbon and M Sigelle, A fast and exact algorithm for total variation minimization, IbPRIA, 3522 (2005), 351-359.
[21]	Jérôme Darbon, Global optimization for first order Markov random fields with submodular priors, Discrete Applied Mathematics, June, 2009.
[22]	Jerome Darbon and Marc Sigelle, A fast and exact algorithm for total variation minimization, IbPRIA 2005, 3522 (2005), 351-359.
[23]	Jérôme Darbon and Marc Sigelle, Image restoration with discrete constrained total variation part I: Fast and exact optimization, J. Math. Imaging Vis., 26 (2006), 261-276.doi: 10.1007/s10851-006-8803-0.
[24]	Jérôme Darbon and Marc Sigelle, Image restoration with discrete constrained total variation part II: Levelable functions, convex priors and non-convex cases, J. Math. Imaging Vis., 26 (2006), 277-291.doi: 10.1007/s10851-006-0644-3.
[25]	Q. Duan, E. Angelini, S. Homma and A. Laine, Tracking endocardium using optical flow along iso-value curve, in "Engineering in Medicine and Biology Society, 2006. EMBS '06. 28th Annual International Conference of the IEEE," (2006), 707-710.
[26]	E. Esser, Applications of lagrangian-based alternating direction methods and connections to split Bregman, UCLA CAM technical report 09-31, 2009.
[27]	Ernie Esser, Xiaoqun Zhang and Tony Chan, A general framework for a class of first order primal-dual algorithms for TV minimization, UCLA CAM Report 09-67, 2009.
[28]	Herbert Federer, "Geometric Measure Theory," Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York Inc., New York, 1969.
[29]	L. R. Ford, Jr. and D. R. Fulkerson, Maximal flow through a network, Canadian Journal of Mathematics, 8 (1956), 399-404.doi: 10.4153/CJM-1956-045-5.
[30]	Stuart Geman, Donald Geman, K. Abend, T. J. Harley and L. N. Kanal, Stochastic relaxation, gibbs distributions and the bayesian restoration of images, Journal of Applied Statistics, 20 (1993), 25-62.doi: 10.1080/02664769300000058.
[31]	Guy Gilboa and Stanley Osher, Nonlocal linear image regularization and supervised segmentation, Multiscale Model. Simul., 6 (2007), 595-630.doi: 10.1137/060669358.
[32]	Tom Goldstein and Stanley Osher, The split Bregman method for l1 regularized problems, UCLA CAM Report 08-29, 2008.
[33]	D. M. Greig, B. T. Porteous and A. H. Seheult, Exact maximum a posteriori estimation for binary images, Journal of the Royal Statistics Society, 51 (1989), 271-279.
[34]	N. Hata, A. Nabavi, W. Wells, S. Warfield, R. Kikinis, P. Black and F. Jolesz, Three-dimensional optical flow method for measurement of volumetric brain deformation from intraoperative MR images, J. Comput. Assist. Tomogr., 07 2000.
[35]	F. Heitz and P. Bouthemy, Multimodal estimation of discontinuous optical flow using Markov random fields, IEEE Trans. Pattern Anal. Mach. Intell., 15 (1993), 1217-1232.doi: 10.1109/34.250841.
[36]	Berthold K. P. Horn and Brian G. Schunck, Determining optical flow, Technical report, Massachusetts Institute of Technology, Cambridge, MA, 1980.
[37]	Hiroshi Ishikawa, Exact optimization for Markov random fields with convex priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, 25 (2003), 1333-1336.doi: 10.1109/TPAMI.2003.1233908.
[38]	Satoru Iwata, Lisa Fleischer and Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM, 48 (2000), 761-777.doi: 10.1145/502090.502096.
[39]	Stephen L. Keeling and Wolfgang Ring, Medical image registration and interpolation by optical flow with maximal rigidity, J. Math. Imaging Vis., 23 (2005), 47-65.doi: 10.1007/s10851-005-4967-2.
[40]	S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680.doi: 10.1126/science.220.4598.671.
[41]	Vladimir Kolmogorov and Ramin Zabih, What energy functions can be minimized via graph cuts?, in "Computer Vision - ECCV 2002: 7th European Conference on Computer Vision," Copenhagen, Denmark, May 28-31, 2002, Proceedings, Part III, (2002), 185-208.
[42]	Vladimir Kolmogorov and Ramin Zabih, What energy functions can be minimized via graph cuts, IEEE Trans. Pattern Anal. Mach. Intell., (2004), 147-159.
[43]	R. Malladi, R. Kimmel, D. Adalsteinsson, G. Sapiro, V. Caselles and J. A. Sethian, A geometric approach to segmentation and analysis of 3d medical images, in "MMBIA '96: Proceedings of the 1996 Workshop on Mathematical Methods in Biomedical Image Analysis (MMBIA '96)," IEEE Computer Society, Washington, DC, USA, (1996), 244.doi: 10.1109/MMBIA.1996.534076.
[44]	H. Nagel and W. Enkelmann, An investigation of smoothness constraints for the estimation of displacement vector fields from image sequences, IEEE Trans. Pattern Anal. Mach. Intell., 8 (1986), 565-593.doi: 10.1109/TPAMI.1986.4767833.
[45]	J. P. Oliveira, J. M. Bioucas-Dias and M. Figueiredo, Adaptive total variation image deblurring: A majorization-minimization approach, Signal Process., 89 (2009), 1683-1693.doi: 10.1016/j.sigpro.2009.03.018.
[46]	Stanley Osher, Martin Burger, Donald Goldfarb, Jinjun Xu and Wotao Yin, An iterative regularization method for total variation-based image restoration, MMS, 4 (2005), 460-489.
[47]	J. C. Picard and H. D. Ratliff, Minimum cuts and related problems, Networks, 5 (1975), 357-370.doi: 10.1002/net.3230050405.
[48]	Thomas Pock, Antonin Chambolle, H. Bischof and D. Cremers, A convex relaxation approach for computing minimal partitions, In "IEEE Conference on omputer Vision and Pattern Recognition (CVPR)," Miami, Florida, 2009.doi: 10.1109/CVPR.2009.5206604.
[49]	Thomas Pock, Daniel Cremers, Horst Bischof and Antonin Chambolle, Global solutions of variational models with convex regularization, SIAM J. Imaging Sci., 3 (2010), 1122-1145.
[50]	Thomas Pock, Thomas Schoenemann, Gottfried Graber, Horst Bischof and Daniel Cremers, A convex formulation of continuous multi-label problems, in "ECCV'08: Proceedings of the 10th European Conference on Computer Vision," Springer-Verlag, Berlin, Heidelberg, 2008, 792-805.
[51]	Renfrey B. Potts, Some generalized order-disorder transformations, Proceedings of the Cambridge Philosophical Society, 48 (1952), 106-109.doi: 10.1017/S0305004100027419.
[52]	Marc Proesmans, Luc J. Van Gool, Eric J. Pauwels and André Oosterlinck, Determination of optical flow and its discontinuities using non-linear diffusion, in "ECCV'94: Proceedings of the Third European Conference-Volume II on Computer Vision," Springer-Verlag, London, UK, (1994), 295-304.
[53]	L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica. D., 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[54]	Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Comb. Theory Ser. B, 80 (2000), 346-355.doi: 10.1006/jctb.2000.1989.
[55]	S. Setzer, Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, in "Proceedings of the Second International Conference on Scale Space Methods and Variational Methods in Computer Vision," 2009.doi: 10.1007/978-3-642-02256-2_39.
[56]	E. Strekalovskiy, B. Goldluecke and D. Cremers, Tight convex relaxations for vector-valued labeling problems, in "IEEE International Conference on Computer Vision (ICCV)," IEEE, Nov., (2011), 2328-2335.
[57]	Y. Wang, W. Yin and Y. Zhang, A fast algorithm for image deblurring with total variation regularization, CAAM Technical Reports, 2007.
[58]	Joachim Weickert and Christoph Schnörr, A theoretical framework for convex regularizers in pde-based computation of image motion, Int. J. Comput. Vision, 45 (2001), 245-264.doi: 10.1023/A:1013614317973.
[59]	Mingqiang Zhu and Tony Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, UCLA CAM technical report 08-34, 2008.
[60]	Jie Zhu-Jacquot, Graph cuts segmentation with geometric shape priors for medical images, in "Image Analysis and Interpretation," SSIAI 2008, IEEE Southwest Symposium, March, (2008), 109-112.