Projet MBAI
Zoom par zero-padding
Lionel Steinitz et Nils Raynaud
Une méthode classique pour agrandir une image consiste à dupliquer les pixels de l'image d'origine, ce qui a pour effet d'introduire un effet <<d'escalier>> qui visuellement n'est pas agréable.
Nous allons introduire ici la méthode de <<zero-padding>>, qui permet d'effectuer un zoom sur l'image sans effet d'escalier. Le zero-padding consiste en fait à considérer la transformée de Fourier discrète de l'image comme celle d'une image plus grande où les hautes fréquences auraient été annulées.
On verra cependant qu'un autre phénomène indésirable apparaît : on observe des oscillations de la luminosité de l'image sur les bords de celles-ci. On montrera comment remédier à ce problème en appliquant la méthode à la transformée en cosinus discrète (DCT) et non plus à la transformée de Fourier discrète (DFT).
On considèrera des images en niveaux de gris, étant donné que le traitement d'une image couleur revient à traiter trois images en niveaux de gris.
I.Rappels sur la transformée de Fourier discrète (DFT)
Cliquez ici.
II.Mise en oeuvre de la méthode de zero-padding
On considère l'image comme un signal périodique, dont la période horizontale est la largeur L1 de l'image, et dont la période verticale est la hauteur H1 de l'image.
On effectue alors la transformée discrète de l'image : on obtient ainsi une matrice complexe de la même taille que l'image de départ. Notons H1*L1 la taille de cette matrice.
Si l'on veut obtenir une image finale de taille H2*L2, avec H2>H1 et L2>L1, on rajoute des zéros dans la matrice transformée de Fourier de façon à lui donner la taille H2*L2, en plaçant les zéros sur les hautes fréquences, c'est-à-dire sur les fréquences que l'on ne connaît parmi les fréquences de l'image zoomée. On effectue ensuite une transformée de Fourier inverse, qui nous donne une image de la taille désirée.
Remarquons que le contenu fréquentiel de l'image finale est exactement le même que celui de l'image d'origine. Ainsi plus l'agrandissement est important, plus l'image paraît floue, puisque l'on n'a apporté aucun détail.
L'algorithme est le suivant:
- transformation de Fourier discrète suivant les lignes, puis suivant les colonnes (ou l'inverse)
- rajouter des zéros autour de la matrice transformée pour lui donner la taille voulue.
- Opérer une transformation de Fourier discrète inverse suivant les lignes, puis suivant les colonnes (ou l'inverse).
Attention :
ce schéma n'est valable que si l'implémentation de la transformée de Fourier discrète place la fréquence (0,0) au centre de la matrice des coefficients de Fourier de l'image. Dans le cas où la fréquence nulle se trouve en haut à gauche de la matrice, comme c'est le cas pour l'implémentation sous matlab, en raison de la périodicité du spectre de l'image, les hautes fréquences sont atteintes au milieu de la matrice :
Résultats
image d'origine :
A gauche, image zoomée par duplication des pixels. A droite, image zoomée par zero-padding.
La différence est plus visible sur un détail (les détails ont été agrandis de la même manière, par duplication des pixels) :
A gauche, le zoom classique, à droite, le zero-padding :
III.Le phénomène de Gibbs sur les bords de l'image
AComme on peut le voir sur le détails des images précédentes, le zero-padding fait apparaître des oscillations vers les bords de l'image.
L'explication en est la suivante :
Dès lors que l'on tronque la série de Fourier d'un signal périodique, c'est-à-dire si l'on ne conserve que les basses fréquences, la restitution du signal perd en précision. Mais cela a aussi pour effet d'entrainer de légères oscillations du signal au voisinage des discontinuités, qui s'atténuent d'autant plus vite que l'on a conservé de hautes fréquences, mais dont l'amplitude ne dépend pas de l'ordre de cette troncature. Pour un signal unidimensionnel temporel, par exemple, cela signifie que le nombre de termes de la série de Fourier que l'on garde ne diminue en rien l'amplitude des oscillations; en revanche, à partir d'un certain nombre de termes, ces oscillations s'amortiront suffisamment vite dans le temps pour que les appareils de mesure ne les détectent pas. Il s'agit du phénomène de Gibbs. En voici l'illustration sur un signal unidimensionnel :
Pour les images :
Lorsque l'on prend la transformée de Fourier de l'image (c'est-à-dire des lignes puis des colonnes), on traite chaque ligne de l'image comme un signal périodique dont la période est la largeur de l'image, et il en va de même pour les colonnes. On recolle ainsi côte à côte des niveaux de gris provenant de bords opposés de l'image, ce qui introduit a priori une forte discontinuité, qui correspond, dans le plan de Fourier, a des très hautes fréquences. Or, les hautes fréquences de l'image zoomée, étant inconnues, sont prises égales a zéro. L'effet de Gibbs est alors flagrant: on voit apparaître des oscillations caractéristiques sur les bords de l'image, et de façon générale sur toutes les fortes discontinuités (sur des contours très marqués) à l'intérieur de l'image.
Cela est flagrant sur l'exemple suivant, où l'on observera que l'effet de Gibbs est aussi présent à l'intérieur de l'image, là où il y a de fortes discontinuités :
image d'origine :
Image zoomée par duplication des pixels :
Image zoomée par zero-padding :
Remarque :
On peut observer que les images zoomées par zero-padding perdent un peu de contraste : les zones blanches, par exemple, deviennent plus sombres. Ce n'est guère étonnant car les oscillations de Gibbs dépassent la valeur 255 (blanc), et donc, lorsque l'on renormalise l'image pour avoir des valeurs de niveaux de gris entre 0 et 255, le blanc, qui n'est plus la valeur maximale, devient plus sombre. C'est-à-dire que la matrice de l'image finale contient des valeurs inférieures à zéro, d'autres supérieures à 255. Il suffit de tronquer les valeurs de cette matrice pour retrouver le même contraste qu'à l'origine. Une autre manière de résoudre ce problème est de saturer la courbe d'intensité de l'image (renormalisée) vers 0 et vers 255, ce qui donne le résultat suivant :
Nous allons voir comment supprimer les oscillations indésirables dues à l'effet de Gibbs là où elles sont les plus fréquentes, donc les plus gênantes, à savoir sur les bords de l'image.
IV.Suppression du phénomène de Gibbs sur les bords de l'image
Le phénomène de Gibbs sur les bords de l'image provient de ce que la périodisation de l'image introduit de fortes discontinuités au niveau des contours. Une façon de s'affranchir de cet effet négatif est de symétriser l'image avant d'opérer la transformation de Fourier, ce qui revient à opérer une transformée en cosinus (DCT) de l'image (en effet, symétriser le signal revient à le rendre pair, et ainsi la série de Fourier associée ne fait intervenir que des cosinus). De cette façon, on supprime l'effet de Gibbs aux bords de l'image. En revanche, les fortes discontinuités dues à l'image elle-même ne peuvent être supprimées.
L'algorithme est identique au précédent:
- symétrisation de l'image.
- transformation de Fourier suivant les lignes, puis suivant les colonnes (ou l'inverse).
- rajouter des zéros autour de la matrice transformée pour lui donner le double de la taille voulue.
- Opérer une transformation en de Fourier inverse suivant les lignes, puis suivant les colonnes (ou l'inverse).
- Tronquer l'image obtenue de façon à ce qu'elle ne soit plus symmétrique.
Une image symétrisée :
Si l'on reprend notre image de damier, on voit que cette nouvelle technique a effectivement fait disparaître l'effet de Gibbs sur les bords de l'image. En revanche, l'effet de Gibbs dû aux discontinuités de l'image elle-même demeurent, comme l'on pouvait s'y attendre :
Mais pour des images plus conventionnelles, l'amélioration est notable :
Image d'origine :
Image zoomée par duplication des pixels :
A gauche, image zoomée par zero-padding en Fourier. A droite, image zoomée par zero-padding avec transformation en cosinus :
La différence est plus flagrante si l'on réhausse le contraste :
A gauche, image zoomée par zero-padding en Fourier. A droite, image zoomée par zero-padding avec transformation en cosinus :
Si vous voulez voir d'autres exemples.
On peut se douter que ce procédé est plus lourd en temps de calcul, mais, comme vous pouvez le constater sur les exemples, les résultats sont bien meilleurs.
Nils Raynaud
Last modified: Fri Mar 17 18:09:43 MET 2000