Corrigé du TD Quart de Tour⚓︎
Algorithme Naïf de rotation d'un quart de tour Droite⚓︎
Choisir une image de taille carrée \(512\times512\)⚓︎
Algorithme Naïf de rotation d'un quart de Tour Droite⚓︎
\((a,b)_{\text{img\_rot}}=(x,y)_{\text{img}}\) avec \( \left\{ \begin{array}{ll} a=n-1-y\\ b=x \end{array} \right. \)
Conclusion: \((n-1-y,x)_{\text{img\_rot}}=(x,y)_{\text{img}}\)
D'après la question précédente, \((x,y)_{\text{img\_rot}}=(a,b)_{\text{img}}\) avec \( \left\{ \begin{array}{ll} x=n-1-b\\ y=a \end{array} \right. \Leftrightarrow \left\{ \begin{array}{ll} b=n-1-x\\ a=y \end{array} \right. \Leftrightarrow \left\{ \begin{array}{ll} a=y\\ b=n-1-x \end{array} \right. \)
Conclusion: \((x,y)_{\text{img\_rot}}=(y,n-1-x)_{\text{img}}\) Le pixel \((x,y)\) de l'image rotationnée droite provient du pixel \((y,n-1-x)\) de l'image initiale
OK, c'est fait
from PIL import Image
img = Image.open("img/bateau.jpg")
largeur, hauteur = img.size
n = largeur
img_rot = Image.new("RGB",(largeur,hauteur))
for x in range(n):
for y in range(n):
# 1/4 Tour Droite : Solution 1
# On mémorise le pixel (x,y) de l'image initiale
# On place ce pixel à sa nouvelle position après rotation droite
(r,g,b) = img.getpixel((x,y)) # getter de la composante RGB du pixel (x,y)
img_rot.putpixel((n-1-y,x),(r,g,b)) ## setter de la composatnte RGB du pixel (x,y)
## 1/4 Tour Droite : Solution 2
## le pixel (x,y) de l'image rotationnée droite provient du pixel (y,n-1-x) de l'image initiale
#(r,g,b) = img.getpixel((y,n-1-x)) # getter de la composante RGB du pixel (x,y)
#img_rot.putpixel((x,y),(r,g,b)) ## setter de la composatnte RGB du pixel (x,y)
img_rot.save("img/bateauRot.jpg") # sauvegarde l'image
img_rot.show() # Affiche l'image
La taille des entrées est la largeur \(n\).
Il y a deux boucles Pour imbriquées, chacune de taille \(n\).
Les instructions à l'intérieur des deux boucles sont donc répétées \(n\times n = n^2\) fois. L'instruction img.getpixel() a un coût unitaire, de même que l'instruction img.putpixel(), donc la Complexité Temporelle en \(O(n\times n) = O(n^2)\)
Pour chaque image de taille \(n\), il faut créer une nouvelle image dont la taille vaut \(n\), c'est-à-dire avec \(n^2\) pixels dont chacun a une taille constante (à priori 3 octets pour le code RGB). donc la Complexité Spatiale est aussi en \(O(n^2)\)
Algorithme de rotation d'un quart de tour Droite, avec Espace mémoire constant⚓︎
Il suffit de récupérer les valeur des pixels et de les mettre à leur nouvel emplacement :
def echangePixels(image,x0,y0,x1,y1):
pixel0 = image.getpixel((x0,y0))
pixel1 = image.getpixel((x1,y1))
image.putpixel((x0,y0), pixel1)
image.putpixel((x1,y1), pixel0)
La permutation circulaire est réalisée en enchaînant plusieurs échanges de cadran, dont voici un exemple de stratégie possible:
Il suffit de récupérer les valeurs des pixels et de les mettre à leur nouvel emplacement :
def echangeQuadrants(image,x0,y0,x1,y1,n):
for i in range(n):
for j in range(n):
echangePixels(image,x0+i,y0+j,x1+i,y1+j)
echangePixels(...) # BON APPEL D'UNE PROCÉDURE
# et NON PAS comme une fonction:
img = echange(...) # MAUVAIS APPEL D'UNE PROCÉDURE
On applique la Méthode du ¼ de Tour Droite en Diviser Pour Régner décrite sur la 1ère figure ci-dessus, en faisant attention de ne le faire que si le quadrant est au minimum de taille \(2\times 2\). Dans le cas contraire, le quadrant est composé d'un unique pixel, auquel cas il est inutile de faire quoi que ce soit (c'est-à-dire de retourner un unique pixel). On fait également attention à utiliser une division entière, pour préserver le type des données.
def tourneQuadrants(image,x0,y0,n):
if n>=2 :
m = n // 2
tourneQuadrants(image,x0,y0,m) # Tourne A
tourneQuadrants(image,x0+m,y0,m) # Tourne B
tourneQuadrants(image,x0,y0+m,m) # Tourne C
tourneQuadrants(image,x0+m,y0+m,m) # Tourne D
echangeQuadrants(image,x0,y0,x0+m,y0,m) # Echange A et B --> B passe en (x0,y0), A en (x0+m,y0)
echangeQuadrants(image,x0,y0,x0+m,y0+m,m) # Echange B et D --> D passe en (x0,y0), B en (x0+m,y0+m)
echangeQuadrants(image,x0,y0,x0,y0+m,m) # Echange D et C --> C passe en (x0,y0), D en (x0,y0+m)
Il suffit de lancer la procédure tourneImage(image), et de lancer les instructions finales dans le programme principal:
def tourneImage(image):
n, p = image.size
assert n == p
tourneQuadrants(image,0,0,n)
# Programme Principal
img = Image.open("img/bateau.jpg")
tourneImage(img)
img.show() # Affiche l'image
img.save("img/bateauRotDivPourRegner.jpg")
La taille des entrées, est la largeur (/hauteur) de l'image, que nous noterons \(n\).
Il s'agit d'étudier la complexité temporelle de la procédure tourneQuadrants(image,x0,y0,n)
La relation de Récurrence vérifiée par la Complexité Temporelle est:
\(T(n) = 4T \left( \dfrac n2 \right)+O(n^2)\) avec \(T(1)=0\) car une image de largeur \(1\) ne subit aucun traitement.
En effet, le \(O(n^2)\) provient de la permutation circulaire, nécessaire après le traitement récursif: C'est la Complexité Temporelle de chaque procédure echangeQuadrants(image,x0,y0,x1,y1,n), car deux bloucles Pour imbriquées, chacune de taille \(n\), donc complexité temporelle en \(O(n\times n)=O(n^2)\)
def echangeQuadrants(image,x0,y0,x1,y1,n):
for i in range(n):
for j in range(n):
echangePixels(image,x0+i,y0+j,x1+i,y1+j)
On sait que \(n\) est une puissance de \(2\), Notons \(n=2^p\), donc \(n^2=(2^p)^2=2^{2p}\)
\(T(n) = O(n^2) + 4T \left( \dfrac n2 \right)\) \(T(n) = O(n^2) + 4\times \left[ O\left( \left( \dfrac n2 \right)^2 \right)+ 4\times T\left( \dfrac{n}{2^2} \right) \right]\) \(T(n) = O(n^2) + 4\times O\left( \dfrac {n^2}{2^2} \right)+ 4^2\times T\left( \dfrac{n}{2^2} \right)\) \(T(n) = O(n^2) + O( n^2 )+ 4^2\times \left[ O\left( \left( \dfrac {n}{4} \right)^2 \right)+ 4\times T\left( \dfrac{n}{2^3} \right) \right]\) \(T(n) = O(n^2) + O( n^2 ) + 4^2\times O\left( \dfrac {n^2}{4^2} \right)+ 4^3\times T\left( \dfrac{n}{2^3} \right)= etc...\) \(T(n) = O(n^2) + O( n^2 ) + O( n^2 ) + 4^3\times O\left( \dfrac{n^2}{(2^3)^2} \right) +...+ 4^{p-1}\times T\left( \dfrac{n}{2^{p-1}} \right)\) \(T(n) = O(n^2) + O( n^2 ) + O( n^2 ) + 4^3\times O\left( \dfrac{n^2}{4^3} \right) +...+ 4^{p-1}\times O\left( \dfrac{n^2}{2^{2p-2}} \right) +4^p\times T\left( \dfrac {n}{2^p} \right)\) De plus : \(n=2^p\) donc \(\dfrac {n}{2^p}=1\), donc \(T(n) = O(n^2) + O( n^2 ) + O( n^2 ) + O( n^2 ) +...+ 4^{p-1}\times O\left( \dfrac{n^2}{4^{p-1}} \right) +4^p\times T(1)\) \(T(n) = O(n^2) + O( n^2 ) + O( n^2 ) + O( n^2 ) +...+ O( n^2 ) + 4^p\times 0\) car \(T(1)=0\) \(T(n) = p\times O(n^2)\) \(T(n) = O(p\times n^2)\)
De plus, \(n=2^p \Leftrightarrow p=log_2n\) donc \(T(n) = O(log_2n\times n^2) = O(n^2\times log_2n)\) donc la Complexité Temporelle est en \(O(n^2 log_2 n)\)
Les pixels sont toujours échangés deux à deux, donc cet algorithme est en espace mémoire constant, i.e. en \(O(1)\)