TP n°2 : Interpolation et transformations géométriques ====================================================== Mise en route ------------- Comme dans les séances précédentes, vous aurez à tester un certain nombre d'algorithmes sur des images. Rappel: pour copier une image dans le fichier src (utilisé pour les commandes), il vous suffit d'entrer la commande ccopy lena.img src (ici l'image choisie est lena.img). La liste des images disponibles pour ce TP s'obtient par ls $MEGAWAVE2/data/tp2 et vous pouvez visualiser n'importe laquelle de ces images par cview & Si vous avez besoin de connaître la taille d'une image, utilisez la commande fsize Dans un premier temps, nous allons comparer différents interpolateurs (sinus cardinal sinc, bicubique de Keys, splines) dans leur aptitude à réaliser les transformations euclidiennes (translation, rotation, et zoom avant). Le cas particulier du zoom arrière (réduction) sera considéré plus tard car la perte d'information qu'il requiert nécessite une approche légèrement différente. Dans les expériences qui vont suivre, vous serez amenés à mettre en évidence essentiellement quatre types de défauts liés à l'interpolation : la pixellisation, le flou, le ringing et l'aliasing. 1. Translation -------------- Si la translation d'une image d'un vecteur entier ne pose pas de problème, en revanche la translation sub-pixellique est l'exemple typique d'un processus nécessitant une interpolation de l'image. Comme nous l'avons vu en cours, l'interpolation sinc discrète (interpolation à l'aide de la transformée de Fourier discrète) permet de réaliser cette transformation de façon réversible (donc sans perte d'information), et c'est la seule méthode linéaire vérifiant cette propriété. En choisissant successivement plusieurs images, testez la translation de vecteur (1/2,1/2) à l'aide de la commande fftrot -x 0.5 -y 0.5 src trans et comparez le résultat à l'original. N'hésitez pas à zoomer le résultat (cview -z ...) si besoin. Q1. Quel type de défaut observe-t-on sur les bords du cadre de l'image ? A quoi est il dû ? Pour limiter les oscillations de Gibbs introduites au bord de l'image par la périodisation brutale de celle-ci, on a souvent recours à une symétrisation de l'image, ce qui conduit formellement (mais aussi algorithmiquement en général) à remplacer la transformée de Fourier par la transformée en cosinus (la DCT, ou Discrete Cosine Transform, est utilisée par la technique de compression JPEG). Appliquez cette symétrisation à votre image source à l'aide de la commande fsym2 et visualisez le résultat. Visualisez ensuite le spectre de cette image symétrisée et justifiez ses propriétés de symétrie. Appliquez ensuite la translation de cette image symétrisée et ``dé-symétrisez'' le résultat par fsym2 -i. Q2. Vérifiez que les bords du cadre sont désormais bien traités. Quelles sont maintenant les parties de l'image où l'interpolation est discutable et pourquoi ? 2. Rotation ----------- La rotation d'une image est un transformation intéressante car elle met bien en évidence la capacité d'un interpolateur à préserver l'information contenue dans l'image. Commençons par ``préparer'' l'image source en la limitant à un disque fmaskrot src src_disc puis faisons lui subir 36 rotations de 10 degrés cp src_disc mov_0 @ n = 0 while ($n < 35) @ old = $n @ n ++ fzrt -o 0 mov_$old mov_$n 1 10 0 0 end Mkmovie Cmovie mov 0 35 cmview -l mov & (attention, cet ensemble de commandes ne fonctionnera pas si vous n'avez pas au préalable lancé tcsh). Le résultat est catastrophique mais ce n'est pas très étonnant compte tenu du fait que nous avons effecté la rotation au moyen d'une interpolation au plus proche voisin (option -o 0 de fzrt). Nous pouvons maintenant faire varier la méthode d'interpolation en changeant cette valeur (o=1,-3,3,5, taper fzrt seul pour obtenir la signification de ces nombres). Pour générer directement le résultat après 36 rotations (sans le film), vous pouvez utiliser les commandes cp src_disc rotated repeat 36 fzrt -o 0 rotated rotated 1 10 0 0 cview rotated & Vous pouvez aussi bien sûr changer le nombre de rotations et l'angle correspondant. Q3. Comparez et commentez les résultats obtenus pour chaque méthode d'interpolation (o=-3,1,3,5). A priori, une rotation par interpolation de Fourier (sinc) demanderait O(N^4) opérations, puisqu'en général n'y a pas de correspondance simple entre la grille de départ et la grille après rotation (sauf pour des angles multiples de pi/2...). Il est assez surprenant que l'on puisse en fait réaliser cette opération en O(N^2 log N) opérations, en décomposant la rotation en produit de glissements, ainsi nous l'avons vu en cours. Testez cette méthode en remplaçant le précédent "repeat ..." par repeat 36 fftrot -a 10 rotated rotated et observez le résultats obtenu. Q4. Que concluez-vous ? Pourquoi n'y a-t-il (quasiment) aucune perte d'information ? Quel est le prix à payer pour ce résultat ? Indication : vous pouvez faire afficher le temps de calcul lors de l'utilisation d'une commande en la faisant précéder de "time" (exemple: "time repeat 36 ... "); le premier nombre affiché (suivi d'un u minuscule) est alors le temps consacré au calcul (en secondes). 3. Zoom ------- Posons-nous maintenant le problème du zoom, c'est-à-dire de l'agrandissement d'une image par suréchantillonnage. D'après la théorie de Shannon, la ``bonne'' manière de procéder est ce que l'on appelle le zero-padding : on calcule la transformée de Fourier de l'image, on agrandit le domaine spectral en complétant les nouvelles hautes fréquences par zéro et on reprend la transformée de Fourier inverse. Cette opération est réalisée par la commande fftzoom. Exemple (à réaliser plutôt sur une image de petite taille) : fftzoom -z 4 src zoomed Visualisez ensuite le spectre de l'image initiale et celui de l'image agrandie, et vérifiez que le résultat est conforme à vos attentes. Q5. Quels défauts constatez-vous dans l'image agrandie par zero-padding ? Comment les expliquez-vous ? Comparez maintenant le résultat obtenu avec un zoom par interpolation spatiale cview -z 4 -o ... src & avec différentes méthodes d'interpolation (o=0,1,-3,3,5,7,9). Vous pouvez aussi utiliser la commande llview (que nous emploierons plus spécifiquement dans une séance ultérieure) en tapant llview -d 0 src & puis en utilisant le bouton de droite dans la fenêtre pour zoomer (taper 'h' pour une liste complète des commandes) et en cliquant dans la fenêtre de commandes pour changer la méthode d'interpolation. Q6. Comparez les différentes méthodes de zoom sur quelques images, et indiquez à chaque fois (en précisant le nom de l'image) la méthode qui vous semble réaliser le meilleur compromis. Quels sont les défauts mis en concurrence ? 4. Réduction ------------ La réduction d'une image ne peut se faire correctement par sous-échantillonnage direct car apparaît en général un phénomène d'aliasing dû au repliement spectral des fréquences qui ne peuvent plus être exprimées compte tenu de la résolution de la nouvelle image. Une coupure fréquentielle préalable est tout aussi délicate car si elle est réalisée brutalement, il y a apparition de ringing. Nous avons déjà constaté ces deux phénomènes lors de la dernière séance, mais vous pouvez les reproduire simplement en choisissant une image de grande taille (512 x 512) et en la dézoomant d'un facteur 4 de 2 façons différentes au moyen de fftzoom -i -z 4 src reduced1 puis de fsample src reduced2 4 A. Convolution préalable Pour obtenir un compromis entre l'aliasing et l'effet de Gibbs, il semble raisonnable de chercher à effectuer une coupure fréquentielle progressive en multipliant le spectre initial par une fonction porte ``adoucie''. Cette multiplication spectrale est équivalente à une convolution, et l'on souhaite en général que le support du noyau de convolution associé soit le plus petit possible, à la fois pour limiter le phénomène de diffusion produit dans l'image et pour pouvoir calculer rapidement cette convolution. Le choix typique est la convolution par une fonction de Gauss bidimensionnelle d'écart-type sigma. Pour simuler cette opération, nous pouvons utiliser la commande fsepconvol (option -g) suivie de fsample : fsepconvol -g 1.1 src flou fsample flou reduced 2 Q7. Expérimentalement, quelle valeur de sigma (option -g) vous semble la meilleure (pour l'image considérée) ? Essayez ensuite d'associer à cette convolution gaussienne une coupure fréquentielle exacte (commande fftzoom -i) et comparer avec la méthode précédente. Quel défaut potentiel de la réduction supprime-t-on ainsi ? B. Projection spline La réduction par convolution préalable (gaussienne ou prolate) n'est pas une projection : si l'image de départ est déjà sous-échantillonnable (i.e. si son spectre est déjà nul pour toutes les fréquences qui seront perdues lors du changement de résolution), alors alors il y aura tout de même une perte d'information lors de la convolution. Ceci n'était pas le cas avec un zoom Fourier inverse par coupure fréquentielle (fftzoom -i), qui, en revanche, est bien la projection L^2 associée à l'interpolation sinc. L'échantillonnage par splines tombe à point pour trancher ce dilemme : plutôt que de projeter dans l'espace des fonctions sinc, nous pouvons projeter dans une base de splines d'ordre donné (n). L'image réduite obtenue sera alors celle qui minimisera l'écart (en norme L^2) entre l'interpolée de l'image originale et l'interpolée de l'image réduite, les deux interpolations étant entendues au sens des splines d'ordre n. Cette opération est réalisée au moyen de la commande funzoom : funzoom -z 4 -o 0 src reduced A noter que pour l'ordre 0, la projection revient à intégrer l'image de départ (interpolée à l'ordre 0) sur une matrice de pixels carrés jointifs. Ce dispositif reproduit donc assez fidèlement le fonctionnement d'une matrice CCD. Q8. Testez et commentez l'influence de l'ordre de la base de splines utilisée (option -o, de 0 à 5) sur le résultat. Quel vous semble être le choix le plus adapté (en fonction de l'image utilisée) ?