by Mark Berthod, Zoltan Kato, Shan Yu, Josiane Zerubia
Abstract:
In this paper, we present three optimisation techniques, Deterministic Pseudo-Annealing (DPA), Game Strategy Approach (GSA), and Modified Metropolis Dynamics (MMD), in order to carry out image classification using a Markov random field model. For the first approach (DPA), the a posteriori probability of a tentative labelling is generalised to a continuous labelling. The merit function thus defined has the same maxima under constraints yielding probability vectors. Changing these constraints convexities the merit function. The algorithm solves this unambiguous maximisation problem, and then tracks down the solution while the original constraints are restored yielding a good, even if suboptimal, solution to the original labelling assignment problem. In the second method (GSA), the maximisation problem of the a posteriori probability of the labelling is solved by an optimisation algorithm based on game theory. A non-cooperative n-person game with pure strategies is designed such that the set of Nash equilibrium points of the game is identical to the set of local maxima of the a posteriori probability of the labelling. The algorithm converges to a Nash equilibrium. The third method (MMD) is a modified version of the Metropolis algorithm: at each iteration the new state is chosen randomly, but the decision to accept it is purely deterministic. This is also a suboptimal technique but it is much faster than stochastic relaxation. These three methods have been implemented on a Connection Machine CM2. Experimental results are compared to those obtained by the Metropolis algorithm, the Gibbs sampler and ICM (Iterated Conditional Mode).
Reference:
Mark Berthod, Zoltan Kato, Shan Yu, Josiane Zerubia, Bayesian Image Classification Using Markov Random Fields, In Image and Vision Computing, volume 14, pp. 285-295, 1996.
Bibtex Entry:
@string{ivc="Image and Vision Computing"}
@Article{Berthod-etal96,
author = {Berthod, Mark and Kato, Zoltan and Yu, Shan and
Zerubia, Josiane},
title = {{B}ayesian Image Classification Using {M}arkov
Random Fields},
journal = ivc,
year = 1996,
volume = 14,
pages = {285--295},
keywords = {Bayesian image classification, Markov random fields,
Optimisation},
pdf = {papers/ivc96.pdf},
abstract = {In this paper, we present three optimisation
techniques, Deterministic Pseudo-Annealing (DPA),
Game Strategy Approach (GSA), and Modified
Metropolis Dynamics (MMD), in order to carry out
image classification using a Markov random field
model. For the first approach (DPA), the a
posteriori probability of a tentative labelling is
generalised to a continuous labelling. The merit
function thus defined has the same maxima under
constraints yielding probability vectors. Changing
these constraints convexities the merit
function. The algorithm solves this unambiguous
maximisation problem, and then tracks down the
solution while the original constraints are restored
yielding a good, even if suboptimal, solution to the
original labelling assignment problem. In the second
method (GSA), the maximisation problem of the a
posteriori probability of the labelling is solved by
an optimisation algorithm based on game theory. A
non-cooperative n-person game with pure strategies
is designed such that the set of Nash equilibrium
points of the game is identical to the set of local
maxima of the a posteriori probability of the
labelling. The algorithm converges to a Nash
equilibrium. The third method (MMD) is a modified
version of the Metropolis algorithm: at each
iteration the new state is chosen randomly, but the
decision to accept it is purely deterministic. This
is also a suboptimal technique but it is much faster
than stochastic relaxation. These three methods have
been implemented on a Connection Machine
CM2. Experimental results are compared to those
obtained by the Metropolis algorithm, the Gibbs
sampler and ICM (Iterated Conditional Mode).}
}