Introduction

Preface

Since its beginning, computer vision research has been evolving from heuristic design of algorithms to systematic investigation of approaches. In this process, researchers have realized: (1) The solution to a vision problem should be sought based on optimization principles, albeit explicitly or implicitly, and (2) contextual constraints are ultimately necessary for the understanding of visual information in images. Two questions follow: how to define an optimality criterion under contextual constraints and how to find its optimal solution.

Markov random field (MRF) theory, a branch of probability theory, provides a foundation for the characterization of contextual constraints and the derivation of the probability distribution of interacting features. In conjunction with methods from decision and estimation theory, the MRF theory provides a systematic approach for deriving optimality criteria such as those based on the maximum a posteriori (MAP) concept. This MAP-MRF framework enables us to systematically develop algorithms for a variety of vision problems using rational principles rather than ad hoc heuristics. For these reasons, there has seen increasing interest in modeling computer vision problems using MRFs in recent years.

This book provides a coherent reference to theories, methodologies and recent developments in solving computer vision problems based on MRFs, statistics and optimization. It treats various problems in low- and high-level computational vision in a systematic and unified way within the MAP-MRF framework. The main issues of concern are: how to use MRFs to encode contextual constraints that are indispensable to image understanding, how to derive the objective function, typically the posterior distribution, for the optimal solution to a problem, and how to design computational algorithms for finding the optimal solution.

As the first thorough reference to the subject, the book has four essential parts for solving computational vision problems using MRFs: (1) introduction to fundamental theories, (2) formulations of various vision models in the MAP-MRF framework, (3) parameter estimation, and (4) optimization methods.

Chapter 1 introduces the notion of visual labeling and describes the important results in MRF theory pertinent to applications in vision modeling. A vision problem is posed in terms of Bayes labeling of an MRF. Its optimal solution is then defined as the MAP configuration of the MRF. The role of optimization in computer vision is discussed. These form the basis on which MAP-MRF models are formulated.

Chapter 2 formulates MRF models for low-level vision problems, such as image restoration, reconstruction, edge detection, texture, and optical flow. The systematic MAP-MRF approach for deriving the posterior distribution is illustrated step by step.

Chapter 3 addresses the issue of discontinuities in low-level vision. An important necessary condition is derived for any MRF prior potential function to be adaptive to discontinuities to avoid oversmoothing. This gives rise to the definition of a class of adaptive interaction functions and thereby a class of MRF models capable of dealing with discontinuities.

Chapter 4 provides a comparative study on discontinuity adaptive MRF priors and robust M-estimators based on the results obtained in Chapter 3. To tackle the problems associated with M-estimators, a method is presented to stabilize M-estimators with respect to its initialization and convergence.

Chapter 5 presents MRF models for object recognition and pose determination in high-level vision. Relational measurements are incorporated into the energy function as high-level constraints. The concept of line process is extended to the separation of overlapping objects and the elimination of outlier features.

Chapter 6 describes various methods for both supervised and unsupervised parameter estimation, including coding method, pseudo-likelihood, least squares method and expectation maximization. A simultaneous image labeling and parameter estimation paradigm is also presented, which enhances the low-level models in Chapter 2.

Chapter 7 presents a theory of parameter estimation for optimization-based object recognition. Two levels of criteria are proposed for the estimation: correctness and optimality. Optimal parameters are learned from examples using supervised learning methods. The theory is applied to parameter learning for the MRF recognition.

Chapters 8 and 9 present local and global methods, respectively, for energy optimization in finding MAP-MRF solutions. These include various algorithms for continuous, discrete, unconstrained and constrained minimization and strategies for approximating global solutions.

The final version of this manuscript benefited from comments on earlier versions by a number of people. I am very grateful to Anil K. Jain and Kanti V. Mardia for their valuable suggestions. I would like to thank Kap Luk Chan, Lihui Chen, Yi-Ping Hung, Eric Sung, Han Wang, Ming Xie and Dekun Yang. Their corrections have had a very positive effect on the book. I am particularly indebted to Yunjun Zhang, Weiyun Yau and Yihong Huang for their proofreading of the whole manuscript. Finally, I owe a deep debt of gratitude to my wife, Qun Pan, for her understanding, patience, and support.

S.Z. Li

Introduction