\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Global minimization of Markov random fields with applications to optical flow

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: 46N10, 68U10, 90C26.

    Citation:

    \begin{equation} \\ \end{equation}
  • [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.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(190) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return