4.2- TP - Réduction d'image

Ce travail a pour objectif la programmation d'algorithmes permettant de réduire une image dans le sens de la largeur.

Vous allez travailler sur des images en niveaux de gris qui seront des listes de listes d'entiers compris entre 0 et 255.

La première cellule de code utilise la bibliothèque PIL pour charger trois images qui vous serviront de tests. Ces images au format PIL sont converties en liste de listes.

Pour afficher ces images vous utiliserez la fonction imshow définie dans cette première cellule.

Vous devrez donc toujours exécuter cette cellule au début de votre travail.

Python

Loading editor...

from PIL import Image
from numpy import array
import matplotlib.pyplot as plt

def imshow(LL):
    """Affiche une image donnée sous forme de liste de listes"""
    plt.figure()
    plt.imshow(array(LL), cmap="gray")
    plt.axis("off")
    plt.show()
    
flamants = [ [int(pixel) for pixel in ligne] for ligne in array(Image.open("flamantsNB.jpg"))]
guepiers = [ [int(pixel) for pixel in ligne]  for ligne in array(Image.open("guepiersNB.jpg"))]
rue = [ [int(pixel) for pixel in ligne]  for ligne in array(Image.open("rueNB.jpg"))]

Python

Loading editor...

imshow(guepiers)

Préliminaires : manipulation d'images

Q1

Compléter la fonction dim, qui prend en argument une image et renvoie le couple d'entiers (h, w), w étant la largeur de l'image, et h sa hauteur (en nombre de pixels). On pourra ainsi dans la suite utiliser (h, w) = dim(img) pour récupérer les dimensions d'une image.

Python

Loading editor...

def dim(image) :
    ...

Q2

Faire afficher les images suivantes obtenues à partir de guepiers

en inversant le contraste ;
en remplaçant la valeur d'un pixel par la moyenne des 9 pixels du carré de taille 3 qui l'entourent. Attention à adapter le traitement pour les pixels du bord.

Python

Loading editor...

#Q2 a)

Python

Loading editor...

#Q2 b)

I. Réduction naïve de moitié

Q3

Écrire une fonction reduction_moitie_ligne, qui prend en argument une liste de longueur paire contenant des entiers , et renvoie la liste de longueur contenant , etc.

Python

Loading editor...

Q4

Écrire une fonction reduction_moitie_image, qui prend en argument une image (ayant une largeur paire) et en construit une nouvelle en appliquant à chaque ligne l'opération décrite dans la question précédente.

Python

Loading editor...

Q5

Quelle est sa complexité en fonction du nombre de lignes et du nombre de colonnes de l'image?
Testez, et constatez la déformation obtenue. (Justifier la complexité)

Python

Loading editor...

# tests

II. Calcul de l'énergie d'un pixel

Si l'on note le niveau de gris du pixel de coordonnées , l'énergie d'un pixel intérieur à l'image est définie comme

Cette quantité est d'autant plus petite que le pixel est dans une zone uniforme de l'image, et d'autant plus grande qu'il est dans une zone de forte variation du niveau de gris (par exemple au niveau d'un contour).

Il s'agit en fait d'une version discrétisée de , qui est une norme du gradient de l'image.

Q6

Complétez la fonction energie, qui prend en argument une image, et renvoie une nouvelle image correspondant à son énergie (les pixels n'auront plus nécessairement une valeur entière).
On réfléchira en particulier à comment adapter la formule ci-dessus à un pixel situé sur un bord de l'image.
Quelle est la complexité de votre fonction?
Testez, et affichez l'image des énergies obtenue.

Python

Loading editor...

def energie(img):
    '''Calcule l'énergie d'une image img.'''
    (h, w) = dim(img)
    
    
    return e

Python

Loading editor...

# tests

III. Deux algorithmes

Nous disposons d'une image et de son énergie.
Nous allons programmer deux algorithmes pour réduire l'image en utilisant l'énergie

Pour réduire la largeur d'une image d'un pixel, nous allons simplement enlever un pixel d'énergie minimale dans chaque ligne.
Pour réduire la largeur d'une image d'un pixel, nous allons supprimer la colonne de moindre énergie

Q7

Écrire une fonction indice_min qui renvoie l'indice de la valeur minimale d'une liste.

Python

Loading editor...

def indice_min(L):
    ...

Python

Loading editor...

Q8

Écrire une fonction enlever, qui prend en argument une liste L et un indice i compris entre 0 et la longueur de L moins 1, et renvoie une nouvelle liste correspondant à L dont l'élément d'indice i a été supprimé. On pourra utiliser des extractions de tranches et concaténations de listes.

Python

Loading editor...

def enlever(L, i):
    ...

Python

Loading editor...

Q9

Écrire le code de la fonction reduction_par_ligne, qui prend en arguments une image img et son énergie, et la modifie en supprimant un pixel d'énergie minimale dans chacune de ses lignes.

Votre fonction devra aussi enlever le pixel correspondant du tableau énergie.

Python

Loading editor...

def reduction_par_ligne(img, e):
    ...

Python

Loading editor...

Q10

Écrire le code de itere_reduction_par_ligne, qui prend en arguments une image img et un entier , applique fois la procédure décrite dans la question précédente à img. On ne veut calculer l'energie qu'une seule fois au total !

Python

Loading editor...

def iterer_reduction_par_ligne(img, n):
    ...

Python

Loading editor...

Q11

Quelle est sa complexité?
La tester. (On pourra par exemple réduire de 100 pixels la largeur de l'image flamants : au-delà, le calcul risque de dépasser la limite de 15 secondes.)
Expliquez les distorsions observées.

Python

Loading editor...

# tests

Question 12 : Programmation de l'algorithme 2

L'énergie d'une colonne est la somme des énergies des pixels de la colonne.

Écrire une fonction meilleure_colonne qui renvoie l'indice de la colonne d'énergie minimale d'une image.
Écrire le code de itere_reduction_colonne, qui prend en arguments une image img et un entier , et supprime n fois la colonne d'energie minimale. Votre fonction devra calculer une seule fois l'energie.
Testez, et expliquez qualitativement pourquoi les résultats obtenus sont «bons» sur les images guepiers et flamants, mais pas sur rue.

Python

Loading editor...

def meilleure_colonne(img, e):
    pass

Python

Loading editor...

Python

Loading editor...

def itere_reduction_colonne(img, n):
    pass

Python

Loading editor...

#tests

Python

Loading editor...

IV. Algorithme de Seam carving

L'idée de l'algorithme de Seam carving, introduit en 2007 par S.Avidan et A.Shamir est d'assouplir un peu la contrainte de réduction colonne par colonne.

On définit un chemin de pixels comme une suite de pixels connectés (verticalement ou en diagonale) dont le premier appartient au bord haut de l'image, le dernier au bord bas, et contenant exactement un pixel par ligne de l'image.

L'énergie d'un chemin est la somme des énergies des pixels le constituant.

Voici par exemple un chemin d'énergie 6 (en gras) dans une image des énergies jouet de pixels.

1	1	0	3
5	1	2	4
2	3	3	3
6	3	4	3

Python

Loading editor...

e = [[1, 1, 0, 3],
     [5, 1, 2, 4],
     [2, 3, 3, 3],
     [6, 3, 4, 3]]

Pour réduire la largeur d'une image d'un pixel, on souhaite trouver puis enlever un chemin d'énergie minimale.

On définit un chemin partiel comme un chemin, sans la contrainte que son dernier pixel atteigne le bord bas de l'image. Afin de calculer un chemin minimal, on va commencer par calculer, pour chaque pixel, l'énergie minimale d'un chemin partiel terminant sur ce pixel.

Par exemple, pour notre image des énergies , on obtient le tableau suivant:

1	1	0	3
6	1	2	4
3	4	4	5
9	6	8	7

Question 13 : programmation dynamique du seam carving

Expliquez comment construire à partir de , en procédant ligne par ligne.
Établir précisément, pour , la relation entre , et avec

La programmation de la recherche d'un chemin d'énergie minimale va se faire par étape. Vous testerez chaque étape avec le tableau jouet donné en exemple.
Écrire une fonction seam_carving qui prend en paramètre un tableau ener contenant les énergies d'une image et qui calcule le tableau E.
Complétez votre fonction pour qu'elle crée et complète un tableau choix de même dimensions que E et tel que pour tout , choix[i][j] contient l'entier tel que E[i][j] = E[i-1][k] + e[i][j]
Complétez votre fonction pour qu'elle renvoie la liste des coordonnées d'un chemin d'énergie minimale
Écrire alors une fonction reduction_seam_carving qui a pour paramètre une image et qui renvoie une nouvelle image obtenue après suppression d'un chemin d'énergie minimale puis une fonction itere_reduction_seam_carving. Donnez sa complexité et testez là !

Python

Loading editor...

def seam_carving1(ener) :    # version initiale , calcul de E
    ...

Python

Loading editor...

# test

Python

Loading editor...

def seam_carving2(ener) :    # version 2 , calcul de E et choix
    ...

Python

Loading editor...

Python

Loading editor...

def seam_carving3(ener) :   # version 2 , calcul de E,choix et chemin
    ...

Python

Loading editor...

Python

Loading editor...

def reduction_seam_carving(img, ener):
    ...

Python

Loading editor...

Python

Loading editor...

def itere_reduction_seam_carving(img, n):
    ...

Python

Loading editor...

Python

Loading editor...

# tests

Entrez le code donné en cours pour accéder à la solution :

Code d'accès