Algorithme de « Seam-carving »

Le seam carving ou recadrage intelligent, est un algorithme de redimensionnement d’images introduit par Shai Avidan et Ariel Shamir. Cet algorithme permet de changer le rapport hauteur/largeur des images sans pour autant écraser les sujets. Ainsi, ce n’est pas un redimensionnement par une mise à l’échelle classique, mais une suppression des pixels dits de moindre importance.

L’importance d’un pixel est en général mesurée par son contraste comparé à ses plus proches voisins, on parle alors de leur énergie. L’algorithme détecte les chemins de plus basse énergie, c’est-à-dire ceux qui portent le moins d’information utile et les supprime.

Le but final de ce projet était d’implémenter l’algorithme qui enlève les n colonnes dont la somme des énergies est la plus petite possible, ce qui est plus compliqué et plus intéressant algorithmiquement que la plupart des méthodes proposées par les logiciels du commerce (mais plutôt long en temps d’exécution).

Voici les résultats de l’application programmée par Alexis et Julien.

Image originale

oiseau

Mise à l’échelle classique

oiseauReduit

Redimensionnement par « seam-carving »

oiseauRedim

Fonction d’intérêt

oiseauRouge

 

Image originale

chat

Mise à l’échelle classique

chatReduit

Redimensionnement par « seam-carving »

chatRedim

Fonction d’intérêt

chatRouge