Big Logo

List of Student Projects


Rotation chez Fourier

Servet Patrick
Section Microtechnique


February 2001


Résumé

Le but de ce projet est de comprendre puis d'implémenter deux algorithmes de rotation d'image se basant tout les deux sur les propriétés de la transformée de Fourier mais faute de temps seule le premier algorithme proposé par C.B Owen en 1996 a été implémenté.
Il s'agit d'un algorithme de rotation 2-D séparable. Il décompose la rotion en opérations de translation 1-D qui s'applique aux colonnes et aux lignes de l'image. Cette décomposition en trois étapes consiste uniquement en opérations de décalage (skew operations) sur les lignes et sur les colonnes:


Fig. 1 Décompsition de la rotation

De plus cet algorithme de rotation réalise l'interpolation et le décalage des lignes et des colonnes dans le domaine de Fourier en utilisant la FFT.


Fig. 2 Diagramme en bloc de l'opérateur de translation digital

Cependant, et c'est là la nouveauté, il met en évidence les problèmes liés à cette méthode et propose un algorithme pour y remédier. En effet il montre qu'un décalage dans une dimension de l'image équivaut à un décalage dans l'autre dimension et de signe opposé du spectre de l'image. Or le spectre d'une image carré étant une image carré, le spectre de l'image après décalage n'est plus carré mais plutÙt un parallélogramme qui ne tient plus dans les limites du carré délimitées par le théorème de l'échantillonage. L'image étant par définition bande limitée avant le décalage, les coins du parallélogramme après le décalage introduisent des problème d'aliasing comme le montre la figure 3.


Fig. 3 Problème d'aliasing après décalage

Ce problème se répétant lors des trois décalages le résultat final est montré dans la figure 4.


Fig. 4 "Déplacement" spectral après les trois étapes de la rotation

On s'attend donc à ce qu'une partie du spectre doive être masquée pour que l'image soit sans aliasing. Cependant cela ne peut se faire par un filtrage ultérieur car les deux zones grisées de la figure 3 sont à l'intérieur des limites spectrales et constitues donc une condition d'erreur évidente. Il s'agit d'un mélange incorrect du spectre.
L'algorithme d'Owen propose une méthode pour éviter ce mélange en étendant deux fois l'image mais dans une seule dimension à la fois.

Résultat:

Les résultats obtenus avec l'algorithme d'Owen sont très bon. En effet avec le protocole de test utilisé, c'est à dire une succession de 15 rotations de 24° en ne conservant que la zone centrale de l'image (de 128 à 383 pixels aussi bien en x qu'en y) puis calcul du SNR, ils sont meilleurs que toutes les méthodes testées précédemment dans le laboratoire.
Cependant visuellement la différence entre le résultat de Owen et un algorithme similaire mais ne se préoccupant pas des problèmes de mélange spectral décrit plus haut n'est pratiquement pas visible.
De plus il faut remarquer que les résutats de l'algorithme d'Owen sont meilleur pour des images riche en haute fréquences ce qui est normal vu que l'algorithme vise à supprimer les problèmes d'aliasing se produisant dans les hautes fréquences.


Fig.5 Résultats après les 15 rotations ainsi que leur différences avec l'image de départ avec (a) Owen (b) idem sans résoudre les problèmes de mélange spectral (b) plus proche voisin


Fig.6 Résultats sous forme numérique