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 va rétrécir la taille de vos images comme suit:

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.

Sentez-vous libre d'utiliser les fonctions d'énergie de l'article (ou d'en utiliser une autre de votre choix). 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). 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 -- vont apparaître 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 vont en souffrir, alors que les scènes d'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 travail précédent, celui-ci sera remis dans un format page Web. Rappel: le site Web n'a pas besoin d'être esthétiquement agréable; ne faites que décrire ce que vous avez fait.

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

• Explication de l'algorithme que vous avez implémenté. Illustrez au besoin. Par exemple, affichez les résultats des fonctions d'énergie et les joints détectés.
• Montrez vos résultats sur toutes ces images, ainsi que sur d'autres images de votre choix (voir Google Images, ou Flickr). Assurez-vous d'afficher des images qui auront été re-dimensionnées de façon significative (e.g. au moins 25% de la taille de l'image). Expliquez vos résultats, et n'oubliez pas de citer vos sources!
• Expliquez les crédits supplémentaires que vous avez implémentés. 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.

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 code matlab doit être dans un dossier tp2/code. De préférence, ne pas inclure les images que vous avez utilisées pour produire vos résultats dans ce dossier dans le but de ne pas alourdir le fichier.

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

• Your report in the HTML format inside a folder named tp2/web. Your images for this web page should be inside a folder named tp2/web/images.
• Your matlab code should be put inside the folder tp2/code. Please do not include the images you have used to produce your results inside this folder.

Évaluation

Ce travail est évalué sur 100 points. La répartition des points va comme suit:

• (50 pts, 30 pts pour étudiants gradués) Implémentation fonctionnelle de l'algorithme de découpage de joints (horizontal et vertical). Ces points sont sur l'explication de l'implémentation ainsi que le code lui-même.
• (30 pts) Inclure beaucoup (huit ou plus dont les quatre qui vous ont été fournies) d'exemples d'images redimensionnées (ces images peuvent être prises par vous-même ou peuvent provenir de l'Internet, mais n'oubliez pas citez vos sources!). Décrivez vos résultats.
• (20 pts) Après les bons résultats, montrez-nous aussi vos échecs. Plus spécifiquement, expliquez comment ces mauvais résultats sont possibles.
• (N pts) Éblouissez-nous avec vos crédits supplémentaires. Expliquez et illustrez ce que vous avez fait.

Evaluation

This assignment is evaluated on 100 points, as follows:

• (50 pts, 30 pts for graduate students) Functional implementation of the basic seam carving algorithm (horizontal and vertical). These points are on the explanations as well as the code itself.
• (30 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.

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!