Markov

Markov

Markov Random Fields and Images
by
Patrick P_erez

At the intersection of statistical physics and probability theory, Markov random_elds and Gibbs distributions have emerged in the early eighties as powerful tools for modeling images and coping with high-dimensional inverse problems from low-level vision. Since then, they have been used in many studies from the image processing and computer vision community. A brief and simple introduction to the basics of the domain is proposed.

1. Introduction and general framework
With a seminal paper by Geman and Geman in 1984 [18], powerful tools known for long by physicists [2] and statisticians [3] were brought in a com-prehensive and stimulating way to the knowledge of the image processing and computer vision community. Since then, their theoretical richness, their prac-tical versatility, and a number of fruitful connections with other domains, have resulted in a profusion of studies. These studies deal either with the mod-eling of images (for synthesis, recognition or compression purposes) or with the resolution of various high-dimensional inverse problems from early vision (e.g., restoration, deblurring, classi_cation, segmentation, data fusion, surface reconstruction, optical ow estimation, stereo matching, etc. See collections of examples in [11, 30, 40]).
The implicit assumption behind probabilistic approaches to image analysis is that, for a given problem, there exists a probability distribution that can capture to some extent the variability and the interactions of the di_erent sets of relevant image attributes. Consequently, one considers the variables of the problem as random variables forming a set (or random vector) X = (Xi)ni=1 with joint probability distribution PX 1.
1 PX is actually a probability mass in the case of discrete variables, and a probability density
function when the Xi's are continuously valued. In the latter case, all summations over
states or con_gurations should be replaced by integrals.

Logic Of Triplet Markov Fields

Unsupervised image segmentation using triplet Markov fields
by
Dalila Benboudjema, Wojciech Pieczynski

Abstract
Hidden Markov fields (HMF) models are widely applied to various problems arising in
image processing. In these models, the hidden process of interest X is a Markov field and must be estimated from its observable noisy version Y. The success of HMF is mainly due to the fact that the conditional probability distribution of the hidden process with respect to the observed one remains Markovian, which facilitates different processing strategies such as Bayesian restoration. HMF have been recently generalized to ‘‘pairwise’’ Markov fields (PMF), which offer similar processing advantages and superior modeling capabilities. In PMF one directly assumes the Markovianity of the pair (X,Y). Afterwards, ‘‘triplet’’ Markov fields (TMF), in which the distribution of the pair (X,Y) is the marginal distribution of a Markov field (X,U,Y), where U is an auxiliary process, have been proposed and still allow restoration processing. The aim of this paper is to propose a new parameter estimation method adapted to TMF, and to study the corresponding unsupervised image segmentation methods. The latter are validated via experiments and real image processing.
@ 2005 Elsevier Inc. All rights reserved.

Keywords: Hidden Markov fields; Pairwise Markov fields; Triplet Markov fields; Bayesian classification; Mixture estimation; Iterative conditional estimation; Stochastic gradient; Unsupervised image segmentation

1. Introduction
Hidden Markov fields (HMF) are widely used in solving various problems, comprising two stochastic processes X = (Xs)s2S and Y = (Ys)s2S, in which X = x is unobservable and must be estimated from the observed Y = y. This wide use is due to the fact that standard Bayesian restoration methods can be used in spite of the large size of S: see [3,12,19] for seminal papers and [14,33], among others, for general books. The qualifier ‘‘hidden Markov’’ means that the hidden process X has a Markov law. When the distributions p (y|x) of Y conditional on X = x are simple enough, the pair (X,Y) then retains the Markovian structure, and likewise for the distribution p(x|y) of X conditional on Y = y. The Markovianity of p(x|y) is crucial because it allows one to estimate the unobservable X = x from the observed Y = y, even in the case of very rich sets S. However, the simplicity of p (y|x) required in standard HMF to ensure the Markovianity of p(x|y) can pose problems; in particular, such situations occur in textured images segmentation [21]. To remedy this, the use of pairwise Markov fields (PMF), in which one directly assumes the Markovianity of (X,Y), has been discussed in [26]. Both p(y|x) and p(x|y) are then Markovian, the former ensuring possibilities of modeling textures without approximations, and the latter allowing Bayesian processing, similar to those provided by HMF. PMF have then been generalized to ‘‘triplet’’ Markov fields (TMF), in which the distribution of the pair Z = (X,Y) is the marginal distribution of a Markov field T = (X,U,Y), where U = (Us)s2S is an auxiliary random field [27]. Once the space K of possible values of each Us is simple enough, TMF still allow one to estimate the unobservable X = x from the observed Y = y. Given that in TMF T = (X,U,Y) the distribution of Z = (X,Y) is its marginal distribution, the Markovianity of T does not necessarily imply the Markovianity of Z; and thus a TMF model is not necessarily a PMF one. Therefore, TMF are more general than PMF and thus are likely to be able to model more complex situations. Conversely, a PMF model can be seen as a particular TMF model in which X = U. There are some studies concerning triplet Markov chains [18,28], where general ideas somewhat similar to those discussed in the present paper, have been investigated. However, as Markov fields based processing is quite different from the Markov chains based one, we will concentrate here on Markov fields with no further reference to Markov chains.