TP2: Découpage d'images

Par Mathieu Garon

Introduction

Avec l'arrivé des téléphones et des tablettes, le besoin d'avoir un contrôle sur la résolution des images à émergé. Les propriétaires des sites webs souhaite rejoindre le maximum d'utilisateur peu importe leurs plateforme, et pour ce faire, les images doivent nécessairement être manipuler de manière intélligente. Pour palier au problèmes de format d'image, Shai Avidan et Ariel Shamir ont publié un article sur une manière innovative pour modifier les dimensions de l'image de manière à conserver le maximum d'informations importante. Le rapport suivant présente un approche d'implémentation de l'algorithm ainsi que plusieurs expérimentations intéressantes.

Approche

En utilisant les techniques appropriées, l'implémentation d'un tel algorithme peu être relativement simple. Comme tous les problèmes, il suffit de diviser la tâche en plusieurs sous problèmes simples et de les tester individuellement. Les sections suivantes présente les différents problèmes et leurs solutions.

Fonction d'énergie

En premier lieu, il est nécessaire de définir quels informations sont importantes dans l'image. Il n'y a pas de bonne réponses dans la manière d'implémenter cette fonction puisque l'information critique n'est pas nécessairement un choix logique. Par exemple, dans la section Retrait de zone, la fonction d'énergie est directement modifier par l'utilisateur en fonction de ses besoins. Par contre, il est possible d'utiliser des méthodes génériques. En effet, en général les informations importantes sont les arêtes ou les haute fréquences dans une image. L'image suivante présente la fonction utilisé dans ce rapport, il s'agit d'un filtre sobel horizontal et vertical appliqué sur l'image, ensuite les trois cannaux sont simplement additionnés.


Calcules des chemins

Ensuite, il est nécessaire d'utiliser les informations précédentes afin de trouver le chemin le moins couteux dans l'image. La programmation dynamique peu être utilisé dans ce cas pour accèlerer le traitement. À partir de l'image d'énergie (M), les pixels inférieurs doivent être additionner à la valeurs minimum parmis les trois pixels supérieures.

M[y, x] = M[y, x] + min(M[y-1, x-1], M[y-1, x], M[y-1, x+1])

Dans l'image suivante, le poids des chemins sont visibles. Une caractéristique de cet algorithme est la forme triangulaire observés sous les zones élevé en informations. Cela est du au fait que les chemins se déplace d'un pixel par lignes. À cette étape, il est possible de prédire visuellement quels zones de l'image seront préservés et lesquels seront retirés.


Sélection du chemin le plus court

Lorsque la "carte" des chemins est établie, l'étape suivante est de sélectionner dans la dernière rangé de pixel la valeur minimal et de remonter le chemin en sélectionnant la valeur minimum des pixels supérieurs. Cette opération retourne une colonne entière de pixel qui représente le chemin comportant le moins d'informations.


Retirer le chemin

Finalement, le chemin calculé doit simplement être retiré afin de retourner l'image contenant une colonne de moins. L'image suivante présente un retrait de 25% de l'image original. Les étapes sont recalculés à tous les itérations.


Images

Dans l'image suivante, le throne n'est pas affecté car il représente trop de détails, par contre, il n'est plus centré dans l'image puisque la fumé à sa droite contient moins de transitions. Donc la méthode présente peu changer la composition de l'image.
(Largeur : -40%)



Le centre de la lune est évité puisqu'elle contient beaucoup de détails. L'effet revient à centrer la sphère et retirer les bordures. Il s'agit encore là d'une limitation de l'algorithme.
(Largeur : -50%, Hauteur : -50%)



Un effet intéressant est la compression du texte. Les informations importantes (les caractères) sont intacte alors qu'une grande partie des pixels ont été retirés. De plus, le texte est toujours lisible.
(Largeur : -25%, Hauteur : -25%)







Ici il est important de noté que la ligne diagonale à mal subit la transformation, puisque des lignes horizontales ont été retirés de l'image.
(Hauteur : -30%)



(Largeur : -50%)



(Hauteur : -50%)



Le cas suivant est un exemple des limitations sévères de l'algorithme. Cette image contient trop de détails pour que celle-ci ne soit pas "endommagé" lors du retrait des colonnes et des lignes.
(Largeur : -25%, Hauteur : -25%)

Images personnelles

Ici on prouve clairement qu'une forme comme un cercle ne peut pas être préservé. Le principe peu être utilisé pour imiter les peintures de Dali!


(Largeur : -40%)



Reconstruction du monde il y a 240 millions d'années.


(Largeur : -60%, Hauteur -25%)





(Largeur : -60%)



Trouvez la différence?


(Largeur : -60%)



Crédit supplémentaires

Interface Interactive

Pour assurer une qualité de l'image lors du retrait des colonnes, une interface simple à été réalisé. Le script permet de choisir l'image à modifier et peu prendre en option le nombre de colonnes maximum à retirer dans le but d'alleger le temps de calcule si nécessaire. Pour avoir une fluidité exceptionnel, les images calculés sont simplement garder en mémoire. Le "slider" permet d'indexer les images. Une limitation de l'interface est que celle-ci ne permet pas de modifier les rangées et les colonnes en même temps.




Agrandissement d'image

Agrandir les images avec le même algorithme est moins aisé. En effet, ajouter une colonne à la fois donnera un résultat indésirable du au fait que la ligne ayant le plus petit poid sera toujours sélectionné. Pour contrer ce problème, il suffit de précalculer une liste de ligne ayant le poid minimal, pour ensuite faire l'insertion de celles-ci. Dans le cas présent, une moyenne avec les pixels avoisinant est fait pour chaque nouveau pixel.
Colonnes ayant le moins d'importance



(Largeur : +25%)



Erreur de l'algorithme

Dans l'image précédente, certaines colonnes de la maison ont été affecté car les colonnes ne sont pas mis à jours avec les nouvelles versions de l'image. Pour ce faire, il faudrait s'assurer que l'index de chaques pixels n'ai pas été décallé de un.

Limitation

Dans le cas ou les poids minimals sont tous dans la même zone, le bruit causer par l'ajout des lignes est fortement indésirable. Pour contrer cela, il est possible d'utiliser la protection de zone proposé dans la section Protection de zone. Ici le même algorithme est utilisé, par contre, une très grande quantité de lignes ont été calculé dans la même zone (pour vous convaincre, parmis la zone étiré une branche est visible.)
(Largeur : +25%)



Retrait de zone

Pour facilement retirer des zones spécifiques de l'image, un interface graphique permet de prendre les entrés de l'utilisateur. Le principe consiste à modifier directement la fonction d'énergie de l'image. Pour le retrait d'une zone spécifique dans l'image, la zone peu avoir un poid de -1000. De cette manière, les chemins les plus courts vont passer par la section avec les valeurs négatives, en prenant pour aquis que les valeurs sont assez basses pour assurer un plus court chemin. À la manière de Shai Avidan et Ariel Shamir, trouvez le pigeon retiré!
Original



Modifié


Protection de zone

Avec la même interface que le retrait des zones, il est possible d'ajouter un poid élevé à une section. En ajoutant un poid de 1000 par exemple, assure la protection de la zone. Cette méthode peu généré des effets indésirables dans des cas spéciaux. Par exemple, une zone très large va faire en sorte que les colonnes dessous auront une valeur trop haute pour être retiré. Cela est du au fait que la recherche des chemins se fait à l'aide des pixels avoisinants. Un exemple intéressant pour la protection de zone est lors de la prise d'une photo ayant comme élément principale un objet contenant peu de détails relativement au reste de l'image. Par exemple :




Avec la protection de la chute :


Interface

Le programme consiste à laisser l'utilisateur modifier la fonction d'énergie en temps réel. Le clique gauche de la souris dessine une zone à protèger (vert) alors que le clique droit ajoute une zone à retirer (rouge). Dans le but de laisser une liberté à l'utilisateur, la touche "espace" retire une colonne à la fois, ainsi il est possible de continuer de modifier la fonction d'énergie même après avoir retiré plusieurs colonnes.


Problèmes rencontrés

Lors de la première implémentation du retrait des colonnes, le temps de calcule était d'environ 32.5 secondes pour retirer 50 colonnes. L'implémentation traitait les données une à une. Pour contrer cela, le calcules des chemins était le goulot d'étranglement principale et une autre méthode à été implémenté. Celle-ci prend en considération numpy qui gère mieu la mémoire avec les matrices. Le temps de l'algorithme est divisé par trois avec les calcules par colonnes. Grossièrement, au lieu de traiter les données une à une, une ligne numpy de la grandeur de l'image est alloué est les pixels mininums y sont insérés, ensuite un addition matriciel est simplement fait sur la ligne suivante.