115 lines
3.6 KiB
Python
115 lines
3.6 KiB
Python
# TP p 128
|
|
|
|
# 1. L'étape (ii) fait des appels récursifs
|
|
|
|
# 2. Pour une image de 2^n x 2^n pixels il y auras une profondeur de récurstion de n et il y auras 4^n appels récursifs
|
|
|
|
# 3. Oui, l'algorithme reste corect si l'on inverse l'ordre des étapes (i) et (ii).
|
|
|
|
# 4. Non, cet algorithme n'est pas facilement adaptable pour fonctionner avec
|
|
# des rectangles car il se base sur le fait de pouvoir diviser en 4 l'image.
|
|
|
|
# 5. L'algorithme peut transformer l'image sur place.
|
|
|
|
def echange_2blocs(m, x1, y1, x2, y2, w):
|
|
"""
|
|
Echange sur place (sans les pivoter) 2 blocs de w x w dans la matrice m,
|
|
le bloc 1 étant compris entre (x1, y1) et (x1 + (w-1), y1 + (w-1)) inclus,
|
|
et le bloc 2 étant de façon similaire entre (x2, y2) et (x2 + (w-1), y2 + (w-1)) inclus
|
|
Chaque pixel dans un bloc est échangé avec le pixel de même coordonnées dans le second bloc.
|
|
-------
|
|
Complexité : quadratique en w.
|
|
"""
|
|
for i in range(w):
|
|
for j in range(w):
|
|
m[x2+i][y2+j], m[x1+i][y1+j] = m[x1+i][y1+j], m[x2+i][y2+j]
|
|
|
|
|
|
def permuter_4blocs(m, x, y, w):
|
|
"""
|
|
Permute sur place (sans les pivoter) les 4 blocs d'un carré dans l'image m,
|
|
le carré de w x w pixels compris entre (x, y) et (x + (w-1), y + (w-1)) inclus.
|
|
-------
|
|
Suppose (entre autres) que w est pair.
|
|
-------
|
|
Complexité : quadratique en w.
|
|
-------
|
|
Attention, on adopte la convention "image" pour les matrices :
|
|
m[i][j] donne la i-ième ligne et j-ième colonne en partant du haut à gauche.
|
|
La permutation se fait en échangeant les quartiers 2 à 2:
|
|
- (imin, jmin) avec (imin, jmax)
|
|
- (imin, jmin) avec (imax, jmin)
|
|
- (imax, jmin) avec (imax, jmax)
|
|
où par exemple (imin, jmin) représente le bloc comportant les plus petites valeurs sur i et j.
|
|
"""
|
|
echange_2blocs(m, x, y, x, y + w // 2, w // 2)
|
|
echange_2blocs(m, x, y, x + w // 2, y, w // 2)
|
|
echange_2blocs(m, x + w // 2, y, x + w // 2, y + w // 2, w // 2)
|
|
|
|
|
|
def pivoter_rec(m, x, y, w):
|
|
"""
|
|
Pivote récursivement d'un quart de tour
|
|
le carré compris entre (x, y) et (x + (w-1), y + (w-1)) inclus
|
|
dans la matrice m.
|
|
-------
|
|
Suppose (entre autres) que w est une puissance de 2.
|
|
-------
|
|
Complexité : quadratique en w.
|
|
"""
|
|
if w > 1:
|
|
new_w = w//2
|
|
pivoter_rec(m, x, y, new_w)
|
|
pivoter_rec(m, x+new_w, y, new_w)
|
|
pivoter_rec(m, x+new_w, y+new_w, new_w)
|
|
pivoter_rec(m, x, y+new_w, new_w)
|
|
permuter_4blocs(m, x, y, w)
|
|
|
|
|
|
def pivoter(m):
|
|
"""
|
|
Pivote une image d'un quart de tour à droite en utilisant l'algorithme récursif
|
|
de type « diviser pour régner » présenté dans le manuel.
|
|
-------
|
|
Entrée:
|
|
- une matrice m, de dimensions 2^k x 2^k.
|
|
- m[0][0] représente le coin en haut à gauche de l'image, m[0][len(m)] le coin en haut à droite.
|
|
Modifie la matrice m sur place.
|
|
-------
|
|
Complexité: k x 2^k x 2^k.
|
|
"""
|
|
w = len(m)
|
|
assert (w & (w - 1) == 0) and w != 0
|
|
assert w == len(m[0])
|
|
pivoter_rec(m, 0, 0, w)
|
|
|
|
|
|
# Test:
|
|
m = [['a','b'],['d','c']]
|
|
pivoter(m)
|
|
print(m==[['d', 'a'], ['c', 'b']])
|
|
|
|
m = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
|
|
pivoter(m)
|
|
print(m==[[13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3], [16, 12, 8, 4]])
|
|
|
|
# Attention de choisir une image carrée (même nombre de pixels sur x et y) dont les dimensions soient une puissance de 2.
|
|
import matplotlib.pyplot as plt
|
|
import matplotlib.image as mpimg
|
|
|
|
|
|
m = [[.4,.1],[.8,.8]]
|
|
plt.imshow(m)
|
|
plt.show()
|
|
pivoter(m)
|
|
plt.imshow(m)
|
|
plt.show()
|
|
|
|
img = mpimg.imread('python256_couleur.png').tolist()
|
|
imgplot = plt.imshow(img)
|
|
plt.show()
|
|
|
|
pivoter(img)
|
|
plt.imshow(img)
|
|
plt.show()
|