TP1 - Photographie algorithmique

L'objectif du présent TP est de créer un programme qui:

1. Sépare une image représentant les composantes RGB en trois
2. Aligne les trois composantes
3. Combine les composantes pour en faire une image couleur

Quelques approches seront explorées

• Une recherche force brute à une seule échelle dans le domaine spacial
• Une recherche force brute à une plusieurs échelles dans le domaine spacial
• L'alignement par recherche de descripteurs BRIEF (Bonus)
• L'alignement par recherche de descripteurs ORB (Bonus)
• L'alignement dans le domaine des fréquences par corrélation croisée (Bonus)

Deux autres améliorations automatiques aussi sont testées, soit:

• Le recradrage automatique
• L'amélioration des contrastes et de la balance des couleurs automatique

Description des techniques

Force brute à échelle simple

Cette technique consiste simplement à faire glisser le canal vert sur le canal blue et à conserver l'image le résultat ayant la plus petite erreur. La même opération est répétée pour le canal rouge. Le désavantage de cette technique est la lenteur et sa précision dépend de la façon utilisée pour calculer l'erreur. Dans ce travail, deux méthodes de de calcul d'erreur ont été testées, soit la somme des différences au carré (SDC) et Structural Similarity (SSIM)

Force brute à échelle multiple

Cette technique est une amélioration de la précédante. Plutôt que de refaire un lourd calcul d'erreur à chaque déplacement de un pixel, une "pyramide" d'image est construite. L'image est rapetissé par un facteur deux jusqu'à atteindre une certaine taille. En commençant par la plus petite image, les huit déplacements de un pixel sont testés en plus de la position initiale. Ainsi, une image réduite d'un facteur 32 dont le décalage mesuré est -1, 0 signifie que le déplacement sur l'image non réduite est de -32, 0. Chaque étape centre l'alignement autour de la valeur trouvée sur l'image précédante. Cette algorithme est donc une recherche binaire.

BRIEF

Cette technique détecte des coins sur chacune des images à aligner puis leur attribut une signature. En associant les signatures, il est possible de déterminer le déplacement entre chaque élément de la pair.

ORB

ORB est une version modifiée de BRIEF qui supporte aussi la détection des rotations.

Corrélation croisée

En faisant la corrélation croisée entre les deux images, une troisième image est obtenue représentant l'erreur avec une directionnalitée. L'avantage de cette technique est qu'elle est supposée être rapide puisqu'elle est basée sur une FFT. Un autre avantage est qu'il est possible d'obtenir un résultat plus précis que le pixel en suréchantillonnant la DFT.

Recadrage automatique

Chacune des canaux des images possèdent des bordures de taille inégales. Le but ici est de détecter automatiquement le mieux possible où couper l'image final. Des compromis doivent être fait étant donné qu'après l'alignement, un bord d'image peut contenir de l'information dans un des canaux et rien dans un autre.

Amélioration des contrastes et de la balance des couleurs automatique

Plusieurs de ces images possèdent un contraste insatisfesant, une balance des blancs incorrect ou une saturation insuffisante. L'objectif est de corrigé automatique ces défaults.

Implémentation

Logiciels utilisés

L'entièreté de l'expérience est faite avec Python 3. La librarie numpy est utilisé pour représenté l'image et pour fournir des fonctions hautes performances de calcul mathématique. La librarie Scikit Image est aussi utilisé pour fournir des fonctions propres au traitement d'images.

Dataset

Les expériences ont lieu sur trois type d'image, les originals en basse résolution compressé jpeg, les originals haute résolution non-compressé et trois photos personnels

Pour les photos personnels, dans chaque cas, trois images sont prises avec un téléphone Sony Xperia Z3 Compact. Celui-ci possède une résolution encore plus grande que celle des images fournies, mais produit beaucoup plus de bruit et moins de contraste. Le canal B est extrait de la première image, le canal G de la deuxième et le canal R de la troisième. La première photo est un sujet humain et donc en plus du mouvement de la caméra, une partie de l'image aussi bouge. La deuxième photo est identique mais sans sujet sur la photo. Cette image possède beaucoup de détails fins et peu de détails grossiers. La dernière photo représente le cas inverse, c'est à dire qu'elle présente plusieurs objets avec des arrêtes bien définies.

Méthode simple

1. L'image est découpée en ses trois composantes
2. Le canal vert est superposé sur le bleu
3. L'image est coupée de chaque côté de 10%
4. La SDC est calculée
5. Le canal vert est décalé de 1px et l'étape 1 est recommencée
6. L'opération est répétée pour tous les décalages possible de +/- 30 px de haut en bas et de gauche à droite
7. L'opération est répétée pour le canal rouge

Méthode par pyramide

1. L'image est découpée en ses trois composantes
2. Le canal vert est superposé sur le bleu
3. L'image est rapetissée d'un facteur deux jusqu'à atteindre 2^12 pixels
4. L'image est coupée de chaque côté de 10%
5. La SDC est calculée
6. Le canal vert est décalé de 1px et l'étape 1 est recommencée
7. L'opération est répétée pour tous les décalages possible de +/- 1 px de haut en bas et de gauche à droite
8. L'opération est recommencée pour l'image immédiatement plus grande en la centrant autour des valeurs précédantes trouvée multipliée par deux tant que l'image de taille originale n'est pas obtenue
9. L'opération est répétée pour le canal rouge

BRIEF

1. L'image est découpée en ses trois composantes
2. Les canaux bleu et vert sont coupés de chaque côté de 10%
3. Le détecteur de coin Harris est appliquée sur ces canaux
4. BRIEF est appliqué sur chaque coin pour leur attribuer une signature
5. Les descripteurs des deux canaux sont associés en pair
6. Un vecteur de déplacement est calculé
7. Les cas de déplacement extrèmes sont filtrés
8. Un filtre de RANSAC ou médianne détermine la bonne valeur
9. L'opération est répétée pour le canal rouge

ORB

ORB fonctionne de la même façon que BRIEF à l'exception qu'il possède son propre détecteur de point d'intérêt (au lieu de Harris).

Corrélation croisée

L'algorithme est entièrement implémenté dans Scikit Image selon le papier suivant: Manuel Guizar-Sicairos, Samuel T. Thurman, and James R. Fienup, “Efficient subpixel image registration algorithms,” Optics Letters 33, 156-158 (2008). Un paramètre permet de suréchantillonner la DFT et ainsi avoir une précision sous l'ordre du pixel.

Recadrage automatique

En commencant de chaque côté, la variance d'un pixel du bord est prise entre les trois canaux. Si elle est très grande ou très petite, il s'agit d'une bordure et l'algorithme continue. Pour éviter qu'une imperfection de l'image arrêt l'algorithme prématurément, la condition est faite sur quatre points. Par exemple pour le côté gauche de l'image, à la première ittération, les points choisis sont ceux situé au tier et au deux tiers de la hauteur sur la première et la deuxième colonne.

Amélioration des contrastes et de la balance des couleurs automatique

La fonction equalize_adapthist de Scikit image est utilisée. Il s'agit de l'algorithme d'égalisation par histogramme vu en classe, mais celui-ci est appliqué séparemment sur plusieurs régions de l'image de façon à fournir un meilleur contraste local.

Résultats

En général le résultat le plus précis est obtenue avec la technique par pyramide ou par BRIEF. Ce sont aussi les deux techniques les plus rapides. Il est intéressant de voir que même si la technique par pyramide tente de minimiser l'erreur, la corrélation croisée atteint des valeurs plus basses. L'erreur obtenue par la SDC n'est pas très représentative de la qualité de l'image perçue par l'oeil humain puisque la corrélation croisée ne fonctionne visiblement pas dans ce cas d'utilisation. ORB fonctionne, mais produit un résultat généralement de moins bonne qualité que la pyramide et BRIEF. Cela est probablement du au grand nombre de paramètre entrant dans l'algorithme, un travail plus poussé pourrait probablement le rendre aussi performant que BRIEF.

Le découpage automatique fonctionne bien, mais des compromis doivent être faits. Ainsi parfois une bordure demeure car un des canal possède de l'information à cet endroit.

La seule application de equalize_adapthist améliore grandement la rendu des couleurs et le contraste à un point plus que satisfaisant.

Résultats sur photo personnelles

Dans la première photo avec sujet, l'algorithme pyramide est celui fonctionnant le mieux. Malgré tout des artéfactes sont présents autour du sujet dû à son mouvement. Dans la deuxième photo identique, mais statique, l'algorithme pyramide est aussi le meilleur. Certains artéfacts sont présents à quelques endroits probablement car la rotation n'est pas corrigé. Dans la troisième image, l'algorithme pyramidale produit le meilleur résultat. BRIEF donne un résultat satisfaisant.

Dans tous les cas, l'algorithme de corrélation croisée fonctionne étragement bien. Je n'ai pas d'hypothèse par rapport à cela.

Amélioration possible

Les résulats obtenus ne sont pas parfaits et certains problèmes ont été recontrés. D'abord l'algorithme simple est très lent et n'est donc qu'adapté aux petites images. La solution est évidemment d'utiliser un autre algorithme.

L'algorithme pyramidale ne fonctionne pas dans un cas. Cela est probablement dû à sa dépendance envers une méthode de mesure d'erreur. Dans ce cas, la SDC ne donne pas toujours un résultat significatif, il est possible de minimiser l'erreur avec un mauvais alignement. L'utilisation d'un algorithme prenant en compte les textures améliorerait probablement significativement la précision des résultats. Des tests préliminaires ont été fait avec SSIM, mais la vitesse d'exécution beaucoup plus lente rendait impraticable son utilisation.

BRIEF fonctionne généralement bien, sauf le cas de la dernière image où le data association n'est pas bon. Pour résoudre cela, BRIEF possède plusieurs paramètres pouvant être ajustés, mais la véritable solution est probablement d'utiliser un filtre RANSAC robuste pour éliminer les mauvaises données. Aussi, quelques images sont noirs, cela est causé par le fait que dans ces images, un nombre insuffisant de points d'intérêt à été trouvé causant l'échec de l'algorithme et une image erronée. Puis, cette image a été effacée en passant dans l'algorithme de détection de bordure.

ORB est très difficile à ajuster correctement et c'est pour cela que les résultats sont de généralement moins bonne qualité. Un travail plus poussé pourrait sans doute l'amener à être meilleur que les autres solutions tout en supportant l'alignement en rotation.

Pour des raisons citées plus haut, la corrélation croisée n'est pas adéquate pour ce cas d'utilisation et donc tenter de l'améliorer serait futile.

Conclusion

Cette expérience prouve que la recherche de descripteurs est une technique envisageable pour l'alignement de canaux RGB d'une image. L'utilisation de cette technique avec un filtre tel que RANSAC permet d'obtenir un résultat robuste dans plusieurs types d'images. Les nombreux paramètres entrant dans l'algorithme BRIEF signifie que des optimisations subséquantes pourraient améliorer sa vitesse et sa précision à un point dépassant la méthode par pyramide.

L'éxpérience a aussi prouvé que l'utilisation de la corrélation croisée n'est pas utile pour l'alignements des différents canaux. Cela est probablement du au fait que entre deux canaux de larges régions diffèrent en intensité ce qui oriente fortement le gradient obtenu alors que les coins sont semblables dans tous les cas.

Annexe

Résultat du recadrage automatique et de la correction par histogramme

Originale avec la méthode par pyramide

Recadrée et corrigée automatiquement

Résultats final de l'alignement automatique

Pyramid

BRIEF

ORB

CrossCorrelation