Résumé

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 cette première partie du TP, 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 (dans la partie B), vous aurez à développer une méthode de détection de points d'intérêt et d'appariement automatiques.

En Python, il existe déjà des fonctions effectuant en grande partie la tâche qui vous est demandée, par exemple dans le module skimage.transform. Cependant, l'objectif du TP est que vous implémentiez vous-même les algorithmes.

Par conséquent, vous n'êtes pas autorisés à utiliser les fonctions qui calculent et appliquent des transformations entre des images. Par exemple, votre code ne peut pas utiliser skimage.transform.warp!

Bien entendu, il existe 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.

Overview

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.

In this first part of the homework, you will do the registration (matching of similar features in different images to transform different sets of data into one coordinate system) manually. Afterwards (in part B), you will have to implement a way to automatically detect and match interesting features in images.

In Python, there are some functions that can do much of what is needed, for example in the skimage.transform package. However, we want you to write your own code.

Therefore, you are not allowed to use functions that compute and apply transformations from images. For example, you code cannot use skimage.transform.warp!

On the other hand, there exists 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 = np.array([[0.9752, 0.0013, -100.3164], [-0.4886, 1.7240, 24.8480], [-0.0016, 0.0004, 1.0000]])

H2 = np.array([[0.1814, 0.7402, 34.3412], [1.0209, 0.1534, 60.3258], [0.0005, 0, 1.0000]])

Vous devriez obtenir l'une ou l'autre de ces deux images (en fonction de la façon dont votre code gère les bordures de l'image) :

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$ (ceci est le cas pour l'homographie H1 ci-haut). 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 = np.array([[0.9752, 0.0013, -100.3164], [-0.4886, 1.7240, 24.8480], [-0.0016, 0.0004, 1.0000]])

H2 = np.array([[0.1814, 0.7402, 34.3412], [1.0209, 0.1534, 60.3258], [0.0005, 0, 1.0000]])

You should obtain one of the following (depending on how your code manages the image borders):

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$ (this is the case for the H1 transformation above). Your code must be able to handle this case.

Détails

L'algorithme d'assemblage de photos consiste à :

1. Apparier des points caractéristiques
2. Calculer l'homographie
3. Déformer les images grâce à une transformation projective
4. Fusionner les images en une mosaïque

Chacune des étapes de l'algorithme sont décrites plus bas.

Details

The image stitching algorithm can be summarized as:

1. Features matching
2. Compute homography
3. Projective warping
4. Blending the images into a mosaic

All of these steps are described further down.

1. Appariement de caractéristiques

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 vous-même une petite interface, ou encore adaptez le code du TP3.

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.

1. Features matching

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 or adapt code from HW3.

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.

2. Calculer l'homographie

Avant de pouvoir déformer les images en appliquant votre fonction appliqueTransformation de votre réchauffement, vous devez tout d'abord estimer cette transformation pour chaque paire d'images. La transformation à estimer est une homographie (ou une transformation projective) : $\mathbf{p}^\prime= \mathbf{H}\mathbf{p}$, où $\mathbf{H}$ est la matrice $3 \times 3$

$$ \mathbf{H} = \left[ \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array} \right] \,, $$

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 (donc 8 points au total) 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ère (singular value decomposition, ou SVD en anglais) de la matrice $\mathbf{A}$:

$$ \mathbf{A} = \mathbf{U} \Sigma \mathbf{V}^T \,. $$

Utilisez numpy.linalg.svd pour calculer la SVD. 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.

Nous vous conseillons de tester votre fonction calculerHomographie en dessinant deux quadrilatères (comme dans les capsules), en calculant l'homographie à partir de leurs coins, et de transformer le premier quadrilatère selon l'homographie obtenue. Vous devriez obtenir exactement les coordonnées du second!

2. Compute homography

Before you can warp your images into alignment using your warmup, 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 (so 8 points in total) 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{A} = \mathbf{U} \Sigma \mathbf{V}^T \,. $$

Use numpy.linalg.svd to compute the SVD. 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.

We recommend you test your computeHomography function by drawing two quadrilaterals (just like in the videos), compute the homography from their corners, and transform the first one according to the homography. You should obtain exactly the coordinates of the second one!

3. Déformation projective

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 pour le réchauffement.

3. Projective warping

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 the warmup.

4. Fusionner les images en une mosaïque

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.

4. Blend the images into a mosaic

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.

Crédits supplémentaires

Essayez une de ces idées pour approfondir vos connaissances (et augmenter votre note) :

• (jusqu'à 5% chacun) Utilisez des homographies pour combiner des images de façons intéressantes et créatives. Voici quelques suggestions :
  • Ajouter un graffiti sur un édifice ou un dessin à la craie sur le sol.
  • Remplacer un panneau sur la route par une photo de vous ou votre famille.
  • Créer une mosaïque en effectuant un mélange d'images prises à des moments différents (jour vs nuit) ou au cours de différentes saisons.
  • Créer une mosaïque en effectuant un mélange d'une image historique avec une moderne d'un même endroit.
  • Créer une mosaïque intéressante/étrange comme, par exemple, une mosaïque avec plusieurs copies d'une même personne.
• (jusqu'à 10%) Meilleur mélange : exploitez votre code du TP2 et utilisez une pyramide (ou une pile) laplacienne au lieu de calculer une moyenne entre les images se chevauchant.

Extra credit

Try one of these ideas to increase your understanding on this subject (and increase your score):

• (up to 5 points each) Use homographies to combine images in interesting and creative ways. Here are a few suggestions:
  • Put fake graffiti on buildings or chalk drawings on the ground.
  • Replace a road sign with your family portrait.
  • Create a mosaic by spatially blending images taken at different times (day vs. night) or during different seasons.
  • Create a mosaic by spatially blending a historic photograph with a modern picture of the same place.
  • Create an interesting/bizarre mosaic, like the ones with multiple copies of the sample person.
• (up to 10 points) Better blending: exploit your code from HW2 and use Laplacian pyramid (or stack) blending instead of computing the mean of overlapping images.

Pour cette partie du travail, vous n'avez pas à remettre de rapport. Par contre, vous devez nous remettre des fichiers montrant vos mosaïques ainsi que votre code. Le rapport que vous allez remettre à la prochaine partie devra contenir ces résultats ainsi que des explications sur tout ce que vous nous montrez pour cette partie.

• (20%) Vos deux transformations pour le réchauffement.
• (80% pour 4105, 60% pour 7105) Votre mosaïque pour chacun des 3 jeux de données (Serie1, Serie2, Serie3) fournis pour la "1-PartieManuelle".
  • Pour les images de la « Serie1 », vous pouvez utiliser les points fournis.
  • Pour les autres séries, vous devez identifier manuellement les points de correspondance.
• (N%) Résultats pour vos crédits supplémentaires.

For this part of the homework, you do not have to provide a report. However, you need to give us files showing results of your mosaics, as well as your code. The report that you will have to deliver for the next homework part will have to contains these results and explain everything you showed us in this part.

• (20%) Both transformations for the warmup.
• (80% for 4105, 60% for 7105) Your mosaic for each of the 3 datasets (Serie1, Serie2, Serie3) given for the "1-PartieManuelle".
  • For the "Serie1" images, you can use the correspondence points provided.
  • For the other series, you have to manually identify the correspondences.
• (N%) Results for your extra credits.

Pour la remise de votre travail, créez un fichier tp4.zip qui contient:

• Vos résultats dans un dossier tp4a/resultats.
• Votre code dans un dossier tp4a/code.

Nous vous conseillons fortement d'identifier clairement les principales « portes d'entrée » de votre code (ex: main_rechauffement.py, main_manuel.py, 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 PAX!

For this homework, you must create a tp4.zip file which contains:

• Your results in a folder tp4a/results.
• Your code in the folder tp4/code.

You should clearly identify the "entry points" to your code (ex: main_warmup.py, main_manual.py, etc.). This will help the grading!

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 PAX!

Beware! The file size limit on the "portail" is 250MB.

Remerciements

Merci à Alyosha Efros d'avoir créé le TP original qui a servi d'inspiration pour celui-ci!

Thanks

Many thanks to Alyosha Efros for creating the assignment which inspired this one!