A Game Strategy Approach to Relaxation Labeling

Shan Yu 1 Marc Berthod 1
1 PASTIS - Scene Analysis and Symbolic Image Processing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we propose a relaxation algorithm based on the game theory for scene labeling problems. Using a Bayesian modeling by Markov random fields, we consider the maximization of the a posteriori probability of labelings. We design a (noncooperative) game which yields an easily parallelizable relaxation algorithm. We prove that all the labelings which maximize the a posteriori probability are Nash equilibrium points of the game, and that all the Nash equilibrium points are local maxima. We also prove that our relaxation algorithm converges to a Nash equilibrium. Experimental results show that the algorithm is very efficient and effective, and that it exhibits very fast convergence.
Document type :
Journal articles
Liste complète des métadonnées

Contributor : Shan Yu <>
Submitted on : Thursday, November 27, 2014 - 4:09:25 AM
Last modification on : Saturday, January 27, 2018 - 1:32:19 AM

Links full text




Shan Yu, Marc Berthod. A Game Strategy Approach to Relaxation Labeling. Computer Vision and Image Understanding, Elsevier, 1995, 61 (1), pp.32-37. ⟨10.1006/cviu.1995.1003⟩. ⟨hal-01087880⟩



Record views