Utilisateur:Béranger BRACQ/Brouillon

• Gérer mon brouillon
• Demander une relecture (voir les demandes)
• Publier mon brouillon

Cette page est un brouillon appartenant à Béranger BRACQ

Conseils de rédaction

• → N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
• → Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.

Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :

• Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
• Indiquez les éléments démontrant la notoriété du sujet (aide).
• Liez chaque fait présenté à une source de qualité (quelles sources  – comment les insérer).
• Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
• Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).

• → Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.

Régularisation et non-négativité en déconvolution

En mathématiques, la déconvolution est un procédé algorithmique destiné à inverser les effets de la convolution. La déconvolution est largement utilisé en traitement du signal et traitement d'image, notamment en microscopie et astronomie. La régularisation et la non-négativité sont des concepts mathématiques inventés par divers chercheurs afin de parfaire les résultats de la déconvolution.

Principe de la déconvolution.

La déconvolution est une opération en traitement du signal qui, idéalement, corrige les effets de la convolution produite par un système linéaire et invariant dans le temps avec un signal d’entrée. Dans la déconvolution, le signal de sortie et le système sont connus; l’objectif étant de reconstruire le signal d’entrée.

Dans la pratique, pour effectuer la déconvolution une image, on cherche à optimiser le critère des moindres carrés. On recherche donc l'estimateur ${\hat {X}}$ qui minimise la fonction $J(X)$ :

$J(X)=||Y-HX||^{2}$

Cependant, au sens de Hadamard, il y a deux problèmes à retenir :

• Il n'y a pas unicité de la solution
• La solution retenue ne sera pas stable

En effet, la déconvolution présente un problème majeur lié au bruit : les variations de l'image observée $Y$ sont inversement proportionnelles aux variations de l'image restaurée $X$. De petites fluctuations sur $Y$seront lourdes d'impact sur $X$.

Notion de régularisation

La régularisation est une méthode mathématique qui consiste à chercher l'estimateur ${\hat {X}}$ qui minimise l'énergie U(X). Le but est de lisser le bruit (dans les zones homogènes) et de préserver les discontinuités (détails intéressants et contours).

$U(X)={\frac {1}{\sigma ^{2}}}||Y-HX||^{2}+\lambda \phi (X)$

• ${\frac {1}{\sigma ^{2}}}||Y-HX||^{2}$ représente le terme d'attache aux données (la donnée étant $Y$);
  

• $\lambda$ et $\delta$ sont appelés les hyperparamètres du modèle : $\lambda$ est le poids du terme de régularisation par rapport à l'attache aux données et $\delta$ fixe le seuil des discontinuités;

• $\phi (X)$ est le terme de régularisation, qui pénalise les images bruitées, avec :

$\phi (X)=\sum _{i,j}{\Bigg (}\varphi {\bigg (}{\frac {(\mathrm {d} _{X}X)_{(}i,j)}{\delta }}{\bigg )}+\varphi {\bigg (}{\frac {(\mathrm {d} _{Y}X)_{(}i,j)}{\delta }}{\bigg )}{\Bigg )}$

Le gradient de $X$ dans la formule précédente représente la différence entre pixels voisins.

Les gradients augmentent $U(X)$ car $\varphi$ est croissante : l'amplification du bruit est limitée. Préservation des forts gradients (contours) car $\varphi$ augmente moins vite au-delà d'un certain seuil. $\varphi$ doit vérifier trois propriétés :

• $\lim _{x\to 0 \atop x\geq 0}{\frac {\varphi '(u)}{2u}}=1$

• $\lim _{u\to \infty }{\frac {\varphi '(u)}{2u}}=0$

• ${\frac {\varphi '(u)}{2u}}$ est continue et strictement décroissante sur $[0,+\infty [$

$\lambda$ et $\delta$ peuvent être choisis manuellement, mais le travail de recherche des bons paramètres est long et fastidieux, il est préférable de trouver une méthode pour les choisir automatiquement.

Choix automatique des hyperparamètres

La détermination manuelle de $(\lambda ,\delta )$ est longue et fastidieuse. Pour cela, il est préférable d'adopter des méthodes déterministes, comme par exemple la méthode du maximum de vraisemblance, afin de gagner en efficacité.

Méthode du maximum de vraisemblance

On cherche à optimiser un critère qui dépend de ces hyperparamètres. C'est le maximum de vraisemblance de $\lambda$, $\delta$ sur l'image observée Y:

$({\hat {\lambda }},{\hat {\delta }})=ar\!g\,\max {P(Y|\lambda ,\delta )}$

Cela revient à maximiser une probabilité par rapport à $\lambda$,$\delta$

$P(Y|\lambda ,\delta )=\sum _{X\in \Omega }P(Y,X|\lambda ,\delta )$

Où $\Omega$ est l'ensemble des images $N_{x}*N_{y}$, avec $M$ niveau de gris

On emploie la règle de Bayes pour calculer la vraisemblance :

$P(X,Y|\lambda ,\delta )=P(Y|X,\lambda ,\delta )P(X|\lambda ,\delta )$

Deux lois de probabilité apparaissent :

• $P(Y|X,\lambda ,\delta )$ : probabilité d'obtenir l'observation $Y$ sachant l'image de départ $X$ (vraisemblance jointe de $X$ et des hyperparamètres);
  

• $P(X|\lambda ,\delta )$ : probabilité a priori sur l'image $X$ calculée sans attache aux données, elle caractérise le type de régularisation choisie.

Calcul de la vraisemblance

$Y$ suit la distribution du bruit gaussien $N(\sigma )$, $N=Y-HX$:

$P(Y|X,\lambda ,\delta )={\frac {1}{K_{\sigma }}}e^{-}{\frac {\|Y-HX\|^{2}}{2\sigma ^{2}}}$

Distribution a priori de $X$ : c'est une probabilité gibbsienne, car $X$ est un champ de Markov.

$P(X|\lambda ,\delta )={\frac {1}{Z}}e^{-\phi (X,\lambda ,\delta )}$

La vraisemblance de $\lambda$,$\delta$ s'écrit donc :

$P(Y|\lambda ,\delta )={\frac {Z_{Y}}{ZK_{\sigma }}}$

$Z$,$Z_{Y}$ est une fonction de partition (voir physique statistique) : ces deux termes sont des constantes de normalisation.

$Z=\sum _{X\in \Omega }e^{-\phi (X,\lambda ,\delta )}$

$Z_{Y}=\sum _{X\in \Omega }e^{-{\frac {\|Y-HX\|^{2}}{2\sigma ^{2}}}-\phi (X,\lambda ,\delta )}$

$\Omega$ est l'ensemble des images $N_{x}*N_{y}$, $M$ niveaux de gris.

$Card(\Omega )=M^{N_{x}*N_{y}}$ : minimum $256^{128*128}$

Il est donc impossible de calculer directement les fonctions de partition à cause de la dimension de l'espace $\Omega$. Il est préférable de les estimer que de les calculer.

Calcul du logarithme de la vraisemblance

Il faut minimiser $J=-\log {P}(Y|\lambda ,\delta )$ par rapport à $\lambda$,$\delta$ .

Pour cela, il faut calculer ses dérivées par rapport aux hyperparamètres :

${\frac {\partial J}{\partial \theta }}={\frac {\partial \log {Z_{Y}}}{\partial \theta }}-{\frac {\partial \log {Z}}{\partial \theta }}$

avec : ${\frac {\partial \log {Z}}{\partial \theta }}=-E_{X\sim P(X|\lambda ,\delta )}[{\frac {\partial U(X|\lambda ,\delta )}{\partial \theta }}]$

où $E[]$ est l'espérance calculée sur des échantillons $X$

Il y a par conséquent deux types d'espérance à calculer :

• $E[]$ loi a priori : $X\sim P(X|\lambda ,\delta )$ sans attache aux données

• $E[]$ loi a posteriori : $X\sim P(X|Y,\lambda ,\delta )$ avec attache aux données

Modèle a priori

Au voisinage du premier ordre, on utilise des échantillonneurs de Geman & Yang, Gibbs ou encore Metropolis.

• λ=0,3 et δ=10
  λ=0,3 et δ=10
• λ=1 et δ=15
  λ=1 et δ=15
• λ=1 et δ=5
  λ=1 et δ=5

Modèle a posteriori

On s'attache ici aux données (image observée Y), on avoisine un ordre élevé dépendant de la taille de H. On emploie uniquement l'échantillonneur de Geman & Yang modifié puisque ceux de Gibbs et de Metropolis sont trop lents a ce niveau d'ordre.

• λ=0,5 et δ=10
  λ=0,5 et δ=10
• λ=0,5 et δ=1
  λ=0,5 et δ=1
• λ=10 et δ=10
  λ=10 et δ=10
• Image Y
  Image Y

Echantillonneur de Geman & Yang modifié

On utilise un développement semi-quadratique de $\varphi$:

$\varphi (u)\mapsto (u-b)^{2}+\psi (b)$

On introduit ici la variable auxiliaire $b$, images auxiliaires $B^{x}$ et $B^{y}$ (gradients sur $X$ et $Y$). On effectue un échantillonnage de triplets ($X$, $B^{x}$,$B^{y}$) de manière alternée sur $X$ et $B^{x}$,$B^{y}$. Les pixels de $B^{x}$ et $B^{y}$ sont indépendants et la probabilité de $X$ sachant $B^{x}$, $B^{y}$ est gaussienne. Le tirage de $X$ s'effectue en une seule fois (contrairement à Gibbs et Metropolis), le traitement est indépendant de la taille du voisinage, ce qui en fait un algorithme rapide pour échantillonner la distribution a posteriori.

Algorithme d'estimation MCMCML

MCMCML signifie Markov Chain Monte Carlo Maximum Likelihood". Dans cet algorithme, on minimise le logarithme de la vraisemblance :

$({\hat {\lambda }},{\hat {\delta }})=arg\,min[-\log {P(Y,\lambda ,\delta )}]$

Méthode de descente : utilisation du gradient du critère sur $\lambda$,$\delta$ . On fixe $\delta$, et on utilise uniquement $\nabla _{\lambda }$, le gradient du critère par rapport à $\lambda$ est fixé, car pour tout $\delta$ on peut trouver un $\lambda$ tel que le couple $(\lambda ,\delta )$ soit optimal. L'estimation et la restauration sont simultanées : échantillonneur de Geman-Yang initialisé avec ${\hat {X}}$)

Le cheminement de l'algorithme est détaillé dans ce lien.

Algorithme de restauration ICM-DCT

Cet algorithme, déterministe, est basé sur l'échantillonneur de Geman & Yang modifié a posteriori, dont on supprime la partie aléatoire.

On utilise le même développement semi-quadratique de $\varphi$ :

$\varphi (u)\mapsto (u-b)^{2}+\psi (b)$

variable auxiliaire $b$, images auxiliaires $B^{x}$ et $B^{y}$ (gradients sur $x$ et $y$). Minimisation alternée sur $x$ et $B^{x}$, $B^{y}$. Le critère à optimiser s'écrit alors :

${\hat {X}}=\arg \,\inf[{\frac {1}{2\sigma ^{2}}}\|Y-HX\|^{2}+\phi ^{*}(X,B^{x},B^{y})]$

avec le nouveau terme de régularisation :

$\phi ^{*}(X,B^{x},B^{y})=\lambda ^{2}(\|{\frac {\nabla X}{\delta }}-B^{x}\|^{2}+\sum \psi (B_{ij}^{x})+(\|{\frac {\nabla X}{\delta }}-B^{y}\|^{2}+\sum \psi (B_{ij}^{y}))$

Le cheminement de l'algorithme est détaillé dans ce lien.

Notion de non-négativité

Le problème standard de factorisation en matrices à coefficients positifs, sous la forme la plus générique possible, s’exprime comme suit : étant donnée une matrice V de dimensions F × N à coefficients réels positifs ou nuls, la NMF est la détermination d’une factorisation approchée :

V ≈ WH = V

où W et H sont des matrices de dimensions respectives F × K et K × N dont tous les coefficients sont des réels positifs ou nuls, et où l’opérateur ≈ désigne une « approximation » à définir.

L’ordre du modèle, K, est habituellement choisi tel que FK + KN ≪ F N, ce qui fait de la NMF une technique de réduction de la dimensionnalité.

Si l’on attribue plus ou moins de fait la « paternité » de la NMF à Lee et Seung en1999, il faut cependant remarquer que, cinq ans plus tôt, Paatero et Tapper en 1994 posent et résolvent le même problème.

La gloire lui échappera pour une dénomination malheureuse : la « factorisation en matrices positives » (PMF, ou Positive Matrix Factorization) contient une ambiguïté sur la notion de matrice positive (est-elle à coefficients positifs, ou semi-définie positive c’est-à-dire à valeurs propres réelles positives ?).

Malgré cette maladresse, on trouve de nombreuses applications de la PMF entre 1994 et 1999, principalement dans des domaines liés à la chimie, l’étude des pollutions et les sciences de l’environnement.

Néanmoins, c’est véritablement Lee et Seung en 1999 qui font date et créent l’enthousiasme autour de la NMF, qui prend alors son nom définitif et commence à être appliquée dans de très nombreux domaines.

Nous illustrerons la variété des domaines d’applications par quelques exemples :

– Traitement de l’image : représentation d’images de visages, classification d’images.

– Traitement du texte : surveillance de messages électroniques, classification de documents, extraction de caractéristiques sémantiques dans des textes.

– Économie : diversification de portefeuilles d’actions

– Biologie : clustering 2 de gènes impliqués dans le cancer, détection de l’activité neuronale pour les interfaces cerveau-machine.

– Gastronomie : clustering de scotch whiskeys.

Applications

Les principales applications actuelles de la déconvolution sont la sismologie ou encore l’optique.

- En optique, le terme de « Déconvolution » est spécifiquement utilisé pour se référer aux processus qui corrigent les distorsions optiques (diffraction et aberrations des lentilles) liées à l’utilisation des microscopes, des télescopes, et autres instruments optiques. - La déconvolution permet ainsi d’obtenir des images plus claires, parfois même plus proche de la réalité.

Un exemple concret d’application: Les images du « Télescope Hubble » sont souvent traitées par déconvolution pour les rendre plus nettes, et donc plus facilement interprétables.

- Le concept de déconvolution avait une application au début de la réflexion de la sismologie . En 1950 , Enders Robinson était étudiant au MIT . Il a travaillé avec d'autres au MIT , comme Norbert Wiener , Norman Levinson afin de développer le " modèle de convolution " d'un sismogramme de réflexion . Ce modèle transpose le sismogramme enregistré en une fonction. C'est la convolution d'une fonction dite "Terre de réflectivité" et d'une onde sismique émise à partir d'une source ponctuelle pendant un temps donné représentant la durée d'enregistrement.

- Le principe de déconvolution, se retrouve également dans des domaines tels que la médecine ou la chimie. En effet les procédés de chromatographie ou d'imagerie médicale nécessitent un traitement par déconvolution afin de facilité la lecture des résultats.

Sources

Rôle de la régularisation

Estimation rapide du paramètre de régularisation en déconvolution d’images

http://micro.magnet.fsu.edu/primer/digitalimaging/deconvolution/deconvolutionhome.html

http://visl.technion.ac.il/demos/bss

http://pichotjm.free.fr/Photos/Traitement/Deconv/Deconv.php

http://www.dspguide.com/ch17/2.htm

1. Haeberlé O., Colicchio B., «Technique d'amélioration de la résolution en microscopie de fluorescence: de la production des photons au traitements des images. », Spectra Analyse, vol. 244,‎ 2005, p. 22-26 (lire en ligne [archive])
2. Nasse M. J., Woehl J. C., Huant S., « High resolution mapping of the three dimensional point spread function in the near-focus region of a confocal microscope », Appl. Phys. Lett., vol. 90, no 031106,‎ 2007, p. 031106-1-3(DOI 10.1063/1.2431764)
3. Blind Image Deconvolution: Theory and Applications sur Google Livres