Transformation bijective d'image

En informatique et en photographie, on appelle transformation bijective d'image une transformation d'une image finie de $(n\times p)$ pixels sur elle-même : chaque pixel est donc déplacé et aucun pixel n'est perdu, ce qu'on appelle en mathématiques une permutation de l'ensemble des pixels et en langage courant un mélange.

Par exemple, la transformation de l'image $(n\times p)$ qui déplace le pixel $(i,j)\in [|0,n-1|]\times [|0,p-1|]$ en $((i+1)\ {\text{mod }}n,j)$, correspond à un décalage d'un pixel vers la droite de l'image. De manière triviale, $n$ applications de cette transformation redonnent l'image initiale.

Cette propriété est générale : pour toute transformation bijective d'image, il existe un plus petit entier $k$, appelé temps de retour, tel que appliquée $k$ fois, la transformation redonne l'image initiale.

Ce résultat est une conséquence immédiate du fait que l'ensemble des transformations bijectives d'une image $(n\times p)$ est un groupe fini d'ordre $(np)!$.

Les transformations bijectives d'images les plus connues, introduites par JP Delahaye et P Mathieu du LIFL/USTL dans Pour la Science 242, dec. 1997, sont :

• La transformation du boulanger, dans le cas discret .
• La transformation du photomaton.
• La transformation de Hilbert (voir ci-dessous).

Le nombre d'étapes avant de voir réapparaitre l'image est parfois très grand et dépend d'une part de la transformation et d'autre part de la taille de l'image. Par exemple, pour les transformations du boulanger et du photomaton, une image carrée dont le côté est une puissance de 2 reviendra très vite, alors qu'avec deux nombres quelconques, le temps de retour peut-être extrêmement long. Durant ces étapes, on passe parfois par des reconstitutions très proches de l'image initiale.

Cas $n=2$ ; par la transformation de Hilbert, chacun des $2^{4}=16$ est envoyé sur le suivant.

Exemple de la transformation de Hilbert

Cette transformation est définie pour une image ayant $(2^{n}\times 2^{n})$ pixels. On numérote les pixels de cette image de 1 à $2^{2n}$en suivant le parcours de l'étape $n$ de la courbe de Hilbert. la transformation de Hilbert est celle qui envoie chaque pixel sur le pixel suivant, le dernier étant envoyé sur le premier.

Le temps de retour est évidemment égal à $2^{2n}$.

Liens externes

• JP Delahaye et Ph Mathieu, « Les transformations bijectives d'images » (Descriptions de nombreuses transformations dont celle du boulanger et exemples d'images), sur www.cristal.univ-lille.fr