TP diviser pour mieux régner : rotation d'image

La bibliothèque Pillow

from PIL import Image

Si le module PIL n'est pas trouvé, ouvrez un terminal linux et exécutez : pip3 install Pillow

img = Image.new("RGB", (largeur, hauteur))
img_2 = Image.open("NOM_DU_FICHIER")

new permet de créer une image vide et open d'en ouvrir une (si le fichier est au bon endroit).

Dans les deux cas la valeur de retour est un objet d'une classe spécifique à PIL qui contient et permet de manipuler l'image. Voici ce dont on va se servir :

largeur, hauteur = img.size

img.size est un attribut qui contient le tuple (hauteur, largeur) de l'image.

couleur = img.getpixel((x,y))

Attention, getpixel prend en paramètre les coordonnées du pixel voulu sous forme d'un tuple. Le pixel en haut à gauche de l'image a les coordonnées (0,0).

Si l'image est en RGB, cette fonction renvoie également un tuple : les valeurs du rouge, vert et bleu pour ce pixel (si elle est en RGBA, il y a une quatrième valeur pour la transparence).

img.putpixel((x,y), (r,g,b))

Change la couleur du pixel.

img.save("NOM_DU_FICHIER")

Vous avez deviné.

img.show()

Ouvre directement l'image dans un logiciel de visualisation.

Démarrage

On va travailler sur cette image:

dragon

Question

Quelle est la couleur du pixel de coordonnées (230,300) ?

spoiler

(233,58,55) soit 233 de rouge, 58 de vert et 55 de bleu

En hexadécimal c'est le code couleur #E93A37 car 233=E9, 58=3A, 55=37

Question

Combien y a-t-il de pixels complètement noirs sur l'image ? De pixels complètement blancs ?

spoiler

292 pixels noirs, 18 pixels blancs

Algorithme de rotation récursif "diviser pour régner"

On veut tourner l'image d'un quart de tour vers la droite.

L'idée de l'algorithme est la suivante :

Cas de base : S'il y a un seul pixel dans l'image, il n'y a rien à faire pour la rotation.
Sinon, on va la couper en 4 sous-images de même taille comme ceci:
```
A | B
-----
C | D
```
On va récursivement faire la rotation des sous-images A,B,C et D.
Enfin on va faire changer de place les sous-images (mais sans avoir besoin de les faire tourner). A passe à la place de B, qui passe à la place de D, qui passe à la place de C, qui passe à la place de A.

Question

Si on sait seulement échanger deux sous-images entre elles, comment peut-on faire la dernière étape ?

Dessiner sur un brouillon la position des images après chaque étape.

Question

Quelle doit être la condition sur l'entier n pour que l'algorithme fonctionne ?

Échange de sous-images

Programmez d'abord une fonction echange_pixel qui prend 5 paramètres:

image une image sous forme d'un objet de Pillow
x0 la colonne du premier pixel
y0 la ligne du premier pixel
x1 la colonne du deuxième pixel
y1 la colonne du deuxième pixel

et qui échange les couleurs des pixels (x0,y0) et (x1,y1).

Aide si vous n'y arrivez pas

def echange_pixel(image,x0,y0,x1,y1):
	#votre code ici

Il va falloir utiliser deux fois la méthode getpixel, puis deux fois la méthode putpixel.

Puis programmez une fonction echange_images qui prend 6 paramètres:

image
x0 et y0 les coordonnées du coin en haut à gauche de la première sous-image
x1 et y1 idem pour la deuxième sous-image
n la taille des sous-images carrées à échanger.

qui échange deux sous-images d'une image. Utilisez la fonction echange_pixel que vous venez de créer.

Aide si vous n'y arrivez pas

def echange_images(image,x0,y0,x1,y1,n):
	#votre code ici

Il faut parcourir tous les coordonnées de pixels d'une sous-image avec deux boucles for imbriquées, et utiliser la fonction echange_pixel à chaque fois.

Faites un petit dessin au brouillon, avec les deux sous-images, les coordonnées de leurs coins en haut à gauche, et les valeurs des indices de ligne et de colonne de vos boucles pour trouver les coordonnées à échanger dans image.

Testez votre fonction sur l'image de dragon (avec les morceaux à échanger que vous voulez).

Rotation

Programmez maintenant la fonction récursive rotation qui prend 4 paramètres:

image
x0 et y0 les coordonnées du coin en haut à gauche de la partie à tourner
n la taille de l'image nxn à tourner

Testez bien sûr le résultat sur l'image de dragon.

Visualisation de l'algorithme

Cet algorithme n'est pas très efficace par rapport à l'algorithme plus simple qui consiste à créer une nouvelle image de la bonne taille, et à copier chaque pixel au bon endroit dans la nouvelle image.

Il a l'intérêt d'être un algorithme en-place, c'est à dire qu'on n'a pas besoin de créer une nouvelle image et qu'on n'utilise donc presque pas de mémoire en plus de celle pour stocker l'image initiale. Mais cet intérêt est limité, en pratique on ne fera sans doute jamais ça.

Par contre il est joli à visualiser 🤩

Initialisez une liste vide au début du programme (dans une variable frames)
À chaque appel de la fonction rotation si n est supérieur ou égal à 32, ajoutez à la fin de la liste frames une copie de l'image actuelle (avec image.copy())

Après avoir fait la rotation, sauvegardez le résultat au format GIF comme ceci :

image.save("animation.gif", format="GIF", append_images=frames,
        save_all=True, duration=200, loop=0)

Allez voir le résultat !

Extension 1

Si on veut visualiser les étapes plus profondes de la récursion, on a un problème de taille d'image car il y a beaucoup d'étapes à stocker. Écrivez une fonction qui divise la taille d'une image par deux en faisant la moyenne des quatre pixels voisins pour créer les pixels de l'image réduite. Puis visualisez une étape de plus dans la récursion.

Extension 2

Programmez l'algorithme "normal" de rotation sans récursion

Extension 3

Trouvez une manière de faire l'algorithme "normal" sans récursion et cette fois sans créer une nouvelle image, donc en utilisant une mémoire supplémentaire constante.