Redimensionner une image : le seam carving

Cours · algorithmique (école d'ingénieur), chapitre 6 · école d'ingénieur, informatique · le début du chapitre, la suite sur Adloun

Objectifs du chapitre

Découvrir une application spectaculaire et récente de la programmation dynamique au traitement d'images.
Enchaîner plusieurs traitements sur des tableaux à deux dimensions : image $\to$ énergies $\to$ coûts minimum $\to$ chemin $\to$ image réduite.
Écrire une récurrence de chemin de coût minimum dont le départ et l'arrivée sont libres.

6.1 Le problème

Une photographie de $1920 \times 1080$ pixels doit être affichée sur un écran de téléphone, en mode portrait. Comment réduire sa largeur ?

Mise à l'échelle : on réduit toute l'image. Les personnages et les objets sont écrasés, déformés.
Recadrage : on coupe les bords. On perd ce qui s'y trouvait, peut-être l'essentiel.

En 2007, Shai Avidan et Ariel Shamir ont proposé une troisième voie, le seam carving (« découpe de coutures » ; S. Avidan, A. Shamir, Seam carving for content-aware image resizing, ACM Transactions on Graphics (SIGGRAPH), 26(3), 2007). L'idée : retirer de l'image, un par un, des chemins de pixels qui traversent l'image de bas en haut en passant par les zones les moins intéressantes (un ciel uniforme, une étendue de sable, un mur). Chaque chemin retiré diminue la largeur d'un pixel, et le contenu important est préservé. L'algorithme est aujourd'hui présent dans les logiciels de retouche (sous le nom de mise à l'échelle en fonction du contenu) ; on peut l'essayer dans de nombreux démonstrateurs en ligne.

Définition 6.1Couture

Soit une image de $L$ lignes et $C$ colonnes (la ligne $0$ est en bas). Une couture verticale est une suite de $L$ pixels $(0, c_{0}), (1, c_{1}), \dots, (L - 1, c_{L - 1})$ , un par ligne, telle que deux pixels consécutifs sont voisins : $\forall l, 1 \leq l < L : ∣ c_{l} - c_{l - 1} ∣ \leq 1$ .

Autrement dit, on part d'un pixel quelconque de la ligne $0$ , et l'on monte d'une ligne à chaque pas, vers le Nord-Ouest, le Nord ou le Nord-Est. Retirer une couture, c'est retirer exactement un pixel par ligne : l'image reste rectangulaire, avec $C - 1$ colonnes.

6.2 L'énergie d'un pixel

Qu'est-ce qu'une « zone peu intéressante » ? Une zone où les pixels ressemblent à leurs voisins. On mesure cela par l'énergie d'un pixel. Nous travaillons avec des images en niveaux de gris : chaque pixel $p$ a un niveau de gris $g (p) \in [0 : 256]$ .

Définition 6.2Énergie d'un pixel

Soit $V (p)$ l'ensemble des voisins du pixel $p$ (les pixels qui le touchent, y compris en diagonale). L'énergie de $p$ est l'écart moyen entre son niveau de gris et celui de ses voisins :

$e (p) = \frac{1}{∣ V ( p ) ∣} p^{'} \in V (p) \sum g (p) - g (p^{'}) .$

Un pixel intérieur a $8$ voisins, un pixel du bord (hors coins) en a $5$ , un pixel de coin en a $3$ .

Exemple 6.3un pixel intérieur

Un pixel a le niveau de gris $20$ ; quatre de ses voisins valent $0$ et les quatre autres $60$ . Son énergie est $(4 \times ∣20 - 0∣ + 4 \times ∣20 - 60∣) /8 = 30$ . Un pixel au milieu d'une zone uniforme a une énergie nulle ; un pixel sur un contour net (un bord d'objet) a une énergie élevée.

La suite du cours est sur Adloun

Le chapitre en entier, formules et figures comprises, avec le tuteur, les fiches, les QCM et les exercices.

Lire la suite du cours

En accès libre, sans inscription.

Exercices corrigés de ce chapitre

Lire la suite du cours →