Page Principale

Cette page démontre un algorithme de traitement d'images appelé Seam carving (que l'on pourrait traduire par «découpe de chemins»), introduit en 2007 par S.Avidan et A.Shamir dans cet article. Il a depuis été implémenté dans de nombreux logiciels de traitement d'images (par exemple dans gimp sous le nom liquid rescale).
Son premier usage est de redimensionner de façon «intelligente» une image : plutôt que d'appliquer un simple facteur d'échelle qui va déformer les objets, l'algorithme de Seam carving cherche à supprimer des pixels «peu importants». Enlever un pixel dans une zone de couleur uniforme (le fond par exemple) sera visuellement moins perceptible que de l'enlever sur le contour d'un objet de l'image.

Cette page a été adaptée sous forme de TP Python à destination d'élèves en première ou seconde année de CPGE scientifique.

Contours et gradient

Une image en noir et blanc peut-être vue comme une version discrétisée d'une application $I:[0,w]\times [0,h]\longrightarrow [0,1]$, où $w$ et $h$ désignent la largeur et hauteur de l'image, et où $I(x,y)$ est le niveau de gris au point $(x,y)\in[0,w]\times [0,h]$. Nous adoptons la convention que l'origine $(0,0)$ de l'image est en haut à gauche dans toute la suite.
Le gradient de l'image au point $(x,y)$ est défini par $\nabla I(x,y)=\left(\frac{\partial I}{\partial x}(x,y),\frac{\partial I}{\partial y}(x,y)\right)$. Sa norme est un bon indicateur de la variation de niveau de gris autour du point considéré. La norme du gradient va être proche de 0 dans les zones où le niveau de gris varie peu, et elle va être grande au niveau des points de contours (la direction du gradient étant orthogonale à celle du contour - nous n'allons pas utiliser cette information dans la suite).
En pratique, on peut calculer une version discrétisée du gradient d'une image au pixel de coordonnées $(i, j)\in\left\{0\cdots w-1\right\}\times\left\{0\cdots h-1\right\}$ en utilisant la formule suivante $\nabla I(i,j)\approx \left(\frac{I(i+1, j)-I(i-1, j)}{2},\frac{I(i, j+1)-I(i, j-1)}{2}\right)$ (à adapter aux bords de l'image), puis calculer la norme de ce vecteur. On peut adapter cela sans difficulté au cas des images en couleur en remplaçant les différences d'intensité par la distance entre les couleurs.
On obtient alors une «carte d'énergies» que vous pouvez observer dans l'application ci-dessous.

Enlever des pixels…

On souhaite réduire la largeur d'une image d'un pixel. pour ce faire, on va enlever un pixel dans chaque ligne, en privilégiant le choix d'un pixel de basse énergie.

• Une première idée est d'enlever un pixel d'énergie minimale sur chaque ligne. vous pouvez tester cela dans l'application en choisissant l'algorithme «Ligne par ligne», puis en réduisant de 50 pixels horizontalement. Cette approche détruit rapidement la structure de l'image, des portions de lignes adjacentes étant rapidement décalées.
• Une solution est d'enlever la colonne de pixels donc l'énergie est minimale (l'énergie d'une colonne étant définie comme la somme de l'énergie de ses pixels). C'est l'algorithme «Meilleure colonne» dans l'application. Il fonctionne de façon satisfaisante sur certaines images, mais pas sur celles présentant des niveaux de détails important (tester une réduction de 100 pixels horizontalement sur l'image «rue 1» : les voitures sont fortement déformées).
• L'algorithme de Seam carving utilise une idée intermédiaire. On enlève maintenant un chemin d'énergie minimale, un chemin étant défini comme un ensemble de pixels de la forme $(i(0),0),(i(1),1),\cdots (i(h-1),h-1)$ tels que pour tout $j\in\{0\cdots h-2\}$, $|i(j)-i(j+1)|\leq 1$. On donne ainsi plus de souplesse au chemin pour éviter les zones à fort gradient, tout en assurant une certaine cohésion entre les lignes une fois les pixels retirés.

On obtient alors des résultats visuellement bons sur la plupart des images. On peut bien sûr utiliser la même méthode en intervertissant les lignes et les colonnes pour réduire la hauteur de l'image.

Image : Algorithme : Seam carving (par programmation dynamique) Ligne par ligne Meilleure colonne Chemin glouton Énergie : ∥∇I∥₁ ∥∇I∥₂
Réinitialiser
Réduire de 1 pixel horizontalement Réduire de 20 pixels horizontalement Réduire de 50 pixels horizontalement
Réduire de 1 pixel verticalement Réduire de 20 pixels verticalement Réduire de 50 pixels verticalement
Amplification de contenu : réduction de 1/6
Étendre de 1 pixel horizontalement Étendre de 20 pixels horizontalement Étendre de 50 pixels horizontalement
Étendre de 1 pixel verticalement Étendre de 20 pixels verticalement Étendre de 50 pixels verticalement




Réinitialiser
Réduire de 1 pixel horizontalement Réduire de 20 pixels horizontalement Réduire de 50 pixels horizontalement
Réduire de 1 pixel verticalement Réduire de 20 pixels verticalement Réduire de 50 pixels verticalement
Amplification de contenu : réduction de 1/6
Étendre de 1 pixel horizontalement Étendre de 20 pixels horizontalement Étendre de 50 pixels horizontalement
Étendre de 1 pixel verticalement Étendre de 20 pixels verticalement Étendre de 50 pixels verticalement

Calcul d'un chemin minimal

Pour calculer un chemin minimal :

• on peut tenter un algorithme approché glouton : un pixel $p_0$ d'énergie minimale de la première ligne de l'image est d'abord choisi. Parmi les deux ou trois pixels possibles de la deuxième ligne (les voisins de $p_0$), on choisit celui qui est d'énergie minimale. Puis on continue ainsi ligne par ligne. Cet algorithme est rapide (de complexité $O(w+h)$), mais donne des chemins assez éloignés de l'optimum, et souvent contraints à traverser des contours.
• On pourrait utiliser l'algorithme de Dijkstra, en construisant un graphe orienté du haut vers le bas de l'image dont les arcs correspondraient aux pixels, et les poids aux énergies. Mais la forme du problème permet de mettre en place une solution plus simple.

Utilisation de programmation dynamique

Pour calculer l'énergie $E(i,j)$ minimale d'un chemin reliant la première ligne de l'image à un pixel de coordonnées $(i,j)$ intérieur à l'image, il suffit de connaître l'énergie de ses trois pixels voisins sur la ligne précédente : $E(i,j)=\min(E(i-1,j-1),E(i,j-1),E(i+1,j-1))+e(i,j)$ où $e(i,j)$ est l'énergie du pixel $(i,j)$.
Nous sommes dans une situation où l'on peut utiliser la programmation dynamique - définie par Wikipedia comme «consistant à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires.»
Ici, les valeurs de $E$ sur une certaine ligne $j$ ne dépendent que des valeurs de $E$ sur la ligne précédente $j-1$ et des énergies $e$ sur la ligne $j$. On peut donc utiliser l'algorithme suivant, de complexité $O(wh)$, pour calculer $E$ ligne par ligne en partant de la première. On cherche ensuite un indice $i$ minimisant $E(i,h-1)$ sur la dernière ligne, puis on remonte ligne par ligne jusqu'à la première pour obtenir un chemin d'énergie minimale entre la première et la dernière ligne.

Quelques extensions

Amplification de contenu

Les auteurs de l'article proposent d'utiliser l'algorithme de Seam carving pour «amplifier» le contenu d'une image : si l'on réduit la taille de l'image dans la largeur et la longueur de façon à préserver le rapport $w/h$, puis que l'on remet l'image à la taille de départ en lui appliquant un simple facteur d'échelle, on obtient une image où les zones de faibles gradients auront été réduites, amplifiant ainsi les zones de forts gradients, dont le contenu est a priori plus «intéressant».

Se pose le problème de savoir dans quel ordre on alterne les retraits de lignes et de colonnes. L'article original propose une nouvelle fois une approche à base de programmation dynamique pour aborder cette question.

Vous pouvez voir cela dans l'application ci-dessus, où les suppressions de lignes et de colonnes sont intercalées de façon naïve. Tester par exemple les images «Cheveaux», «Plage» ou «Machaon» (l'exécution dure quelques secondes).

Augmentation de la taille d'une image

On peut utiliser le Seam carving pour augmenter la taille d'une image dans l'une ou l'autre des deux dimensions.

• La première idée est d'insérer un chemin au niveau du chemin de plus basse énergie - les couleurs sur ce nouveau chemin étant les moyennes des couleurs des chemins parallèles voisins. L'inconvénient est que des ajouts successifs auront lieu au niveau du même chemin, créant une zone d'artefact étiré.
• Une autre approche est donc, si l'on veut étendre de $N$ pixels, de calculer les $N$ chemins $c_1,\cdots c_N$ utilisés lors d'une réduction de $N$ pixels, puis d'insérer des chemins comme expliqué dans le point précédent au niveau de $c_1,\cdots c_N$. Cela donne des résultats visuellement meilleurs.

Suppression d'objets

On peut utiliser l'algorithme de Seam carving pour supprimer un objet dans une image.
Une fois sélectionnée la partie de l'image que l'on souhaite supprimer, on associe à chaque pixel de cette partie une énergie fortement négative, de façon à contraindre les chemins optimaux à passer par au moins l'un de ses pixels.
On applique des réductions de hauteur ou de largeur successives jusqu'à ce que la zone sélectionnée ait complètement disparu. On peut ensuite étendre l'image comme expliqué dans la section précédente pour lui redonner sa taille de départ.
Testez avec les images «suppression» dans l'application !

Redimensionnement en temps réel

Afin de permettre un redimensionnement en temps réel (par exemple pour obtenir une image adaptable à la taille de l'écran sur lequel elle est affichée), il est possible de précalculer les chemins à supprimer lors de réductions successives. C'est ce qui est fait dans l'application ci-dessous, pour une réduction dans le sens de la largeur. L'intensité des pixels de l'image «pixels à supprimer» correspond à leur ordre de suppression : les pixels les plus clairs apparaissent dans les premiers chemins à supprimer, les plus foncés dans les derniers.
Redimensionner l'image est beaucoup plus rapide : plus besoin de calculer les chemins à supprimer uns à uns, il suffit de supprimer de l'image les pixels dont l'intensité dépasse une certaine valeur dans l'image «pixels à supprimer».
Vous pouvez tester ce redimensionnement en temps réel à l'aide du bouton coulissant situé sous les images.
Rumble fish Train Chevaux