Le but de ce travail est l'étude et l'implémentation de l'algorithme de zoom décrit dans l'article de F. Guichard et F. Malgouyres, ``Total Variation Based Interpolation''.
Nous décrirons brièvement le principe du zoom et l'algorithme de l'article, avant de donner quelques exemples et de comparer ces résultats à ceux donnés par des méthodes classiques.
Zoomer dans une image revient à augmenter la résolution de l'image, c'est-à-dire sur-échantillonner.
Si l'on veut sur-échantillonner une image et que l'on ne veut pas rajouter de plus hautes fréquences que celles contenues dans l'image de départ, on emploie la méthode du zero-padding. Cette méthode consiste à mettre à zéro les coefficients de Fourier correspondants aux hautes fréquences absentes dans l'image de départ. Ainsi, on aura la même information dans l'image initiale et l'image sur-échantillonnée. Cette méthode donne de très mauvais résultats visuels en pratique, en raison du phénomène de Gibbs.
De plus, avec une idée naive du zoom, on pourrait s'attendre à ce que les contours s'affinent et que les variations locales d'intensité lumineuse soient plus fortes. Ceci entraînerait une augmentation de la fréquence dans certaines parties de l'image.
F. Guichard et F. Malgouyres introduisent une méthode d'interpolation basée sur un calcul de la variation totale de l'image.
Dans l'article le signal u est un signal discret de taille N. Le signal w est un signal deux fois plus grand. Donc le facteur de zoom dans cet article est implicitement fixé à 2.
Si w est obtenu par interpolation de u, on peut vouloir une condition de réversibilité, à savoir que u peut être obtenu à partir de w par filtrage passe-bas puis sous-échantillonnage, ce qui est exprimé par la formulation:
où Q désigne l'opérateur de sous-échantillonnage et S désigne le filtre linéaire.
Si cette condition de réversibilité est satisfaite, l'article donne, dans le cas particulier où le facteur de zoom est de 2, une propriété sur les spectres des images. On a :
où 
est la réponse fréquentielle du filtre passe-bas.
Si l'on sous-échantillonne S(w), la propriété (2) exprime le phénomène du repliement spectral et quantifie la ``répartition'' des fréquences du signal initial discret dans le signal sous-échantillonné.
L'article introduit la notation pour désigner
l'espace des images w qui satisfont la propriété (1)
. On remarque que l'article définit cette propriété comme étant
une contrainte. Le paragraphe suivant donne une interprétation de
cette formule.
La méthode de l'article est similaire à celles de restauration
classiques où l'on profite d'une connaissance a priori sur l'image
à obtenir (appartenance à BV par exemple). D'où l'idée de formuler le
problème de l'estimation de l'image w à partir de u en contrôlant
la régularité de w - c'est-à-dire son appartenance à 
(connaissance a priori) :
où 
est un terme d'attache ou de fidélité aux
données - l'image u - et 
est un terme de régularisation,
par exemple la variation totale. Si 
est petit, on aura
une bonne fidélité aux données. Si augmente on aura une
image beaucoup plus régulière. Dans le cas qui nous intéresse,
le terme de fidélité peut être exprimé par la condition
1, c'est à dire l'appartenance à l'espace
. Il reste à choisir une mesure de régularité
pour le terme .
Dans le cas continu unidimensionnel, une mesure de régularité peut faire intervenir une norme sur la ``dérivée première'' du signal que l'on considère. Dans le cas d'un signal discret unidimensionnel de taille finie, l'article introduit la fonction
avec 
.
L'article détaille le principe du choix de 
et conclut
qu'une valeur intéressante de est 
. Cette
valeur particulière correspond à prendre la variation totale de
l'image.
L'article propose la méthode suivante. On souhaite minimiser
L'article suggère une méthode itérative basée sur une descente de gradient.
, par exemple avec la méthode du zero-padding;
;
;
;
où s est le pas d'adaptation que l'on peut
calculer pour avoir la plus forte minimisation à chaque étape.
Dans cette procédure on voit comment est formulée l'attache aux
données. En effet, la projection sur l'espace
garantit qu'à chaque étape on ne modifie pas l'information contenue
dans les basses fréquences qui correspondent à l'image initiale.
Pour la mise en oeuvre numerique, on supposera connues les techniques de calculs de la variation totale dans le cas discret.
Les exemples ont tous été obtenus avec notre programme. Les paramètres sont peu nombreux. Ils sont tous passés sur la ligne de commande sauf un (celui qui quantifie le pourcentage de coefficients à modifier). Quelques centaines d'itérations sont nécessaires pour obtenir un résultat si nous faisons décroître le pas avec r=0.95. Le pas initial est à 2.0 dans tous les exemples. Les calculs annexes PSNR/entropie, etc, ont été réalisés avec Matlab.
Nous présentons d'abord quelques images qui montrent que la qualité visuelle du zoom utilisé dans l'article est satisfaisante. Ensuite nous essayons de comparer quantitativement la méthode utilisant la minimisation de la variation totale avec les méthodes classiques d'interpolation.
Nous commençons par l'image de Lena afin d'illustrer la relative bonne performance qualitative du zoom (b = 0.2 dans le programme pour cet exemple et les suivants ou b est le facteur d'echelle attribue au terme de regularisation). Par rapport à une interpolation bilinéaire classique, on peut constater que les bords apparaissent davantage accentués et plus réguliers (l'effet marches d'escalier est atténué). En revanche dans les zones plus homogènes, on a l'impression que des détails de l'image sont perdus (comme des contrastes par exemple) et que certaines zones sont mises en relief de manière artificielle.
Comme deuxième exemple nous présentons cette fois une image où les structures caractéristiques apparaissent plus précisément que dans l'exemple précédent. L'objectif est de regarder comment ces structures se transforment pour de forts facteurs de zoom. L'exemple choisi est encore l'image d'un oeil qui offre une meilleure résolution que l'oeil de Lena. Par rapport à une interpolation classique on a encore une impression de meilleure netteté de l'image. En revanche, l'image obtenue avec une interpolation classique semble plus naturelle.
Dans l'exemple que nous donnons, nous sous-échantillonnons une image d'avion (objet simple et présentant peu de détails par ailleurs) de manière à ce que l'image apparaisse très pixélisée. De nombreuses structures de l'image initiale sont perdues lors de cette opération. Le zoom par minimisation de la variation totale donne un résultat visuel satisfaisant car il restitue très bien les bords.
Dans cette dernière section nous avons tenté de quantifier numériquement les résultats obtenus. Cette quantification est délicate car il faut pouvoir disposer de distances adéquates. Partant d'images offrant une bonne résolution, nous avons sous-échantillonné ces images et nous avons comparé différentes méthodes d'interpolation à l'aide de deux mesures, le rapport signal sur bruit en crête (PSNR : Peak Signal/Noise Ratio) qui quantifie l'erreur pixel par pixel entre deux images, et la distance de Kullback qui quantifie les différences de propriétés statistiques entre les images.
Entre deux images 
et 
de taille pxn et quantifiées sur 256
niveaux de gris, on définit le PSNR comme :
Pour calculer la distance de Kullback, on établit les histogrammes des deux images, et on en déduit une approximation des densités de probabilités des deux images. Entre deux densités de probabilité p(x) et q(x) on calcule la distance de Kullback par:
Pour la comparaison quantitative des méthodes, nous avons utilisée cette image de vélo. Le principal intérêt de cette image est qu'elle est de bonne qualité et que les objets apparaissent très précisement ce qui laisse penser qu'une bonne reconstitution par interpolation pourrait être atteinte. Les deux imagettes à droite sont des détails du résultat de l'interpolation. En haut, interpolation bicubique, en bas interpolation par variation totale. Nous rapportons ci-dessous les résultats de la comparaison. Les paramètres suivant ont été utilisés: -z 2 -s 2.0 -r 0.95 ou z est le facteur de zoom, s le pas de depart et r le facteur de reduction du pas.
On peut constater que la méthode d'interpolation par variation totale donne des résultats plutôt mauvais si l'on ne regarde que le PSNR. Ceci s'explique assez bien par le fait que l'image d'origine n'est pas exactement conservée pixel par pixel avec l'algorithme proposé dans l'article. Le PSNR n'est pas une bonne mesure de la qualité de l'image. En revanche la comparaison avec la distance de Kullback est plus favorable.
En dernier lieu, il nous a semblé intéressant de pouvoir quantifier l'erreur (PSNR) en fonction de la complexité de l'image. Nous avons utilisé l'entropie pour évaluer cette complexité puisque l'entropie représente la quantité d'information contenue dans un signal. Nous sommes partis d'une image satellite 512x512 présentant de nombreuses structures et nous l'avons décomposée en blocs (256 blocs 32 x 32). Nous avons calculé l'entropie de chaque bloc et nous avons ensuite évalué le PSNR sur chacun des blocs pour un zoom x2. On obtient la courbe de la figure. On constate encore une fois que l'interpolation bicubique présente un meilleur PSNR que le zoom par minimisation de la variation totale, quelle que soit l'entropie.
Les résultats apportés par le zoom par minimisation de la
variation totale sont plutôt satisfaisants, ils apportent une
qualité visuelle très acceptable, mais nous pensons que certaines
améliorations auraient été possibles en renoncant à quelques
contraintes de l'article (l'appartenance à 
était
peut-être une attache aux données trop forte pour faire
disparaître les oscillations de Gibbs.
De manière plus générale, on soulignera l'intérêt de méthodes d'interpolation efficaces pour augmenter la résolution des images. Les applications sont nombreuses: impression avec une bonne qualité des images, augmentation de la résolution des appareils numériques d'acquisition d'images (scanners, webcam, etc). Les techniques classiques d'interpolation basées sur la convolution de l'image avec un noyau unique, type bilinéaire ou bicubique, ont des limites évidentes. En revanche, définir le problème de l'augmentation de résolution comme un problème inverse mal conditionné paraît très intéressant. Il y a deux questions à se poser ensuite. Quelle information a priori est susceptible de donner de bons résultats? Quels sont les algorithmes à employer ?
Nous ne nous étendrons pas sur la réalisation du programme. Ecrit en langage C ANSI, nous nous sommes
efforcés de respecter un minimum de lisibilité du code. Nous avons séparé
la structure de données (les données manipulées par l'algorithme)
et le chemin de controle (la séquence des opérations effectuées sur
les données). La structure des données est représentée physiquement
par une structure 'Algorithme'. Le controle de l'algorithme se fait au niveau de la
fonction ControleAlgorithme qui se trouve dans le fichier algo.c.
Il est à noter que nous avons utilisé une bibliothèque de FFT : FFTW
disponible à l'adresse http://www.fftw.org.
Vous pouvez télécharger notre code source sous la forme d'un fichier
source.tar.gz.