Transformation du Photomaton

1)Principe

Pour une image de largeur 2m et de hauteur 2n,
chaque pixel de l’image est repéré par un couple (i,j) de ses coordonnées où 0≤i≤2m-1 et 0≤j≤2n-1,
Si la coordonnée est de rang pair p alors on la déplace au rang p//2 (division entière)
Si la coordonnée est de rang pair p alors on la déplace au rang m+p//2
2)Relation de récurrence

On note :
x₀ le numéro de colonne d’un pixel de l’image de départ
x_k le numéro de la colonne dans laquelle il se trouve après k itérations.

Les numéros de lignes sont notés de même y₀ et y_0k.

Si x_k=2i-1, alors x_k+1=m+i Si x_k=2i alors x_k+1=i.

On en déduit que, pour tout entier k : 2x_k+1≡x_k (2m-1) donc que pour tout entier k : , 2^k+1x_k+1≡ x₀ (2m-1).
Le déplacement des lignes suit évidemment les mêmes règles, on retrouve donc des propriétés analogues pour les y_k.

3) Image à l’étape k soit identique à l’image initiale

Il est nécessaire et suffisant que toutes les colonnes et les lignes retrouvent leurs places initiales,
c’est-à-dire que, pour les colonnes, pour tout x₀ de {0, …, 2m-1},
2^kx₀-x₀ soit divisible par 2m-1 soit 2^k-1 soit divisible par 2m-1 (car la propriété doit être vraie pour toutes les valeurs de x.

De même, il suffit que 2^k-1 soit divisible par 2n-1 en réfléchissant sur les lignes.
La condition nécessaire et suffisante pour que l’image à l’étape k soit identique à l’image initiale est donc :
2n-1 et 2m-1 sont des diviseurs de 2^k-1 ».

Si l’image contient 2^a lignes et 2^a colonnes.
La condition s’écrit : 2^a+1-1 est un diviseur de 2^k-1.
La condition est vérifiée si 2^a+1=2^k c’est-à-dire k=a+1 (plus petite valeur de k qui convient)

Dans le cas d’une image 256 × 256, a=b=8 (2⁸ =256)
on retrouve donc pour la première fois l’image initiale après 9 itérations.