Votre boulanger est-il discret? (1/2)

Quelle différence faites-vous entre l’infini et le « très très grand »? Comment vous représentez-vous l’ensemble des nombres rationnels contenus dans l’intervalle [0,1]? Bon, je ne vous sens pas franchement emballés par mes questions métaphysiques, mais ne zappez pas tout de suite! Pour y répondre, je vous propose un phénomène bluffant qui non seulement prend vos intuitions à contre-pied, mais qui illustre également la différence qualitative entre fini et infini, discret et continu. Et si au pire vous n’y comprenez rien, l’effet spectaculaire en vaut la peine, promis!

PART1: quelle différence entre fini et infini?

Pour bien mélanger son pétrin, le boulanger prend un carré de pâte, l’étire dans un sens puis le replie pour retomber sur son carré initial et il recommence: il étire puis replie pendant une bonne demi-heure (ça muscle!):

La transformation du boulanger

Si au lieu de faire ça avec une pâte à pain, on s’amuse à faire la même chose avec une image numérique, l’image se brouille très vite:Assez rapidement l’image se brouille…

Evidemment, comme on ne peut pas étirer chaque pixel on a un tout petit peu triché: pour étirer une ligne, on est obligé d’interpénétrer chaque ligne paire avec la ligne impaire suivante avant de replier le tout.

Les mystères de l’éternel retour

L’avantage sur la pâte à pain, c’est que c’est moins fatigant à faire et surtout ça va beaucoup plus vite. Au lieu de s’arrêter au bout d’une dizaine de mélanges comme ce feignant de boulanger, on peut laisser le logiciel tourner des milliers de fois. C’est le miracle de la technique. Mais le plus miraculeux c’est surtout qu’au bout d’un moment, l’image du départ revient comme par magie!

Magique!

Cette transformation très simple aurait-elle des propriétés spéciales? Même pas: on trouve sur internet plein d’autres transformations très différentes qui bouclent sur elles-mêmes de la même façon. Par exemple celle du photomaton qui « disperse » l’image initiale dans les quatre quarts du carré avant de recommencer:

La transformation du photomaton appliquée à l’image de la Joconde

Je me disais qu’il devait être affreusement compliqué de démontrer que « ça boucle », d’autant que le nombre d’itérations nécessaires pour retomber sur ses pieds est très sensible au nombre de pixels de l’image. La démonstration que propose JP Delahaye [1] est pourtant incroyablement simple.

Numérotons les pixels de l’image de 1 à N en fonction de leur position. La  transformation du boulanger envoie le pixel en position X1 à une position X2 qui lui est exclusivement réservée. La transformation du boulanger est donc une bijection entre les N pixels de l’image.  Appliquons  itérativement  cette transformation bijective à notre pixel situé  initialement en position X1, il devient:
X1->X2->X3->X4->….->XN
Puisque la transformation est bijective et qu’il n’y a que N pixels possibles, un peu de réflexion vous convaincra que notre point reviendra fatalement à sa position d’origine en X1 au bout d’un certain nombre d’itérations. Ansi à chaque pixel de l’image correspond un cycle de longueur inférieure à N, cycle au terme duquel il revient à sa position de départ. Tous les pixels appartenant à un cycle de longueur 10, reviennent à leur position initiale au bout de 10 transformations, 20, 30, 40 etc.
Evidemment deux pixels différents peuvent appartenir à des cycles de  longueurs différentes l1 et l2, mais ils seront tous les deux revenus à leur position initiale au bout de l1*l2 cycles.
On peut en principe connaître la liste de toutes les longueurs de cycles correspondant aux pixels d’une image. Supposons par exemple qu’il n’y ait que trois cycles possibles, de longueur 3, 7 et 10. L’image reviendra identique à elle-même au bout de 3*7*10=210 itérations.
De façon générale, si l’on connaît toutes les longueurs de cycle d’une image, le « temps de retour » de l’image sera égal au plus petit commun multiple de toutes les longueurs de cycles. Dans le pire des cas (si chaque point appartient à un cycle de longueur différente) l’image initiale revient au bout de N! cycles. Ca peut être long, mais ça marche à tous les coups!

Tout s’explique!
Ce raisonnement est valable quelle que soit la nature de la transformation (Boulanger, photomaton ou autre), il suffit juste qu’elle soit bijective. Rigolo non? Au passage, cette démonstration aide à comprendre pourquoi au cours des itérations on voit de temps en temps apparaître  l’image initiale un peu brouillée: c’est le cas chaque fois que le nombre d’itérations est un multiple des longueurs de cycles les plus fréquentes. Les très nombreux pixels correspondant à ces cycles sont alors revenus à leur position initiale – c’est ce qui fait qu’on reconnaît l’image- mais pas les autres -c’est ce qui fait que l’image est floue:

8 comments for “Votre boulanger est-il discret? (1/2)

  1. raph
    05/12/2011 at 09:31

    🙂
    Marrant ça!
    Mais du coup la longueur du cycle de chaque pixel dépend de quels paramètres? position du pixel dans l’image? largeur/hauteur de l’image en pixels? type de transformation?
    Une réponse dans le billet 2 peut-être?

    • 05/12/2011 at 22:54

      @ralph: de tout ça effectivement mais je ne connais pas la formule! Par contre pour la transformation du boulanger en version discrète, c’est beaucoup plus simple, mais on en reparle au prochain billet 😉

  2. fx33
    19/12/2011 at 09:58

    Si je ne m’abuse, ni l’exemple « numérique » du boulanger, ni celui du photomaton ne correspond à une bijection. A partir du moment où il y a étirement (boulanger) ou réduction (photomaton) des pixels, tous les pixels ne devraient pas survivre à la transformation !
    Un détail aussi : le boulanger replie sa pâte, donc il y a toujours une couche intérieure pour se replier sur elle-même, ce qui n’est pas ce qui est représenté sur l’image.

  3. 21/10/2012 at 20:56

    @fx33: on n’étire jamais les pixels, on les déplace selon le schéma indiqué dans le billet: c’est bien une bijection et ça ressemble (un peu) au pétrissage du boulanger. Le repliement correspond au passage de la partie droite sous la partie gauche et il est bien figuré sur l’image.

  4. Trirème
    25/07/2013 at 11:24

    Petit oups orthographique 😉
    Dans le paragraphe « Tout s’explique! » on lit : « Ce raisonnement est valable quelque soit la nature de la transformation ».
    Il vaudrait mieux écrire « … quelle que soit… »

    Au plaisir de vous lire.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *