Champs de Markov en Vision par Ordinateur

TNS : TTM5104

Part III : Algorithmes

III : Solutions. On ne veut pas seulement modéliser. Il

faut calculer la valeur d’une estimée.

Les modèles ne sont pas simples: souvent ils demandent de grandes ressources en temps de calcul et en mémoire.

Les espaces sont énormes et il y a beaucoup de minima locaux.

Exemple : le recuit simulé peut prendre des heures même sur les images assez petites.

III : Simulation A. Objet : synthétiser des configurations de

champs markoviens suivant une certaine distribution de Gibbs.

Problème : Z n’est pas calculable. On utilise d’algorithmes de relaxation

itératifs qui convergent vers la distribution : Metropolis (1953) ; Echantillonneur de Gibbs (Geman 1984).

III : Simulation B : MCMC Markov Chain Monte Carlo

On pense d’une configuration dépendant de temps : .

Construction d’une chaîne de Markov

Pr 1 t.q.

limPr Prt

F t F t

F t ff

DF t C

DC

La chaîne visite plus

souvent les

régions de haut

probabilité

III : Simulation C : Metropolis. Tirer d’une nouvelle configuration

F(t) avec probabilité :

Accepter la nouvelle configuration avec probabilité :

Pr 1 , 1F t F t Q F t F t

1 , Prmin 1,

, 1 Pr 1

Q F t F t F t

Q F t F t F t

III : Echantillonneur de Gibbs A Passage de F(t-1) à F(t) :

Choix d’un point p dans le domaine D.

Perturbation de la valeur F(t-1)p.

Choix d’un point p est fait par : Échantillonnage ;

Balayage déterministe.

III : Échantillonneur de Gibbs B Tirage d’une nouvelle valeur

d’après la distribution conditionnelle locale :

Zp est la fonction de partition locale.

:

Pr 1

1exp 1

p N p

q qq Q p qp

F t c F t

F tZ

C

Dp

c C

III : Utilisation des Échantillonneurs. Synthèse de textures :

Estimée de MAP : optimisation globale. Échantillonneur à température

variable : recuit simulé.

Estimée moyenne :

0

0

1Pr

1D

t M

tf C

G f G ff G F tM

III : Estimées de MAP. Il y a beaucoup des algorithmes

différents, mais ils se regroupent dans trois catégories: Variationels;

Stochastiques;

Graphiques.

III : Méthodes Variationelles. Ils descendent à long du gradient.

Rapides, mais normalement on trouve seulement un minimum local.

Dépendantes de l’initialisation.

III : Méthodes Stochastiques. Ils utilisent l’échantillonnage pour

simuler la probabilité. Très lentes, mais on trouve le

minimum global (au moins en théorie).

On peut calculer le moyenne (ou d’autres quantités statistiques).

III : Méthodes Graphiques. Ils utilisent des algorithmes

combinatoires sur les graphes. Pas trop lentes, pas trop rapides, et on

trouve le minimum global plus ou moins sûrement. Il y a des limites sur la forme de la probabilité.

Deux versions differentes: Maximum flow; Graph cuts.

III : Méthodes Variationels : En Bref. On pense d’une configuration dépendant

de temps : .

On change S selon le gradient de l’énergie.

Beaucoup de variations sur cette thème.

Problème : ils trouvent les minima locaux et dépendent de l’initialisation.

DF t C

U F tFt F

III : Recuit Simulé : Relaxation Stochastique Introduction d’un facteur de

température T :

Quand , deviens uniforme.

Quand , se concentre sur les maxima globaux de .

Engendrer une séquence de configurations avec .

1Pr expT

U ff Z T

T

T PrT

0T PrT1Pr Pr

0T

III : Recuit Simulé : Descente de Température. On prouve que, si :

Puis la configuration quand T=0 sera le minimum globale.

Mais il faut attendre !

Plus souvent : .

log

kT t

t

, 1tT t kC C

T

t

III : Recuit Simulé : Problèmes. En pratique, on doit utiliser une loi de

descente de température sous-optimale.

La théorème de convergence peut donner l’impression que tous ira bien, mais…

Expérience avec les algorithmes graphiques, qui trouvent le minimum global dans un temps fini, montre que les lois sous-optimales sont…sous-optimales.

Convergence en 100 – 1000 itérations.

III : Algorithmes Sous-Optimaux : ICM (Besag 1986). Choix d’un point p : balayage

déterministe.

Remise à jour de p par la valeur qui provoque la plus forte augmentation de probabilité.

Echantillonneur de Gibbs à T=0.

III : Algorithmes Sous-Optimaux : ICM. Caractéristiques :

Algorithme déterministe ; Convergence vers un minimum local ; Initialisation et mode de balayage influent le

résultat ; Convergence en ~10 itérations Très utilisé.

Cf. gradient.

III : Algorithmes Sous-Optimaux : HCF (Chou 1988). Highest Confidence First

Mesure de stabilité de la valeur fp à un point p ( est l’énergie de la configuration courante) :

Les points sont classés dans une pile d’instabilités.

0U

0stab min 0pc Cp U f c U

III : Algorithmes Sous-Optimaux : HCF (Chou 1988). À chaque itération le point p0 le plus instable

(sommet de la pile) est remis à jour.

p0 devient stable.

Les stabilités des points de N(p0) sont ré-evaluées.

La pile est réordonnée. Répétez. Caractéristiques :

Algorithme déterministe ; Convergence en ~1 itération.

III : Autres choses. Algorithmes multi-grilles :

Pyramide des étiquettes ;

Pyramide des données.

Algorithmes multi-échelles : Pyramide des étiquettes ;

Données mono-résolution.

Approximation du champs moyen.

IV : Paramètres. Tous les modèles ont des

paramètres.

Normalement, ils sont inconnus.

Qu’est-ce qu’on peut faire ?

Deux approches : Bayesien : marginaliser ;

Estimation.

IV : Marginalisation des Paramètres. L’approche plus correcte. Souvent très difficile ou impossible. Principe : on marginalise toutes les

quantités auxquelles on n’est pas intéressé.

Pr Pr ,

1Pr , Pr Pr

Pr

S I S I

I S SI

IV : Paramètres : Estimation. Maximisation de la vraisemblance :

Normalement on ne sait pas S :

Algorithme EM (Chalmond 1989) : Pas-E : évaluation de l’espérance pour  ;

Pas-M : maximisation par rapport à .

maxPr ,I S

max log Pr , Pr , nS

S I S I

n1n

Historique 1965 : Abend et al. - théorie des réseaux de Markov.

1971 : Hammersley-Clifford - théorie des champs markoviens.

1972 : Woods – théorie des champs markoviens gaussiens.

1974 : Besag – premières applications des champs markoviens.

1982 : Kirkpatrick et al. – recuit simulé.

1983 : Cross et al. – modélisation de textures.

1983 : Therrien – segmentation des textures.

1984 : Geman et al. – restauration d’images.