Hauteur : 384 pixels
Hauteur : 384 pixels
Au fil du temps, plusieurs techniques ont été développées afin de minimiser la perte de contenu d’une image suite au redimensionnement automatique. Une de ces techniques, mentionnée dans un article nommé Seam Carving for Content-Aware Image Resizing par Shai Avidan et Ariel Shamir, propose de se baser sur l’importance des pixels d’une image afin de produire automatiquement une image redimensionnée optimale. Ce projet consiste donc à implémenter notre propre algorithme de redimensionnement d'images en se basant sur les idées présentées dans l'article de Shai Avidan et Ariel Shamir.
En connaissant l’importance de chaque pixel, il est possible de trouver un ensemble de pixels à enlever de l’image afin de réduire la taille de celle-ci tout en conservant les éléments jugés importants.
Premièrement, il faut trouver une « fonction d’énergie » qui nous permettra de quantifier l’importance de chaque pixel d’une image. Il existe plusieurs fonctions d’énergie et chacune possède
des avantages et des inconvénients relatifs à l’image sur laquelle elle est appliquée. Pour ce travail, j’ai choisi d’utiliser la somme des gradients en x au carré et des gradients des y au carré pour chaque pixel
de l’image, tel que suggéré dans les notes de cours. Pour simplifier l'explication de la suite de
l'algorithme, je vais référer à la matrice obtenue par la fonction d'énergie comme étant la matrice "gradient".
Suite à l’obtention d’une matrice, de même dimension que l’image originale, associant à chaque pixel la valeur de son importance, il est possible de déterminer quels pixels enlever pour optimiser le
résultat final. En me référant au même article mentionné plus haut ainsi qu’aux notes de cours, j’ai pu constater qu’il existe plusieurs façons de choisir les pixels à enlever.
La technique optimale suggérée dans l’article amène le concept de chemin minimal. Dans le cas d’un redimensionnement horizontal, nous cherchons à trouver un chemin minimal
qui part d’un pixel de la première ligne de l’image pour se rendre jusqu’à sa dernière ligne en minimisant la somme des pixels parcourus. Le chemin minimal doit aussi passer par un seul pixel de chaque ligne tout en
s’assurant que les pixels d’une ligne à l’autre sont en contact (soit par un coin ou par une face). Cette dernière contrainte limite les possibilités de chemin minimal puisque d’une ligne à l’autre, on peut passer au
pixel en dessous à gauche, directement en dessous, ou en dessous à droite seulement. Une fois le chemin minimal trouvé, il suffit d’enlever les pixels faisant partie de ce chemin pour réduire la taille de l’image et
répéter l’opération autant de fois que désiré.
La technique de calcul de chemin minimal que j’ai utilisé dans le cadre de ce travail consiste, pour chaque pixel x de chaque ligne de la matrice "gradient", trouver lequel des pixels
(en bas à gauche, directement en dessous ou en bas à droite) est le plus petit et à additionner la valeur du pixel x à celle du plus petit pixel. Aussi, simultanément dans une autre matrice de même dimension que l’image,
on note pour chaque pixel, quel est le pixel suivant choisi (en bas à gauche : -1, directement en dessous : 0 ou en bas à droite : 1). Cette deuxième matrice servira de "carte" pour retrouver le chemin minimal.
Après avoir répété ces étapes pour chaque ligne de la matrice "gradient", on peut trouver l’index de l’élément qui a la valeur minimale sur la dernière ligne et remonter la matrice "carte" pour trouver le chemin minimal
et enlever les pixels de l’image réelle au fur et à mesure. On peut ensuite reprendre l’image réduite, recalculer la matrice "gradient" de la nouvelle image et trouver le nouveau chemin minimal et enlever les pixels
correspondants.
Les derniers paragraphes décrivent l’algorithme servant au redimensionnement horizontal. Par contre, il est possible de réduire la taille d’une image verticalement en effectuant une rotation de 90 degrés de
l’image et en appliquant l’algorithme de redimensionnement horizontal sur cette nouvelle image. Il est aussi possible de redimensionner verticalement et horizontalement une image en appliquant les deux algorithmes
l'un à la suite de l'autre.
Il est possible de remarquer avec cette dernière image, la présence d'artéfacts dans l'image réduite, surtout au niveau des deux voitures et de la fenêtre de la banque. Ces artéfacts peuvent être expliqués par le contenu de l'image. En effet, l'image contient beaucoup d'éléments "importants" du point de vue de la fonction d'énergie utilisée. Cet aspect de l'image rend donc difficile la recherche d'un chemin minimal dans l'image et fait en sorte que les résultats obtenus ne sont pas optimaux. Pour remédier à ce proclème, il serait possible d'expérimenter avec d'autres fonctions d'énergie et comparer les résultats obtenus ou même d'implémenter un algorithme qui permet de protéger certains objets de l'image en augmentant leur valeur dans la matrice "gradient" afin de diminuer leur probabilité de se retrouver sur le chemin minimal.
Encore une fois, il est possible de remarquer les artéfacts très présents sur la dernière image. Il serait possible d'appliquer les suggestions mentionnées plus haut afin de tester leur efficacité sur le redimensionnement vertical également.
Tel que mentionné dans l'article de Shai Avidan et Ariel Shamir, les images comportants des visages sont plus suceptibles d'être déformées. En effet, surtout dans le cas de l'image ci-dessous, les proportions ds visages sont très altérées par l'algorithme de redimensionnement. Pour améliorer le résultat obtenu, il faudrait implémenter un algorithme de reconnaissance facial ou plus simplement un algorithme qui permet de protéger des zones spécifiques de l'image spécifiées par l'utilisateur.
Le résultat du redimensionnement de cette image est loin d'être optimal. En effet, en observant le résultat de la fonction d'énergie de l'image, on peut constater que la majorité des zones à faible importance se trouvent entre les rayons de la roue. Les chances que le chemin minimal passe au traver des rayons sont donc très élevées et c'est ce qui explique que lors du redimensionnement, ceux-ci ont l'air tordus.
Comme pour l'image de la roue de vélo présentée plus haut, on peut constater sur l'image de gauche que le pied du globe terrestre a une très faible importance dans l'image. C'est donc ce qui explique que lors du redimensionnement, celui-ci soit déformé et à la limite d'être effacé complètement dans le redimensionnement vertical. Par contre, on peut constater que l'algorithme a conservé l'objet le plus important, soit le globe lui-même, presque intacte dans les deux redimensionnements.
Bien que lent sur de grosses images, l'algorithme que j'ai implémenté donne de bons résultats sur des images qui comportent quelques objets très importants bien définis entourés de régions de très faible importance. Il serait possible d'améliorer l'efficacité de mon algorithme en enlevant simplement le chemin-minimal à la matrice "gradient" à la place de recalculer celle-ci à chaque itération. Il serait également possible d'ajouter certaines fonctionnalités comme la détection de visages ou la protection de certains objets sur l'image pour améliorer les résultats obtenus.
Seam Carving for Content-Aware Image Resizing par Shai Avidan et Ariel Shamir
Notes de cours disponibles sur le site web du cours
Images trouvées sur internet :
Image 1
Image 2
Image 3
Image 4