Difficulté : * *

Dans cette activité nous allons voir comment créer une image fractale.

Vous aurez besoin d'importer dans votre notebook les modules utilisés dans les activités précédentes.

import numpy as np
from math import *
import matplotlib.pyplot as plt
import random

La fonction display également :

def display(imglist,size=5, shape=True):
    cols = len(imglist)
    fig = plt.figure(figsize=(size*cols,size*cols))
    for i in range(0,cols):
        a = fig.add_subplot(1, cols, i+1)
        if len(imglist[i].shape) > 2 :
            subfig = plt.imshow(imglist[i])
        else :
            subfig = plt.imshow(imglist[i],cmap="gray")
        subfig.axes.get_xaxis().set_visible(False)
        subfig.axes.get_yaxis().set_visible(False)
        if shape == True:
            a.set_title(str(imglist[i].shape))
    plt.show()

Vous pouvez enfin placer de nouvelles images dans le répertoire images, pour changer un peu de celles qu'on vous propose.

« Une figure fractale est un objet mathématique(...) qui présente une structure similaire à toutes les échelles.» (Wikipedia). Ce sont en quelques sortes des poupées russes graphiques, infinies.

Nous allons construire pas à pas une fractale appelée « dragon de Heighway ».

Pour construire cette figure, il faut se déplacer dans un repère, en partant du centre O = (0;0) et selon les règles suivantes :

Si on note \left(\begin{array}{c}x_n \\ y_n\end{array}\right) les coordonnées de la position courante, la prochaine position est :

\left( \begin{array}{c}x_{n+1} \\ y_{n+1}\end{array} \right) = \left( \begin{array}{cc}1/2 & -1/2 \\ 1/2 & 1/2\end{array}\right) \times \left(\begin{array}{c}x_n \\ y_n\end{array}\right) + \left(\begin{array}{c}0 \\ 0\end{array}\right) \textrm{ avec probabilité }\frac{1}{2}

\left( \begin{array}{c}x_{n+1} \\ y_{n+1}\end{array} \right) = \left( \begin{array}{cc}-1/2 & -1/2 \\ 1/2 & -1/2\end{array}\right) \times \left(\begin{array}{c}x_n \\ y_n\end{array}\right) + \left(\begin{array}{c}1 \\ 0\end{array}\right) \textrm{ avec probabilité }\frac{1}{2}

La première étape consiste à écrire une fonction qui génère un parcours en suivant la démarche précédente.

Si on appelle path_heighway(steps) cette fonction (où steps représente le nombre de positions à générer), voici un exemple de retour possible :

path_heighway(5)

[[0, 0], [1.0, 0.0], [0.5, 0.5], [0.5, 0.0], [0.25, 0.25]]

Le parcours est ici représenté par une liste de coordonnées du plan.

On peut représenter graphiquement ce parcours avec matplotlib :

path = path_heighway(100000)
x = [p[0] for p in path]
y = [p[1] for p in path]
plt.plot(x,y,'.',ms=0.2)
plt.show()

Il faut ensuite créer une image à partir de ce chemin.

La démarche la plus simple consiste à changer l'échelle des coordonnées obtenues et de les associer aux pixels les plus proches.

Voici une démarche possible pour générer une image de largeur s pixels :

• Trouver i_{\text{min}}, i_{\text{max}}, j_{\text{min}} et j_{\text{max}} respectivement le minimum et le maximum sur la deuxième coordonnée, et le minimum et le maximum sur la première coordonnée. (attention, ici, l'abscisse x est l'indice de colonne dans le tableau de l'image et l'ordonnées y celui de la ligne)
• Pour chaque position :
  • Transformer la première coordonnée x en \left\lfloor (s-1)\times\frac{x - j_{min}}{j_{max}-j_{min}}\right\rfloor
  • Transformer la deuxième coordonnée y en \left\lfloor (s-1)\times\frac{y - i_{min}}{j_{max}-j_{min}}\right\rfloor
• Créer une images avec les coordonnées de pixels obtenues

Attention : l'image obtenue par ce procédé sera visuellement la symétrie verticale de celle obtenue avant ; en effet, l'image est construite de haut en bas, alors que dans le repère, les ordonnées sont croissantes, du bas vers le haut de la représentation ; aussi, pour obtenir la même image, il sera nécessaire de prendre le complémentaire à (h-1) pour la transformation de y (ou h représente la hauteur de l'image en pixels)

Si on appelle path2img(p_list,s) la fonction qui convertit une liste de points du plan en une image carrée de s pixels de côté, on devrait obtenir par exemple :

display([path2img(path_heighway(300000), 256)])

lego = plt.imread("images/solo-256px.png")

side = 256
masque = np.zeros((side,side,3))
dragon = path2img(path_heighway(300000), side)
height_dragon = len(dragon)
width_dragon = len(dragon[0])

for i in range(height_dragon):
    for j in range(width_dragon):
        masque[i+floor((side-height_dragon)/2),j] = np.copy(dragon[i,j])
display([lego, masque])

res = np.zeros((256,256,3))

for i in range(len(res)):
    for j in range(len(res[0])):
        if np.all(masque[i,j]==0):
            res[i,j] = [1 + 0 * sum(lego[i,j])/3] * 3
        else:
            res[i,j] = np.copy(lego[i,j])
display([lego,masque,res])

Pour construire la célèbre fougère de Barnsley, on procède selon le même principe : à chaque itération, on applique au point courant une transformation choisie aléatoirement (pas forcément uniformément) parmi plusieurs possibles.

Cette fois, il y a quatre transformations possibles.

Si on note \left(\begin{array}{c}x_n \\ y_n\end{array}\right) les coordonnées de la position courante, la prochaine position est :

\left( \begin{array}{c}x_{n+1} \\ y_{n+1}\end{array} \right) = \left( \begin{array}{cc}0.0 & 0.00 \\ 0.0 & 0.16\end{array}\right) \times \left(\begin{array}{c}x_n \\ y_n\end{array}\right) + \left(\begin{array}{c}0.0 \\ 0.0\end{array}\right) \textrm{ avec probabilité }0.01

\left( \begin{array}{c}x_{n+1} \\ y_{n+1}\end{array} \right) = \left( \begin{array}{cc}0.85 & 0.04 \\ -0.04 & 0.85\end{array}\right) \times \left(\begin{array}{c}x_n \\ y_n\end{array}\right) + \left(\begin{array}{c}0.0 \\ 1.60\end{array}\right) \textrm{ avec probabilité }0.85

\left( \begin{array}{c}x_{n+1} \\ y_{n+1}\end{array} \right) = \left( \begin{array}{cc}0.20 & -0.26 \\ 0.23 & 0.22\end{array}\right) \times \left(\begin{array}{c}x_n \\ y_n\end{array}\right) + \left(\begin{array}{c}0.0 \\ 1.60\end{array}\right) \textrm{ avec probabilité }0.07

\left( \begin{array}{c}x_{n+1} \\ y_{n+1}\end{array} \right) = \left( \begin{array}{cc}-0.15 & 0.28 \\ 0.26 & 0.24\end{array}\right) \times \left(\begin{array}{c}x_n \\ y_n\end{array}\right) + \left(\begin{array}{c}0.0 \\ 0.44\end{array}\right) \textrm{ avec probabilité }0.07

Exercice

Écrire un fonction path_barnsley(steps) qui retourne les coordonnées d'une réalisation de ce parcours aléatoire.

Exemple

path = path_barnsley(1000000)

plt.figure(figsize=(20,20))
ax = plt.gca()
ax.set_aspect(1.0) 
x = [p[0] for p in path]
y = [p[1] for p in path]
plt.plot(x,y,'.',ms=0.2)
plt.show()