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 convexifies 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).

}, isbn = {0262-8856}, author = {Mark Berthod and Zoltan Kato and Shan Yu and Josiane Zerubia} }