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éfinitionsModifier

  • 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.

AlgorithmeModifier

Description des étapesModifier

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

É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 dynamiqueModifier

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.

  Cliquez sur une vignette pour l’agrandir.

Complexité de l'algorithmeModifier

Soit   le nombre de lignes de l'image (hauteur) et   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  . L'algorithme entier (parcours de toutes les lignes) prend donc  .

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  , les pixels sur le chemin de deuxième moindre énergie le nombre  , et ainsi de suite. Ensuite, à chaque fois qu'un chemin est supprimé, ce tableau est mis à jour en conséquence[1].

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[2].

Applications et limitesModifier

ImplémentationsModifier

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)[3]. 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[4].

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

  Cliquez sur une vignette pour l’agrandir.

LimitesModifier

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[9],[10]

Notes et référencesModifier

  1. a et b (en) Shai Avidan et Ariel Shamir, « Seam carving for content-aware image resizing », SIGGRAPH,‎ (lire en ligne, consulté le )
  2. (en) Aditya Bist et Vinay Palakkode, « Parallel Seam Carving », sur cmu.edu, Université Carnegie-Mellon, (consulté le )
  3. (en) « What's New In Adobe Photoshop CS4 », sur photoshopsupport.com (consulté le )
  4. (en) « Content Aware Scaling », sur knowyourmeme.com, (consulté le )
  5. (en) Liquid Rescale GIMP plugin
  6. (en) New Liquid Rescale tool under construction…
  7. (en) Liquid Rescale - Seam Carving
  8. (en) Intelligent Resizer - Rescale Photos Without Rescaling the Subject!
  9. (en) Michael Rubinstein, Ariel Shamir et Shai Avidan, « mproved Seam Carving for Video Retargeting » [PDF], SIGGRAPH, (consulté le )
  10. (en) Michael Rubinstein, Ariel Shamir et Shai Avidan, « Improved Seam Carving for Video Retargeting ».

Voir aussiModifier

Articles connexesModifier

Liens externesModifier