TNSI : TD Quart de Tour d'une Image⚓︎
Introduction⚓︎
L'objectif de ce TD est d'implémenter des algorithmes permettant de faire tourner une image d'un quart de tour. Choix Technologiques: Nous utiliserons la bibliothèque PIL de Python.
Introduction à PIL⚓︎
PIL est une librairie Python pour la manipulation d'images qui définit les coordonnées \(x\) et \(y\) des pixels d'une image de la manière suivante:
Rappels de Syntaxe PIL:
from PIL import Image
img = Image.open("nom_du_fichier")
largeur, hauteur = img.size
img.getpixel((x,y)) # getter du tuple-composante (R,G,B) du pixel (x,y)
img.putpixel((x,y),(r,g,b)) # setter du tuple- composante RGB du pixel (x,y)
img.save("nom_du_fichier") # sauvegarde l'image
img.show() # Affiche l'image
Une nouvelle image de taille (largeur,hauteur), noire par défaut, et modifiable par la suite, peut être générée grâce à:
imgNew = Image.new("RGB",(largeur, hauteur))
Algorithme Naïf de rotation d'un quart de tour Droite⚓︎
Dans cette partie, nous souhaitons réaliser une rotation d'un quart de Tour vers la Droite de l'image, i.e. dans le sens des aiguilles d'une montre, encore appelé le sens horaire.
Choisir une image de taille carrée \(512\times512\)⚓︎
Algorithme Naïf de rotation d'un quart de Tour Droite⚓︎
Notons img une image carrée initiale de taille \(n\times n\), et img_rot l'image, encore carrée, obtenue par rotation d'un quart de tour dans le sens des aiguilles d'une montre (sens horaire).
1°) On considére un pixel \((x,y)\) de l'image initiale img. Après rotation d'un quart de tour dans le sens horaire, ce pixel se retrouve à la nouvelle position \((a,b)\) dans l'image retournée img_rot.
Nous noterons cette transformation : \((x,y)_{img}\mapsto (a,b)_{img\_rot}\).
Autrement dit, ici, on connaît le point de départ \((x,y)_{img}\) AVANT ROTATION, et on souhaite connaître quel est le point d'arrivée \((a,b)_{img\_rot}\) (de l'image APRÈS ROTATION) ?
Exprimer \(a\) et \(b\) en fonction de \(x\), de \(y\) et de la taille \(n\) de l'image initiale.
2°) Réciproquement, un pixel \((x,y)\) dans l'image retournée img_rot, vient d'un pixel \((a,b)\) de l'image initiale img avant rotation.
Transformation : \((a,b)_{img}\mapsto (x,y)_{img\_rot}\).
Autrement dit, ici, on connaît le point d'arrivée \((x,y)_{img\_rot}\) APRÈS ROTATION, et on souhaite connaître quel est le point de départ \((a,b)_{img}\) (de l'image APRÈS ROTATION) ?
Exprimer \(a\) et \(b\) en fonction de \(x\), de \(y\) et de la taille \(n\) de l'image initiale.
3°) Commencer par créer une nouvelle image carrée img_rot, de taille \(512\times512\), destinée à stocker la future image obtenue par rotation
4°) Écrire un algorithme python qui stocke dans la nouvelle image celle obtenue par rotation de l'image initiale, et qui affiche la nouvelle image.
5°) Étudier la complexité temporelle de cet algorithme
6°) Étudier la complexité spatiale de cet algorithme
Algorithme de rotation d'un quart de tour Droite, avec Espace mémoire constant⚓︎
La suite de ce problème a pour but de réaliser un algorithme permettant d'effectuer la rotation d'un quart de tour Droite d'une image sans utiliser d'Espace mémoire supplémentaire. Cet algorithme, assez lent, n'est pas utilisé en pratique.
1°) Écrire une procédure qui echangePixels(image,x0,y0,x1,y1) qui échange les pixels de coordonnées (x0,y0) et (x1,y1) de l'image passée en argument
2°) Écrire une procédure echangeQuadrant(image,x0,y0,x1,y1,n) qui prend en argument l' image considérée, et échange deux quadrants carrés de taille \(n\) dont le premier a pour coordonnées de départ \((x0,y0)\) et le deuxième a pour coordonnées de départ \((x1,y1)\).
3°) Écrire une procédure récursive tourneQuadrants(image,x0,y0,n) qui prend en argument l'image considérée, une coordonnée de départ \((x0,y0)\), et une taille \(n\), et :
- qui applique récursivement des rotations à chacun des 4 sous-cadrans du cadran initial passé en argument (défini par \((x0,y0)\) et la taille \(n\), puis
- qui applique les permutations circulaires échangeant les quatre quadrants pour finaliser la rotation.
4°) Écrire une procédure tourneImage(image) effectuant la rotation du quart de tour de l'image. Enregistrer l'image et l'afficher.
5°) Étudier la complexité temporelle de cet algorithme
6°) Étudier la complexité spatiale de cet algorithme