Petit cours d'histoire

Sergei Mikhailovich Prokudin-Gorskii (1863-1944) était un homme en avance sur son temps. En 1907, convaincu que la photographie couleur était la voie de l'avenir, il a obtenu une permission spéciale du Tsar (le dernier, d'ailleurs) pour traverser le vaste empire russe et de prendre des photographies couleurs de tout ce qu'il voyait. Il a photographié des gens, des édifices, des paysages, des chemins de fer, des ponts... pour ainsi produire des milliers de photos en couleur. Tout ça avant que la photographie couleur n'existe! 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. Comme il était impossible d'imprimer ces photos par la suite, il s'imaginait des projecteurs spéciaux installés dans des locaux de classe «multimédia» où les enfants russes pourraient en apprendre plus sur leur vaste pays. Hélas, ses plans ne furent 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 capturés par M. Prokudin-Gorskii survécurent 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.

Brief history lesson

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 online.

Survol

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'artifacts visuels possible. Pour ce faire, il vous faudra extraire les trois canaux de couleurs, les chevaucher l'un «par-dessus» l'autre, et les aligner pour que leur combinaison forme une image couleur en RGB. Dans ce TP, nous ferons l'hypothèse qu'un simple modèle de translation (en x,y) est suffisant pour aligner les images correctement. Par contre, puisque les plaques de verre numérisées ont une très grande résolution, votre procédure d'alignement devra être 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. To do so, 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 translation model $(x,y)$ is sufficient for proper alignment. However, the full-size glass plate images are very large, so your alignment procedure will need to be fast and efficient.

Détails

Votre programme devra prendre une image de la plaque de verre en entrée et devra retourner l'image couleur correspondante 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)$ qui produit le «meilleur» alignement avec la première.

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

Tout d'abord, vous devez implémenter une approche simple qui consiste à essayer toutes les combinaisons de déplacements en $x$ et $y$, et de choisir le meilleur. Pour ce faire, définissez tout d'abord une plage de déplacements possibles (par exemple $[-15, 15]$ pixels et $x$ et en $y$). Pour chaque déplacement:

1. appliquez le déplacement à l'image R (et G);
2. comparez l'image R (et G) déplacée avec l'image B avec une métrique de comparaison et ainsi calculer un «score»;
3. stockez le score pour ce déplacement.

Quand tous les déplacements ont un score, conservez celui qui a le score minimal.

Il existe plusieurs métriques de comparaison permettant d'évaluer si les images sont bien alignées. La plus simple est la norme L2, ou «somme des différences au carré» (SDC). Comme son nom l'indique, cette mesure se calcule de cette façon entre deux images $\mathbf{I}_1$ et $\mathbf{I}_2$: $$ \text{SDC} = \sum_i \sum_j \left( \mathbf{I}_1(i,j) - \mathbf{I}_2(i,j) \right)^2 $$ Vous êtes encouragés à expérimenter avec des mesures plus ingénieuses! Par exemple, vous pouvez expérimenter avec la corrélation croisée normalisée (normxcorr2 dans Matlab ou Python).

2. Approche à échelles multiples (40%)

La recherche exhaustive de l'étape précédente devient rapidement trop lourde si le déplacement de pixels est trop grand. En effet, un plage de déplacements de $[-15, 15]$ (ok pour des images à faible résolution) nécessite l'évaluation de $31^2$ possibilités. Cependant, une image à plus haute résolution (par exemple, 10 fois plus grande) nécessiterait une plage de recherche de $[-150, 150]$, ce qui équivaudrait à $301^2$ possibilités!

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 représentent 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 (bien que si vous en avez, n'hésitez pas à expérimenter!). 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.

Details

Your program will take a glass plate image as input and produce a single color image as output.

The program should:

1. divide the image into three equal parts;
2. align the second and the third parts (G and R) to the first (B). For each image, you will need to compute the $(x,y)$ displacement vector that was used to align the parts.

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

First, you will have to implement a simple approach, which is to try all possible displacements in $x$ and $y$, and to choose the best. To do so, first define a window of possible displacements (say $[-15,15]$ pixels in $x$ and $y$). For each displacement:

1. apply the displacement to the R (and G) image;
2. compare the translated R (and G) image to the B image using a comparison metric and compute a "score";
3. store the score for this displacement.

When you have computed a score for all the displacements in the window, keep the one with minimum 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 between images $\mathbf{I}_1$ and $\mathbf{I}_2$ as: $$ \text{SSD} = \sum_i \sum_j \left( \mathbf{I}_1(i,j) - \mathbf{I}_2(i,j) \right)^2 $$ Another is normalized cross-correlation (NCC), which is simply a dot product between two normalized vectors (see the Matlab function normxcorr2, available in Python as well). You are encouraged to experiment with other, cleverer metrics!

2. Multiscale 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). Indeed, a displacement window of $[-15,15]$ (appropriate for low resolution images) generates $31^2$ possibilities. However, a high resolution image (say, 10 times bigger) would require a displacement window of $[-150,150]$, which would generate $301^2$ possibilities!

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 did 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.

Crédits supplémentaires

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

• (jusqu'à 10%) Vos résultats, bien que photoréalistes, ne seront probablement pas aussi beaux que ceux restaurés manuellement sur le site Web de la Librairie du Congrès. Il faudrait ajuster les niveaux de couleurs, enlever les taches, ajouter du contraste, etc. Appliquez certains de ces ajustements automatiquement. Comparez les résultats avant/après vos améliorations.
• (jusqu'à 10%) 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 parties "valides" des images, mais pas pour les bordures...).
• (jusqu'à 5%) Plutôt que de les calculer directement sur les valeurs de pixels en RGB, les métriques proposées plus haut peuvent aussi être calculées sur les gradients de l'image, ou sur les arêtes. Expérimentez avec ces options et comparez avec le calcul sur les valeurs RGB.
• (jusqu'à 5%) Effectuez une recherche sur l'espace des rotations et facteurs d'échelle, en plus de la translation proposée ci-haut. Cela prendra plus de temps, mais pourra probablement vous permettre d'atteindre de meilleurs résultats. Comparez vos résultats avec la translation seulement.
• (jusqu'à 10%) pour vos propres idées à essayer (que vous aurez fait approuver par le professeur au préalable).

Bells & Whistles for extra credit

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

• (up to 10%) 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%) 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 5%) Instead of computing the metrics on the RGB pixels, they can also be computed on transformations of the image (e.g. gradients, edges, etc.). Experiment with these options and compare with the original solution.
• (up to 5%) Perform a search over the space of rotations and scaling factors (in addition to translation as proposed above). This will be more expensive to compute, but will likely allow you to obtain better results. Compare to results obtained with translation only.
• (up to 10%) for ideas you come up with on your own (get it approved by the course professor first);

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 B-G-R (et non R-G-B)!
• Les métriques pour calculer les scores n'ont pas à être calculées sur toute l'image.
• Les fonctions Matlab imread, imwrite, imshow, im2double, cat, circshift, sum, and imresize devraient vous être utiles.
• Les fonctions Python imread, imsave, imshow de la librarie scikit-image, de même que roll, dstack de la librarie numpy devraient l'être également.

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 B-G-R, not R-G-B!
• The metrics to score each displacement do not 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 will find Python functions imread, imsave, imshow from the scikit-image library, as well as roll, dstack from the numpy library to be helpful.

Livrables et pondération

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.

La page doit contenir:

• Une brève description du projet et de votre approche;
• (55%, 35% pour gradués) Les résultats de votre algorithme à une seule échelle sur toutes les images JPG contenues dans le fichier suivant.
• (40%) Les résultats de votre algorithme à échelles multiples sur des images à haute résolution. Comme ces images sont grosses, affichez une image de taille plus faible (.jpg) avec un lien vers l'image de la taille réelle convertie en .jpg pour sauver de l'espace. Montrez les résultats pour:
  • toutes les images TIF contenues dans le fichier suivant.
  • un minimum de 10 images de votre propre choix, pris de la collection Prokudin-Gorskii (et différentes de celles fournies dans le fichier ci-haut). Pour vous aider à les trouver, voici la liste de toutes les images de la librairie en format TIF (haute résolution).
• (5%) Les résultats de vos algorithmes sur des photos que vous aurez pris vous-mêmes. Incluez un minimum de 3 images personnelles.
• Si vous avez rencontré des problèmes sur certaines images, décrivez ces problèmes et expliquez comment vous avez tenté de les résoudre;
• Si vos algorithmes échouent sur certaines images, décrivez les problèmes et expliquez pourquoi ils surviennent selon vous;
• (N%) Décrivez tous vos crédits supplémentaires. Affichez clairement les images avant et après.

Deliverables and grading

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;
• (55%, 35% for grads) The results of your single scale algorithm on all the JPG images in this file.
• (40%) The results of your multiscale algorithm on high resolution images. Since these images are quite large, display a JPG image with a link to a full size JPG version of the TIF file to save space. Show results for:
  • all the TIF images in this file.
  • a minimum of 10 images of your own choosing, downloaded from the Prokudin-Gorskii collection (and different than those in the file above). Here is a list of all the images of the library in TIF (high resolution).
• (5%) 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 how you tried to solve them;
• If your algorithm failed to align any image, briefly explain why it does;
• (N%) Describe all of your bells and whistles. Clearly show before and after images.

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.

Identifiez clairement les principales «portes d'entrée» de votre code (ex: main, main_multiechelle, etc.). Cela permettra à votre correcteur de s'y retrouver plus facilement!

Finalement, veuillez téléverser votre fichier tp1.zip sur le portail des cours 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!

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.

Clearly identify the main "access points" to your code (ex: main, main_multiscale, etc.). This will facilitate grading!

Finally, you should upload this file (tp1.zip) on the "portail des cours" 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!

Liens

• Ébauche de page web;
• Ébauche de code Matlab pour vous aider à démarrer (vous n'êtes pas obligés de l'utiliser);
• Ébauche de code Python pour vous aider à démarrer (vous n'êtes pas obligés de l'utiliser);
• Images sur lesquelles vous devez obligatoirement tester vos algorithmes (JPG = basse résolution, TIF = haute résolution);
• Liste de toutes les images de la librarie en format JPG (basse résolution), TIF (haute résolution).

Links

• Webpage template;
• Matlab code template to help get you started (you don't have to use it);
• Python code template to help you get started (you don't have to use it either);
• Images on which you are required to test your algorithms (JPG = low resolution, TIF = high resolution);
• List of all the library images in format JPG (low resolution), TIF (haute resolution).

Remerciements

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

Thanks

Many thanks to Alyosha Efros for the original version of this assignment!