Seam carving

Le seam carving, ou recadrage intelligent, est un algorithme de redimensionnement d'image développé par Shai Avidan et Ariel Shamir en 2007. Cet algorithme redimensionne, non pas par une mise à l'échelle classique (par interpolation) ou un recadrage, mais par la suppression ou l'addition de chemins de pixels dits de moindre énergie (en anglais, low-energy seams).

L'énergie d'un pixel est en général mesurée par son contraste comparé à ses plus proches voisins, mais d'autres techniques, comme la détection de forme, peuvent être utilisées. De plus, il est possible de définir ou de détecter automatiquement des zones de haute énergie, afin de les protéger de toute suppression. À l'inverse, on peut définir des zones de basse énergie, à retirer en premier. À partir de ces informations, l'algorithme calcule les chemins de plus basse énergie et les supprime, ou calcule les chemins de pixels qui peuvent être ajoutés.

L'une des applications de l'algorithme est de redimensionner des images sans distorsion pour des sites web réactifs.

Définitions

• Un chemin (en anglais, seam) est une suite continue de pixels allant soit du haut au bas de l'image, soit de sa gauche à sa droite.
• L'énergie d'un pixel est définie par une fonction d'énergie qui mesure le contraste (la différence de couleur) d'un pixel par rapport à ses voisins.

Algorithme

Description des étapes

L'exemple ci-dessous décrit l'algorithme de seam carving, dans le cas de la réduction de l'image :

Étape	Image
1) Choisir l'image à redimensionner.
2) Calculer l'énergie de chaque pixel, ici à partir du gradient d'intensité lumineuse. D'autres méthodes peuvent être utilisées, basées par exemple sur la saillance ou l'entropie (en).
3) À partir de cette fonction d'énergie, calculer une liste de chemins classés par niveau d'énergie. Cela peut être fait de plusieurs manières : en programmation dynamique (méthode la plus utilisée), avec l'algorithme de Dijkstra ou un algorithme glouton. Sur l'image, les chemins en rouge représentent les chemins de faible énergie, à retirer de l'image.
4) Retirer les chemins de plus faible énergie, autant que nécessaire pour obtenir la taille d'image désirée. Si l'on souhaite au contraire agrandir l'image, cette étape est remplacée par la copie d'un chemin de moindre énergie puis le calcul de la moyenne de ses pixels avec ses voisins
5) Utiliser l'image finale.

Calcul de l'énergie des chemins en programmation dynamique

La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes que l'on résout en stockant les résultats intermédiaires. Dans le cas du seam carving, il s'agit de calculer, pour chaque pixel de la rangée du haut de l'image, le chemin (continu) de moindre énergie qui descend jusqu'à un pixel de la rangée du bas.

Les illustrations ci-dessous montrent le processus de programmation dynamique utilisé pour calculer un chemin optimal du haut vers le bas. Chaque carré représente un pixel, chaque valeur à gauche en rouge dans une case représente l'énergie du pixel correspondant, et chaque valeur en noir représente la somme des énergies de tous les pixels du chemin menant à ce pixel inclus.

• 
  Initialisation : Par définition, la ligne supérieure n'a aucune ligne au-dessus d'elle, la somme des énergies conduisant à un pixel de cette ligne (en noir) est donc égale à l'énergie du pixel en question.
• 
  Parcours : Pour chaque pixel d'une autre ligne, l'énergie minimale qui y conduit est égale à la somme de l'énergie du pixel et du minimum d'énergie des trois pixels du dessus. Pour une ligne donnée, on calcule ainsi l'énergie minimale pour atteindre chaque pixel de cette ligne. Il suffit de répéter cet algorithme pour chaque ligne, jusqu'en bas, pour obtenir l'énergie minimale qui mène à chaque pixel de l'image.
• 
  Conclusion : L'énergie minimale atteinte en bas (5 dans cet exemple) indique l'énergie totale des chemins de moindre énergie. Il suffit ensuite de remonter chaque chemin, en sélectionnant à chaque fois le pixel de moindre énergie parmi les trois possibles, pour trouver les chemins de moindre énergie (dessinés en blanc ici), qui peuvent donc être supprimés.

Complexité de l'algorithme

Soit $n$ le nombre de lignes de l'image (hauteur) et $p$ le nombre de pixels par ligne (largeur). Chaque étape de programmation dynamique décrite ci-dessus (qui calcule les niveaux d'énergie de tous les pixels d'une ligne) nécessite un nombre constant d'opérations pour chaque pixel (somme de l'énergie du pixel avec les trois énergies des chemins y menant, et comparaison de ces trois sommes) et se réalise donc en temps $O(p)$. L'algorithme entier (parcours de toutes les lignes) prend donc $O(n\times p)$.

En revanche, si l'on souhaite supprimer plusieurs chemins simultanément, la troisième partie de l'algorithme peut donner lieu à des chemins qui s'intersectent. Pour parer à cette éventualité tout en évitant de recalculer toutes les énergies à chaque fois qu'un chemin est supprimé, Avidan propose d'ajouter un tableau qui stocke, pour chaque pixel, le numéro minimal du chemin sur lequel il est situé : les pixels sur le chemin de moindre énergie auront le nombre $1$, les pixels sur le chemin de deuxième moindre énergie le nombre $2$, et ainsi de suite. Ensuite, à chaque fois qu'un chemin est supprimé, ce tableau est mis à jour en conséquence.

Il est également possible d'ignorer cette complexité et de recourir à une approximation. Pour ce faire, on peut d'abord effectuer les deux premières étapes de l'algorithme décrit ci-dessus, ce qui permet de classer les pixels de la dernière ligne par niveaux d'énergie croissants. Ensuite, on peut considérer chacun de ces pixels dans l'ordre d'énergie croissant, et effectuer la troisième étape de recherche de chemin, sans jamais remettre à jour les énergies, mais en marquant les pixels utilisés pour ne pas les sélectionner plusieurs fois.

Applications et limites

Implémentations

Adobe a acquis une licence non-exclusive de la technologie de seam carving, implémentée comme fonctionnalité de Photoshop CS4, sous le nom de Content Aware Scaling (en français, mise à l'échelle sensible au contenu). Cette fonctionnalité est utilisable pour redimensionner une image de manière interactive, ce qui a donné lieu à des détournements sous forme de mèmes.

D'autres applications d'infographie ont repris cette fonctionnalité, dont GIMP, digiKam et ImageMagick, en plus d'applications dédiées comme iResizer qui a publié des versions libres et open source de l'algorithme.

• 
  Démonstration interactive SVG du seam carving, utilisant la fonction liquid-rescale d'ImageMagick. En cliquant ci-dessus, on peut ensuite survoler pour comparer l'image originale (en haut), l'image redimensionée avec le seam carving (au milieu), l'image redimensionnée de la manière la plus classique, par interpolation (en bas).
• 
  Démonstration interactive SVG du seam carving, utilisant la fonction liquid-rescale d'ImageMagick. En cliquant ci-dessus, on peut survoler pour comparer les trois images : on note que les visages sont moins affectés que le reste.

Limites

L'algorithme peut nécessiter une intervention de l'utilisateur pour éviter les erreurs (par exemple dans le cas où les images contiennent des visages que l'on ne veut pas déformer). Plusieurs interfaces implémentant cet algorithme proposent de « peindre » les zones à conserver, ce qui a pour effet d'augmenter leur niveau d'énergie dans l'exécution de l'algorithme. Dans le cas de visages, des algorithmes de reconnaissance faciale peuvent être utilisés.

En enlevant un chemin de moindre énergie, l'algorithme a parfois tendance à créer des chemins de haute énergie (en rapprochant des pixels qui ont un fort contraste entre eux). Pour éviter cet écueil, il est possible de simuler les conséquences de la suppression d'un chemin et de calculer la différence d'énergie de l'ensemble pour voir si elle augmente. Si c'est le cas, il peut être préférable de choisir un autre chemin à supprimer

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Seam carving » (voir la liste des auteurs).

Voir aussi

Articles connexes

• Inpainting

Liens externes

• Seam carving for content-aware image resizing, dans la revue SIGGRAPH
• Publication initiale des auteurs
• Démonstration vidéo