TP1: Colorisation de l'Empire Russe

Résumé

Ce travail a pour but d'implémenter un algorithme d'alignement d'images RGB issues de la collection Prokudin-Gorskii. Quatre méthodes d'alignement utilisant trois métriques différentes sont présentées ci-dessous. Des algorithmes de découpage et de traitement d'images implémentés sont présentés par la suite. Enfin, les résultats sont présentés à la fin de cette page avec une analyse des performances des algorithmes.

Méthode

La méthode principale d'alignement consiste à prendre chacun des canaux de couleur de l'image choisie et aligner les canaux vert et bleu avec le canal rouge. L'algorithme teste itérativement t*t alignements (translations x,y autour de 0,0) différents et retourne l'alignement jugé optimal selon les contraintes imposées. L'alignement optimal issu du traitement est celui optimisant la valeur de la métrique utilisée pour évaluer la qualité de l'alignement entre deux canaux. À cet effet, les bordures des images sont ignorées lors des calculs pour les métriques. La largeur de ces bordures est choisie manuellement afin de ne pas tenir compte des zones invalides dans l'image (lignes noires ou blanches, brûlures, etc.). Cette méthode peut être utilisée aussi bien sur une simple image RGB que sur une pyramide d'images RGB afin d'alléger la quantité de calculs à effectuer. C'est d'ailleurs ce qui est fait dans la deuxième section de ce travail.

Afin de tenter d'optimiser les alignements, des options ont été ajoutées à l'algorithme. Une première option consiste à égaliser la moyenne des canaux R,G et B entre eux avant de tenter d'aligner les canaux. Bien que les canaux RGB soient corrélés, ceci ne garantit pas que la valeur d'un pixel en R équivaut à ses valeurs en G et B. Par exemple, un objet blanc collé sur un objet rouge pourrait être facilement segmenté dans les canaux G et B, mais plus difficilement dans le canal R. À grande échelle, ceci pourrait engendrer des alignements suboptimaux avec certaines métriques sensibles à l'écart entre deux valeurs, par exemple la somme des différences au carré (SDC). Les moyennes sont égalées à la moyenne la plus faible parmi les trois canaux afin d'éviter de saturer les pixels.

La deuxième option implémentée consiste aussi à traiter l'image avant de déterminer le meilleur alignement. Ici, une détection d'arêtes (Sobel) est effectuée sur chacun des canaux. Les images binaires résultantes sont par la suite utilisées pour déterminer l'alignement optimal, plutôt que d'utiliser directement les canaux. Puisque les erreurs d'alignement sont surtout visibles aux endroits contenant des arêtes, cette option permet de mettre l'accent sur ces zones, plutôt que juger également toute l'image RGB.

Métriques

SDC

Cette métrique représente simplement la somme des différences au carré entre les pixels du canal de référence (R) et ceux du canal étant en train d'être aligné. L'avantage de cette métrique est qu'elle pénalise davantage pour des erreurs importantes que pour de faibles erreurs.

CCN

Cette métrique représente le niveau de similarité ([-1,1]) entre le canal de référence (R) et celui en train d'être aligné. Plus la métrique est élevée, meilleur est l'alignement. L'avantage de cette métrique est qu'elle donne une mesure basée autour du contenu de l'image plutôt que sur ses pixels individuels.

SSIM

Cette dernière métrique représente aussi le niveau de similarité entre deux canaux. L'avantage de cette métrique (selon ses auteurs) est qu'elle représente une mesure de similarité entre deux images basées autour de la structure de l'image plutôt que des pixels. Dès lors, elle serait plus représentative du processus d'évaluation du système de vision humaine. Cette spécificité est importante ici, puisqu'un mauvais alignement est très facile à voir autour des régions d'intérêt dans l'image (objets, bâtiments, etc.).

Post-traitements

Découpage automatique

Une fois les canaux alignés, les bordures de l'image sont rognées une première fois afin de ne garder que les zones où les trois canaux se superposent (ex.: une translation de 15 pixels vers la droite du canal vert crée une zone invalide de 15 pixels à la bordure gauche de l'image).

Par la suite, un deuxième rognage est effectué sur les bordures restantes. Pour déterminer l'ampleur du rognage, la corrélation entre les colonnes de chaque canal est calculée et ensuite seuillée (un seuil de 0.45 semble être optimal pour les images testées). Un filtre médian est ensuite appliqué sur les résultats pour ne garder que le début de la zone "valide" dans l'image. L'indice maximal entre les trois comparaisons (R-G,R-B,B-G) indiquant le début de la zone valide de l'image est considéré comme étant le nombre de colonnes à rogner à gauche. L'indice minimal à partir de la droite correspond quant à lui au début de la zone valide de l'image pour le côté droit. Ces indices sont enfin comparés à une valeur maximale de colonne à rogner afin de ne pas rogner une section trop importante dans l'image. Si les valeurs dépassent la valeur maximale, la valeur maximale sera utilisée pour le rognage. Une fois le rognage effectué sur les colonnes, le même processus est effectué sur les lignes de l'image.

Le traitement est effectué sur les colonnes avant les lignes puisque les colonnes invalides sont plus faciles à détecter dans les images pour ce travail. La limite est fixée empiriquement à environ 10% du nombre de lignes/colonnes dans l'image. Sans cette limite, les régions sans détails sont souvent détectées comme des zones invalides. Pour chaque image alignée dans ce travail, leur version rognée est affichée à ses côtés.

Couleurs

Les algorithmes suivants ont été testés et implémentés: équilibre des blancs(monde gris selon R/G/B, monde blanc avec ou sans canal G), égalisation d'histogramme (L de L*a*b*, V de HSV), modification de la saturation (S de HSV), tone mapping (RGB^gamma,L^gamma). L'hypothèse du monde blanc sans le canal G provient du fait que les images ont souvent des teintes rougeâtre ou bleuâtre, mais très rarement verdâtre. Dès lors, modifier ce canal ne devrait pas avoir un grand impact. Une comparaison des algorithmes est affichée dans la section résultats. De plus, pour chaque image alignée, l'image traitée jugée optimale est affichée à la droite de l'image alignée et rognée.

Résultats

Cette section présente les meilleurs résultats obtenus pour chacune des images testées.

Approche monoéchelle



Translations optimales: G = [-6,1]; B = [-10,0].
Méthode utlisée: Arêtes, égalisation, SDC, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%
Post-traitement: Égalisation selon monde blanc (3 canaux).

Translations optimales: G = [-3,-2]; B = [-5,-5].
Méthode utlisée: SDC seulement, image utilisée = 90%.
Découpage: Lim - 10%,Seuil - 50%
Post-traitement: Égalisation selon monde blanc (R et B seulement).

Translations optimales: G = [-6,0]; B = [-12,0].
Méthode utlisée: SDC seulement, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 50%
Post-traitement: Monde gris selon canal G.

Translations optimales: G = [-3,-1]; B = [-5,-3].
Méthode utlisée: SDC seulement, image utilisée = 90%.
Découpage: Lim - 10%,Seuil - 50%
Post-traitement: Équilibrage d'histogramme pour V (HSV) avec alpha = 0.2. Augmentation de la saturation de 20%.

Translations optimales: G = [-3,1]; B = [-6,1].
Méthode utlisée: Arêtes, égalisation, SDC, image utilisée = 90%.
Découpage: Lim - 8%,Seuil - 50%
Post-traitement: Monde gris (canal G comme référence).

Translations optimales: G = [-12,1]; B = [-13,2].
Méthode utlisée: Égalisation, CCN, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%
Post-traitement: Monde gris (canal G comme référence).

Translations optimales: G = [-3,0]; B = [-4,-2].
Méthode utlisée: SDC seulement, image utilisée = 90%.
Découpage: Lim - 9%,Seuil - 40%
Post-traitement: Tone mapping L*a*b* (L^0.98).

Translations optimales: G = [-6,0]; B = [-12,-1].
Méthode utlisée: SDC seulement, image utilisée = 90%.
Découpage: Lim - 10%,Seuil - 45%
Post-traitement: Équilibrage d'histogramme pour V (HSV) avec alpha = 0.2. Augmentation de la saturation de 20%.

Translations optimales: G = [-8,-2]; B = [-14,-4].
Méthode utlisée: SDC seulement, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 55%
Post-traitement: Égalisation selon monde blanc (3 canaux).

Approche multiéchelle



Translations optimales: G = [-52,-18]; B = [-92,-33].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%
Post-traitement: Égalisation selon monde blanc (3 canaux).

Translations optimales: G = [-52,-18]; B = [-92,-33].
Méthode utlisée: 5 étages (16/8/4/2/1),arêtes, SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 7%,Seuil - 45%
Post-traitement: Égalisation d'histogramme L (L*a*b*). Alpha = 0.2.

Translations optimales: G = [-17,-12]; B = [-49,-36].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%
Post-traitement: Égalisation d'histogramme L (L*a*b*). Alpha = 0.2.

Translations optimales: G = [-44,-27]; B = [-85,-28].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 8%,Seuil - 60%
Post-traitement: Égalisation selon monde blanc (R et B seulement).

Translations optimales: G = [-34,-8]; B = [-50,-14].
Méthode utlisée: 5 étages (16/8/4/2/1), SSIM, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 10%,Seuil - 60%
Post-traitement: Monde gris avec R comme référence.

Translations optimales: G = [-67-8]; B = [-125,-33].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 50%
Post-traitement: Égalisation d'histogramme L (L*a*b*). Alpha = 0.2.

Translations optimales: G = [-26,-1]; B = [-42,-4].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 60%
Post-traitement: Tone mapping L*a*b* (L^0.98).

Translations optimales: G = [-26,-8]; B = [-11,-17].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 7%,Seuil - 40%
Post-traitement: Égalisation d'histogramme L (L*a*b*). Alpha = 0.2.

Translations optimales: G = [-47,-15]; B = [-71,-33].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 8%,Seuil - 45%
Post-traitement: Égalisation d'histogramme L (L*a*b*). Alpha = 0.2.

00193u.tif
Translations optimales: G = [-64,-4]; B = [-89,-12].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%
Post-traitement: Égalisation selon monde gris avec R comme référence, suivi d'un tonemapping de L en L*a*b* (L^0.98).

00282u.tif
Translations optimales: G = [-89,3]; B = [-124,2].
Méthode utlisée: 5 étages (16/8/4/2/1), CCN, image utilisée = 90%.
Découpage: Lim - 9%,Seuil - 65%
Post-traitement: Égalisation selon monde gris avec R comme référence.

00323u.tif
Translations optimales: G = [-84,-8]; B = [-116,-16].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 65%
Post-traitement: Égalisation selon monde gris avec G comme référence.

00402u.tif
Translations optimales: G = [-74,-6]; B = [-152,-27].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 8.2%,Seuil - 65%
Post-traitement: Égalisation selon monde blanc (3 canaux).

00481u.tif
Translations optimales: G = [-54,-6]; B = [-91,-12].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 6%,Seuil - 65%
Post-traitement: Égalisation d'histogramme L (L*a*b*). Alpha = 0.2.

00510u.tif
Translations optimales: G = [-70,20]; B = [-117,11].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%
Post-traitement: Tone mapping RGB (RGB^0.9).

00826u.tif
Translations optimales: G = [-45,8]; B = [-90,-3].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 10%,Seuil - 65%
Post-traitement: Égalisation d'histogramme L (L*a*b*). Alpha = 0.2.

01207u.tif
Translations optimales: G = [-35,4]; B = [-65,-12].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%
Post-traitement: Égalisation selon monde blanc (canaux R et B seulement).

01285u.tif
Translations optimales: G = [-42,6]; B = [-80,-15].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, arêtes, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%
Post-traitement: Égalisation selon monde blanc (3 canaux).

01709u.tif
Translations optimales: G = [-59,11]; B = [-120,16].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 70%
Post-traitement: Égalisation selon monde blanc (3 canaux).

Images personnelles

Gauche: Trois canaux RGB de trois images différentes. Droite: Image alignée et rognée

Translations optimales: G = [-10,18]; B = [-49,101].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%

Translations optimales: G = [14,6]; B = [-2,-20].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%

Translations optimales: G = [-16,15]; B = [-11,28].
Méthode utlisée: 5 étages (16/8/4/2/1), SDC, égalisation, image utilisée = 90%.
Découpage: Lim - 15%,Seuil - 45%

Méthodes possible

Les résultats obtenus avec l'image 00106v.jpg avec toutes les méthodes monoéchelles sont résumées dans le tableau ci-dessous. Le résultat optimal est reproduit plus bas.
Métrique [égalisation,arêtes] G =[ty,tx] B =[ty,tx] Temps exec.
SDC [1,1] [-6,1] [-10,0] 1sec.
SDC [1,0] [-5,1] [-9,1] 1sec.
SDC [0,1] [-6,1] [-10,0] 1sec.
SDC [0,0] [-5,1] [-9,1] 1sec.
CCN [1,1] [-6,1] [-10,0] 24sec.
CCN [1,0] [-5,1] [-9,1] 24sec.
CCN [0,1] [-6,1] [-10,0] 25sec.
CCN [0,0] [-5,1] [-9,1] 25sec.
SSIM [1,1] [-6,1] [-9,0] 23sec.
SSIM [1,0] [-5,2] [-9,1] 20sec.
SSIM [0,1] [-6,1] [-9,0] 17sec.
SSIM [0,0] [-5,2] [-9,1] 17sec.

Post-traitements possibles

Les résultats obtenus avec les divers post-traitements implémentés sont affichés ci-dessous avec l'image 01657v.jpg.

Image sans post-traitement.

Image traitée selon hypothèse de monde gris selon canal de référence R,G et B.

Image traitée selon hypothèse de monde blanc (gauche: 3 canaux; droite: R et B seulement).

Image traitée en égalisant l'histogramme de L (L*a*b*) avec un alpha de 20%,50% et 80%.

Image traitée en égalisant l'histogramme de V (HSV) avec un alpha de 20%,50% et 80% et en amplifiant la saturation de 20%.

Image traitée en effectuant du tone mapping sur les canaux RGB avec un gamma de 0.8,0.9 et 1.2 (RGB^gamma).

Image traitée en effectuant du tone mapping sur le canal L (L*a*b*) avec un gamma de 0.92,0.98 et 1.05 (L^gamma).

Analyse

Dans l'ensemble, égaliser les moyennes des couleurs dans les images avant d'effectuer l'alignement ne donne pas de meilleures performances, compte tenu que les images n'ont généralement pas de canal prédominant au niveau de l'intensité. Cela dit, la détection d'arêtes, elle, permet d'obtenir de meilleurs alignements, mais ne réduit l'erreur que d'environ 1-2 pixels par rapport à l'alignement effectué sans détection. Cette diminution de l'erreur est davantage négligeable lorsque les images ont 12Mpixels. Bien sûr, utiliser des détecteurs plus performants (voire, utiliser SIFT) permettrait de faire des alignements plus précis, mais il n'y a pas d'intérêt ici, considérant que les résultats sont déjà satisfaisants.

En ce qui a trait aux métriques, les CCN et SSIM donnent généralement de meilleurs résultats (de l'ordre de quelques pixels seulement), mais prennent beaucoup plus de temps à calculer (voir tableau). Dès lors, il est difficile de justifier leur utilisation, puisque la métrique SDC donne déjà de bons résultats.

Ironiquement, puisque l'algorithme "de base" est déjà très performant, il est difficile de quantifier les avantages des méthodes plus complexes par rapport à ce dernier. Cela dit, il existe une modification qui permettrait d'obtenir de meilleurs résultats. En effet, pour faciliter l'alignement, il faudrait pouvoir découper les images au départ pour enlever les zones invalides de l'images et ce, même avant de découper l'image en trois pour recréer une image couleur. Ceci nous permettrait de garder plus d'informations dans l'image, la segmentation étant plus précise. Par exemple, le problème des mollets de l'homme dans la première image se retrouvant au haut de l'image n'existerait pas. Malgré tout, grâce à l'algorithme de rognage implémenté, les résultats en sortie, ayant très peu d'artéfacts en contour, ressemblent beaucoup à de vraies photos.

Pour ce qui est des images prises avec mon cellulaire, on peut remarquer que les alignements ne sont pas tout à fait justes à certains endroits. Ceci est surtout dû au mouvement entre chaque prise de photo. Dès lors, la perspective change et la scène change légèrement. Pour régler ce problème, on peut trouver l'homoographie permettant de passer d'une image à l'autre afin de rétablir la bonne perspective. Sinon, déterminer une matrice de rotation entre les deux images peut aussi être utile dans le cas où seule l'orientation de la caméra a été modifiée entre deux photos.

Enfin, concernant les méthodes de traitement d'images implémentées, celles les plus efficaces pour les images testées sont l'égalisation avec l'hypothèse d'un monde blanc et l'égalisation d'histogramme appliqué sur le canal L de L*a*b*. On remarque aussi que lorsque l'image originale a un fond de couleur dominant, comme rouge pour 00193u.tif, le traitement le plus simple pour diminuer cet effet est d'égaliser les canaux RGB avec l'hypothèse d'un monde gris. En égalisant avec R comme référence, on vient cacher le fond rouge. Il aurait été intéressant de tester un algorithme d'égalisation automatique permettant de diminuer ces effets de teinte lorsqu'un des canaux RGB est jugé trop différent des autres. Il aurait aussi été intéressant de tester des algorithmes permettant de cacher les artéfacts visuels hors contours dans les images. En somme, bien que les méthodes de modification implémentées sont simples, on remarque que leurs effets peuvent être tout de même impressionnants.