TP1 Colorisation de l'Empire Russe
Par Pier-Luc Auger

Au premier numéro, il était demandé de développé un algorithme permettant de recréer une image couleur à partir de trois images ayant été prises avec l'utilisation de trois filtres: rouge, vert et bleu. L'algorithme que j'ai développé est simple et effectue cette tâche tel le pseudo-code ci-bas:
À noter que ce pseudo-code sera imagé et détaillé davantage pour l'algorithme 2, qui s'avère très analogue en terme de fonctionnement.

Pour aligner les images, une simple double boucle 'for' parcours une étendue de 15x15 pixels et pour tenter de trouver le décalage optimal pour avoir des images alignées. Pour trouver cet alignement, j'ai procédé en utilisant la somme des différences au carré des deux images. Le résultat optimal est celui retournant la plus basse valeur, car on sait que la somme des différences de deux images et de 0. L'algorithme parcours donc l'étendue et garde en mémoire le meilleur résultat et le retourne lorsque le bouclage est terminé.

Instictivement, on peut apréhender le fait que cet algorithme s'avérera limité dans les contextes où l'image nécessitera d'être décalé au-delà de la plage de 15x15 pixels. Le traitement des images à haute définition m'a rapidement permis de le confirmer. En effet, on remarque que le décalage optimal trouvé par l'algorithme n'est pas exact et on perçoit aisément que l'alignement n'est pas bon. Voici un exemple illustant bien cette limitation. La solution simple que l'on pourrait voir serait de hausser la plage de recherche à par exemple 150x150 pixels. Or là, on se retrouve avec un autre problème: le temps de calcul. En effet, sur un image à haute résolution, le calcul de la SDC devient assez fastidieux, et de le faire 22500 fois pour chacune de nos deux images à aligner devient une opération coûteuse en temps de calcul. C'est pour cette raison qu'un second algorithme a été développé. Nous verons bien qu'un bon design d'algorithme permettra de remplir la même tâche pour des images à haute résolution dans un temps de calcul très court.

Il est à noter que certaines optimisations ont été faites sur ces images, notamment l'ajustement de la balance des blancs, un découpage des bordures de même qu'un ajustement du contraste. C'est optimisations seront détaillées plus bas.

Vu le problème rencontré avec les images de haute définition avec l'algorithme 1, il a fallu trouvé un alternative plus perfomante. Les indications dans l'énoncé pointait vers une piste plus qu'intéressante pour y arriver. Cette piste suggérait d'implanter un algorithme récursif travaillant sur des images de résolutions réduite pour trouver le meilleur décalage et d'appeler récursivement l'algorithme de SDC sur les images de résolutions de plus en plus près de la pleine résolution. La méthode que j'ai utilisé va directement en ce sens. J'ai réutilisé mon algorithme de calcul de la SDC auquel j'ai ajouté 2 paramètres correspondant au couple (x,y) qui réfère à un décalage pour démarrer la recherche. Cette astuce m'a permis de découvrir que le décalage trouvé par le SDC n'était jamais plus de 3 pixels à côté du point de recherche que suggérait le calcul du SDC fait sur l'image dont la résolution était 2 fois plus petite. Cela m'a permis d'améliorer la rapidité de calcul en faisant passer la plage de recherche de 15x15 pixels à 5x5 pixels. Un gain appréciable en performance fut perçu.
En amont, le SDC est appelé par un algorithme qui gère la résolution des images passées à la fonction de calcul du SDC. Cet algorithme cherche à construire une pyramide d'images correspondant par exemple à des résolutions de 1/8, 1/4, 1/2 et finalement, pleine résolution. On passe à l'algorithme la 'hauteur' de pyramide qu'on veut, et l'algorithme boucle tant que la pyramide n'atteint pas de hauteur égale à 0. Le facteur de redimensionnement est calculé tel que
resizeFactor=1/(2^pyramidHeight);
lequel nous permet d'utilisé la fonction 'imresize' pour redimensionner nos images avant de calculer d'utiliser le SDC pour trouver le meilleur décalage.
Voici un exemple de trace que laisse mon algorithme. Dans cette trace, on voit bien que la recherche ce fait à la distance double de celle trouvée trouvée par l'itération précédente. C'est logique, car on double la résolution! On remarque aussi ce qui a été énoncé plus haut, à savoir que le décalage n'est jamais bien loin que celui trouvé via l'image de plus basse résolution.

---> New search around offset:(0,0)
---> Best offset:(1,0)

---> New search around offset:(2,0)
---> Best offset:(2,1)

---> New search around offset:(4,2)
---> Best offset:(5,2)

---> New search around offset:(10,4)
---> Best offset:(10,4)

---> New search around offset:(20,8)
---> Best offset:(19,8)

---> New search around offset:(38,16)
---> Best offset:(39,15)

Offset of full definition image is:(39,15)

C'est cet algorithme qui est appelé dans le traitement en boucle effectué sur toutes les images de hautes résolution. Voici en détail l'approche utilisé pour reconstruire l'image couleur. Il faut ici préciser que la logique est la même pour l'algorithme de la question 1, sauf que pour cette question, l'algorithme utilisé pour aligner les trois images est celui détaillé plus tôt.

Limitation de l'algorithme

Pseudo-code imagé de l'algorithme