Embed Size (px)
Citation preview
Page 1
ZENG Tieyong, PhD Defense
Université Paris Nord
EtudeEtude de modde modèèles les variationnelsvariationnels
et apprentissage de dictionnaireset apprentissage de dictionnaires
ZENG Tieyong
Oct. 9, 2007
Page 2
ZENG Tieyong, PhD Defense
Université Paris Nord
Introduction
� Restauration/débruitage d’images
� Seuillage par ondelettes
� Modèle de Rudin-Osher-Fatemi
� Modèle
� NL-means
� K-SVD
� Représentations parcimonieuse
� Basis pursuit
� Matching Pursuit, OMP
� Décomposition d’images
� Modèle de R.O.F, Modèle de Meyer
� Analyse en composantes morphologiques (MCA)
Modèles variationnels + Dictionnaire
Page 3
ZENG Tieyong, PhD Defense
Université Paris Nord
Plan
� Dictionnaire et modèle
� Représentations parcimonieuses
� Résolution du Basis Pursuit
� Etude de deux modèles d’optimisation
� MP shrinkage
� Une approche statistique pour l‘apprentissage de dictionnaires
� Conclusion
Page 4
ZENG Tieyong, PhD Defense
Université Paris Nord
Le modèle
Nous considérons le problème du débruitage, une image est observée en présence
de bruit,
où:
image idéale
bruit blanc Gaussien
On voudrait résoudre ce problème par le modèle
pour un dictionnaire et la variation totale discrète:
avec
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 5
ZENG Tieyong, PhD Defense
Université Paris Nord
Résolution du modèle
Méthode de pénalisation
où
Algorithme de descente de gradient à pas optimal
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 6
ZENG Tieyong, PhD Defense
Université Paris Nord
Problème principal: choisir
� Dictionnaires non invariant par translations
� Dictionnaire de paquets d‘ondelettes, 2002 F.Malgouyres
� Dictionnaire de curvelettes, 2002 E.Candes & F.Guo
� Nouvelle approche
� Dictionnaire invariant par translations
Considérer un sous-ensemble fini de
Pour tout et , on définit
Enfin, on utilise le dictionnaire
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 7
ZENG Tieyong, PhD Defense
Université Paris Nord
Dictionnaires de Gabor
Filtre de Gabor
Gabor I
Gabor IIGabor III
Curvelet
Transformée de Fourier
Petit, moyen, grand
Zones intéressantesParamètre définissant les dictionnaires
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 8
ZENG Tieyong, PhD Defense
Université Paris Nord
Expériences
Image bruitée curvelet moyen Gabor II moyen
PSNR - 26.88
PSNR - 20.81
Gabor II, III: presque isotrope!
Presque les mêmes!
Zone 1
Zone 2 Gabor III, II
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 9
ZENG Tieyong, PhD Defense
Université Paris Nord
Post-traitement pour l’algorithme
K-SVD
La performance de débruitage constitue l’état de l’art
Efface peu de détail
Perd un peu de texture
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
L’algorithme K-SVD suppose que tous les patches d’images naturelles peuvent être
représentés parcimonieusement dans un dictionnaire . Pour restaurer
à partir de l’image bruitée
cette méthode essaie de résoudre un problème de minimisation:
Page 10
ZENG Tieyong, PhD Defense
Université Paris Nord
Combien d'itérations pour la
pénalisation du .
ROF k=1
Choisir k au maximum de TV !
TV: bruit+texture/structure
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Le modèle peut retrouver les
informations perdues rapidement.
Nombre d’itération k
Page 11
ZENG Tieyong, PhD Defense
Université Paris Nord
Algorithme de post-traitementIntroduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Choisir kmaximisant TV
Résultat de K-SVD
Dictionnaire de Gabor II
On peut proposer un algorithme de post-traitement
Page 12
ZENG Tieyong, PhD Defense
Université Paris Nord
Expériences
+7.90db +8.49db
+4.89db
Image bruitée
Post-traitement
Niveau du bruit
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 13
ZENG Tieyong, PhD Defense
Université Paris Nord
Analyse du modèle
Supposons que est la solution du modèle
En utilisant la théorie de l'optimisation, nous savons qu’il existe un vecteur de Kuhn-
Tucker
tel que:
Quand le dictionnaire contient seulement un élément ,
il est intéressant de choisir:
Dictionnaire ad-hoc
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Courbure de l’image Lenna
Page 14
ZENG Tieyong, PhD Defense
Université Paris Nord
Expérience sur le dictionnaire
ad-hoc
Débruitage avec le dictionnaire ad-hocROF
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 15
ZENG Tieyong, PhD Defense
Université Paris Nord
Expérience en décomposition
d'image
Composante « texte »
Image idéale Image bruitée
Dictionnaire
Composante « fond »
ROF
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 16
ZENG Tieyong, PhD Defense
Université Paris Nord
Expérience en débruitage d’image
dictionnaire
ROF
Mécanisme:
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 17
ZENG Tieyong, PhD Defense
Université Paris Nord
Plan
� Dictionnaire pour le modèle
� Représentations parcimonieuses
� Résolution du Basis Pursuit
� Etude de deux modèles d’optimisation
� MP shrinkage
� Une approche statistique pour l‘apprentissage de dictionnaires
� Conclusion
Page 18
ZENG Tieyong, PhD Defense
Université Paris Nord
Variante du Basis Pursuit
Données: une image , un dictionnaire
But : chercher une représentation parcimonieuse
� Modèle du Basis Pursuit
pour
� Nouvelle variante
pour
But
Construire un algorithme efficace pour résoudre cette variante sous
conditions :
A.
B.
Pourquoi la nouvelle variante ?
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 19
ZENG Tieyong, PhD Defense
Université Paris Nord
Formulation duale et
algorithme de point proximal
Le problème pré-dual pour est
On voudrait le résoudre par une méthode qui calcule également un de ses vecteurs
de Kuhn-Tucker . Ce dernier est une solution de
L'algorithme de point proximal prend la forme
pour une séquence croissante et le convexe
Les résultats généraux sur l'algorithme de point proximal garantiront que
converge vers la solution de (P).
Que peut-on dire pour des vecteurs correspondants de Kuhn-Tucker ?
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 20
ZENG Tieyong, PhD Defense
Université Paris Nord
L'algorithme principal
Nous écrivons:
où
Nous proposons l'algorithme suivant :
On peut montrer que :
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 21
ZENG Tieyong, PhD Defense
Université Paris Nord
Aspects importants
� On peut calculer exactement:
� On peut calculer exactement:
� Le gradient de f est Lipschitz !
Il existe une constante telle que pour tous les , dans , on a toujours:
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 22
ZENG Tieyong, PhD Defense
Université Paris Nord
Algorithme d'Uzawa
Nous pouvons résoudre la maximisation
par l’algorithme de gradient projeté à pas constant.
Pour trouver le
la méthode d'Uzawa s’écrit:
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
la régle d’Armijo
Page 23
ZENG Tieyong, PhD Defense
Université Paris Nord
Description des expériences
Nous utilisons le dictionnaire de cosinus locaux qui est symétrique, invariant par translations
Pour évaluer la convergence,
A. Mesure de parcimonie
B. Mesure de régularité
C. Mesure de fidélité aux données
D. Temps
correspondant à une décomposition et à une recomposition dans le dictionnaire
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 24
ZENG Tieyong, PhD Defense
Université Paris Nord
Algorithme de descente
parallèle sur les coordonnées
L’algorithme de descente parallèle sur les coordonnées (PCD) résout le modèle du Basis
Pursuit par
Seuillage Itératif (IT)
choisit toujours
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 25
ZENG Tieyong, PhD Defense
Université Paris Nord
Comparaison de la mesure de
fidélité aux donnéesIntroduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Mesure de fidélité aux données
Page 26
ZENG Tieyong, PhD Defense
Université Paris Nord
Comparaison de la mesure de
régularitéIntroduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Mesure de régularité
Page 27
ZENG Tieyong, PhD Defense
Université Paris Nord
Comparaison de mesure de
parcimonie Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Mesure de parcimonie
Page 28
ZENG Tieyong, PhD Defense
Université Paris Nord
Deux modèles d’optimisation
dans
Nous considérons deux modèles:
où est un dictionnaire fini dans et
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Supposons que est normalisé, on cherche une
représentation parcimonieuse d’une image bruitée:
où
Page 29
ZENG Tieyong, PhD Defense
Université Paris Nord
Résultats de stabilité
Résultat similaire pour
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
La cohérence mutuelle d’un dictionnaire normalisé est définie comme
Page 30
ZENG Tieyong, PhD Defense
Université Paris Nord
MP shrinkage hilbertien
� Fonction de seuillage générale
� Contrôlée par
� Contrôlée strictement par
� Le saut est défini comme: Seuillage dur
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Seuillage douxSeuillage durIdentitéGarrote non-négativeFirm shrinkageSeuillage généralisé
Page 31
ZENG Tieyong, PhD Defense
Université Paris Nord
Données : Un espace de Hilbert , une image bruitée
un dictionnaire , fini, normalisé
But: chercher une représentation parcimonieuse
MP shrinkage
On propose un algorithme:
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
MP shrinkageMP
Seuillage par ondelettes
Page 32
ZENG Tieyong, PhD Defense
Université Paris Nord
Aspects théoriques sur le MP
shrinkageIntroduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
� Théorème 2. Si la fonction est contrôlée par . Alors
converge quand m tend à .
Soient:
� Théorème 3. Si le saut de la fonction est strictement positif, alors le
MP shrinkage s’arrête automatiquement après au plus de
itérations, où est la partie entière.
� Théorème 4. Si la fonction est strictement contrôlée par . Alors quand
, converge à la projection . Précisément, il existe une
constante tels que:
� Théorème 5. Si la fonction est contrôlée par . Alors
Page 33
ZENG Tieyong, PhD Defense
Université Paris Nord
ExpérienceIntroduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
PSNR en fonction du nombre d’itérations M pour le seuillage doux et divers
Page 34
ZENG Tieyong, PhD Defense
Université Paris Nord
Plan
� Dictionnaire pour le modèle
� Représentations parcimonieuses
� Résolution du Basis Pursuit
� Etude de deux modèles d’optimisation
� MP shrinkage
� Une approche statistique pour l‘apprentissage de dictionnaires
� Conclusion
Page 35
ZENG Tieyong, PhD Defense
Université Paris Nord
Approche statistique pour
l’apprentissage de dictionnaires
On note:
le tore discret support des images
l’espace des images
une famille d’atomes locaux générant le dictionnaire
translation des atomes sur le plan
Nous considérons le modèle génératif suivant :
où
variable de Bernoulli, i.i.d, drapeau: présence/absence
coefficient aléatoire , i.i.d, intensité
bruit blanc
But: étant donné , apprendre
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 36
ZENG Tieyong, PhD Defense
Université Paris Nord
Deux modèles : BEM et BGM
� Le modèle du Bernoulli-Exponentielle (BEM)
est de loi exponentielle
La vraisemblance complète
� Le modèle de Bernoulli-Gaussien (BGM)est de loi gaussienne
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
l’espace des paramètres
l’espace des paramètres
Page 37
ZENG Tieyong, PhD Defense
Université Paris Nord
Problème d'identifiabilité
On se pose une question:
Peut-on distinguer deux distributions sur Y données par deux paramètres différents ?
Pour les deux modèles: sous conditions faibles, OUI !
� BEM
Relation d'équivalence: si et
modulo une permutation sur les indices
Prop. Si sont différentes, alors le BEM est identifiable dans
� BGM
Résultat similaire.
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 38
ZENG Tieyong, PhD Defense
Université Paris Nord
De la vraisemblance aux MCMC
L'approche de maximum de vraisemblance calcule
La méthode EM est itérative
où est la loi a posteriori de (X, B) sachant Y
avec Z est le facteur de normalisation et est la mesure dominante.
(E)-step, (M)-step
Nous pouvons approcher la loi a posteriori par MCMC:
On génère une chaîne de Markov ergodique associée à
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 39
ZENG Tieyong, PhD Defense
Université Paris Nord
Champ moyen pour BGM
difficile à calculer
Champ moyen: on approche par un produit de lois sur et
Considérer l’ensemble des lois produits sur et telles que
est de loi Bernoulli
est de loi
Ensuite nous prenons
où K est la divergence de Kullback-Leibler.
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 40
ZENG Tieyong, PhD Defense
Université Paris Nord
L’équation de point fixe et
mise à jour du paramètre
Pour la divergence de Kullback-Leibler, la loi optimale satisfait une équation de
point fixe
Ensuite, l'étape de mise à jour du paramètre est donnée par
Par conséquent, on a:
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 41
ZENG Tieyong, PhD Defense
Université Paris Nord
Expériences
MCMC
Champ moyen
Ensemble d’apprentissage
Dictionnaire idéal
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 42
ZENG Tieyong, PhD Defense
Université Paris Nord
Expériences sur le champ
moyen
Exemples dans l’ensemble
d’apprentissage
Dictionnaire idéal
Champ moyen
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Page 43
ZENG Tieyong, PhD Defense
Université Paris Nord
Expériences sur le champ
moyenIntroduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Dictionnaire idéal Le champ moyen
Page 44
ZENG Tieyong, PhD Defense
Université Paris Nord
Conclusion et discussion
MécanismeMécanisme
Variante du BP
Variante du BP
Post-traitement
Post-traitement
MP shrinkage
Méthode d’optimisation
Dict. inv. par trans. Modèle de
Autre dictionnaire de
type Gabor
En utilisant
la courbureDécomposition d’images
Plus d’images
Vitesse de
convergence
Comparaison avec des
méthodes itératives
Représentations parcimonieuses Apprentissage
de dictionnaires
Image naturelle
Débruitage
DictionnaireDictionnaire
Introduction-Dictionnaire-Basis Pursuit-Stabilité-MP shrinkage-Apprentissage-Conclusion
Parcimonie
Page 45
ZENG Tieyong, PhD Defense
Université Paris Nord
Merci!
Page 46
ZENG Tieyong, PhD Defense
Université Paris Nord
Gabor filtre
Page 47
ZENG Tieyong, PhD Defense
Université Paris Nord
Détails de K-SVD
Page 48
ZENG Tieyong, PhD Defense
Université Paris Nord
Régle d’Armijo
Le principe de cet algorithme (pour la maximisation) est de définir
L'algorithme emploie la mise à jour
où pour un fixé et pour le premier nombre entier non
négatif m tel que
pour
Nous avons limité notre recherche à
et prenons:
Page 49
ZENG Tieyong, PhD Defense
Université Paris Nord
Lenna pour post-traitement
Page 50
ZENG Tieyong, PhD Defense
Université Paris Nord
Algorithme d’acceptation-rejet
Soit une loi d’intérêt de densité et une loi de proposition de densité telle que
sur le support de . Alors, on peu simuler suivant avec l’algorithme suivant
Page 51
ZENG Tieyong, PhD Defense
Université Paris Nord
Champ moyen pour image
naturelle
