HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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
Complete list of metadata

Contributor : Shan Yu Connect in order to contact the contributor
Submitted on : Thursday, November 27, 2014 - 4:09:25 AM
Last modification on : Friday, February 4, 2022 - 3:12:32 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