Les transformations bijectives d'images

JP Delahaye et Ph Mathieu
Vous êtes le compteur visiteur de cette page

* Présentation générale

L'objectif de ce travail est l'étude des propriétés des transformations bijectives d'une image. Ce type de transformation déplace les points d'une image d'un endroit à un autre sans en ajouter ni en enlever aucun.

Une propriété remarquable de ces transformations bijectives est qu'elles reviennent toujours au point de départ après un nombre d'applications plus ou moins important. Par exemple, la transformation qui échange les lignes de numéros pairs avec les lignes de numéros impairs revient à son point de départ au bout de deux itérations. De même, la transformation Rotation Droite dans laquelle chaque point est déplacé d'un pixel vers la droite, revient au point de départ après un nombre d'itérations égal à la largeur de l'image.

voir la page Wikipedia à ce sujet.

Une applet a été réalisée pour illustrer les transformations présentées dans nos articles Images brouillées, Images retrouvées (num 242, dec 1997) et Une scytale Informatique (num 359, sept 2007) de la rubrique «Logique et Calcul» de la revue « Pour la Science.

Cette applet vous permet de charger une image de votre choix et de choisir une transformation (19 sont programmées) (onglet Paramètres), de lui appliquer différentes transformations Image Transformée, de calculer le temps de retour, d'aller en accès direct à l'itération n sans passer par les précédentes, de sauvegarder toutes les images obtenues, de visualiser les cheminements de points d'une transformation sur une image donnée (onglet Visualisation), d'appliquer des chaines de transformations et enfin d'intégrer un texte dans l'image afin de pratiquer la stéganographie (onglet Cryptage).

Email: N'hesitez pas à nous envoyer un mail si vous avez des remarques ou des idées d'amélioration.

Applet réalisée à partir de transfo.zip par M Braure, M Dref, N Kondratek, sous la direction de P Mathieu.
Vous pouvez aussi la télécharger sous forme d'application autonome. (Java 1.5)

Cette application nécessite Java 1.5 ou supérieur.
En cas de problème, aller sur http://www.java.com/fr

Conseils d'utilisation

  1. Pour des raisons techniques, l'applet est signée afin de permettre l'accès à vos images personnelles. Son chargement provoque l'affichage d'une fenetre d'acceptation qui pourrait inquiéter certains. Sans cet avertissement, une Applet ne pourrait pas accéder à votre disque.
  2. En choisissant des images dont le nombres de lignes et le nombre de colonnes sont des puissances de 2 (ou possèdent beaucoup de divisieurs) vous obtiendrez des temps de retour plus petits et donc ce sera sans doute plus sympa
  3. En choisissant un pas qui est un diviseur du nombre d'étapes, vous obtiendrez comme un effet de zoom sur la transformation (par ex prendre 256 pour un nombre d'étapes de 65536). Pour les longues périodes, c'est alors plus rapide et plus joli.
  4. Attention, certaines transformation nécessitent des images ayant une taille bien pécise et si elles ne l'ont pas, elles reconfigurent automatiquement l'image. Par exemple pour Hilbert l'image doit ête carrée et le coté doit être une puissance de 2. Si voux proposez du 240x160, l'image obtenue fera 128x128
  5. La partie Cryptographie permet l'usage de chaines de bijections : BO3;PH5 par exemple qui effectue 3 fois Boulanger puis 5 fois PhotoMaton. A cause des recadrages propres à chaque bijection, il est conseillé de ne pas utiliser Peano qui nécessite des tailles puissance de 3. En conséquence, partir d'une image 100x100 avec une chaine "PE5;HI5" recadre en 81x81 puis 64x64. Si on décode, on passe enfin en 27x27 ... un timbre poste

L'ancienne version du logiciel, réalisée en C++ est toujours disponible transfo.zip. Attention, cette version ne fonctionne que sous Windows.

Bijections programmées

Double Rotation
Déplacement d'un pixel de l'image sur l'axe des x et des y simultanément. Revient à décaler l'image d'un pixel vers le coin inférieur droit. Le coin inférieur droit est recopié au coin supérieur gauche. Pas de contrainte de taille d'image. Période: ppcm(largeur,hauteur).
Binaire
Fonctionne comme le mélange binaire en battage de cartes : on constitue le paquet des cartes en position paires qu'on fait suivre par le paquet des cartes en position impaire. Pour l'image, on considère les coordonnées linéaires (on met tous les pixels les uns derriere les autres : ligne du haut, ligne suivante, etc.) et on applique le principe du mélange binaire. Contrainte : largeur ou hauteur doit être pair. Période : Si le nb de points total (larg*haut) est 2^n la période est n.
Double Binaire
On mélange d'abord les lignes comme pour le mélange binaire ci dessus, puis on fait la même opération sur les colonnes. S'occuper d'abord des colonnes et ensuite des lignes donnerait évidemment le même résultat. Contrainte : largeur ET hauteur doivent être paires.
Trois Cycles
Les points étant pris en coordonnées linéaires, on découpe en 3 paquets : paquet 1 pixels 0,3,6,9 .., paquet 2 pixels 1,4,7,..., paquet 3 pixels 2,5,8,.... Le pixel i passe alors en position (i+3) pour le 1er paquet, (i+12) pour le second paquet, (i+30) pour le 3è paquet. Les coefficients 3,12,30 ont été choisis car ce sont des multiples de 3 (les points d'un paquet restant les mêmes) et permettent de faire "voyager" les paquets à différentes vitesses. Contrainte : largeur ou hauteur multiple de 3.
Quatre Cycles
Idem mais en 4 paquets avec des décalages de (4,12,20,36). Contrainte : largeur*hauteur multiple de 4.
En X
Pour chaque pixel, si son numéro de ligne est pair, on l'augmente de 2, s'il est impair on le diminue de 2. Même chose pour la colonne. Contrainte de taille d'image : hauteur et largeur paires. Période : ppcm(larg/2, haut/2)
Twist
L'image est tordue comme une lavette. Le point (i,j) part en (i+1,j+1). Pas de contrainte de taille d'image. Période : ppcm des n premiers entiers avec n=min(larg,long)
Photo Maton
L'image est recomposée en 4 images rétrécies récursivement. L'image est découpée en carrés de 4 pixels, le pixel en haut à droite d'un carré sert à recomposer une image de taille 1/2 en haut à droite, idem pour la partie en haut à gauche, en bas à droite, en bas à gauche. Contrainte de taille d'image : hauteur et largeur paires. Période : si larg=2^n et haut=2^m alors ppcm(n,m) sinon c'est plus complexe.
Boulanger
A la manière de la pâte du boulanger, l'image est étirée, puis repliée en dessous. Deux lignes consécutives sont imbriquées l'une dans l'autre (a1,a2,a3,.. et b1,b2,b3,.. donnent a1,b1,a2,b2,a3,b3,..). On obtient donc un rectangle 2 fois plus large et deux fois moins haut. Celui-ci est coupé en deux, la partie droite est placée en dessous après avoir été retournée. Ce qui redonne la taille initiale. Contrainte : Largeur et hauteur paires. Période : si larg=2^n et haut=2^m alors (n+m+1) sinon c'est plus complexe.
Couplage
Chaque étape est constituée d'une fois le PhotoMaton puis une fois le Boulanger.
Peano, Hilbert, Moore, Lebesgue
Voir MathCurve On s'appuie ici sur les courbes de Peano, Hilbert et Lebesgue (Pour Hilbert la courbe utilisée a été retournée de 180 degrés). Ces courbes parcourrent tous les pixels du carré, ce qui permet de numéroter les pixels. La transformation consiste à faire passer le pixel 1 en position 2, le pixel 2 en position 3 etc. Contraintes : Les images doivent être carrées. Pour Peano le coté du carré doit être une puissance de 3, pour les autres ce doit être une puissance de 2.
Svastika
Basée sur un principe analogue à celui du Photo Maton mais avec une rotation à 90 degrès de chacune des sous-images. Contrainte : l'image doit être carrée et les cotés doivent être pairs.
Fleur
Basée sur un principe analogue à celui du Photo Maton mais avec un effet miroir pour passer d'une sous-image à une autre dans le sens des aiguilles d'une montre. Contrainte: les cotés doivent être pairs.
Spirale
On décrit une spirale en partant du centre qui recouvre toute l'image. Le pixel en position i passe en position i-1. L'image s'enroule ainsi autour de son centre. Contrainte : aucune.
Colonne
On traite l'image en colonnes en interclassant les colonnes de la 2è moitié de l'image entre les colonnes de la première moitié. Contrainte : aucune
Crèpe
On traite l'image ligne par ligne par paquet de 4 consécutives. La première est mise dans le paquet du haut, la dernière dans le paquet du bas et les deux du mileu restent dans le paquet du milieu. Les images obtenues sont donc aplaties à la manière d'une crèpe. Contrainte : nombre de lignes multiple de 4.
Random 1 Cycle
L'ordre des points est tiré au hasard pour ne constituer qu'un seul cycle. L'avantage c'est que ça brouille immédiatement. L'inconvénient c'est que la clé est constituée du cycle en extension. Ce cycle a été fixé une fois pour toutes, ce qui permet de l'utiliser dans la partie Cryptographie du logiciel.
Random n Cycle
On tire au hasard le nombre de cycles. Tous les points de l'image sont alors distribués dans ces cycles. Comme précédemment le nombre de cycles et les points les constituant ont été fixés une fois pour toutes, ce qui permet de l'utiliser dans la partie Cryptographie du logiciel.

Quelques images ...

* La transformation du boulanger

Quelques applications complètes (600K chacune) à:

* La transformation du Photo-Maton

Quelques applications complètes (300K chacune) à :

* Images approximatives

* Illustration de cycles

* Transformations fractales (Quelques exemples)

* Cryptographie - Stéganographie (Quelques exemples)

* Quatre images en une (Quelques exemples)

* Invariants (Quelques exemples)