Introduction au cours “Modèles stochastiques en

traitement d’image”

J. ZERUBIA – INRIA Sophia Antipolis

Remerciements : X. Descombes, I. Jermyn, les post-docs, doctorants et stagiaires de Master

Recherchedu projet ARIANA (INRIA/I3S)

2

0. Images : déconvolution

3

0. Images : segmentation

4

0. Buts Définitions : que sont les champs de

Markov ?

Exemples : comment sont-ils utilisés pour la compréhension des images ?

Algorithmes : comment peut-on extraire l’information désirée des modèles ?

Partie I : définitions

6

I. Modèles Probabilistes d’Images Une image étant donnée (observation),

on veut connaître quelque chose sur la ‘scène’ (variable cachée).

Exemple : on veut savoir s’il y avait une personne dans la scène, et si oui, où ?

La théorie des probabilités décrit le raisonnement dans les situations de connaissance incomplète.

7

I. Théorème de Bayes On veut connaître la probabilité de la scène

connaissant l’image. Le théorème de Bayes/Laplace transforme la

probabilité de l’image sachant la scène en la probabilité de la scène sachant l’image.

K représente toute la connaissance que l’on a avant de voir l’image 

Pr , PrPr ,

Pr

I S K S KS I K

I K

8

I . Théorème de Bayes La probabilité de l’image sachant la

scène et K (la formation de l’image) : a souvent un modèle physique, appelée la vraisemblance.

La probabilité de la scène avant d’avoir vu l’image (mais avec la connaissance K) : appelée la probabilité a priori.

On doit construire des modèles pour les deux (vraisemblance et a priori).

9

I. Les espaces d’images

Une image est une fonction d’un domaine D ½ ZN vers un espace C. Les signaux acoustiques : N = 1. Les images standard : N = 2.

Les images IRM : N = 3.

Les séquences vidéo : N = 3 = « 2 + 1 ».

10

I. Les espaces d’images La dimension de C :

Images monochromatiques : 1. Images en couleur : 3. Images multi- ou hyper-spectrales : de 10 à

plus de 200.

D est envisagé comme plongé dans RN. Cela veut dire que les notions de géométrie peuvent être appliquées si N > 1.

11

I. Les espaces de scène : sémantique

Information sur le monde 3D : Distances et positions des objets dans une

photo; Types de végétation dans une image aérienne; Position d’une tumeur dans une image

médicale ; Géométrie des bâtiments dans un plan. Paramètres de la caméra.

Jugements plus subjectifs : Émotion d’un visage ; Style d’architecture.

12

I. Les espaces de scène : mathématique

Une fonction de D vers un autre espace : Restauration : CD;

Segmentation : LD où L est un ensemble (étiquettes d’interprétation) ;

Une région : {0,1}D.

13

I. Probabilités sur ces espaces

L’espace des images est énorme. 10157826 images possibles de 256 x 256

pixels.

Il faut donc essayer de simplifier

14

I. Simplification des probabilités Les probabilités se simplifient

quand quelques variables sont indépendantes les unes des autres.

Les champs de Markov sont une façon (mais pas la seule) de définir des probabilités simplifiées, mais néanmoins utiles.

15

I. Exemple : indépendance Si la scène est décrite par une

fonction sur D, la probabilité peut se factoriser sur les pixels  :

Dans ce cas, on peut traiter chaque pixel séparément (problème à une dimension).

p D

Pr Pr p pp D

S I S I

16

I. Champs de Markov (MRFs) Un champ de Markov sur un

ensemble D est une probabilité sur l’espace de fonctions CD de D vers un autre espace C satisfaisant les 2 conditions ci-dessous.

Positivité : . On peut savoir tout ce qui est

possible de la valeur de fp sachant seulement les valeurs des ‘voisins’ fN(p)-p.

Pr 0f

17

I. Champs de Markov (MRFs) Voisinage : pour chaque

point , il y a un sous-ensemble t.q.

p D N p D

Pr Pr , Dp D p p N p p

p N p p N p

ff ff f C

18

I. Interprétation comme un graphe Un graphe non-orienté G est :

Un ensemble V (noeuds);

Un sous-ensemble t.q.

Etant donné un champs de Markov, on définit un graphe de la façon suivante :

E V V

, ,v v E v v E

, , t.q.V D E p p D D p N p

19

Un sous-ensemble est une clique ssi : .

On définit comme l’ensemble de toutes les cliques dans le graphe G.

I. Cliques

S V , , ,s s S S s s E

2VQ G

20

I. Distributions de Gibbs Pour une fonction : Q(G) £ CD ! R,

la probabilité suivante est appelée une distribution de Gibbs:

1Pr exp

expDf C

q qq Q G

f Z U f

Z U f

U ff

21

I. Distribution de Gibbs U est appelé l’énergie. Z est

appelé le fonction de partition. Pour une distribution de Gibbs,

l’estimée MAP prend une forme simple:

argminDf C

f U f

22

I. Théorème de Hammersley-Clifford 1971. Très important parce qu’il

permit la construction facile de champs de Markov.

Pour chaque fonction , est un champs de Markov.

Pour chaque champs de Markov Pr, on peut trouver une fonction t.q.

Conclusion: GIBBS = MRF

Pr

Pr Pr

23

I. Estimées Utilité = fonction de coût :

Utilité moyenne :

Estimée :

ˆ ,̂ PrDf C

ff ff

ˆˆargmax

Df Cff

Г : CD £ CD ! R

24

I. Estimées : MAP Maximum A Posteriori :

ˆ

ˆ ˆ, ,

ˆ ˆPr

ˆargmaxPrDf C

ff ff

ff

ff

25

I. Estimées : MPM “Marginal Posterior Mode”

ˆ

ˆ ˆ, ,

ˆ ˆPr

ˆargmaxPrp

p pp D

pp D

p pf C

ff ff

ff

ff

26

I. Estimées : champs moyen Erreur quadratique moyenne.

2

2 2

ˆ ˆ,

ˆ ˆ ˆ2

p pp D

p p p pp D

ff ff

ff ff f

ff

Partie II : exemples

28

II. Exemple 1 : bruit La lumière reflétée par la

scène est bruitée avant d’attendre la caméra : Conditions atmosphériques ; Bruit photonique et

électronique dans la caméra.

On veut connaître l’image originale avant l’addition de bruit. On connaît l’image bruitée.

29

II. Exemple 1 : modélisation On veut modéliser deux choses :

La formation de l’image à partir de la scène ;

La scène : l’image originale est inconnue.

Le domaine D est l’ensemble de pixels dans l’image.

La scène prend des valeurs dans R (image monochromatique).

30

II. Exemple 1 : formation On suppose que le bruit est :

Additif : le bruit s’ajoute au signal ; Stationnaire : la probabilité d’une

configuration de bruit est la même pour toutes les translations possibles ;

Blanc : le bruit en un point est indépendant du bruit aux autres points ;

Gaussien : le niveau de bruit en chaque point est distribué selon une loi gaussienne.

31

II. Exemple 1 : formation Le bruit est un champs de Markov

trivial. Toutes les variables sont indépendantes.

Le graphe n’a pas d’arcs:

12 2

Pr , ; ,

; , exp

p pp D

p p p p

I S G I S

G I S I S

32

II : Exemple 1 : la Scène Qu’est-ce que l’on sait de la scène

 ?

Peut-être rien : Pr(S) = constant.

Les estimées par le MAP, MPM et la moyenne sont en accord : S = I.

On n’a rien fait. Pas très satisfaisant !

33

II. Exemple 1 : la Scène En fait, on sait beaucoup plus de

choses sur la scène.

Une hypothèse souvent utilisée est que la scène est plus lisse que l’image. Deux pixels voisins ont généralement

des valeurs proches.

34

II. Exemple 1 : la Scène On utilise un voisinage à 4 ou 8 voisins :

Le modèle est stationnaire ( est constant).

Z est une fonction de .

84

21Pr exp p pp D p N p

S Z S S

35

II. Exemple 1 : difficultés Le modèle de la scène n’est pas très bon :

Le terme quadratique est trop fort ;

Les images ont des discontinuités.

On ne connait pas ou .

On doit : Soit les estimer ;

Soit les intégrer (marginaliser).

36

II. Exemple 2 : classification On suppose que, dans la scène, il y a des

classes différentes.

Les classes sont indexées par les éléments d’un ensemble L.

On veut assigner une de ces étiquettes à chaque point dans le domaine de l’image.

Donc la scène est une fonction de D vers L.

37

II. Exemple 2 : images satellitaires Une des tâches importantes dans

le traitement d’images satellitaires est d’identifier les diverses classes de couverture du terrain. Zones urbaines ou

suburbaines ; Forêts ; Aéroports ; Routes.

38

II. Exemple 2 : la Scène Comme toujours, le graphe est

formé par les pixels dans D.

Deux modèles sont les plus fréquents : Indépendant : chaque étiquette ne

dépend pas de ses voisins (classification pixélique) ;

Modèle de Potts : chaque pixel essaie d’avoir la même étiquette de ses 4 ou 8 voisins (classification contextuelle).

39

II. Exemple 2 : formation Normalement, on fait l’hypothèse

suivante ( est le sous-ensemble qui a l comme cible) :

Pour chaque étiquette, on a un modèle d’images qui ne contient que cette classe.

lR D

Pr Prl lR R

l L

I S I S l

40

II. Exemple 2 : formation : niveaux de gris

Chaque classe a un niveau de gris moyen et une variance.

Cela veut dire que

2 2

Pr exp

R

R R l p lp R

I S l I

2 2

Pr exp

Rl

lpS p S p

p Dl L

I S I

41

II. Exemple 2 : la Scène : indépendant

Chaque pixel est distribué selon la même loi : .

Cela veut dire que

Pr p lS l

Pr S pp D

S

42

II. Exemple 2 : la Scène : indépendant

Si Si l’on connaît les valeurs   ;

L’estimée MAP devient

l1

l L

constantl

2argminp p ll LS I

43

II. Exemple 2 : difficultés Le problème est que

chaque pixel prend sa décision seul.

L’estimée est trop rugueuse.

Il faut régulariser la solution en utilisant une probabilité a priori plus compliquée.

44

II. Exemple 2 : la Scène : Potts

Le modèle de Potts favorise les configurations qui contiennent des voisins avec la même étiquette.

1Pr exp 1 ,p pp p N p

S Z S S

45

II. Exemple 2 : la Scène : Potts

Le modèle de Potts rend la solution plus lisse et plus homogène.

Partie III : algorithmes

47

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

aussi calculer la valeur des paramètres des modèles choisis.

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

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

Exemple : le recuit simulé peut prendre des heures dans des cas compliqués. Pour pallier ce problème si les images sont très grandes, on peut paralléliser.

48

III. Simulation Objet : synthétiser des configurations de

champs markoviens suivant une certaine distribution de Gibbs.

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

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

1984).

49

III. Simulation : MCMC “Markov Chain Monte Carlo”.

Soit une configuration dépendant du temps : .

Construire 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 forte

probabilité

50

III. Simulation : Metropolis Tirer 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

51

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

Choix d’un point p dans le domaine D ;

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

Le choix d’un point p est fait : Soit par échantillonnage ;

Soit par balayage déterministe.

52

III. Échantillonneur de Gibbs 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

53

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

Estimée du 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

54

III. Recuit Simulé : relaxation stochastique Introduction d’un facteur de

température T :

Quand , devient 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

55

III. Recuit Simulé : descente de température On prouve la convergence vers le

minimum global si :

Le plus souvent : pour aller plus vite.

Convergence entre 300 et 1000 itérations.

log

kT t

t

, 1tT t kC C

T

t

56

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é (modes).

57

III. Algorithmes sous-optimaux : ICM

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

sur le résultat ; Convergence en ~10 à 30 itérations Très utilisé.

Cf. gradient.

58

III. Algorithmes sous-optimaux : HCF (Chou et Brown 1988) 

“High 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é.

0U

0stab min 0pc Cp U f c U

59

III. Algorithmes sous-optimaux : HCF (Chou et Brown 1988)

A 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é-évaluées.

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

Algorithme déterministe ;

Convergence en ~1 à 5 itérations (après avoir fait un ICM en général).

60

III. Variantes Algorithmes multi-grilles :

Pyramide sur les étiquettes ;

Pyramide sur les données.

Algorithmes multi-échelles : Pyramide sur étiquettes ;

Données mono-résolution.

61

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

paramètres.

Pour les estimer, deux approches : Etre bayésien : marginaliser ;

Estimation.

62

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

quantités par lesquelles on n’est pas intéressé.

Pr Pr ,

1Pr , Pr Pr

Pr

S I S I

I S SI

63

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

Normalement on ne connaît pas S :

Algorithme EM (Dempster, 1977) : 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