S. M. Aji and R. J. Mceliece, The generalized distributive law, IEEE Transactions on Information Theory, vol.46, issue.2, pp.325-343, 2000.
DOI : 10.1109/18.825794

K. Alahari, P. Kohli, and P. H. Torr, Reduce, reuse & recycle: Efficiently solving multi-label MRFs, 2008 IEEE Conference on Computer Vision and Pattern Recognition, 2008.
DOI : 10.1109/CVPR.2008.4587402

M. Asem, A. A. Ali, and G. L. Farag, Gimel'farb. Optimizing binary MRFs with higher order cliques, European Conference on Computer Vision (ECCV), 2008.

A. Amir, T. E. Amini, R. C. Weymouth, and . Jain, Using dynamic programming for solving variational problems in vision, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol.12, issue.9, pp.855-867, 1990.

M. Andriluka, S. Roth, and B. Schiele, Pictorial structures revisited: People detection and articulated pose estimation, 2009 IEEE Conference on Computer Vision and Pattern Recognition, 2009.
DOI : 10.1109/CVPR.2009.5206754

D. Anguelov, P. Srinivasan, H. Pang, D. Koller, S. Thrun et al., The correlated correspondence algorithm for unsupervised registration of nonrigid surfaces, Advances in Neural Information Processing Systems (NIPS), 2004.

A. Ayvaci and S. Soatto, Motion segmentation with occlusions on the superpixel graph, 2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops, 2009.
DOI : 10.1109/ICCVW.2009.5457630

D. Batra, A. C. Gallagher, D. Parikh, and T. Chen, Beyond trees: MRF inference via outer-planar decomposition, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2010.
DOI : 10.1109/CVPR.2010.5539951

D. Batra and P. Kohli, Making the right moves: Guiding alpha-expansion using local primal-dual gaps, CVPR 2011, 2011.
DOI : 10.1109/CVPR.2011.5995449

R. Bellman, Dynamic Programming, 1957.

D. P. Bertsekas, Nonlinear Programming (Second Edition), Athena Scientific, 1999.

J. Besag, Spatial Interaction and the Statistical Analysis of Lattice Systems, Journal of the Royal Statistical Society. Series B (Methodological), vol.36, issue.2, pp.192-236, 1974.

J. Besag, On the Statistical Analysis of Dirty Pictures Julian Besag (with discussion), Journal of the Royal Statistical Society (Series B), vol.48, issue.3, pp.259-302, 1986.

A. Besbes, N. Komodakis, G. Langs, and N. Paragios, Shape priors and discrete MRFs for knowledge-based segmentation, 2009 IEEE Conference on Computer Vision and Pattern Recognition, 2009.
DOI : 10.1109/CVPR.2009.5206649
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.380.195

C. M. Bishop, Neural networks for pattern recognition, 1995.

C. M. Bishop, Pattern recognition and machine learning (Information Science and Statistics), 2006.

A. Blake and A. Zisserman, Visual Reconstruction, 1987.

G. Borgefors, Distance transformations in digital images Computer vision, graphics, and image processing, pp.344-371, 1986.

E. Boros, P. L. Hammer, and X. Sun, Network flows and minimization of quadratic pseudo-Boolean functions, 1991.

E. Boros, P. L. Hammer, and G. Tavares, Preprocessing of unconstrained quadratic binary optimization, 2006.

E. Boros and P. L. Hammer, Pseudo-Boolean optimization, Discrete Applied Mathematics, vol.123, issue.1-3, pp.155-225, 2002.
DOI : 10.1016/S0166-218X(01)00341-9
URL : https://hal.archives-ouvertes.fr/hal-01150533

S. Boyd and L. Vandenberghe, Convex Optimization, 2004.

Y. Boykov and G. Funka-lea, Graph Cuts and Efficient N-D Image Segmentation, International Journal of Computer Vision, vol.18, issue.9, pp.109-131, 2006.
DOI : 10.1007/s11263-006-7934-5
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.657

Y. Boykov and M. Jolly, Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images, Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, 2001.
DOI : 10.1109/ICCV.2001.937505

Y. Boykov and V. Kolmogorov, Computing geodesics and minimal surfaces via graph cuts, Proceedings Ninth IEEE International Conference on Computer Vision, 2003.
DOI : 10.1109/ICCV.2003.1238310
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.123.6433

Y. Boykov, O. Veksler, and R. Zabih, Markov random fields with efficient approximations, Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231), 1998.
DOI : 10.1109/CVPR.1998.698673
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.3857

Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, International Conference on Computer Vision (ICCV), 1999.
DOI : 10.1109/iccv.1999.791245
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6806

Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.23, issue.11, pp.1222-1239, 2001.
DOI : 10.1109/34.969114
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6806

P. Carr and R. Hartley, Minimizing energy functions on 4-connected lattices using elimination, 2009 IEEE 12th International Conference on Computer Vision, 2009.
DOI : 10.1109/ICCV.2009.5459450

A. Chambolle, Total Variation Minimization and a Class of Binary MRF Models, International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), 2005.
DOI : 10.1007/11585978_10

F. Tony, J. Chan, and . Shen, Image processing and analysis: variational, PDE, wavelet, and stochastic methods, Society for Industrial and Applied Mathematics, 2005.

P. B. Chou, P. R. Cooper, M. J. Swain, C. M. Brown, and L. E. Wixson, Probabilistic network inference for cooperative high and low level vision, Markov Random Fields: Theory and Applications, pp.211-243, 1993.

B. Paul, C. M. Chou, and . Brown, The theory and practice of Bayesian image labeling, International Journal of Computer Vision (IJCV), vol.4, issue.3, pp.185-210, 1990.

H. Thomas, C. E. Cormen, R. L. Leiserson, C. Rivest, and . Stein, Introduction to algorithms, 2009.

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The complexity of multiway cuts (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing , STOC '92, 1992.
DOI : 10.1145/129712.129736

A. P. Dawid, Applications of a general propagation algorithm for probabilistic expert systems, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp.25-36, 1992.
DOI : 10.1007/BF01890546

M. Egmont-petersen, D. De-ridderb, and H. Handelsc, Image processing with neural networks???a review, Pattern Recognition, vol.35, issue.10, pp.2279-2301, 2002.
DOI : 10.1016/S0031-3203(01)00178-9

M. Eichner and V. Ferrari, Better appearance models for pictorial structures, Procedings of the British Machine Vision Conference 2009, 2009.
DOI : 10.5244/C.23.3

H. W. Engl, M. Hanke, and A. Neubauer, Regularization of inverse problems, 1996.

P. F. Felzenszwalb, R. B. Girshick, D. Mcallester, and D. Ramanan, Object Detection with Discriminatively Trained Part-Based Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.32, issue.9, pp.1627-1645, 2010.
DOI : 10.1109/TPAMI.2009.167

F. Pedro, D. P. Felzenszwalb, and . Huttenlocher, Pictorial Structures for Object Recognition, International Journal of Computer Vision (IJCV), vol.61, issue.1, pp.55-79, 2005.

F. Pedro, D. P. Felzenszwalb, and . Huttenlocher, Efficient Belief Propagation for Early Vision, International Journal of Computer Vision (IJCV), vol.70, issue.1, pp.41-54, 2006.

F. Pedro, J. J. Felzenszwalb, and . Mcauley, Fast Inference with Min-Sum Matrix Product, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol.33, issue.12, pp.2549-2554, 2011.

F. Pedro, R. Felzenszwalb, and . Zabih, Dynamic programming and graph algorithms in computer vision, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol.33, issue.4, pp.721-740, 2011.

M. A. Fischler and R. A. Elschlager, The Representation and Matching of Pictorial Structures, IEEE Transactions on Computers, vol.22, issue.1, pp.67-92, 1973.
DOI : 10.1109/T-C.1973.223602

A. Fix, A. Gruber, E. Boros, and R. Zabih, A graph cut algorithm for higher-order Markov Random Fields, 2011 International Conference on Computer Vision, 2011.
DOI : 10.1109/ICCV.2011.6126347

D. Freedman and P. Drineas, Energy Minimization via Graph Cuts: Settling What is Possible, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), 2005.
DOI : 10.1109/CVPR.2005.143

W. T. Freeman, T. R. Jones, and E. C. Pasztor, Example-based super-resolution, IEEE Computer Graphics and Applications, vol.22, issue.2, pp.56-65, 2002.
DOI : 10.1109/38.988747

W. T. Freeman, E. C. Pasztor, and O. T. Carmichael, Learning low-level vision, Proceedings of the Seventh IEEE International Conference on Computer Vision, pp.25-47, 2000.
DOI : 10.1109/ICCV.1999.790414

B. J. Frey, Graphical models for machine learning and digital communication, 1998.

J. Brendan, D. J. Frey, and . Mackay, A revolution: Belief propagation in graphs with cycles, Advances in Neural Information Processing Systems (NIPS), 1998.

B. Fulkerson, A. Vedaldi, and S. Soatto, Class segmentation and object localization with superpixel neighborhoods, 2009 IEEE 12th International Conference on Computer Vision, 2009.
DOI : 10.1109/ICCV.2009.5459175

C. Andrew, D. Gallagher, D. Batra, and . Parikh, Inference for Order Reduction in Markov Random Fields, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011.

D. Geiger, T. Verma, and J. Pearl, Identifying independence in bayesian networks, Networks, vol.9, issue.5, pp.507-534, 1990.
DOI : 10.1002/net.3230200504

S. Geman and D. Geman, Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol.6, issue.6, pp.721-741, 1984.

A. Globerson and T. Jaakkola, Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations, Advances in Neural Information Processing Systems (NIPS), 2007.

B. Glocker, T. H. Heibel, N. Navab, P. Kohli, and C. Rother, TriangleFlow: Optical Flow with Triangulation-Based Higher-Order Likelihoods, European Conference on Computer Vision (ECCV), 2010.
DOI : 10.1007/978-3-642-15558-1_20

B. Glocker, N. Komodakis, G. Tziritas, N. Navab, and N. Paragios, Dense image registration through MRFs and efficient linear programming???, Medical Image Analysis, vol.12, issue.6, pp.731-741, 2008.
DOI : 10.1016/j.media.2008.03.006

B. Glocker, N. Paragios, N. Komodakis, G. Tziritas, and N. Navab, Optical flow estimation with uncertainties through dynamic MRFs, 2008 IEEE Conference on Computer Vision and Pattern Recognition, 2008.
DOI : 10.1109/CVPR.2008.4587562
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.205.6681

A. V. Goldberg and R. E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM, vol.35, issue.4, pp.921-940, 1988.
DOI : 10.1145/48014.61051

D. M. Greig, B. T. Porteous, and A. H. Seheult, Exact Maximum A Posteriori Estimation for Binary Images, Journal of the Royal Statistical Society (Series B), vol.51, issue.2, pp.271-279, 1989.

L. Gui, J. Thiran, and N. Paragios, Cooperative Object Segmentation and Behavior Inference in??Image Sequences, International Journal of Computer Vision, vol.127, issue.3, pp.146-162, 2008.
DOI : 10.1007/s11263-008-0146-4

P. L. Hammer, P. Hansen, and B. Simeone, Roof duality, complementation and persistency in quadratic 0???1 optimization, Mathematical Programming, pp.121-155, 1984.
DOI : 10.1007/BF02612354

J. M. Hammersley and P. Clifford, Markov fields on finite graphs and lattices. unpublished, 1971.

X. He, R. S. Zemel, and M. A. Carreira-perpinan, Multiscale conditional random fields for image labeling, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2004.

T. Heimann, H. Meinzer, ]. F. Heitz, and P. Bouthemy, Statistical shape models for 3D medical image segmentation: a review Multimodal estimation of discontinuous optical flow using Markov random fields, Medical Image Analysis IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol.13, issue.412, pp.543-63, 1993.

A. Hervieu, P. Bouthemy, and J. Cadre, A HMM-Based Method for Recognizing Dynamic Video Contents from Trajectories, 2007 IEEE International Conference on Image Processing, 2007.
DOI : 10.1109/ICIP.2007.4380072

M. Isard, PAMPAS: real-valued graphical models for computer vision, 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings., 2003.
DOI : 10.1109/CVPR.2003.1211410
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.151

H. Ishikawa, Exact optimization for markov random fields with convex priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.25, issue.10, pp.1333-1336, 2003.
DOI : 10.1109/TPAMI.2003.1233908

H. Ishikawa, Higher-order clique reduction in binary graph cut, 2009 IEEE Conference on Computer Vision and Pattern Recognition, 2009.
DOI : 10.1109/CVPR.2009.5206689

H. Ishikawa, Transformation of General Binary MRF Minimization to the First-Order Case, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.33, issue.6, pp.1234-1249, 2011.
DOI : 10.1109/TPAMI.2010.91

H. Ishikawa and D. Geiger, Segmentation by grouping junctions, Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231), 1998.
DOI : 10.1109/CVPR.1998.698598

E. Ising, Beitrag zur theorie des ferromagnetismus. Zeitschrift fur Physik, pp.253-258, 1925.
DOI : 10.1007/bf02980577

V. Jojic, S. Gould, and D. Koller, Accelerated dual decomposition for MAP inference, International Conference on Machine Learning (ICML), 2010.

I. Michael and . Jordan, An introduction to probabilistic graphical models. In preparation, 2007.

O. Juan and Y. Boykov, Active Graph Cuts, 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Volume 1 (CVPR'06), 2006.
DOI : 10.1109/CVPR.2006.47

R. E. Kalman, A New Approach to Linear Filtering and Prediction Problems, Journal of Basic Engineering, vol.82, issue.1, pp.35-45, 1960.
DOI : 10.1115/1.3662552

E. Kalogerakis, A. Hertzmann, and K. Singh, Learning 3d mesh segmentation and labeling, ACM Transactions on Graphics (TOG), vol.29102, issue.4, pp.1-10212, 2010.
DOI : 10.1145/1833349.1778839
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.179.640

J. Hendrik-kappes, S. Schmidt, and C. Schnorr, MRF Inference by k-Fan Decomposition and Tight Lagrangian Relaxation, European Conference on Computer Vision (ECCV), 2010.

M. Kass, A. Witkin, and D. Terzopoulos, Snakes: Active contour models, International Journal of Computer Vision, vol.5, issue.6035, pp.321-331, 1988.
DOI : 10.1007/BF00133570
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.124.5318

J. Kim and J. W. Woods, Spatio-temporal adaptive 3-D Kalman filter for video, IEEE Transactions on Image Processing (TIP), vol.6, issue.3, pp.414-424, 1997.

U. Kjae-rulff, Inference in bayesian networks using nested junction trees, Proceedings of the NATO Advanced Study Institute on Learning in graphical models, 1998.

P. Kohli, L. Ladicky, and P. H. Torr, Robust higher order potentials for enforcing label consistency, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2008.

P. Kohli, L. Ladický, and P. H. Torr, Robust Higher Order Potentials for Enforcing Label Consistency, International Journal of Computer Vision, vol.24, issue.3, pp.302-324, 2009.
DOI : 10.1007/s11263-008-0202-0

P. Kohli and M. P. Kumar, Energy minimization for linear envelope MRFs, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2010.
DOI : 10.1109/CVPR.2010.5539858
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.188.999

P. Kohli, M. P. Kumar, and P. H. Torr, P3 & Beyond: Solving Energies with Higher Order Cliques, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
DOI : 10.1109/CVPR.2007.383204
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.119.2624

P. Kohli, M. P. Kumar, and P. H. Torr, P3 & beyond: move making algorithms for solving higher order functions, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), issue.9, pp.311645-1656, 2009.

P. Kohli, J. Rihan, M. Bray, and P. H. Torr, Simultaneous Segmentation and Pose Estimation of Humans Using??Dynamic Graph Cuts, International Journal of Computer Vision, vol.57, issue.3, pp.285-298, 2008.
DOI : 10.1007/s11263-007-0120-6

P. Kohli, A. Shekhovtsov, C. Rother, V. Kolmogorov, and P. H. Torr, On partial optimality in multi-label MRFs, Proceedings of the 25th international conference on Machine learning, ICML '08, 2008.
DOI : 10.1145/1390156.1390217

P. Kohli and P. H. Torr, Efficiently solving dynamic Markov random fields using graph cuts, Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, 2005.
DOI : 10.1109/ICCV.2005.81

P. Kohli and P. H. Torr, Dynamic Graph Cuts for Efficient Inference in Markov Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.12, pp.2079-2088, 2007.
DOI : 10.1109/TPAMI.2007.1128

P. Kohli and P. H. Torr, Measuring uncertainty in graph cut solutions, Computer Vision and Image Understanding, vol.112, issue.1, pp.30-38, 2008.
DOI : 10.1016/j.cviu.2008.07.002

D. Koller and N. Friedman, Probabilistic graphical models: Principles and techniques, 2009.

V. Kolmogorov, Convergent Tree-Reweighted Message Passing for Energy Minimization, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, issue.10, pp.1568-1583, 2006.
DOI : 10.1109/TPAMI.2006.200
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.2409

V. Kolmogorov and C. Rother, Minimizing Nonsubmodular Functions with Graph Cuts-A Review, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.7, pp.1274-1279, 2007.
DOI : 10.1109/TPAMI.2007.1031

V. Kolmogorov and M. J. Wainwright, On the optimality of tree-reweighted maxproduct message-passing, Conference on Uncertainty in Artificial Intelligence (UAI), 2005.

V. Kolmogorov and R. Zabih, What energy functions can be minimized via graph cuts?, European Conference on Computer Vision (ECCV), pp.147-159, 2002.
DOI : 10.1109/TPAMI.2004.1262177
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.113.1823

N. Komodakis, Towards More Efficient and Effective LP-Based Algorithms for MRF Optimization, European Conference on Computer Vision (ECCV), 2010.
DOI : 10.1007/978-3-642-15552-9_38

N. Komodakis and N. Paragios, Beyond Loose LP-Relaxations: Optimizing MRFs by Repairing Cycles, European Conference on Computer Vision (ECCV), 2008.
DOI : 10.1007/978-3-540-88690-7_60
URL : https://hal.archives-ouvertes.fr/hal-00918715

N. Komodakis and N. Paragios, Beyond pairwise energies: Efficient optimization for higher-order MRFs, 2009 IEEE Conference on Computer Vision and Pattern Recognition, 2009.
DOI : 10.1109/CVPR.2009.5206846

N. Komodakis, N. Paragios, and G. Tziritas, MRF Optimization via Dual Decomposition: Message-Passing Revisited, 2007 IEEE 11th International Conference on Computer Vision, 2007.
DOI : 10.1109/ICCV.2007.4408890

N. Komodakis, N. Paragios, and G. Tziritas, MRF Energy Minimization and Beyond via Dual Decomposition, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.33, issue.3, pp.531-552, 2011.
DOI : 10.1109/TPAMI.2010.108
URL : https://hal.archives-ouvertes.fr/hal-00856311

N. Komodakis and G. Tziritas, Approximate Labeling via Graph Cuts Based on Linear Programming, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.8, pp.1436-1453, 2007.
DOI : 10.1109/TPAMI.2007.1061

N. Komodakis, G. Tziritas, and N. Paragios, Fast, Approximately Optimal Solutions for Single and Dynamic MRFs, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
DOI : 10.1109/CVPR.2007.383095

N. Komodakis, G. Tziritas, and N. Paragios, Performance vs computational efficiency for optimizing single and dynamic MRFs: Setting the state of the art with primal-dual strategies, Computer Vision and Image Understanding, vol.112, issue.1, pp.14-29, 2008.
DOI : 10.1016/j.cviu.2008.06.007
URL : https://hal.archives-ouvertes.fr/hal-00918699

V. K. Koval and M. I. Schlesinger, Dvumernoe programmirovanie v zadachakh analiza izobrazheniy (Two-dimensional programming in image analysis problems), pp.149-168, 1976.

V. A. Kovalevsky and V. K. Koval, A diffusion algorithm for decreasing energy of max-sum labeling problem, Glushkov Institute Of Cybernetics, 1975.

P. Krähenbühl and V. Koltun, Efficient inference in fully connected crfs with gaussian edge potentials, Advances in Neural Information Processing Systems (NIPS), 2011.

R. Frank, B. J. Kschischang, H. Frey, and . Loeliger, Factor graphs and the sum-product algorithm, IEEE Transactions on Information Theory, vol.47, issue.2, pp.498-519, 2001.

S. Kumar and M. Hebert, Discriminative fields for modeling spatial dependencies in natural images, Advances in Neural Information Processing Systems (NIPS), 2004.

D. Kwon, K. Lee, D. Yun, and S. U. Lee, Nonrigid Image Registration Using Dynamic Higher-Order MRF Model, European Conference on Computer Vision (ECCV), 2008.
DOI : 10.1007/978-3-540-88682-2_29

L. Ladicky, C. Russell, P. Kohli, and P. H. Torr, Associative hierarchical CRFs for object class image segmentation, 2009 IEEE 12th International Conference on Computer Vision, 2009.
DOI : 10.1109/ICCV.2009.5459248

L. Ladicky, C. Russell, P. Kohli, and P. H. Torr, Graph Cut Based Inference with Co-occurrence Statistics, European Conference on Computer Vision (ECCV), 2010.
DOI : 10.1007/978-3-642-15555-0_18

L. Ladicky, C. Russell, P. Kohli, and P. H. Torr, Inference Methods for CRFs with Co-occurrence Statistics, International Journal of Computer Vision, vol.103, issue.2, 2011.
DOI : 10.1007/s11263-012-0583-y

L. Ladicky, P. Sturgess, K. Alahari, C. Russell, and P. H. Torr, What, Where and How Many? Combining Object Detectors and CRFs, European Conference on Computer Vision (ECCV), 2010.
DOI : 10.1007/978-3-642-15561-1_31
URL : https://hal.archives-ouvertes.fr/hal-01216730

J. D. Lafferty, A. Mccallum, and F. C. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, International Conference on Machine Learning (ICML), 2001.

X. Lan, S. Roth, D. P. Huttenlocher, and M. J. Black, Efficient Belief Propagation with Learned Higher-Order Markov Random Fields, European Conference on Computer Vision (ECCV), 2006.
DOI : 10.1109/TIP.2003.819861

S. L. Lauritzen, Graphical Models, 1996.

D. Lee and T. Pavlidis, One-dimensional regularization with discontinuities, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.10, issue.6, pp.822-829, 1988.
DOI : 10.1109/34.9105

V. Lempitsky, C. Rother, S. Roth, and A. Blake, Fusion Moves for Markov Random Field Optimization, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.32, issue.8, pp.1392-1405, 2010.
DOI : 10.1109/TPAMI.2009.143
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.1633

A. Levinshtein, C. Sminchisescu, and S. Dickinson, Optimal Contour Closure by Superpixel Grouping, European Conference on Computer Vision (ECCV), 2010.
DOI : 10.1007/978-3-642-15552-9_35
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.228.2448

S. Z. Li, Markov random field modeling in image analysis, 2009.
DOI : 10.1007/978-4-431-67044-5

C. Liu, J. Yuen, and A. Torralba, SIFT Flow: Dense Correspondence Across Scenes and Its Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol.33, issue.5, pp.978-994, 2011.
DOI : 10.1007/978-3-319-23048-1_2

J. Julian, T. S. Mcauley, and . Caetano, Faster Algorithms for Max-Product Message- Passing, Journal of Machine Learning Research, vol.12, pp.1349-1388, 2011.

M. A. Moni and A. B. Ali, HMM based hand gesture recognition: A review on techniques and approaches, 2009 2nd IEEE International Conference on Computer Science and Information Technology, 2009.
DOI : 10.1109/ICCSIT.2009.5234536

A. P. Moore, S. J. Prince, and J. Warrell, Lattice Cut" -Constructing superpixels using layer constraints, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2010.

S. Nowozin and C. H. Lampert, Global connectivity potentials for random field models, 2009 IEEE Conference on Computer Vision and Pattern Recognition, 2009.
DOI : 10.1109/CVPR.2009.5206567

A. Mark and . Paskin, Thin Junction Tree Filters for Simultaneous Localization and Mapping, International Joint Conference on Artificial Intelligence (IJCAI), 2003.

V. Pavlovic, Dynamic Bayesian Networks for Information Fusion with Application to Human-Computer Interfaces, 1999.

M. P. Kumar, Combinatorial and Convex Optimization for Probabilistic Models in Computer Vision, 2008.

M. P. Kumar, V. Kolmogorov, and P. H. Torr, An Analysis of Convex Relaxations for MAP Estimation of Discrete MRFs, Journal of Machine Learning Research, vol.10, pp.71-106, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00773608

M. , P. Kumar, and P. H. Torr, Fast memory-efficient generalized belief propagation, European Conference on Computer Vision (ECCV), 2006.

M. P. Kumar, P. H. Torr, and A. Zisserman, Learning Layered Pictorial Structures from Video, The Indian Conference on Computer Vision, Graphics and Image Processing (ICVGIP), 2004.

J. Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, 1988.

J. Pearl, Causality: Models, Reasoning, and Inference, 2009.
DOI : 10.1017/CBO9780511803161

K. Petersen, J. Fehr, and H. Burkhardt, Fast generalized belief propagation for MAP estimation on 2D and 3D grid-like markov random fields. DAGM-Symposium, pp.41-50, 2008.

B. Potetz, Efficient Belief Propagation for Vision Using Linear Constraint Nodes, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
DOI : 10.1109/CVPR.2007.383094

B. Potetz and T. Lee, Efficient belief propagation for higher-order cliques using linear constraint nodes, Computer Vision and Image Understanding, vol.112, issue.1, pp.39-54, 2008.
DOI : 10.1016/j.cviu.2008.05.007
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.4487

R. B. Potts, Some generalized order-disorder transitions, Proceedings of the Cambridge Philosophical Society, pp.106-109, 1952.
DOI : 10.1017/s0305004100027419

A. Quattoni, M. Collins, and T. Darrell, Conditional random fields for object recognition, Advances in Neural Information Processing Systems (NIPS), 2004.

L. R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Proceedings of the IEEE, pp.257-286, 1989.

D. Rajan and S. Chaudhuri, An MRF-based approach to generation of superresolution images from blurred observations, Journal of Mathematical Imaging and Vision, vol.16, issue.1, pp.5-15, 2002.
DOI : 10.1023/A:1013961817285

S. Ramalingam, P. Kohli, K. Alahari, and P. H. Torr, Exact inference in multi-label CRFs with higher order cliques, 2008 IEEE Conference on Computer Vision and Pattern Recognition, 2008.
DOI : 10.1109/CVPR.2008.4587401
URL : https://hal.archives-ouvertes.fr/hal-01217304

J. Romberg, H. Choi, and R. Baraniuk, Bayesian tree-structured image modeling using wavelet-domain hidden Markov models, IEEE Transactions on Image Processing, vol.10, issue.7, pp.1056-1068, 2001.
DOI : 10.1109/83.931100

I. G. Rosenberg, Reduction of bivalent maximization to the quadratic case, Cahiers du Centre d'etudes de Recherche Operationnelle, pp.71-74, 1975.

S. Roth and M. J. Black, Fields of Experts: A Framework for Learning Image Priors, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), 2005.
DOI : 10.1109/CVPR.2005.160

S. Roth and M. J. Black, On the spatial statistics of optical flow, Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, pp.33-50, 2007.
DOI : 10.1109/ICCV.2005.180

S. Roth and M. J. Black, Fields of Experts, International Journal of Computer Vision, vol.27, issue.2, pp.205-229, 2009.
DOI : 10.1007/s11263-008-0197-6

C. Rother, P. Kohli, W. Feng, and J. Jia, Minimizing sparse higher order energy functions of discrete variables, 2009 IEEE Conference on Computer Vision and Pattern Recognition, 2009.
DOI : 10.1109/CVPR.2009.5206739

C. Rother, V. Kolmogorov, and A. Blake, "GrabCut", ACM Transactions on Graphics, vol.23, issue.3, pp.309-314, 2004.
DOI : 10.1145/1015706.1015720

C. Rother, V. Kolmogorov, V. Lempitsky, and M. Szummer, Optimizing Binary MRFs via Extended Roof Duality, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
DOI : 10.1109/CVPR.2007.383203
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.63.4613

S. Roy and I. J. Cox, A maximum-flow formulation of the N-camera stereo correspondence problem, Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271), 1998.
DOI : 10.1109/ICCV.1998.710763

S. Roy and V. Govindu, MRF solutions for probabilistic optical flow formulations, Proceedings 15th International Conference on Pattern Recognition. ICPR-2000, 2000.
DOI : 10.1109/ICPR.2000.903724
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.4458

H. Rue and L. Held, Gaussian Markov Random Fields: Theory and Applications, 2005.
DOI : 10.1201/9780203492024

R. Salakhutdinov, Learning in Markov random fields using tempered transitions, Advances in Neural Information Processing Systems (NIPS), 2009.

D. Schlesinger and B. Flach, Transforming an arbitrary minsum problem into a binary one, 2006.

D. Seghers, D. Loeckx, F. Maes, D. Vandermeulen, and P. Suetens, Minimal Shape and Intensity Cost Path Segmentation, IEEE Transactions on Medical Imaging, vol.26, issue.8, pp.1115-1129, 2007.
DOI : 10.1109/TMI.2007.896924
URL : https://lirias.kuleuven.be/bitstream/123456789/72327/1/Seghers07IEEETMI.pdf

D. Ross, . Shachter, I. Bayes-ball-alexander-shekhovtsov, V. Kovtun, and . Hlavac, The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams Efficient MRF deformation model for non-rigid image matching, Conference on Uncertainty in Artificial Intelligence (UAI), pp.91-99, 1998.

J. Shotton, J. Winn, C. Rother, and A. Criminisi, TextonBoost for Image Understanding: Multi-Class Object Recognition and Segmentation by Jointly Modeling Texture, Layout, and Context, International Journal of Computer Vision, vol.62, issue.1???2, pp.2-23, 2009.
DOI : 10.1007/s11263-007-0109-1

L. Sigal and M. J. Black, Measure Locally, Reason Globally: Occlusion-sensitive Articulated Pose Estimation, 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Volume 2 (CVPR'06), 2006.
DOI : 10.1109/CVPR.2006.180
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.62.5114

L. Sigal, M. Isard, B. H. Sigelman, and M. J. Black, Attractive People: Assembling Loose-Limbed Models using Non-parametric Belief Propagation, Advances in Neural Information Processing Systems (NIPS), 2003.
DOI : 10.1007/s11263-011-0493-4

D. Singaraju, L. Grady, and R. Vidal, P-brush: Continuous valued MRFs with normed pairwise distributions for image segmentation, 2009 IEEE Conference on Computer Vision and Pattern Recognition, 2009.
DOI : 10.1109/CVPR.2009.5206669
URL : http://cis.jhu.edu/%7Edheeraj/papers/cvpr09-pbrush.pdf

D. Sontag and T. Jaakkola, New outer bounds on the marginal polytope, Advances in Neural Information Processing Systems (NIPS), 2007.

T. Starner, J. Weaver, and A. Pentland, A wearable computer based american sign language recognizer, Assistive Technology and Artificial Intelligence: Applications in Robotics, User Interfaces and Natural Language Processing, pp.84-96, 1998.
DOI : 10.1109/iswc.1997.629929
URL : http://c2000.cc.gatech.edu/classes/cs8113c_99_spring/readings/starner.pdf

P. Strandmark and F. Kahl, Parallel and distributed graph cuts by dual decomposition, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2010.
DOI : 10.1109/CVPR.2010.5539886

E. B. Sudderth, A. T. Ihler, M. Isard, W. T. Freeman, and A. S. Willsky, Nonparametric belief propagation, Communications of the ACM, vol.53, issue.10, pp.95-103, 2010.
DOI : 10.1145/1831407.1831431

E. B. Sudderth, M. I. Mandel, W. T. Freeman, and A. S. Willsky, Distributed occlusion reasoning for tracking with nonparametric belief propagation, Advances in Neural Information Processing Systems (NIPS), 2004.

E. B. Sudderth, M. I. Mandel, W. T. Freeman, and A. S. Willsky, Visual Hand Tracking Using Nonparametric Belief Propagation, 2004 Conference on Computer Vision and Pattern Recognition Workshop, 2004.
DOI : 10.1109/CVPR.2004.474

J. Sun, N. Zheng, and H. Shum, Stereo Matching Using Belief Propagation, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), vol.25, issue.7, pp.787-800, 2003.
DOI : 10.1007/3-540-47967-8_34
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.221.2039

C. Sutton and A. Mccallum, An Introduction to Conditional Random Fields. Foundations and Trends in Machine Learning, 2011.

R. Szeliski, Computer vision: algorithms and applications, 2010.
DOI : 10.1007/978-1-84882-935-0

R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov et al., A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.30, issue.6, pp.301068-1080, 2008.
DOI : 10.1109/TPAMI.2007.70844

F. Marshall, W. T. Tappen, and . Freeman, Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters, IEEE International Conference on Computer Vision (ICCV), 2003.

D. Tarlow, I. E. Givoni, and R. S. Emel, HOP-MAP: Efficient Message Passing with High Order Potentials, International Conference on Artificial Intelligence and Statistics (AISTATS), 2010.

D. Terzopoulos, Regularization of Inverse Visual Problems Involving Discontinuities, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.8, issue.4, pp.413-424, 1986.
DOI : 10.1109/TPAMI.1986.4767807

D. Terzopoulos and R. Szeliski, Tracking with Kalman snakes, Active vision, pp.3-20, 1993.

A. N. Tikhonov and V. Y. Arsenin, Solutions of ill-posed problems, 1977.

L. Torresani, V. Kolmogorov, and C. Rother, Feature Correspondence Via Graph Matching: Models and Global Optimization, European Conference on Computer Vision (ECCV), 2008.
DOI : 10.1007/978-3-540-88688-4_44

F. Tupin, H. Maitre, J. Mangin, J. Nicolas, and E. Pechersky, Detection of linear features in SAR images: application to road network extraction, IEEE Transactions on Geoscience and Remote Sensing, vol.36, issue.2, pp.434-453, 1998.
DOI : 10.1109/36.662728

V. Vijay and . Vazirani, Approximation Algorithms, 2001.

O. Veksler, Star Shape Prior for Graph-Cut Image Segmentation, European Conference on Computer Vision (ECCV), 2008.
DOI : 10.1007/978-3-540-88690-7_34

O. Veksler, Y. Boykov, and P. Mehrani, Superpixels and Supervoxels in an Energy Optimization Framework, European Conference on Computer Vision (ECCV), 2010.
DOI : 10.1007/978-3-642-15555-0_16

S. Vicente, V. Kolmogorov, and C. Rother, Graph cut based image segmentation with connectivity priors, 2008 IEEE Conference on Computer Vision and Pattern Recognition, 2008.
DOI : 10.1109/CVPR.2008.4587440

S. Vicente, V. Kolmogorov, and C. Rother, Joint optimization of segmentation and appearance models, 2009 IEEE 12th International Conference on Computer Vision, 2009.
DOI : 10.1109/ICCV.2009.5459287

G. Vogiatzis, C. Hernández-esteban, P. H. Torr, and R. Cipolla, Multiview Stereo via Volumetric Graph-Cuts and Occlusion Robust Photo-Consistency, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.12, pp.292241-2246, 2007.
DOI : 10.1109/TPAMI.2007.70712

M. J. Wainwright, T. Jaakkola, and A. Willsky, Tree consistency and bounds on the performance of the max-product algorithm and its generalizations, Statistics and Computing, vol.14, issue.2, pp.143-166, 2004.
DOI : 10.1023/B:STCO.0000021412.33763.d5

M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky, MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming, IEEE Transactions on Information Theory, vol.51, issue.11, pp.513697-3717, 2005.
DOI : 10.1109/TIT.2005.856938

J. Martin, M. I. Wainwright, and . Jordan, Graphical Models, Exponential Families, and Variational Inference, Machine Learning, pp.1-305, 2007.

C. Wang, M. , L. Gorce, and N. Paragios, Segmentation, ordering and multiobject tracking using graphical models, IEEE International Conference on Computer Vision, 2009.

C. Wang, O. Teboul, F. Michel, S. Essafi, and N. Paragios, 3D Knowledge-Based Segmentation Using Pose-Invariant Higher-Order Graphs, International Conference, Medical Image Computing and Computer Assisted Intervention (MICCAI), 2010.
DOI : 10.1007/978-3-642-15711-0_24
URL : https://hal.archives-ouvertes.fr/hal-00856051

C. Wang, Y. Zeng, and L. Simon, Ioannis Kakadiaris, Dimitris Samaras, and Nikos Paragios. Viewpoint invariant 3d landmark model inference from monocular 2d images using higher-order priors, IEEE International Conference on Computer Vision (ICCV), 2011.

Y. Weiss and W. T. Freeman, On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs, IEEE Transactions on Information Theory, vol.47, issue.2, pp.736-744, 2001.
DOI : 10.1109/18.910585

T. Werner, A Linear Programming Approach to Max-Sum Problem: A Review, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.7, pp.1165-1179, 2007.
DOI : 10.1109/TPAMI.2007.1036

T. Werner, High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (MAP-MRF), 2008 IEEE Conference on Computer Vision and Pattern Recognition, 2008.
DOI : 10.1109/CVPR.2008.4587355

T. Werner, Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.32, issue.8, pp.1474-1488, 2010.
DOI : 10.1109/TPAMI.2009.134

O. J. Woodford, P. H. Torr, I. D. Reid, and A. W. Fitzgibbon, Global Stereo Reconstruction under Second-Order Smoothness Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), issue.12, pp.312115-2128, 2009.

W. Wu, M. J. Black, Y. Gao, E. Bienenstock, M. Serruya et al., Neural Decoding of Cursor Motion using a Kalman Filter, Advances in Neural Information Processing Systems (NIPS), 2002.

B. Xiang, C. Wang, J. Deux, A. Rahmouni, and N. Paragios, Tagged cardiac mr image segmentation using boundary & regional-support and graphbased deformable priors, IEEE International Symposium on Biomedical Imaging (ISBI), 2011.
URL : https://hal.archives-ouvertes.fr/hal-00856116

C. Yanover, T. Meltzer, and Y. Weiss, Linear Programming Relaxations and Belief Propagation-An Empirical Study, The Journal of Machine Learning Research, vol.7, pp.1887-1907, 2006.

J. S. Yedidia, W. T. Freeman, and Y. Weiss, Understanding Belief Propagation and its Generalizations, Exploring artificial intelligence in the new millennium, pp.239-269, 2003.

Y. Zeng, C. Wang, Y. Wang, X. Gu, D. Samaras et al., Dense non-rigid surface registration using high-order graph matching, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2010.
DOI : 10.1109/CVPR.2010.5540189
URL : https://hal.archives-ouvertes.fr/hal-00856064

Y. Zeng, C. Wang, Y. Wang, and X. Gu, Dimitris Samaras, and Nikos Paragios . A generic local deformation model for shape registration, 2011.

Y. Zeng, C. Wang, Y. Wang, and X. Gu, Dimitris Samaras, and Nikos Paragios . Intrinsic dense 3d surface tracking, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011.

Y. Zhang and Q. Ji, Active and dynamic information fusion for facial expression understanding from image sequences, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.27, issue.5, pp.699-714, 2005.
DOI : 10.1109/TPAMI.2005.93

Y. Zhang, R. Hartley, J. Mashford, and S. Burn, Superpixels via pseudo-Boolean optimization, 2011 International Conference on Computer Vision, 2011.
DOI : 10.1109/ICCV.2011.6126393

C. Song, A. Zhu, and . Yuille, Region competition: unifying snakes, region growing, and Bayes/MDL for multiband image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.18, issue.9, pp.884-900, 1996.
DOI : 10.1109/34.537343

B. Networks and .. , Directed Graphical Models)

F. Markov-random, Undirected Graphical Models)

.. Belief-propagation-algorithms, 17 4.2.1 Belief Propagation in Tree, Junction Tree Algorithm

.. Inference-in-higher-order-mrfs, 22 4.4.1 Order Reduction and Graph Cuts, p.23