Figure-Ground Discrimination: a Combinatorial Optimization Approach

Abstract : In this paper we attack the figure-ground discrimination problem from a combinatorial optimization perspective. In general the solutions proposed in the past solved this problem only partially: either the mathematical model encoding the figure-ground problem was too simple or the optimization methods that were used were not efficient enough or they could not guarantee to find the global minimum of the cost function describing the figure-ground model. The method that we devised and which is described in this paper is tailored around three main contributions. First, we suggest a mathematical model encoding the figure-ground discrimination problem that makes explicit a definition of shape (or figure) based on cocircularity, smoothness, proximity, and contrast. This model consists of building a cost function on the basis of image element interactions. Moreover, this cost function fits the constraints of a interacting spin system which in turn is a well suited physical model to solve hard combinatorial optimization problems. Second, we suggest two combinatorial optimization methods for solving the figure-ground problem, namely (i) mean field annealing which combines mean field approximation theory and annealing and (ii) microcanonical annnealing. Mean field annealing may well be viewed as a deterministic approximation of stochastic methods such as simulated annealing. We describe in detail the theoretical bases of these methods, derive computational models, and provide practical algorithms. Third, we provide a comparison of the efficiency of mean field annealing, simulated annealing, and microcanonical annealing algorithms. Within the framework of such a comparison, the figure-ground problem may well be viewed as a benchmark.
Type de document :
Article dans une revue
IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 1993, 15 (9), pp.899--914. 〈10.1109/34.232076〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00590016
Contributeur : Team Perception <>
Soumis le : mardi 3 mai 2011 - 09:07:32
Dernière modification le : jeudi 11 janvier 2018 - 06:20:04
Document(s) archivé(s) le : jeudi 4 août 2011 - 02:40:14

Fichiers

HeraultHoraud-pami-93.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

IMAG | INRIA | CEA | UGA | DRT

Citation

Laurent Herault, Radu Horaud. Figure-Ground Discrimination: a Combinatorial Optimization Approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 1993, 15 (9), pp.899--914. 〈10.1109/34.232076〉. 〈inria-00590016〉

Partager

Métriques

Consultations de la notice

355

Téléchargements de fichiers

163