Correction : Rotation d'une image d'1/4 de tour

2. Algorithme "naïf"

from PIL import Image

def rotation(image):
    largeur, hauteur = image.size
    nv_image = Image.new("RGB", (largeur, hauteur))

    for x in range(largeur):
        for y in range(hauteur):
            pixel = image.getpixel((y, largeur - 1 -x)) # attention les coordonnées doivent être sous forme de tuple
            nv_image.putpixel((x,y), pixel) # même remarque !

    return nv_image
    
img = Image.open("joconde.jpg") # ouverture fichier image et récupération du tableau de pixels
nv_image = rotation(img) # appel de la fonction avec l'image d'origine en argument, et récupération de son résultat renvoyé ( la nouvelle image )
nv_image.show() # ou nv_image.save('joconde_tournée.jpg')
    		

Complexité :

• en temps : boucle y en O(n), imbriquée dans une boucle x en O(n) → complexité temporelle en O(n²).
• en espace : si on appelle n le nombre de pixels horizontaux ou verticaux de l'image, alors complexité en espace en O(n²).
  Et comme on crée une deuxième image de même taille que celle d'origine, la complexité globale est en O(2⨯n²) soit O(n²).

Donc si on double la taille de l'image, on quadruple l'occupation mémoire : pas terrible !

3. Algorithme Diviser pour régner

Ppur "repérer" les 4 sous-images dans une image de taille n x n, il est bon de prendre un papier et un crayon :

from PIL import Image

def echange_pixel(image, x0, y0, x1, y1):
    temp = image.getpixel((x0,y0))	# technique similaire à l'échange de deux variables
    image.putpixel((x0,y0), image.getpixel((x1,y1)))
    image.putpixel((x1,y1), temp)
    
def echange_images(image, x0, y0, x1, y1, n): 
    for i in range(n):
        for j in range(n):
            echange_pixel(image, x0 + i, y0 + j, x1 + i, y1 + j)

def rotation2(image, x0, y0, n):
     
    if n >= 2 :
        m = n // 2
        rotation2(image, x0, y0, m)
        rotation2(image, x0, y0 + m, m)
        rotation2(image, x0 + m, y0, m)
        rotation2(image, x0 + m, y0 + m, m)
        
        echange_images(image, x0, y0, x0 + m, y0, m)
        echange_images(image, x0, y0, x0 + m, y0 + m, m)
        echange_images(image, x0, y0, x0, y0 + m, m)

img = Image.open("joconde.jpg") # ouverture fichier image et récupération du tableau de pixels
rotation2(img, 0, 0, img.size[0]) # appel de la fonction avec l'image d'origine en argument; pas de résultat renvoyé, l'image est modifiée "en place"
img.show() # ou img.save('joconde_tournée.jpg')
    		

Complexité :

• en temps : O(n².log n) non démontré.
• en espace : l'image est modifiée "en place", on ne fait qu'échanger ses pixels, donc pas d'utilisation d'espace supplémentaire → complexité en espace constant, soit O(1).