Markov Random Field









  1. Introduction/Tutorial

  2. Applications

    1. Image Inpainting
    2. Image Segmentation
  3. Algorithm (Energy Minimization)

    1. Graph Cut

      • ECCV06_tutorial
      • ICCV07_tutorial
      • An Experimental Comparison of Min-Cut_Max-Flow Algorithms for Energy Minimization in Vision
      • Motion Layer Extraction in the Presence of Occlusion Using Graph Cuts
    2. ICM

      • Iterative Conditional Modes
    3. Belief Propagation

      • Also called Max-Product/Min-Sum Algorithm.
      • Comparing the mean field method and belief propagation for approximate inference in MRFs, Weiss Y. To appear in Saad and Opper (ed) Advanced Mean Field Methods. MIT Press. (gzipped postscript 89K)
  4. Library/Open Source

    1. Graph Cut Optimization

    • Max-Flow/Min-Cut
      • Program information: MaxFlow-v3.01.zip, C/C++ source, Ver. 3.01, 2010/01
      • Reference papers: Boykov-Kolmogorov algorithm, B-K algorithm Yuri Boykov and Vladimir Kolmogorov, "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 9, pp. 1124-1137, 2004.
      • Implementated methods: Graph Cut
    • Multi-Label Optimization
      • Program information: gco-v3.0.zip, C/C++ source with Matlab wrapper, Ver. 3.0, 2010/08
      • Reference papers:
        • Y. Boykov, O. Veksler, R. Zabin, "Fast Approximate Energy Minimization via Graph Cuts," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 11, pp. 1222-1239, 2001.
        • Yuri Boykov and Vladimir Kolmogorov, "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 9, pp. 1124-1137, 2004.
        • Andrew Delong · Anton Osokin · Hossam N. Isack · Yuri Boykov, "Fast Approximate Energy Minimization with Label Costs" International Journal of Computer Vision, 2011.
        • Vladimir Kolmogorov, Ramin Zabih, "What Energy Functions Can Be Minimized via Graph Cuts?" IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 147-158, 2004.
      • Implementated methods: Graph Cut
    • Middlebury MRF
      • Program information: MRF16.zip: C/C++ , Ver. 1.6, 2006
      • Reference papers: A Comparative Study of Energy Minimization Methods for Markov Random Fields R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, and C. Rother. In Ninth European Conference on Computer Vision(ECCV 2006), volume 2, pages 19-26, Graz, Austria, May 2006.
      • Implementated methods: ICM, Graph Cut, Max-Product Belief Propagation
    • Misc
      • James Malcom: Graph cut for image segmentation and multi-object tracking, Matlab wrapper witout source code.
  5. Books

    • Markov Random Field Modeling in Image Analysis, S. Z. Li, Springer, 2001.
    • Stochastic Image Processing, C. S. Won and R. M. Gray, Kluwer, 2004.
    • Image Analysis, Random Fields and Dynamic Monte Carlo Methods, - A Mathematical Introduction, G. Winkler, Springer, 1995.
    • Markov Random Fields - Theory and Application, R. Chellappa and A. Jain, Academic Press, 1993.