Résumé

Un des problèmes qui a reçu beaucoup d'attention ces dernières années en recherche est celui du redimensionnement automatique d'images: comment faire pour redimensionner une image sans toutefois perdre son contenu? Un des articles les plus importants sur ce sujet a été publié récemment à SIGGRAPH et s'intitule Seam Carving for Content-Aware Image Resizing par Shai Avidan et Ariel Shamir. Dans ce travail, vous allez implémenter l'algorithme de base présenté dans cet article. Vous concevrez un programme qui pourra rétrécir une image dans une dimension donnée (horizontalement ou verticalement) en retirant une à une les colonnes (ou les lignes) de l'image contenant le moins d'information.

Overview

One of the recent papers at SIGGRAPH that made news was Seam Carving for Content-Aware Image Resizing by Shai Avidan and Ariel Shamir. In this assignment, you'll be implementing the basic algorithm presented therein. To wit, you'll be designing a program which can shrink an image (either horizontally or vertically) to a given dimension.

Détails

Voici un lien vers une vidéo qui présente une courte description de l'algorithme et montre des résultats intéressants. Votre algorithme devra rétrécir la taille de vos images en appliquant l'algorithme suivant:

1. Déterminer l'importance de chaque pixel en utilisant une fonction d'énergie.
2. Jusqu'à ce que l'image soit réduite à la taille désirée:
   1. Trouver le joint avec le moins d'importance dans l'image.
   2. Retirer ce joint.

Vous pouvez utiliser les fonctions d'énergie proposées dans l'article, ou vous pouvez aussi en proposer une autre (que vous devrez expliquer et justifier). Définir une bonne fonction d'énergie est essentiel pour obtenir de bons résultats.

Details

For a brief overview of the algorithm and some inspiring results, check out the video. Your algorithm will shrink images as follows:

1. Determine the 'importance' each pixel has using an energy function.
2. Until image has shrunk to the desired dimension:
   1. Find the lowest-importance seam in the image.
   2. Remove it.

Feel free to use any energy function in the paper (or cook up something on your own---that you must explain and justify). Defining a good energy function seems to be the key to achieving good results.

Un joint horizontal est un chemin reliant un côté de l'image à l'autre en sélectionnant exactement un seul pixel pour chaque colonne. (Un joint vertical est semblable, mais celui-ci relie le haut et le bas de l'image, et contient un seul pixel par rangée.) Trouver le joint avec le moins d'importance peut être fait de façon efficace avec la programmation dynamique. Pour plus de détails, référez-vous à l'article original.

Votre code final devra pouvoir, étant donnée une image d'entrée, produire une image de sortie rétrécie d'un nombre donné de pixels, soit en largeur ou en hauteur (pas nécessairement les deux à la fois). Pour ce faire, il est beaucoup plus simple d'écrire votre code pour une seule dimension, puis transposer l'image pour la rétrécir dans l'autre dimension.

A horizontal seam is a connected path from one side of the image to the other that chooses exactly one pixel from each column. (A vertical seam is the same, but from top to bottom and with rows.) Finding the lowest-importance seam is a simple dynamic programming exercise. This is pretty well explained in the article of Avidan and Shamir.

Your final code should be able to, given an input image, produce an output image shrunk by a given number of pixels either in width or in height (but not both at once!). A simple way to achieve this goal is to write your code to shrink only in one dimension and then create a wrapper function that transposes the image to shrink in the other dimension.

Exemple de découpage vertical

Remarquez comment le contenu de l'image est conservé et que la grande section (plutôt inutile et déprimante) d'asphalte est retirée.

Example: Vertical Carving

Notice how the content in the image is preserved, and the large, boring, area of asphalt is removed.

Exemple de découpage d'artefacts

Lorsque vous poussez l'algorithme à ses limites, des artefacts---comme des distorsions de formes et des angles cubistes étranges---apparaîtront dans l'image. Peaufinez votre code pour atténuer ces effets et tentez de comprendre sur quels types d'images ces effets se produisent. Généralement, des scènes hautement structurées et les images contenant des visages en souffriront, tandis que les scènes contenant des objets texturés sur de simples arrière-plans devraient mieux fonctionner.

Example: Carving Artifacts

As you push the algorithm to its limits, artifacts -- such as shape distortions and odd cubist angles -- will begin to crop up. A lot of time on this project will be spent tweaking your code to mitigate these effects, as well as searching for pictures which don't exhibit them. Generally, highly-structured scenes and human faces will suffer, while scenes with textured objects on simple backgrounds will work better.

Livrables

Comme pour le TP précédent, vous devrez soumettre votre code et une page web simple illustrant vos résultats et contenant une courte discussion sur ceux-ci. Pour vous aider à démarrer, nous vous fournissons une ébauche de page web (facultative). L'apparence esthétique du site Web ne sera pas évaluée, mais il est important que les informations soient clairement présentées.

Plus précisément, la page devrait contenir:

• Une brève description du projet et de votre approche;
• Des figures illustrant votre approche. Par exemple, affichez les résultats des fonctions d'énergie et les joints détectés.
• Les résultats de votre algorithme sur toutes ces images. Dans chaque cas, affichez des images qui auront été re-dimensionnées de façon significative (par exemple, au moins 25% de la taille de l'image original).
• Les résultats de votre algorithme sur au moins quatre images que vous aurez trouvées sur Internet (ex: Google Images). Dans chaque cas, affichez des images qui auront été re-dimensionnées de façon significative (par exemple, au moins 25% de la taille de l'image original). Citez vos sources.
• Les résultats de votre algorithme sur au moins quatre photos que vous aurez prises vous-mêmes.
• Si vous avez rencontré des problèmes sur certaines images, décrivez ces problèmes et décrivez comment vous avez essayé de les résoudre;
• Si vos algorithmes échouent, expliquez pourquoi, selon vous;
• Décrivez tous les crédits supplémentaires que vous aurez implémentés. Montrez les images avant et après, et accompagnez vos explications avec des illustrations.

Deliverables

As in the previous homework, this one will be handed in a webpage format. Remember: the aesthetics of the website will not be evaluated, but it is important that the information be presented clearly.

More precisely, the webpage should:

• Explain the algorithm you have implemented. Illustrate if you think it is needed.
• Show your results on a lot of images including those that we have provided, as well as on other images of your own choosing (see Google Images, or Flickr). Make sure to show results where images are significantly resized (e.g. 25% of the original dimensions). Explain these results, and give credit to the original authors.
• Explain all the bells & whistles you have implemented. Try to illustrate these explanations.

Évaluation

Ce travail est évalué sur 100 points:

• (50 pts) Implémentation fonctionnelle de l'algorithme de découpage de joints (horizontaux et verticaux). Les points sont alloués selon l'explication de l'implémentation ainsi que le code lui-même.
• (25 pts) Résultats et descriptions de ces résultats obtenus sur les quatre images qui vous sont fournies et celles que vous aurez trouvées sur Internet.
• (5 pts) Résultats sur les photos que vous aurez prises vous-mêmes (au moins 4).
• (20 pts) Résultats et descriptions des images sur lesquelles votre algorithme n'a pas bien fonctionné. Expliquez comment ces mauvais résultats sont possibles.
• (N pts) Éblouissez-nous avec vos crédits supplémentaires!

Evaluation

This assignment is evaluated on 100 points, as follows:

• (50 pts) Functional implementation of the basic seam carving algorithm (horizontal and vertical). These points are on the explanations as well as the code itself.
• (25 pts) Include lots (eight or more; remember to use the images that we provided) great examples of resized images (either from yourself or the internet, but remember to give credit to the original authors!)
• (20 pts) Once we're riding high on your success, calm us down with some examples of where your code doesn't work.
• (N pts) Dazzle us with any bells and/or whistles you've added in.

Remise

Pour la remise de votre travail, créez un fichier tp2.zip qui contient:

• Votre rapport en format HTML dans un dossier tp2/web. Vos images doivent être dans un dossier tp2/web/images.
• Votre page principale doit être tp2/web/index.html. De plus, assurez-vous qu'il n'y a aucun caractère spécial (accent, ponctuation, espace, etc.) dans les noms de vos fichiers, images, etc.
• Votre code Matlab doit être dans un dossier tp2/code. N'incluez pas les images que vous avez utilisées pour produire vos résultats dans ce dossier dans le but de ne pas alourdir le fichier.

Finalement, veuillez téléverser votre fichier tp2.zip sur pixel (http://pixel.fsg.ulaval.ca) avant la date limite. La politique des retards mentionnée dans le plan de cours sera appliquée. Pour toutes questions concernant la procédure de remise ou le travail lui-même, posez vos questions sur Piazza!

Attention! La taille limite permise sur Pixel est de 50MB. Assurez-vous que la taille du fichier tp2.zip n'excède pas 50MB.

Handing in procedure

For this homework, you must create a tp2.zip file. In this file you'll put:

• Your report in an HTML format inside a folder named tp2/web. Your images for this web page should be inside a folder named tp2/web/images.
• Your main page has to be tp2/web/index.html. Make sure none of the files have special characters (e.g. accents, punctuation, spaces, etc.) in their filenames.
• Your Matlab code should be put inside the folder tp2/code. Do not include the images you have used to generate your results inside this folder, as this will likely generate huge files.

Finally, you should upload this file (tp2.zip) on pixel (http://pixel.fsg.ulaval.ca) before the deadline. The late submission policy described in the course plan will be applied. For any question regarding the submission process or the project as such, ask your questions on Piazza!

Beware! File size limit on Pixel is 50MB. Make sure that your tp2.zip file size does not exceed 50MB.

Liens rapides

• Ébauche de page web;
• Images sur lesquelles vous devez obligatoirement tester vos algorithmes.

Quick links

• Webpage template;
• Images on which you are required to test your algorithms.

Remerciements

Merci à Alyosha Efros d'avoir créé le TP original qui a servi d'inspiration pour celui-ci!

Thanks

Many thanks to Alyosha Efros for creating the assignment which inspired this one!