Date de remise: 2 avril 2020 à 23h59 26 mars 2020 à 23h59
Due date: April 2nd 2020, 23h59 March 26th 2020, 23h59
L'objectif de ce travail est d'implémenter un algorithme vous permettant de créer une mosaïque d'images. Une mosaïque combine plusieurs images ayant des champs de vue se chevauchant afin de produire un panorama ou une image à haute résolution. La plupart des approches d'assemblage d'images nécessitent un chevauchement très exact et des expositions identiques entre les images pour produire des résultats sans joint apparent. Lors du travail, vous allez apprendre à calculer des homographies et à les utiliser pour déformer les images. Pour le travail, utilisez les photos suivantes : images.zip.
Dans un premier temps, vous ferez le recalage (appariement des caractéristiques similaires dans les différentes images afin de transformer des ensembles différents de données dans un seul système de coordonnées) manuellement. Ensuite, vous aurez à développer une méthode de détection de points d'intérêt et d'appariement automatiques.
Dans Matlab et Python, il existe déjà des fonctions effectuant en grande partie la tâche qui vous est demandée.
Par conséquent, vous n'êtes pas autorisés à utiliser les fonctions qui calculent et appliquent des transformations entre des images.
Bien entendu, Matlab et Python ont tout de même plusieurs fonctions très utiles que vous êtes invités à utiliser (par exemple, pour la résolution de systèmes linéaires, l'inversion des matrices, interpolation linéaire, etc.). Si vous ne savez pas si une fonction particulière est autorisée, n'hésitez pas à nous le demander.
The goal of this assignment is to implement an application of image mosaicking. Image mosaicking (or stitching) is the process of combining multiple images with overlapping fields of view to produce a panorama or high-resolution image. Most approaches to image stitching require nearly exact overlaps between images and identical exposures to produce seamless results. Along the way, you will learn how to compute homographies, and how to use them to warp images. For the homework, use those images: images.zip.
At first, you will do the registration (matching of similar features in different images to transform different sets of data into one coordinate system) manually. Afterwards, you will have to implement a way to automatically detect and match interesting features in images.
In Matlab and Python, there are some functions that can do much of what is needed. However, we want you to write your own code.
Therefore, you are not allowed to use functions that compute and apply transformations from images.
On the other hand, Matlab and Python have a number of very helpful functions (e.g. for solving linear systems, inverting matrices, linear interpolation, etc.) that you are welcome to use. If you are wondering whether a particular function is allowed, ask us.
Avant de créer des mosaïques, il est important de savoir comment transformer une image. En guise de réchauffement, vous devrez implémenter la fonction
imgTrans = appliqueTransformation(img, H);
qui applique une homographie H
à une image img
, et retourne l'image transformée imgTrans
. Pour déterminer la taille du nouveau canevas, il vous faut appliquer la transformation aux quatre coins de l'image; la position minimum de ces quatre points transformés vous donnera le coin en haut à gauche du canevas et la position maximum le coin en bas à droite.
Pour tester votre code, utilisez l'image suivante:
et appliquez les deux homographies suivantes:
H1 = [0.9752 0.0013 -100.3164; -0.4886 1.7240 24.8480; -0.0016 0.0004 1.0000];
H2 = [0.1814 0.7402 34.3412; 1.0209 0.1534 60.3258; 0.0005 0 1.0000];
Si votre code fonctionne correctement, vous devriez obtenir les résultats ci-haut.
Attention : les coordonnées de l'image finale peuvent être négatives ou dépasser la largeur de l'image originale en x et/ou en y. Votre code doit être en mesure de gérer ce cas.
Before creating any mosaic, it is important to know how to transform an image. As a warmup, you will have to implement the function
imgTrans = applyTransformation(img, H);
which applies the homography H
to the image img
, and returns the transformed image imgTrans
. To determine the size of the new canvas, you have to apply the transformation to the four corners of the image; the minimum position of all these transformed points will provide the top left corner of the new canevas and this corner minus the maximum position will provide the size of the canevas.
To test your code, use the following image:
and apply the two transformations:
H1 = [0.9752 0.0013 -100.3164; -0.4886 1.7240 24.8480; -0.0016 0.0004 1.0000];
H2 = [0.1814 0.7402 34.3412; 1.0209 0.1534 60.3258; 0.0005 0 1.0000];
If your code works properly, you should obtain the results above.
Warning: the coordinates of the final image can therefore be negative or higher than the size of the original image in x and/or y. Your code must be able to handle this case.
L'algorithme d'assemblage de photos consiste à:
Chacune des étapes de l'algorithme sont décrites plus bas.
The image stitching algorithm can be summarized as:
All of these steps are described further down.
Comme il a été mentionné dans le cours, le calcul d'une transformation globale comme une homographie nécessite des paires de correspondances. La calcul d'une homographie nécessite au moins 4 paires de correspondances. Dans un premier lieu, sélectionnez manuellement des points d'intérêt se retrouvant dans les deux images.
Établir une correspondance entre des points peut être délicat. Une erreur de quelques pixels peut produire d'énormes changements dans l'homographie estimée. La façon manuelle d'établir les correspondances est d'utiliser la souris. Vous pouvez créer rapidement une petite interface (par exemple, en Matlab, vous pouvez utiliser les fonctions ginput
ou cpselect
).
Nous vous fournissons les points de correspondance à utiliser pour les données «Serie1» du répertoire «1-PartieManuelle» pour vous aider à valider votre code. En utilisant ces points, vous devriez obtenir un résultat similaire à l'image suivante:
Vous devrez sélectionner les points vous-mêmes pour les autres ensembles de photos.
As it was mentioned in class, the calculation as a global homography transformation requires pairs of correspondences. The calculation of a homography requires at least 4 pairs of correspondences. In this part of the homework, you will have to manually select these interest points in both images.
Establishing point correspondences is a tricky business. An error of a couple of pixels can produce huge changes in the recovered homography. The typical way of providing point matches is with a mouse-clicking interface. You can write your own using ginput
or cpselect
.
We provide correspondences for the "Serie1" data in the folder "1-PartieManuelle" to help you validate your code. Using these points, you should obtain a result similar to the following image:
You will have to select your points manually for the other sets.
Avant de pouvoir déformer les images en appliquant votre fonction appliqueTransformation
de la partie 0, vous devez tout d'abord estimer cette transformation pour chaque paire d'images. Dans notre cas, la transformation est une homographie: $\mathbf{p}^\prime= \mathbf{H}\mathbf{p}$, où $\mathbf{H}$ est la matrice $3 \times 3$
possédant 8 degrés de liberté (elle est définie à un facteur d'échelle près). Il est possible d'estimer l'homographie grâce à un minimum de $n=4$ paires de points correspondants prélevés sur les deux images $(\mathbf{p}^\prime, \mathbf{p})$. Pour calculer $\mathbf{H}$, créez un système de $2n$ (8) équations linéaires pouvant être représenté sous la forme $\mathbf{A}\mathbf{h} = 0$, où $\mathbf{h}$ est un vecteur contenant les 9 inconnues de $\mathbf{H}$ tel que vu dans le cours.
Pour résoudre le système d'équations linéaires, calculez ensuite la «décomposition en valeurs singulières» (singular value decomposition, ou SVD en anglais) de la matrice $\mathbf{A}$:
$$ [\mathbf{U},\Sigma,\mathbf{V}] = svd(\mathbf{A}) \,. $$Le vecteur $\mathbf{h}$ que nous cherchons est la colonne de $\mathbf{V}$ qui correspond à la plus petite valeur dans la matrice $\Sigma$ (la plus petite valeur singulière). Cette façon de faire trouve le vecteur $\mathbf{h}$ qui minimise $||\mathbf{A}\mathbf{h}||_2$ sous la contrainte que $||\mathbf{h}||_2=1$ (la norme du vecteur $\mathbf{h}$ est 1).
En pratique, implémentez la fonction suivante:
H = calculerHomographie(im1_pts,im2_pts);
où im1_pts
et im2_pts
sont des matrices $n \times 2$ contenant les positions $(x, y)$ des $n$ correspondances entre les deux images et H
est l'homographie calculée à partir de ces points.
Il est plus robuste de pré-normaliser les points im1_pts
et im2_pts
au préalable, tel que recommandé par Richard Hartley dans son désormais célèbre article « In defense of the 8-point algorithm ». Pour ce faire, vous pouvez simplement soustraire la moyenne des points et diviser par leur écart-type.
Before you can warp your images into alignment, you need to recover the parameters of the transformation between each pair of images. In our case, the transformation is a homography $\mathbf{p}^\prime= \mathbf{H}\mathbf{p}$, where $\mathbf{H}$ is the $3 \times 3$ matrix
$$ \mathbf{H} = \left[ \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array} \right] \,, $$with 8 degrees of freedom (it is defined up to scale). The homography can be estimated from a minimum of $n=4$ pairs of corresponding points on the two images $(\mathbf{p}^\prime, \mathbf{p})$. To compute $\mathbf{H}$, create a system of $n$ linear equations that can be represented with $\mathbf{A}\mathbf{h} = 0$, where $\mathbf{h}$ is a vector containing the 9 unknowns of $\mathbf{H}$ as seen in class.
To solve the resulting linear system of equations, compute the singular value decomposition (SVD) of matrix $\mathbf{A}$:
$$ [\mathbf{U},\Sigma,\mathbf{V}] = svd(\mathbf{A}) \,. $$The $\mathbf{h}$ vector that we are looking for is the column of $\mathbf{V}$ that corresponds to the smallest value in $\Sigma$ (the smallest singular value). This is equivalent to finding the vector $\mathbf{h}$ that minimizes $||\mathbf{A}\mathbf{h}||_2$ under the constraint that $||\mathbf{h}||_2=1$ (the norm of $\mathbf{h}$ is 1).
In practice, implement the following function:
H = computeHomography(im1_pts,im2_pts);
where im1_pts
and im2_pts
are n-by-2 matrices holding the $(x, y)$ locations of $n$ point correspondences from the two images and H
is the recovered homography matrix.
It is more robust to normalize the points im1_pts
et im2_pts
before estimating the homography, as recommended by Richard Hartley in his famous paper "In defense of the 8-point algorithm". To do so, you can simply subtract the mean and divide by the standard deviation.
Maintenant que vous connaissez les paramètres de l'homographie, vous devez déformer vos images à l'aide de celle-ci. Pour ce faire, vous n'avez qu'à utiliser la fonction appliqueTransformation
que vous avez écrite à la partie 0.
Now that you know the parameters of the homography, you need to warp your images using this homography. All you need to do is to use the function applyTransformation
that you wrote in part 0.
Une façon simple de créer une mosaïque est de déterminer (manuellement) une image de référence, et de déformer les autres images pour les aligner avec l'image de référence. Pour fusionner les images ensemble, plusieurs options sont possibles pour déterminer la valeur des pixels aux endroits où les deux images se chevauchent. Par exemple, vous pourriez conserver le pixel d'une des deux images. Vous pourriez aussi conserver la valeur maximale des pixels des deux images. Une troisième option serait de calculer la moyenne pondérée des deux images. Vous pouvez expérimenter avec diverses options et choisir celle que vous préférez.
Warp the images so they're registered and create an image mosaic. Instead of having one picture overwrite the other, which would lead to strong edge artifacts, use weighted averaging. You can leave one image unwarped and warp the other image(s) into its projection, or you can warp all images into a new projection. Likewise, you can either warp all the images at once in one shot, or add them one by one, slowly growing your mosaic.
Maintenant que vous avez une implémentation fonctionnelle de l'algorithme d'assemblage de photos, vous devez remplacer l'étape de sélection manuelle de point d'intérêt par une méthode automatique. Cette méthode peut être décrite en quelques étapes simples:
Un coin représente un endroit dans l'image où les gradients horizontaux et verticaux sont tous les deux très forts. Le classique détecteur de coin de Harris est l'algorithme que vous devrez utiliser pour ce travail pratique. Pour ce faire, vous pouvez utiliser ce code (Matlab: harris.m, Python: harris.py), qui l'implémente. Bien qu'il soit possible de calculer les coins à plusieurs échelles, vous n'avez pas à le faire: une seule échelle est suffisante.
Implémentez la répression maximale non adaptative (adaptive non-maximal suppression, voir l'article). Cet algorithme retire certains coins détectés afin de ne garder que les plus importants. Si cet algorithme vous pose problème, vous pouvez sauter cette étape temporairement et simplement sélectionner un sous-ensemble aléatoire de coins.
Centrez une fenêtre de 40x40 autour du point d'intérêt (coin), et échantillonnez ensuite une petite image de taille 8x8. Il est très important de sous-échantillonner afin d'obtenir un descripteur légèrement flou (l'appariement sera donc calculé sur les basses fréquences de l'image autour du point d'intérêt). Ensuite, normalisez les descripteurs (avec le biais (moyenne) et le gain (écart-type), voir l'article).
Vous devez utiliser les descripteurs pour trouver les paires de coins dans deux images qui se ressemblent le plus dans le but de les apparier. Pour le choix d'appariement, nous vous conseillons d'utiliser l'approche simple de Lowe qui calcule le rapport entre le premier et le deuxième plus proche voisin. Consultez la figure 6b dans l'article pour vous aider à choisir le seuil.
Une fois que vous avez des appariements de caractéristiques, vous pouvez calculer une estimation de l'homographie en utilisant l'algorithme RANSAC sur 4 points expliqués en classe. Vous devez implémenter RANSAC vous-même (c'est très simple).
Now that you have code that creates an image mosaic from a series of correspondences in the images, you will replace the manual selection step with an automatic algorithm. This algorithm can be implemented by following these simple steps:
2. Implement Adaptive Non-Maximal Suppression (see article). The idea is to remove some detected features. The paper section is a little confusing; you may need to read it a few times. You may want to skip this step and come back to it; just choose a random set of corners instead in the meantime.
On each feature points, extract axis-aligned 8x8 patches. Do not worry about rotation-invariance. Note that it’s extremely important to sample these patches from the larger 40x40 window to have a nice big blurred descriptor. Don’t forget to bias/gain-normalize the descriptors (see the article).
You will need to find pairs of features that look similar and are thus likely to be good matches. For thresholding, use the simpler approach from Lowe of thresholding on the ratio between the first and the second nearest neighbors. Consult Figure 6b in the paper to pick the threshold.
Once you have matched features, you can compute an estimate of the homography using the 4-point RANSAC algorithm described in class. Note: you must implement RANSAC yourself (it's very easy).
Testez votre algorithme entièrement automatique sur vos propres images! Si vous prenez vos photos sans trépied, faites bien attention à ne pas tourner la tête trop significativement... rappelez-vous, le centre de projection doit être le même pour toutes les images pour que ça fonctionne bien. Vous devez tester votre algorithme sur au moins deux scènes différentes.
Test your fully automatic algorithm on your own images! If you take photos without a tripod, be careful not to move your head too much off-center... remember, the center of projection must be the same for all images for mosaics to work well. You must test your algorithm on at least two different scenes.
save
), 2) faites la sélection sur toutes images avant d'effectuer la moindre homographie, et 3) les points sélectionnés ne doivent pas être co-planaire.save
), 2) select your points on all the image before doing any homography, and 3) the selected points must not be co-planar.Essayez une de ces idées pour approfondir vos connaissances (et augmenter votre note):
Try one of these ideas to increase your understanding on this subject (and increase your score):
Comme lors des travaux précédents, celui-ci sera remis dans un format page Web. Rappel: le site Web n'a pas besoin d'être esthétiquement agréable; ne faites que décrire ce que vous avez fait.
Voici les parties que vous devrez inclure dans votre rapport. Les séries d'images sont disponibles dans le fichier images.zip.
H1
et H2
sur l'image pouliot.jpg.As in the previous homework, this one will be handed in a webpage format. Remember: the aesthetics of the website will not be evaluated, but it is important that the information be presented clearly.
Below are the parts you must include in your report. The image sets are available in the images.zip file.
H1
and H2
on the image pouliot.jpg. Pour la remise de votre travail, créez un fichier tp4.zip
qui contient:
tp4/web
. Vos images doivent être dans un dossier tp4/web/images
.tp4/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.tp4/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.Nous vous conseillons fortement d'identifier clairement les principales « portes d'entrée » de votre code (ex: main_rechauffement.m
, main_manuel.m
, etc.). Cela permettra à votre correcteur de s'y retrouver plus facilement!
Finalement, veuillez téléverser votre fichier tp4.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!
For this homework, you must create a tp4.zip
file. In this file you'll put:
tp4/web
. Your images for this web page should be inside a folder named tp4/web/images
.tp4/web/index.html
. Make sure none of the files have special characters (e.g. accents, punctuation, spaces, etc.) in their filenames. tp4/code
. Do not include the images you have used to generate your results inside this folder, as this will likely generate huge files.
Finally, you should upload this file (tp4.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!
Beware! The file size limit on the "portail" is 250MB.
Merci à Alyosha Efros d'avoir créé le TP original qui a servi d'inspiration pour celui-ci!
Many thanks to Alyosha Efros for creating the assignment which inspired this one!