Transformation du cliché Photomaton

En informatique et en photographie, la transformation du cliché Photomaton est une description d'un type de mélange analogue à un cliché Photomaton qui à partir d'une image d'ordinateur en fabrique quatre de plus petites dimensions, et ainsi de suite par itération. Cette transformation est un cas particulier de transformation bijective d'image.

Histoire

Cette transformation a été introduite en 1997 par Jean-Paul Delahaye et Philippe Mathieu dans la revue Pour la Science^,^,^,.

Présentation

Le principe de cette transformation est le suivant : pour obtenir une nouvelle image, l'image originale est décomposée en 4 images rétrécies récursivement. L'image est tout d'abord découpée en carrés de 4 pixels (2 × 2) puis le pixel en haut à droite de chaque 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. Cette transformation ne fonctionne qu'avec des images dont la hauteur et la largeur sont paires.

Si on répète un certain nombre de fois cette transformation, on retrouve l'image de départ. Le nombre d'itérations s'appelle période de retour. Il se calcule comme suit pour une image de dimension $2n\times 2m$ pixels :

On détermine le plus petit entier $p$ tel que $2n-1$ divise $2^{p}-1$  ; $p$ est l'ordre de 2 dans le groupe multiplicatif $(\mathbb {Z} /(2n-1)\mathbb {Z} )^{*}$ ;
On détermine le plus petit entier $k$ tel que $2m-1$ divise $2^{k}-1$  ;
On calcule le ppcm de $p$ et $k$ . Le résultat obtenu est la période cherchée.

Démonstration

Soit 2m le nombre de colonnes de pixels constituant l'image. Numérotons ces colonnes de 0 à 2m-1. Soit j un indice de colonne. Cherchons d'où provient un pixel occupant la colonne j après une transformation du cliché Photomaton.

Si j<m, alors le pixel occupait la colonne 2j (un pixel sur deux se retrouve dans la partie gauche de l'image. Il s'agit des pixels occupant initialement une colonne de rang pair).
Sinon, le pixel occupait la colonne 2j-2m+1 (un pixel sur deux se retrouve dans la partie droite de l'image. Il s'agit des pixels occupant initialement une colonne de rang impair).

On remarque que les pixels occupant les colonnes 0 ou 2m-1 ne changent pas de colonnes. Quant aux autres, l'application $j\mapsto 2j\;{\rm {mod}}\;2m-1$ fait le lien entre les rangs des colonnes occupées après et avant la transformation. Il s'agit simplement d'une multiplication du rang par 2, modulo 2m-1.

L'itération de k transformations se traduira par la composée de k telles applications, à savoir $j\mapsto 2^{k}j\;{\rm {mod}}\;2m-1$ . Les colonnes seront donc identiques après une itération de k transformations pour les k tels que $2^{k}=1\;{\rm {mod}}\;2m-1$ , ce qui signifie que 2m-1 divise $2^{k}-1$ . Ces k sont les multiples du plus petit d'entre eux.

On opère de même pour les lignes. Le nombre d'itérations laissant invariant les lignes est multiple du plus petit p tel que 2n-1 divise $2^{p}-1$ .

Le nombre d'itérations laissant invariant à la fois les lignes et les colonnes est un multiple commun des nombres k et p précédents. C'est un multiple de leur ppcm.

Dans le cas où la taille de l'image est $2^{p}\times 2^{k}$ , la période est $\mathrm {ppcm} (p,k)$ .

La suite des temps de retour pour une image carrée de $2n\times 2n$ pixels est, en débutant à $n=1$ : 1, 2, 4, 3, 6, 10, 12, 4, 8, 18,... (suite A002326 de l'OEIS).

Il est important de bien noter que les 4 images qui apparaissent après une étape de transformation ne sont pas identiques comme elles le seraient avec l'appareil photographique de la société Photomaton. Les quatre images sont bien différentes au sens des pixels qu'elles contiennent. Elles proviennent d'une redistribution des pixels de l'image initiale sans aucune duplication ni perte.

Applications

Il s'agit principalement d'une technique de transformation d'images utilisée en informatique. On la compare à la transformation du boulanger comme illustration de la théorie du chaos. En effet, une faible différence au départ (par exemple 2 pixels voisins) conduit à une grande différence au bout de quelques itérations. Cependant à l'inverse de la transformation du boulanger, la différence cesse de croître et les pixels reprennent par la suite une position voisine.

Références

↑ Chercheurs au Laboratoire d'Informatique Fondamentale de Lille (LIFL) de l'université des Sciences et Technologies de Lille
↑ Jean-paul Delahaye, Philippe Mathieu, « Images brouillées, Images retrouvées », Pour la Science, n^o 242,‎ décembre 1997, p. 102-106 (lire en ligne)
↑ Jean-Paul Delahaye et Philippe Mathieu, Jeux mathématiques et mathématiques des jeux, chapitre 15 : images brouillées, images retrouvées, Bibliothèque pour la Science, 1998, p. 98-104
↑ Jean-Paul Delahaye et Philippe Mathieu, « Une Scytale Informatique », Pour la Science, n^o 359,‎ septembre 2007, p. 90-95 (lire en ligne)
↑ Jean-Paul Delahaye, Jeux finis et infinis, Seuil, coll. « Science ouverte », chap. 5 (« Le retour surprise d'une image »), p. 129-160

Voir aussi

Articles connexes

Liens externes

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

Portail de l’imagerie numérique

[1] Chercheurs au Laboratoire d'Informatique Fondamentale de Lille (LIFL) de l'université des Sciences et Technologies de Lille

[:0-2] Jean-paul Delahaye, Philippe Mathieu, « Images brouillées, Images retrouvées », Pour la Science, n^o 242,‎ décembre 1997, p. 102-106 (lire en ligne)

[:1-3] Jean-Paul Delahaye et Philippe Mathieu, Jeux mathématiques et mathématiques des jeux, chapitre 15 : images brouillées, images retrouvées, Bibliothèque pour la Science, 1998, p. 98-104

[4] Jean-Paul Delahaye et Philippe Mathieu, « Une Scytale Informatique », Pour la Science, n^o 359,‎ septembre 2007, p. 90-95 (lire en ligne)

[:2-5] Jean-Paul Delahaye, Jeux finis et infinis, Seuil, coll. « Science ouverte », chap. 5 (« Le retour surprise d'une image »), p. 129-160