Appariement manuel
Une mosaïque est la fusion de plusieurs images pour n'en former qu'une seule. La réalisation d'une mosaïque se fait par une série de transformations géométriques, également appelées homographies. Pour se faire, il suffit d'apparier plusieurs points dans chacune des paires d'images consécutives. La transformation employée pour réaliser la mosaïque est la transformation projective. Puisque celle-ci a 8 degrés de liberté, un minimum de 4 paires de points est nécessaire pour lever l'indétermination du système d'équation linaire permettant d'obtenir l'homographie entre ces deux images. La matrice d'homographie est sous la forme: $$ M = \begin{bmatrix} m_{11} & m_{12} & m_{13} \\ m_{21} & m_{22} & m_{23} \\ m_{31} & m_{32} & m_{33} \end{bmatrix} \quad . $$ Afin de trouver cet opérateur entre deux images données, il est nécessaire de résoudre la relation $$ M \cdot x = x' \quad , $$ où $ x $ et $ x' $ sont respectivement les coordonnées de points appariés dans l'image source et destination et $ M $ est l'homographie entre les deux images. Cependant, cette formulation n'est pas sous forme linéaire. Effectivement, puisque l'homographie $ M $ est de taille 3x3, les points doivent être exprimées en coordonnées homogènes, soit les coordonnées augmentées avec un facteur d'échelle. Ainsi, $$ \frac{x'}{w} = ax + by + c \\ \frac{y'}{w} = dx + ey + f \\ w = gx + hy + i \quad , $$ ce qui, une fois les variables isolés, s'écrit $$ 0 = ax + by + c - gxx' - hyx' - ix' \\ 0 = dx + ey + f - gxy' - hyy' - iy' \quad .$$ Ces équations s'écrivent également sous forme matricielle: $$ A = \begin{bmatrix} x_1 & y_1 & 1 & 0 & 0 & 0 & -gx_1x_1' & -hy_1x_1' & -ix_1' \\ 0 & 0 & 0 & x_1 & y_1 & 1 & -gx_1y_1' & -hy_1y_1' & -iy_1' \\ & & & & & ... & & & \end{bmatrix} \quad . $$ Il suffit ensuite d'augmenter cette matrice avec un minimum de quatre points $ (x_2, y_2), (x_3, y_3), $ etc. et de résoudre l'équation $ An = 0 $. Cette matrice a cependant 8 degrés de libertés et 9 inconnues. Ceci signifie qu'une infinité de solutions existent selon un facteur d'échelle, soit $i$ dans le cas présent. Une façon d'obtenir le résultat stable est de forcer $ ||A|| = 1$, ce qui est possible en résolvant l'équation $ An = 0 $ à l'aide d'une décomposition en valeurs singulières, $ A = U \Sigma V* $. La solution est alors la colonne la plus à droite du vecteur $ V $, correspondant à une des bases de l'espace nul de $ A $.
Une fois les homographies trouvées entre chaque paire d'images consécutives, il suffit d'effectuer la fusion de ces images. Pour se faire, une méthode aisée est d'additionner toutes les images ensemble entre-elles dans un seul panorama, puis de diviser les valeurs des pixels obtenues par la quantité d'images ayant contribuées à la valeur de chaque pixel.
Quelques problèmes surviennent cependant avec cette façon de procéder. Par exemple, les erreurs d'alignement ne sont pas corrigées, seulement noyées dans le moyennage. Ceci produit des effets de ghosting un peut partout au travers de la mosaïque. Une façon de régler ce problème serait d'effectuer une fusion en fondu graduel, où une image se fonderait de plus en plus dans sa cible. De plus, la sélection des points est longue et fastidieuse; les appariements ont donc été effectués sur un nombre réduit de points, ce qui explique la grande quantité de "ghosting".
Appariement automatique
Pour effectuer l'appariement automatique, il suffit de trouver des paires de points analogues par paire d'image de façon automatique. Ceci s'effectue en 4 étapes:
- Détection de features
- Extraction d'un descripteur
- Trouver l'appariement de ces features
- Éliminer les appariements erronnés
Le but de la détection de features est de trouver des points «intéressants» pouvant décrire le contenu de l'image. Une façon de ce faire est de détecter les coins dans l'image; ces zones étant plus potentielles à être près d'informations intéressantes caractéristiques de l'image. Un détecteur de coins bien connu, soit le détecteur de Harris, est employé pour ce travail. Un algorithme de suppression adaptative de non-maximums (ANMS) est également appliqué pour ne garder que les points les plus intéressants dans un certain rayon. Un exemple de détection est présenté à la figure 2.
Figure 2. Exemples de détection (gauche), puis exemple d'application de l'algorithme de suppression adaptative de non-maximums (ANMS) (droite).
Une fois les points intéressants trouvés (appelés des features), il suffit d'en extraire un descripteur. Pour se faire, une zone de 40x40 pixels centré sur le point d'intérêt est capturée puis moyennée en zones de 8x8 pixels. Un exemple de descripteurs avant conversion en tons de gris est montrée à la figure 3.
Figure 3. Exemple de descripteurs avant conversion en tons de gris.
Les descripteurs peuvent ensuite être comparées un à un en effectuant la somme des erreurs au carrée. Cependant, employer le meilleur appariement entre deux points ne donne pas toujours le meilleur résultat. Ceci est dû au fait que certains descripteurs ne représentent pas une zone unique dans l'image ou une zone ressemblant à d'autres zones. Il convient alors mieux de prendre le ratio entre le meilleur appariement et le second meilleur. Si ce ratio est moindre qu'un certain seuil, l'appariement a beaucoup plus de chance d'être correct et unique. Un exemple d'appariement est montré à la figure 4.
Figure 4. Exemple d'appariements de points.
Une fois les appariements effectués, il faut se bâtir un modèle de points pour obtenir l'homographie. L'obtention de l'homographie ne tolère pas beaucoup les valeurs aberrantes, il convient donc de les éliminer à cette étape. Il est possible d'employer l'algorithme RANSAC pour trouver un ensemble de points en écartant les valeurs aberrantes. L'algorithme s'effectue en prenant un groupe aléatoire de 4 appariements, en calculant l'homographie de ces 4 points et de calculer la quantité de points coïncidants avec cette homographie. L'homographie est ensuite calculée sur le plus grand ensemble de points coïncidant.
Les démarcations entre chacune des images sont relativement visible à cause du vignettage sur les images. Ce problème pourrait être corrigé en éliminant le vignettage des images ou en effectuant un fondu en dégradé lors de la fusion d'images. La plupart des images sont bien réussies, à l'exception du panorama 2 où certains points d'intérêt ont été pris sur des éléments dynamiques de la scène, soient des personnes. Ceci peut expliquer le désalignement de certaines des images. Le panorama 1 a été séparé en deux puisqu'il possède plus de 180° de champ de vue.
Mes scènes
L'image dans laquelle je fais preuve d'ubiquité a été recadrée pour ne montrer aucune zone noire. La colline parlementaire à Ottawa est issue de deux photos avec des expositions différentes, l'image de droite étant beaucoup plus sombre que l'image de gauche, expliquant la forte démarcation entre les deux images.
Détection multi-échelle
La détection multi-échelle est implantée à l'aide du paramètre $\sigma$. Celui-ci est la taille d'une gaussienne avec laquelle on filtre l'image avant d'effectuer l'algorithme de Harris. Cette pratique est courante dans l'extraction multi-échelle de descripteurs, par exemple pour les SIFT [1]. Ceci permet de trouver une plus grande variété de points d'intérêts, ce qui augmente la quantité d'appariements possibles. Un exemple de détection multi-échelle est présentée à la figure 7. Notez que tous les résultats de la section avec appariement automatiquement ont été réalisés avec la détection multi-échelle. Les résultats sont très similaires sans et avec la détection multi-échelle.
Figure 7. Détection multi-échelle des features. La rangée du haut est sans supression adaptative des points non-maximaux (ANMS), tandis que la rangée du bas est après exécution de ANMS.
Projection en coordonnées cylindriques
Le but de cette section est de projeter les images, initialement en coordonnées cartésiennes, sur un cylindre. L'équation de projection des points sur un cylindre est définie par $$ (\hat{x}, \hat{y}, \hat{z}) = \frac{1}{\sqrt{X^2 + Z^2}}(X,Y,Z) \quad ,$$ où $(X,Y,Z)$ sont les coordonnées dans le plan cartésien de l'image à projeter sur le cylindre défini par $(\hat{x}, \hat{y}, \hat{z})$. Il est ensuite possible d'obtenir les coordonnées en coordonnées cylindriques, soit sur le cylindre déroulé, à l'aide de: $$ (\sin \theta, h, \cos \theta) = (\hat{x}, \hat{y}, \hat{z}) \quad .$$ Cependant, ce que nous désirons est l'opération inverse, soit savoir à quel point de l'image d'origine correspond chacun des pixels dans la carte en coordonnées cylindriques. Il suffit alors d'isoler $ x $ et $ y $ pour obtenir: $$ x = f \tan \theta \\ y = h \sqrt{x^2 + f^2} + y_c\\ x = x + x_c \quad , $$ où $(x, y)$ sont les coordonnées des pixels de l'image, $f$ la focale de l'image, $h$ la coordonnée verticale dans l'image en coordonnées cylindriques et $x_c, y_c$ sont les coordonnées du centre de l'image. La dernière ligne est séparée de la première puisqu'il est important d'effectuer le calcul de $y$ à l'aide de $x$ sans l'avoir additionné de $x_c$.
Cette opération permet de convertir une image en coordonnées cylindriques, comme montré à la figure 8. Pour effectuer un panorama dans ce système de coordonnées, il suffit d'exécuter le reste de l'algorithme tel que décrit plus haut sur les images converties en coordonnées cylindriques. Un exemple sur le panorama 3 est montré à la figure 9. Dans ce cas, les transformées entre les images sont forcées à des translations. Dans le domaine cylindrique, la translation sur l'axe horizontal (appelé $u$) représente une rotation, permettant ainsi avec de simples translations de couvrir les $2\pi$ du cercle.
Figure 8. Exemple de conversion d'une image (gauche) en coordonnées cylindriques (droite).
Figure 9. Panorama en coordonnées cylindriques. Notez que les transformées entre les images sont des translations.
Figure 10. Second exemple de panorama en coordonnées cylindriques. Les transformées entre les images sont également des translations. Images courtoisie de Marc-André Gardner.