Les transformations bijectives d'images
JP
Delahaye et Ph Mathieu
Vous êtes le 
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).
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
- 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.
- 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
- 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.
- 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
- 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