Markov random field (MRF) modeling provides a basis for the characterization of contextual constraints on visual interpretation and enables us to develop optimal vision algorithms systematically based on sound principles. This book presents a comprehensive study on using MRFs to solve computer vision problems, covering the following parts essential to the subject: introduction to fundamental theories, formulations of various vision models in the MRF framework, MRF parameter estimation, and optimization algorithms. Various MRF vision models are presented in a unified form, including image restoration and reconstruction, edge and region segmentation, texture, stereo and motion, object matching and recognition, and pose estimation. This book is an excellent reference for researchers working in computer vision, image processing, pattern recognition and applications of MRFs. It is also suitable as a text for advanced courses in the subject.

1 Introduction.- 1.1 Visual Labeling.- 1.1.1 Sites and Labels.- 1.1.2 The Labeling Problem.- 1.1.3 Labeling Problems in Vision.- 1.1.4 Labeling with Contextual Constraints.- 1.2 Markov Random Fields and Gibbs Distributions.- 1.2.1 Neighborhood System and Cliques.- 1.2.2 Markov Random Fields.- 1.2.3 Gibbs Random Fields.- 1.2.4 Markov-Gibbs Equivalence.- 1.2.5 Normalized and Canonical Forms.- 1.3 Useful MRF Models.- 1.3.1 Auto-Models.- 1.3.2 Multi-Level Logistic Model.- 1.3.3 The Smoothness Prior.- 1.3.4 Hierarchical GRF Model.- 1.4 Optimization-Based Vision.- 1.4.1 Research Issues.- 1.4.2 Role of Energy Functions.- 1.4.3 Formulation of Objective Functions.- 1.4.4 Optimality Criteria.- 1.5 Bayes Labeling of MRFs.- 1.5.1 Bayes Estimation.- 1.5.2 MAP-MRF Labeling.- 1.5.3 Regularization.- 1.5.4 Summary of MAP-MRF Approach.- 2 Low Level MRF Models.- 2.1 Observation Models.- 2.2 Image Restoration and Reconstruction.- 2.2.1 MRF Priors for Image Surfaces.- 2.2.2 Piecewise Constant Restoration.- 2.2.3 Piecewise Continuous Restoration.- 2.2.4 Surface Reconstruction.- 2.3 Edge Detection.- 2.3.1 Edge Labeling using Line Process.- 2.3.2 Forbidden Edge Patterns.- 2.4 Texture Synthesis and Analysis.- 2.4.1 MRF Texture Modeling.- 2.4.2 Texture Segmentation.- 2.5 Optical Flow.- 2.5.1 Variational Approach.- 2.5.2 Flow Discontinuities.- 3 Discontinuities in MRFs.- 3.1 Smoothness, Regularization and Discontinuities.- 3.1.1 Regularization and Discontinuities.- 3.1.2 Other Regularization Models.- 3.2 The Discontinuity Adaptive MRF Model.- 3.2.1 Defining the DA Model.- 3.2.2 Relations with Previous Models.- 3.2.3 Discrete Data and 2D Cases.- 3.2.4 Solution Stability.- 3.3 Computation of DA Solutions.- 3.3.1 Solving the Euler Equation.- 3.3.2 Experimental Results.- 3.4 Conclusion.- 4 Discontinuity-Adaptivity Model and Robust Estimation.- 4.1 The DA Prior and Robust Statistics.- 4.1.1 Robust M Estimator.- 4.1.2 Problems with M Estimator.- 4.1.3 Redefinition of M Estimator.- 4.1.4 AM Estimator.- 4.1.5 Convex DA and M-Estimation Models.- 4.2 Experimental Comparison.- 4.2.1 Location Estimation.- 4.2.2 Rotation Angle Estimation.- 5 High Level MRF Models.- 5.1 Matching under Relational Constraints.- 5.1.1 Relational Structure Representation.- 5.1.2 Work in Relational Matching.- 5.2 MRF-Based Matching.- 5.2.1 Posterior Probability and Energy.- 5.2.2 Matching to Multiple Objects.- 5.2.3 Experiments.- 5.2.4 Extensions.- 5.3 Pose Computation.- 5.3.1 Pose Clustering and Estimation.- 5.3.2 Simultaneous Matching and Pose.- 5.3.3 Discussion.- 6 MRF Parameter Estimation.- 6.1 Supervised Estimation with Labeled Data.- 6.1.1 Maximum Likelihood.- 6.1.2 Pseudo-Likelihood.- 6.1.3 Coding Method.- 6.1.4 Mean Field Approximations.- 6.1.5 Least Squares Fit.- 6.2 Unsupervised Estimation with Unlabeled Data.- 6.2.1 Simultaneous Restoration and Estimation.- 6.2.2 Simultaneous Segmentation and Estimation.- 6.2.3 Expectation-Maximization.- 6.2.4 Cross Validation.- 6.3 Further Issues.- 6.3.1 Estimating the Number of MRFs.- 6.3.2 Reduction of Nonzero Parameters.- 7 Parameter Estimation in Optimal Object Recognition.- 7.1 Motivation.- 7.2 Theory of Parameter Estimation for Recognition.- 7.2.1 Optimization-Based Object Recognition.- 7.2.2 Criteria for Parameter Estimation.- 7.2.3 Linear Classification Function.- 7.2.4 A Non-parametric Learning Algorithm.- 7.2.5 Reducing Search Space.- 7.3 Application in MRF Object Recognition.- 7.3.1 Posterior Energy.- 7.3.2 Energy in Linear Form.- 7.3.3 How Minimal Configuration Changes.- 7.3.4 Parametric Estimation under Gaussian Noise.- 7.4 Experiments.- 7.4.1 Recognition of Line Patterns.- 7.4.2 Recognition of Curved Objects.- 7.5 Conclusion.- 8 Minimization - Local Methods.- 8.1 Classical Minimization with Continuous Labels.- 8.2 Minimization with Discrete Labels.- 8.2.1 Iterated Conditional Modes.- 8.2.2 Relaxation Labeling.- 8.2.3 Highest Confidence First.- 8.2.4 Dynamic Programming.- 8.3 Constrained Minimization.- 8.3.1 Penalty Functions.- 8.3.2 Lagrange Multipliers.- 8.3.3 Hopfield Method.- 8.3.4 RL using Lagrange-Hopfield Method.- 9 Minimization - Global Methods.- 9.1 Simulated Annealing.- 9.1.1 Random Sampling Algorithms.- 9.1.2 Annealing.- 9.2 Mean Field Annealing.- 9.3 Graduated Non-Convexity.- 9.3.1 Annealing Labeling for MAP-MRF Matching.- 9.4 Genetic Algorithms.- 9.5 Experimental Comparison.- 9.6 Accelerating Computation.- 9.6.1 Multi-resolution Methods.- 9.6.2 Use of Heuristics.- 9.7 Model Debugging.- References.- List of Notation.