Rotations discrètes

Mode d’emploi pour faire tourner une image numérique

Piste rouge Le 5 mai 2018  - Ecrit par  Pierre-Antoine Guihéneuf Voir les commentaires (2)

Comment faire pour tourner une image numérique d’un certain angle ? Cette question est finalement un peu plus complexe qu’on ne pourrait le croire : on verra que si on applique successivement un grand nombre de fois l’algorithme naïf, alors l’image perd énormément en qualité.

Une première idée d’algorithme

Essayons de nous mettre dans la peau des premiers ingénieurs confrontés à cette question au moment de l’avènement des images numériques. Leur but était de trouver un moyen simple, algorithmique, de tourner une image numérique d’un angle donné.

Pour commencer, une image numérique, qu’est-ce que c’est ? C’est une grille formée de petits carrés appelés pixels ; chacun de ces petits carrés étant colorié d’une couleur uniforme. En pratique, on se débrouille pour qu’il y ait assez de ces petits carrés pour qu’ils ne soient pas perceptibles ; mais si on zoome assez sur une image on peut les voir apparaître — comme sur la photo suivante de Claude Shannon, où on a agrandi la région de son œil droit :

Choisissons maintenant un angle dont on veut faire tourner notre image, disons 20°. Quel algorithme peut-on mettre en place pour qu’un ordinateur nous donne l’image tournée d’exactement 20° ?

La première idée qui vient à l’esprit est en général la suivante. On choisit un pixel de l’image de départ, qui est par exemple vert. On considère le point au centre de ce pixel, et on le fait tourner d’un angle de 20° par rapport au centre de l’image. Le point obtenu tombe dans un certain petit carré de la grille, que l’on colorie en vert. L’image tournée de 20° est obtenue en répétant cette opération pour chaque pixel de l’image de départ. Voilà ce que ça donne sur un exemple, avec un zoom sur la partie centrale :

Quelque chose cloche : la couleur de certains pixels de l’image tournée n’est pas du tout définie : si on tourne tous les centres des pixels de l’image de départ, on rate un certain nombre de pixels de l’image d’arrivée [1].

Une petite réparation

Pour éviter ce problème, une astuce consiste à faire les choses à l’envers : on choisit un pixel de l’image d’arrivée, et on tourne son centre de -20° (l’opposé de l’angle qu’on avait choisi au départ). Le point obtenu tombe alors dans un des pixels de l’image de départ, qui est par exemple bleu. On colorie alors le pixel qu’on avait choisi au départ en bleu. On répète l’opération pour chaque pixel de l’image d’arrivée, et ce coup-ci la couleur de chaque pixel est bien définie ! Voilà le résultat sur notre exemple favori (de nouveau, avec un zoom) :

Si on zoome un peu on voit que le résultat est moins bon que l’image de départ, mais en tous cas l’algorithme semble bien meilleur que le précédent.

La perte d’information

Malheureusement, lorsqu’on réfléchit un peu à notre algorithme, on se rend compte qu’il y a encore un problème : la couleur de certains pixels de l’image de départ ne se retrouve pas forcément dans l’image d’arrivée. La proportion de tels pixels de l’image dont la couleur est perdue lors de la rotation est appelée perte d’information.

Notre algorithme nous donnera un résultat d’autant plus satisfaisant que cette perte d’information sera petite : une perte d’information proche de 1 signifie que la couleur de la plupart des pixels de l’image de départ a été perdue lors de la rotation.

Une petite remarque : dans notre cas, la perte d’information est égale à la proportion de pixels dont la couleur n’est pas définie par la première méthode de rotation. On peut s’en convaincre avec l’animation suivante : les pixels blancs sont ceux dont la couleur n’est pas définie avec la première méthode, tandis que les bleus foncés sont ceux où la couleur d’un pixel a été perdue avec la seconde méthode.

Quelques lignes de code suffisent pour calculer la perte d’information associée à chaque angle $\alpha$ de rotation possible. Voici le résultat qu’on obtient, avec en abscisse l’angle et en ordonnée la perte d’information :

La courbe ressemble pas mal à celle d’une fonction du type sinus, avec de petits pics par-ci par-là. Et effectivement, on peut montrer le résultat :

Propriété : Si on appelle $P(\alpha)$ la perte d’information associée à l’angle $\alpha$, alors pour « la plupart » [2] des angles $\alpha$ entre $0$ et $90°$, \[ P(\alpha) = \big(\cos(\alpha) + \sin(\alpha)-1\big)^2. \]

Voilà ce que donne cette formule en version graphique.

Ça ressemble quand même pas mal à la courbe obtenue expérimentalement !

On déduit aussi du théorème qu’en dehors d’un nombre fini d’angles « pathologiques », la perte d’information est toujours inférieure à $3 - 2\sqrt 2 \simeq 0,17$. Autrement dit, on ne perdra jamais plus de $17\%$ des données.

Quelques idées de la démonstration de cette propriété

Rappelons que la perte d’information est égale à la proportion de pixels dont la couleur n’est pas définie avec le premier algorithme de rotation.

Décidons de repérer les centres des pixels par des coordonnées entières. On considère donc un tel centre, de coordonnées $(x,y)$, et on veut savoir si sa couleur est bien définie à l’aide de la première méthode.

C’est le cas si dans le pixel de centre $(x,y)$, on trouve le centre d’un pixel qu’on a tourné d’un angle $\alpha$ ; on note $(a,b)$ les coordonnées (entières) de ce centre. En formules, si on note $C$ le carré de côté 1 centré en l’origine et $R_\alpha$ la rotation d’angle $\alpha$, on a
\[R_\alpha \begin{pmatrix} a \\ b \end{pmatrix} \in \begin{pmatrix} x \\ y \end{pmatrix} + C.\]
Autrement dit, en prenant la rotation d’angle $-\alpha$,
\[R_{-\alpha} \begin{pmatrix} x \\ y \end{pmatrix} \in R_{-\alpha}C + \begin{pmatrix} a \\ b \end{pmatrix}.\]

Cela nous dit que la couleur du pixel de centre $(x,y)$ est bien définie si et seulement si le point
\[R_{-\alpha} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} \cos(\alpha) x + \sin(\alpha) y \\ -\sin(\alpha) x + \cos(\alpha) y \end{pmatrix}\]
est dans un des carrés gris de la figure suivante :

Il s’avère que pour la plupart des angles de rotation, la proportion de points $(x,y)$ tels que le point $R_{-\alpha}(x,y)$ correspondant n’est pas dans un des carrés gris vaut exactement l’aire du petit carré rouge [3]. Autrement dit, dans ce cas, la perte d’information est l’aire du petit carré rouge ; un petit peu de géométrie permet de calculer le côté de ce carré : il vaut $\cos(\alpha) + \sin(\alpha)-1$. Par conséquent, son aire est $\big(\cos(\alpha) + \sin(\alpha)-1\big)^2$, ce qui est exactement ce qu’on voulait démontrer.

Ça ne s’arrête plus de tourner...

Que se passe-t-il lorsqu’on fait plusieurs rotations successives ? C’est une question assez naturelle pour un mathématicien : d’une part il aime bien en général « itérer » les transformations, c’est-à-dire les répéter plusieurs fois, d’autre part l’étude de la perte d’information après plusieurs rotations successives permet d’estimer la robustesse de notre algorithme de rotation. Voilà ce qu’on obtient après 18 rotations successives de 20° (l’image est de nouveau bien droite, simplement parce qu’on a tourné de 18*20° = 360°, soit un tour complet).

On voit que la qualité de l’image est bien moins bonne qu’au départ : notre pauvre Shannon est tout pixelisé ! Pour comparer avec la première méthode, voici ce qu’elle produit, et ce n’est vraiment pas terrible du tout : seulement une petite partie des pixels ont leur couleur bien définie [4].

On a en fait un théorème qui démontre que pour la plupart des angles, ça se passe mal : on a une perte d’information très grande lorsqu’on fait beaucoup de rotations successives.

Théorème [G15] : Pour « la plupart » [5] des angles $\alpha$, si on applique assez de fois la rotation d’angle $\alpha$, alors la perte d’information sera arbitrairement proche de $1$ [6].

Cela n’est pas vraiment une bonne nouvelle pour notre algorithme de rotation : si on l’applique plusieurs fois, on perdra une grande quantité de l’information présente dans l’image initiale.

La preuve de ce théorème fait intervenir de la géométrie des espaces de grande dimension, et en particulier le théorème de Hajòs expliqué ici.

Mais alors, comment fait-on en pratique ?

En pratique, ce n’est pas du tout cet algorithme « naïf » qui est utilisé par les logiciels de traitement d’images.

Aux débuts des images numériques, on utilisait des cisaillements [P86] : toute rotation s’exprime comme la composition de trois transformations appelées transvections (shear en anglais). Le plus simple est certainement de visualiser ce que ça donne sur un exemple (voir aussi [Dat15]) :

Pour les fans de formules, voilà comment on écrit la matrice de rotation :

\[\begin{pmatrix} \cos\alpha & -\sin\alpha \\ \sin\alpha & \cos\alpha \end{pmatrix} = \begin{pmatrix} 1 & -\tan(\alpha/2) \\ 0 &1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ \sin \alpha & 1 \end{pmatrix} \begin{pmatrix} 1 & -\tan(\alpha/2) \\ 0 &1 \end{pmatrix} \]

L’avantage est que toute transvection donne lieu à une transformation de l’image où on ne perd pas d’information ; autrement dit, si on connaît l’angle duquel on a tourné l’image, on est capable de retrouver l’image de départ à partir de l’image tournée. Pas de chance, ça n’empêche pas l’apparition de flou dans l’image, c’est même pire qu’avec l’algorithme naïf : voilà ce que ça donne après 18 rotations successives

Pas terrible... En effet, si une perte d’information grande assure la mauvaise qualité de l’image transformée, une perte d’information nulle n’implique pas que cette qualité sera bonne : les pixels peuvent être localement « mélangés », entraînant un flou dans l’image obtenue [7].

Les algorithmes de rotation actuels utilisent plutôt des interpolations : pour obtenir la couleur d’un pixel de l’image tournée, on fait tourner le centre de ce pixel de l’angle opposé et on fait une moyenne des couleurs des pixels avoisinants. Tout le jeu consiste à choisir le type de moyenne adéquat... Voilà le résultat, après 18 rotations successives, avec une interpolation linéaire :

C’est bien meilleur que les algorithmes précédents ! Actuellement, les logiciels de traitement d’images comme Gimp proposent même d’autres types d’interpolation, encore meilleurs, et répondant aux doux noms de cubique ou sync. Dans tous les cas, la qualité d’une image sera détériorée d’autant qu’on l’aura tournée un grand nombre de fois : pas de solution miracle !


Références :

[Dat15] Une page en anglais expliquant un peu plus en détail le principe des cisaillements.

[G15] Pierre-Antoine Guihéneuf, Degree of recurrence of generic diffeomorphisms, arXiv:1510.00723.

[P86] A.W. Paeth, « A fast Algorithm for General Raster Rotation », Proc. Graphics Interface, pp.77-81, Vancouver (Canada) May 1986.

Post-scriptum :

L’auteur et la rédaction d’IdM remercient chaudement les relecteurs ayant contribué à l’amélioration de l’article : muriel salvatori, amic, Romain Dujardin, Renaud Chabrier, QuentinB et Michaël Bages. L’auteur tient aussi à remercier les secrétaires de rédaction.

Article édité par Romain Dujardin

Notes

[1L’ensemble des pixels qu’on rate forme un ensemble quasi-cristal appelé ensemble modèle, comme expliqué dans cet article.

[2Pour que la formule soit vérifiée, il suffit que $\cos^2(\alpha)$ soit irrationnel, autrement dit que ce ne soit pas une fraction : le nombre d’angles qui ne vérifient pas la formule est au plus dénombrable. De plus, si le dénominateur de $\cos^2(\alpha)$ est assez grand, alors la formule est vraie à $\varepsilon$ près.

[3La preuve de cela repose sur un peu d’algèbre combinée à une propriété d’équiréparition similaire au critère de Weyl.

[4On voit apparaître une figure qui ressemble un peu à celle présentée dans cet article, mais je crois qu’il n’y a pas vraiment de lien logique entre les deux phénomènes, en dehors du fait qu’ils viennent tous les deux de rotations.

[5Pour que le théorème soit vrai, il suffit que $\cos(\alpha)$ soit transcendant, autrement dit qu’il ne soit pas solution d’équation polynomiale à coefficients entiers : le nombre d’angles qui ne vérifient pas la formule est au plus dénombrable. De plus, en dehors d’un nombre fini d’angles $\alpha$, la perte d’information sera à terme plus grande que $1-\varepsilon$.

[6On a un résultat similaire dans le cas où on applique à chaque fois une rotation d’un angle différent. Dans ce cas, on a des conditions de généricité sur la suite des angles successifs.

[7Rappelons qu’il y a quand même un avantage à avoir une perte d’information nulle : on peut revenir en arrière ; autrement dit si on applique la suite des rotations d’angles opposés, on retombe sur l’image initiale ; c’est complètement impossible lorsque les rotations induisent une grande perte d’information.

Partager cet article

Pour citer cet article :

Pierre-Antoine Guihéneuf — «Rotations discrètes» — Images des Mathématiques, CNRS, 2018

Commentaire sur l'article

  • Rotations discrètes

    le 16 mai à 15:28, par Denis Chadebec

    Une notation m’est inconnue, lue après la ligne 8 de la démonstration du théorème sur la perte d’information : que veut dire « vecteur B appartient à vecteur A + le nombre C » ?
    Denis Chadebec

    Répondre à ce message
    • Rotations discrètes

      le 16 mai à 15:33, par Pierre-Antoine Guihéneuf

      Bonjour,

      La notation $C$ désigne un carré. La ligne en question doit donc être lue : « le vecteur $B$ appartient à vecteur $A$ + le carré $C$ », autrement dit « le vecteur $B$ appartient au translaté du carré $C$ par le vecteur $A$ ».

      Bien cordialement

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM