TP1: Colorisation de l'Empire Russe

HW1: Colorizing the Russian Empire

Date limite: 1er février 2015 à 23h59

Due Date: 23h59 on February 1st, 2015

Petit cours d'histoire

Sergei Mikhailovich Prokudin-Gorskii (1863-1944) était un homme bien à l'avance sur son temps. En 1907, convaincu que la photographie couleur était la voie de l'avenir, il a obtenu une permission toute spéciale du Tsar pour traverser le vaste empire russe et de prendre des photographies couleurs de tout ce qu'il voyait. Il a réellement tout photographié: des gens, des édifices, des paysages, des chemins de fer, des ponts... tout ça pour produire des milliers de photos couleurs. Comme la photographie couleur n'existait pas encore, son idée était toute simple: enregistrer sur des lames de verre trois expositions de chaque scène en utilisant un filtre rouge, vert et bleu pour chacune d'elles. Le seul hic c'était qu'il n'y avait à l'époque aucune façon d'imprimer ces photos couleurs! Il s'imaginait des projecteurs spéciaux installés dans des locaux de classe "multimédia" au travers de tout l'empire où les enfants pourraient en apprendre plus sur leur vaste pays. Hélas, ses plans ne se sont jamais concrétisés: il quitta la Russie en 1918, juste après la révolution, pour ne plus jamais y revenir. Heureusement pour nous, les négatifs RGB ("Red-Green-Blue", ou Rouge-Bleu-Vert) capturant les dernières années de l'empire russe ont survécu et furent achetés en 1948 par la Librairie du Congrès aux États-Unis. Celle-ci a récemment (2004) numérisé ces négatifs et les a rendus accessibles sur Internet.

Background

Sergei Mikhailovich Prokudin-Gorskii (1863-1944) was a man well ahead of his time. Convinced, as early as 1907, that color photography was the wave of the future, he won the Tsar's special permission to travel across the vast Russian Empire and take color photographs of everything he saw. And he really photographed everything: people, buildings, landscapes, railroads, bridges... thousands of color pictures! Unfortunately, color photography did not exist yet, so he used a simple idea: record three exposures of every scene onto a glass plate using a red, a green, and a blue filter. Never mind that there was no way to print color photographs until much later -- he envisioned special projectors to be installed in "multimedia" classrooms all across Russia where the children would be able to learn about their vast country. Alas, his plans never materialized: he left Russia in 1918, right after the revolution, never to return again. Luckily, his RGB glass plate negatives, capturing the last years of the Russian Empire, survived and were purchased in 1948 by the Library of Congress. The LoC has recently digitized the negatives and made them available on-line.

Résumé

Le but de ce travail est de générer automatiquement une image couleur à partir des plaques de verre numérisées de la collection Prokudin-Gorskii, et ce, avec le minimum d'artefacts visuels possible. Pour ce faire, il vous faudra extraire les trois canaux de couleurs, les agencer un "par-dessus" l'autre, et les aligner pour que leur combinaison forme une image couleur RGB. Dans ce TP, nous allons assumer qu'un simple modèle de translation (en x,y) est suffisant pour un aligner les images correctement. Par contre, puisque les plaques de verre sont de très grandes tailles, votre procédure d'alignement devra être relativement rapide et efficace.

Overview

The goal of this assignment is to take the digitized Prokudin-Gorskii glass plate images and, using image processing techniques, automatically produce a color image with as few visual artifacts as possible. In order to do this, you will need to extract the three color channel images, place them "on top" of each other, and align them so that they form a single RGB color image. We will assume that a simple x,y translation model is sufficient for proper alignment. However, the full-size glass plate images are very large, so your alignment procedure will need to be relatively fast and efficient.

Détails

Quelques-unes des images de plaques de verre numérisées (basse et haute résolution) sont disponibles via le lien suivant. Votre programme aura une image de la plaque de verre en entrée et devra produire une image en couleur en sortie.

Votre programme devra:

  1. diviser l'image originale en trois images de même dimension;
  2. aligner les deuxième et troisième images (G et R) à la première (B). Pour chaque image, vous devez calculer le vecteur de déplacement (x,y) nécessaire à son alignement avec la première.

1. Approche à une seule échelle (55%, 35% pour les gradués)

La façon la plus facile d'aligner les images est d'effectuer une recherche exhaustive sur une fenêtre de déplacements possibles (disons [-15:15] pixels), évaluer chacun de ceux-ci en utilisant une métrique de comparaison, et conserver le déplacement avec le meilleur score. Il existe plusieurs mesures permettant d'évaluer si les images sont bien alignées. La plus simple est la norme L2, aussi connue sous le nom "somme des différences au carré" (SDC). Comme son nom l'indique, cette mesure se calcule de cette façon:

sum((image1(:)-image2(:)).^2)

Une autre mesure est la corrélation croisée normalisée (CCN), qui est tout simplement un produit scalaire entre deux vecteurs normalisés :

image1 / norm(image1) et image2 / norm(image2)

Notez que dans ce cas particulier, les images devant être alignées n'ont pas réellement les mêmes valeurs de luminosité (car elles représentent différents canaux de couleur). Une mesure plus ingénieuse pourrait alors fonctionner plus adéquatement.

2. Approche à échelles multiples (40%)

La recherche exhaustive de l'étape précédente deviendra trop lourde si le déplacement de pixels est trop grand (ce qui sera le cas pour les analyses de la plaque de verre à haute résolution). Dans ce cas, vous devrez implémenter une procédure de recherche plus rapide basée sur une pyramide d'images. Une pyramide d'image représente l'image à plusieurs échelles. Généralement, on obtient une pyramide en réduisant la taille de l'image d'un facteur de 2 à chaque étape. On obtient donc une série d'images, qui ne sont que l'image originale à l'échelle 1, 1/2, 1/4, etc. L'alignement d'images se fait de manière séquentielle à partir de l'échelle la plus petite (1/4 par exemple) jusqu'à la plus grande (1) en mettant à jour l'estimation de translation au fur et à mesure. Cela est très facile à implémenter en ajoutant des appels récursifs à votre implémentation initiale à une seule échelle.

3. Mettez-vous dans la peau de Prokudin-Gorskii! (5%)

Testez vos algorithmes sur vos propres photos! Pour ce faire, il n'est pas nécessaire d'avoir des filtres couleur. Il suffit de prendre trois photos l'une après l'autre, et d'extraire ensuite le canal "R" de la première, "G" de la deuxième, et "B" de la troisième. Vous pourrez de cette façon simuler ce que M. Prokudin-Gorskii a fait il y a plus de 100 ans avec la technologie d'aujourd'hui. Est-ce que l'alignement est aussi bon quand vous prenez trois photos avec votre appareil? Qu'arrive-t-il s'il y a des éléments dans la scène qui bougent, ou si la caméra s'est légèrement déplacée entre les photos? Expérimentez avec diverses scènes et commentez sur vos résultats.

Résumé

En résumé, votre travail sera d'implémenter un algorithme qui, étant donné trois images indépendantes représentant trois canaux de couleurs, produit une seule image couleur en sortie. Tout d'abord, en utilisant des boucles, implémentez une version simple à échelle unique faisant l'ajustement sur une fenêtre de déplacements spécifiée par l'utilisateur. Une fois cette version terminée, ajoutez une pyramide d'images pour accélérer le traitement de grandes images. Vous testerez vos algorithmes sur les images de Prokudin-Gorskii, ainsi que sur des photos que vous aurez vous-mêmes capturées. Nous vous fournissons une ébauche de code Matlab qui vous aidera à démarrer (vous n'êtes cependant pas obligés de l'utiliser).

Details

A few of the digitized glass plate images (both hi-res and low-res versions) are available through the following link. Your program will take a glass plate image as input and produce a single color image as output. The program should divide the image into three equal parts and align the second and the third parts (G and R) to the first (B). For each image, you will need to print the (x,y) displacement vector that was used to align the parts.

1. Single scale approach (55%, 35% for grads)

The easiest way to align the parts is to exhaustively search over a window of possible displacements (say [-15,15] pixels), score each one using some image matching metric, and take the displacement with the best score. There is a number of possible metrics that one could use to score how well the images match. The simplest one is just the L2 norm also known as the Sum of Squared Differences (SSD) distance which is computed as:

sum((image1(:)-image2(:)).^2)

Another is normalized cross-correlation (NCC), which is simply a dot product between two normalized vectors:

image1 / norm(image1) and image2 / norm(image2)

Note that in this particular case, the images to be matched do not actually have the same brightness values (they are different color channels), so a cleverer metric might work better.

2. Multiple scales approach (40%)

Exhaustive search will become prohibitively expensive if the pixel displacement is too large (which will be the case for high-resolution glass plate scans). In this case, you will need to implement a faster search procedure such as an image pyramid. An image pyramid represents the image at multiple scales (usually resized by a factor of 2) and the processing is done sequentially starting from the coarsest scale (smallest image) and going down the pyramid, updating your estimate as you go. It is very easy to implement by adding recursive calls to your original single-scale implementation.

3. Become Prokudin-Gorskii! (5%)

Test your algorithms on your own photos! You do not need to use color filters to do so. You only need to take three pictures, one after the other, and then extract the 'R' channel from the first, the 'G' channel from the second, and the 'B' channel from the third. This way, you can simulate what Mr. Prokudin-Gorskii has done more than 100 years ago with today's technology. Is the alignment as good with the three pictures from your own camera? What happens if there are some elements that move in the scene, or if the camera itself moves? Experiment with different scenes and comment on your results.

Summary

Your job will be to implement an algorithm that, given a 3-channel image, produces a color image as output. Implement a simple single-scale version first, using for loops, searching over a user-specified window of displacements. Next, add a coarse-to-fine pyramid speedup to handle large images. You will test your algorithms on images from the Prokudin-Gorskii collection, and on your own images as well. To help you start your assignment, we provide you with a Matlab code template.

Crédits supplémentaires

Essayez une (ou plusieurs!) de ces idées pour approfondir vos connaissances (et bonifier votre note):

  • (jusqu'à 10 points) Vos résultats, bien que photoréalistes, sont encore loin des versions restaurées manuellement disponibles sur le site Web de la Librairie du Congrès. Il faudrait ajuster les niveaux de couleurs, enlever les taches, ajouter du contraste, etc. Essayez de faire certains de ces ajustements automatiquement.
  • (jusqu'à 10 points) Trouvez une façon de détecter automatiquement les bordures pour recadrer l'image, et ainsi débarrassez-vous de certaines imperfections reliées aux bordures (indice: l'information dans les différents canaux est très similaire dans les bonnes parties, mais pas pour les bordures...).
  • (jusqu'à 10 points) pour vos propres idées à essayer (que vous aurez fait approuver par le professeur ou le dépanneur au préalable).

Bells & Whistles (Extra Credit)

Try one (or many!) of these ideas to increase your understanding on this subject (and your score):

  • (up to 10 points) Although the color images resulting from this automatic procedure will often look strikingly real, they are still a far cry from the manually restored versions available on the LoC website and from other professional photographers. Of course, make some of these adjustments automatically, without the human in the loop;
  • (up to 10 points) Devise an automatic way of cropping the border to get rid of the unalignable borders (one possible idea is that the information in the good parts of the image generally agrees across the color channels, whereas at borders it does not);
  • (up to 10 points) for bells & whistles you come up with on your own (and OK with course staff);

Trucs et indices

  • Transformez les images en valeur à virgule flottante (single ou double) avant d'effectuer des opérations sur celles-ci. Voyez im2double.
  • L'ordre des filtres de haut en bas est BGR (et non RGB)!
  • La mesure de SDC pour l'alignement automatique n'a pas à être calculée sur toute l'image.
  • Les fonctions Matlab imread, imwrite, im2double, cat, circshift, sum, and imresize devraient vous être utiles.
  • Vous ne pouvez pas utiliser la fonction Matlab imregister, car celle-ci implémente à peu près ce que vous devez faire, sans toutefois vous révéler comment elle le fait! En cas de doute sur les fonctions à utiliser, demandez-nous!

Tips and hints

  • Transform the image data in floating point value (single or double) before performing operations on them. See im2double.
  • The filter order from top to bottom is BGR, not RGB!
  • The SSD measure for automatic alignment doesn't have to be computed on the entire image.
  • You will find Matlab functions imread, imwrite, im2double, cat, circshift , sum and imresize to be helpful.
  • You may not use the imregister Matlab function since it more or less does what we need, without telling you how! If you're wondering which functions are ok to use, ask us!

Livrables

Pour ce travail, 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;
  • Les résultats de votre algorithme à une seule échelle sur toutes les images JPG contenues dans le fichier suivant. Indiquez clairement les translations calculées.
  • Les résultats de votre algorithme à échelles multiples sur toutes les images TIF contenues dans le fichier suivant. Indiquez clairement les translations calculées. Comme ces images sont grosses (.tif), montrez une image compressée (.jpg) avec un lien vers l'image taille réelle (.tif) (ou vers l'image de la taille réelle convertie en .jpg pour sauver de l'espace);
  • Les résultats de vos algorithmes sur quelques exemples de votre propre choix, pris de la collection Prokudin-Gorskii. Pour vous aider à les trouver, voici la liste de toutes les images de la librairie en format JPG (basse résolution), TIF (haute résolution). Incluez un minimum de 10 images de votre choix (5 JPG, 5 TIF, différentes de celles fournies ci-haut).
  • Les résultats de vos algorithmes sur des photos que vous aurez pris vous-mêmes. Incluez un minimum de 3 images.
  • 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.

Deliverables

For this project you must turn in both your code and a project webpage in which you will put your results and a short discussion on these. To help you get started, here's a webpage template (optional). The aesthetic appearance of the website will not be evaluated, but it is important to clearly present the information.

More precisely, the webpage should contain:

  • A short description of the project and your approach;
  • The results of your single scale algorithm on all the JPG images in this file. Clearly indicate the offsets you calculated.
  • The results of your multiple scales algorithm on all the TIF images in this file. Clearly indicate the offsets you calculated. Since these images are quite large, display a .jpg image with a link to your full size .tif (to a full size .jpg version of the .tif file to save space);
  • The results of your algorithm on a few examples of your own choosing, downloaded from the Prokudin-Gorskii collection. Here is a list of all the images of the library in JPG (low resolution) and in TIF (high resolution). Include at least 10 images (5 JPG, 5 TIF, different from those we provided you above).
  • The results of your algorithms on photos you took yourself. Include at least 3 such results.
  • If you encounter problems on some images, describe these problems and tell us own you tried to solve them;
  • If your algorithm failed to align any image, briefly explain why it does;
  • Describe any bells and whistles you implemented. For maximum credit, show before and after images.

Évaluation

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

  • 55 points (35 pour les étudiants gradués) pour l'implémentation à une seule échelle avec des résultats concluants sur des images basse résolution;
  • 40 points pour la version avec la pyramide multi-échelle qui fonctionne avec des images de grandes tailles;
  • 5 points pour des résultats sur vos propres photos;
  • (N pts) pour les crédits supplémentaire. Rappel: les étudiants gradués doivent livrer au moins 20 pts de crédits supplémentaires.

Si vous obtenez une note supérieure à 100%, vos points supplémentaires seront comptabilisés sur la note finale!

Evaluation

This assignment is evaluated on 100 points, as follows:

  • 55 points (35 for the graduate students) for a single-scale implementation with successful results on low-res images;
  • 40 points for a multiscale pyramid version that works on the large images;
  • 5 points for results on your own photos;
  • (N pts) for any bells and/or whistles you've added in. Reminder: graduate students must do at least 20 pts worth of bells and whistles.

If you get more than 100%, your extra points will be added on to your total score when computing your final grade!

Remise

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

  • Votre rapport en format HTML dans un dossier tp1/web. Vos images doivent être dans un dossier tp1/web/images.
  • Votre page principale doit être tp1/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 tp1/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 tp1.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 tp1.zip n'excède pas 50MB. Convertissez les fichiers TIF en JPG pour réduire leur taille, si nécessaire.

Handing in procedure

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

  • Your report in an HTML format inside a folder named tp1/web. Your images for this web page should be inside a folder named tp1/web/images.
  • Your main page has to be tp1/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 tp1/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 (tp1.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. Be sure that your tp1.zip file size does not exceed 50MB. Convert TIF files to JPG to reduce file size if needed.

Liens importants

Important links

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 the original version of this assignment!

Retour à la page web du cours.

Back to the class webpage.