Transformation du boulanger

En théorie des systèmes dynamiques, et en informatique, la transformation du boulanger est une transformation fondée sur l'idée d'un mélange analogue au pétrissage par un boulanger qui étire une pâte jusqu'à ce qu'elle soit d'épaisseur moitié, puis, soit la coupe en deux et superpose les deux moitiés pour lui redonner sa dimension initiale, soit la replie sur elle-même en la faisant pivoter, et réitère le procédé.

La transformation continue du boulanger, avec étirement puis coupure de la "pâte" et superposition, est l’application de ${\displaystyle [0,1]^{2}}$ dans lui-même définie par :

${\displaystyle S(x,y)={\begin{cases}(2x,{\frac {y}{2}})&{\text{si }}0\leqslant x\leqslant {\frac {1}{2}}\\(2x-1,{\frac {y+1}{2}}),&{\text{si }}x>{\frac {1}{2}}\end{cases}}}$^[1].

Concrètement, le carré, étiré horizontalement dans le rapport 2 et contracté verticalement dans le rapport 1/2, est coupé en deux dans le sens de la hauteur, et les deux morceaux sont superposés.

• 
  Carré de départ
• 
  Carré transformé
• 
  Illustration de l'itération de la transformation continue sur une image formée de points rouge et bleus initialement séparés.
• 
  Exemple d'image invariante sous l'action de la transformation du boulanger (sans rotation).

Cette version est souvent évoqué en théorie du chaos, à cause de la sensibilité aux conditions initiales lorsqu'on répète indéfiniment la transformation.

La version continue où le deuxième demi-pâton subit une rotation de 180° avant d'être placé sur le premier demi-pâton est définie par :

${\displaystyle T(x,y)={\begin{cases}(2x,{\frac {y}{2}})&{\text{si }}0\leqslant x\leqslant {\frac {1}{2}}\\(2-2x,1-{\frac {y}{2}}),&{\text{si }}x>{\frac {1}{2}}\end{cases}}}$

La transformation du fer à cheval de Smale est une autre version où l'on tient compte du coude opéré par le repliement de la pâte.

Il existe des versions unidimensionnelles de ces deux transformations^[2], définies sur ${\displaystyle [0,1]}$ par ${\displaystyle t(x)={\begin{cases}2x&{\text{si }}0\leqslant x\leqslant {\frac {1}{2}}\\2-2x,&{\text{si }}x>{\frac {1}{2}}\end{cases}}}$, appelée aussi fonction tente, et ${\displaystyle s(x)={\begin{cases}2x&{\text{si }}0\leqslant x\leqslant {\frac {1}{2}}\\2x-1,&{\text{si }}x>{\frac {1}{2}}\end{cases}}}$.

Il semblerait que c'est sous la forme unidimensionnelle que la transformation du boulanger ("baker's map") a été définie en 1937 par Eberhard Hopf^[3],[4].

Cette version a été introduite en 1997 par Jean-Paul Delahaye et Philippe Mathieu^{[5],[6],[7],[8]}.

On considère une image informatique formée de ${\displaystyle (n\times p)}$ pixels placés en ${\displaystyle (i,j)\in [|0,n-1|]\times [|0,p-1|]}$ ^[9],[10].

Dans la première étape (étirement), le pixel placé en ${\displaystyle (i,j)}$ est envoyé à la place${\displaystyle (i_{1},j_{1})=(\mathrm {quotient} (i,2),2j+\mathrm {reste} (i,2))}$ soit ${\displaystyle {\begin{cases}(i/2,2j)&{\text{si }}i{\text{ est pair}}\\(\lfloor i/2\rfloor ,2j+1)&{\text{si }}i{\text{ est impair}}\end{cases}}}$, ce qui donne une image de dimensions ${\displaystyle (n/2\times 2p)}$.

Dans la deuxième étape (repliement avec rotation), le pixel placé en ${\displaystyle (i_{1},j_{1})}$ est envoyé en ${\displaystyle (i',j')={\begin{cases}(i_{1},j_{1})&{\text{si }}j_{1}<p\\(n-1-i_{1},2p-1-j_{1})&{\text{si }}j_{1}\geqslant p\end{cases}}}$, ce qui redonne une image ${\displaystyle (n\times p)}$.

Par exemple, pour ${\displaystyle n=p=2}$, le tableau ${\displaystyle {\begin{array}{|c|c|c|}\hline (i,j)&j=0&j=1\\\hline i=0&a&b\\\hline i=1&c&d\\\hline \end{array}}}$ est transformé en ${\displaystyle {\begin{array}{|c|c|c|c|c|c|}\hline (i_{1},j_{1})&0&1&2&3\\\hline 0&a&c&b&d\\\hline \end{array}}}$ puis en ${\displaystyle {\begin{array}{|c|c|c|}\hline (i',j')&0&1\\\hline 0&a&c\\\hline 1&d&b\\\hline \end{array}}}$.

Pour ${\displaystyle n=p=3}$, ${\displaystyle {\begin{array}{|c|c|c|}\hline a&b&c\\\hline d&e&f\\\hline g&h&i\\\hline \end{array}}}$ est transformé en ${\displaystyle {\begin{array}{|c|c|c|c|c|c|c|}\hline a&d&b&e&c&f\\\hline g&&h&&i\\\hline \end{array}}}$, puis en ${\displaystyle {\begin{array}{|c|c|c|}\hline a&d&b\\\hline g&i&h\\\hline f&c&e\\\hline \end{array}}}$.

L'application de l'ensemble fini ${\displaystyle [|0,n-1|]\times [|0,p-1|]}$ dans lui-même est une permutation donc est d'ordre fini. Le temps de retour est le nombre d'étapes pour que tous les pixels reviennent à leur place originelle lorsqu'on effectue une succession de transformations du boulanger ; c'est le PPCM des temps de retour de chaque pixel^[7].

Pour ${\displaystyle (n,p)=(2^{k},2^{l})}$, le temps de retour est égal à ${\displaystyle k+l+1}$, mais on ne connait pas de loi générale donnant ce temps d'attente^[7].

Voici quelques valeurs des temps de retour pour une image carrée de ${\displaystyle (n\times n)}$ pixels^[7] ( A393817):

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
	1	3	6	5	72	60	18	7	660	556 920	770	1 008	985 320	339 660	34 320	9

• Transformation bijective d'image
• Transformation du photomaton
• Sensibilité aux conditions initiales
• Chat d'Arnold

• 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

• Portail de l'analyse
• Portail de la physique
• Portail de l’imagerie numérique