Résumé

L'objectif de ce travail est d'implémenter une application 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, 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 suivantes dans votre solution: cp2tform, imtransform, tformarray, tformfwd, tforminv, et maketform. Bien entendu, Matlab a 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 vous demandez 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 mosaicing. Image mosaicing or image stitching is the process of combining multiple images with overlapping fields of view to produce a segmented 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, 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 the following functions in your solution: cp2tform, imtransform, tformarray, tformfwd, tforminv, and maketform. On the other hand, Matlab has 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.

Détails

L'algorithme d'assemblage de photos consiste à:

1. Appariement de caractéristiques
2. Calculer l'homographie
3. Déformation 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. Warping
4. Blending the images into a mosaic

All of these steps are described further down.

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 standard pour créer vos correspondances est d'utiliser la souris. Vous pouvez écrire votre propre interface en utilisant la fonction ginput ou cpselect. Après avoir défini les correspondances manuellement, il est souvent utile de les raffiner automatiquement. Cela peut être fait par SSD ou par corrélation normalisée sur un voisinage autour des points sélectionnés dans les deux images (voir cpcorr). Faites attention, cette approche peut parfois produire des résultats indésirables.

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; 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 the bare-bones ginput function. Or you can use a nifty (but often flaky) cpselect. After defining the correspondences by hand, it’s often useful to fine-tune them automatically. This can be done by SSD or normalized-correlation matching of the patches surrounding the clicked points in the two images (see cpcorr), although sometimes it can produce undesirable results.

Calculer l'homographie

Avant de pouvoir effectuer la déformation projective sur vos images, vous devez récupérer les paramètres de la transformation entre chaque paire d'images. Dans notre cas, la transformation est une homographie: p'= Hp, où H est une matrice 3x3 avec 8 degrés de liberté (coin inférieur droit est un facteur d'échelle et peut être mis à 1). Un moyen de récupérer l'homographie est par l'intermédiaire d'un ensemble de paires de points correspondants prélevés sur les deux images (p', p). Vous allez devoir écrire une fonction sous la forme:

H = computeH(im1_pts,im2_pts)

où im1_pts et im2_pts sont des matrices n-par-2 contenant les positions (x, y) de n correspondances des points des deux images et H est une matrice 3x3 étant l'homographie récupérée. Afin de calculer les valeurs de la matrice H, vous aurez besoin de mettre en place un système de n équations linéaires (c'est-à-dire une équation de la forme Ah = b où h est un vecteur contenant les 8 inconnues de H). Si n = 4, le système peut être résolu de façon standard. Cependant, avec seulement quatre points, le calcul de l'homographie sera très instable et très sensible au bruit. Donc, plus de 4 correspondances doivent être fournies pour produire un système surdéterminé qui serait résolu en utilisant les moindres carrés. Dans Matlab, ces deux opérations peuvent être effectuées en utilisant l'opérateur "\" (voir mldivide pour les détails).

Compute homography

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: p’=Hp, where H is a 3x3 matrix with 8 degrees of freedom (lower right corner is a scaling factor and can be set to 1). One way to recover the homography is via a set of (p’,p) pairs of corresponding points taken from the two images. You will need to write a function of the form:

H = computeH(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 3x3 homography matrix. In order to compute the entries in the matrix H, you will need to set up a linear system of n equations (i.e. a matrix equation of the form Ah=b where h is a vector holding the 8 unknown entries of H). If n=4, the system can be solved using a standard technique. However, with only four points, the homography recovery will be very unstable and prone to noise. Therefore more than 4 correspondences should be provided. This will result in an overdetermined system which should be solved using least-squares. In Matlab, both operations can be performed using the "\" operator (see help mldivide for details).

Déformation projective

Maintenant que vous connaissez les paramètres de l'homographie, vous devez déformer vos images à l'aide de celle-ci. Écrivez une fonction de la forme:

imwarped = warpImage(im,H)

où im est l'image d'entrée à déformer et H est l'homographie. Vous pouvez utiliser la déformation directe ou inverse (mais n'oubliez pas que pour la déformation inverse, vous devrez calculer H dans la bonne "direction"). Évitez le recouvrement spectral lorsque vous ré-échantillonnez l'image. Pour ce faire, pensez à utiliser interp2 et essayez d'écrire toute la fonction sans boucle selon le style Matlab. Vous devez faire attention à la taille de l'image résultante (vous pouvez prédire la taille de la nouvelle image en multipliant les quatre coins de l'image avec H).

Warping

Now that you know the parameters of the homography, you need to warp your images using this homography. Write a function of the form:

imwarped = warpImage(im,H)

where im is the input image to be warped and H is the homography. You can use either forward of inverse warping (but remember that for inverse warping you will need to compute H in the right "direction"). You will need to avoid aliasing when resampling the image. Consider using interp2, and see if you can write the whole function without any loops, Matlab-style. One thing you need to pay attention to is the size of the resulting image (you can predict the bounding box by piping the four corners of the image through H).

Fusionner les images en une mosaïque

Déformez les images une à une afin de créer une mosaïque d'images. Au lieu d'écraser une image par une autre, utilisez une moyenne pondérée entre les images. Vous pouvez laisser une image non déformée et déformer l'autre image ou les autres images dans sa projection, ou vous pouvez déformer toutes les images dans une nouvelle projection. De même, vous pouvez déformer toutes les images d'un seul coup ou une seule à la fois pour les ajouter un par un à votre mosaïque.

Si votre mosaïque s'étend sur plus de 180 degrés, vous aurez besoin de la séparer en morceaux, ou bien d'utiliser des systèmes non projectifs, par exemple, une projection sphérique ou cylindrique.

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.

If your mosaic spans more than 180 degrees, you'll need to break it into pieces, or else use non-projective mappings, e.g. spherical or cylindrical projection.

Appariement de caractéristiques automatique

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 caractéristiques par une méthode automatique. Cette méthode peut être décrite en quelques étapes simples:

• Détection de caractéristiques de coins dans une image
• Extraire un descripteur pour chaque point caractéristique
• Apparier ces descripteurs de caractéristiques entre les deux images
• Utiliser une méthode robuste (RANSAC) pour calculer l'homographie

Les trois premières étapes suivent l'article "Multi-Image Matching using Multi-Scale Oriented Patches" par Brown et coll., mais avec plusieurs simplifications. Nous vous suggérons de lire l'article avant d'implémenter la méthode. Chacune des étapes de l'algorithme est décrite plus bas.

Détection de caractéristiques de coins dans une image

Une caractéristique de coins dans une image représente un endroit dans l'image où les gradients horizontaux et verticaux sont tous les deux très forts. Le détecteur de coin d'Harris (Harris corner detector ou Harris detector) est un algorithme classique pour la détection de coins. Nous ne vous demandons pas de réimplémenter Harris, vous pouvez utiliser ce code Matlab: harris.m. Ne vous souciez pas de la détection de coins sur plusieurs échelles -- faites-le sur une seule.

Implémentez la répression maximale non adaptative (Adaptive Non-Maximal Suppression, voir l'article). L'idée est de retirer certaines caractéristiques précédemment détectées. Cette partie de l'article pourrait sembler compliquée; nous vous suggérons de la relire plusieurs fois. Vous pouvez sauter cette étape pour commencer et simplement sélectionner un sous-ensemble aléatoire de coins.

Extraire un descripteur pour chaque point caractéristique

Sur chacun des points caractéristiques, vous devez extraire des groupements de pixels de 8x8. Il n'est pas nécessaire d'implémenter l'invariance en rotation. Notez qu'il est extrêmement important d'échantillonner ces groupements de pixels sur une plus grande fenêtre de 40x40 afin d'avoir un descripteur légèrement flou. N'oubliez pas de normaliser (avec le biais et le gain) les descripteurs (voir l'article).

Apparier ces descripteurs de caractéristiques entre les deux images

Vous devez utiliser les descripteurs pour trouver les paires de caractéristiques qui se ressemblent dans le but de les apparier. Vous pouvez trouver le code dist2.m utile pour le calcul rapide des distances. Pour le choix d'appariement, nous vous conseillons d'utiliser l'approche simple de Lowe sur 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.

Utiliser une méthode robuste (RANSAC) pour calculer l'homographie

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.

Automatic features matching

• Detecting corner features in an image
• Extracting a feature descriptor for each feature point
• Matching these feature descriptors between two images
• Use a robust method (RANSAC) to compute a homography

For the first three steps, we will follow the paper "Multi-Image Matching using Multi-Scale Oriented Patches" by Brown et al. but with several simplifications. Read the paper first and make sure you understand it. All of these steps are described further down.

Detecting corner features in an image

A corner feature in an image is a location where the horizontal and vertical gradients are both very strong. The Harris corner detector (or Harris detector) is an classic algorithm for corner detection. Re-implementing Harris is a thankless task – so you can use this Matlab code: harris.m. Do not worry about muti-scale feature detection -- just do it on a single scale.

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.

Extracting a feature descriptor for each feature point

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).

Matching these feature descriptors between two images

You will need to find pairs of features that look similar and are thus likely to be good matches. You may find dist2.m useful for fast distance computations. 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.

Use a robust method (RANSAC) to compute a homography

Once you have matched features, you can compute an estimate of the homography using the 4-point RANSAC algorithm described in class.

Crédits supplémentaires

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

• (jusqu'à 5 points) Utilisez vos propres images!
• (jusqu'à 5 points chacun) Mélange et composition: Utilisez des homographies pour combiner des images de façons intéressantes et créatives. Voici quelques suggestions:
  • Ajouter un grafiti 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 points) Meilleur mélange: Implémentez une pyramide laplacienne à plusieurs échelles. Comparez vos résultats avec ceux de la pyramide à deux niveaux.
• (jusqu'à 20 points) Panorama cylindrique à 360 degrés: Au lieu d'une mosaïque avec projection planaire, utilisez une projection cylindrique. Effectuez une déformation cylindrique sur toutes vos images d'entrées et assemblez les ensembles en utilisant uniquement des translations. C'est une façon de produire un panorama de 360 degrés. L'inconvénient de cette approche est la nécessité de connaître les paramètres intrinsèques de votre caméra (longueur focale et les coefficients de distortion radiale) ainsi que d'avoir pris les photos exactement horizontales (l'utilisation d'un tripod vous est suggérée).
• (jusqu'à 5 points) Ajoutez la détection de coins caractéristiques et leur description sur plusieurs échelles.
• (jusqu'à 10 points) Ajouter de l'invariance en rotation aux descripteurs.
• (jusqu'à 15 points) Implémentation d'une reconnaissance de panorama. Avec un ensemble d'images non ordonnées, dont certaines font parties d'un panorama, vous devez automatiquement découvrir les images formant le panorama sous-jacent et assembler ces images ensemble.

Bells and Whistles

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

• (up to 5 points) Use your own images!
• (up to 5 points each) Blending and Compositing: 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: Implement multi-scale Laplacian pyramid blending. Compare it with just a two-level pyramid.
• (up to 20 points) 360-degrees cylindrical panorama: Instead of a planar-projection mosaic, do a cylindrical projection instead. Perform a cylindrical warp on all your input images and stitch them together using translation only. This is one way to produce a full 360 degree panorama. The downside is that this method places more requirements on your camera (you need to know the focal length and radial distortion coefficients), and your data (the images have to be exactly horizontal -- use a tripod).
• (up to 5 points) Add multiscale processing for corner detection and feature description.
• (up to 10 points) Add rotation invariance to the descriptors.
• (up to 15 points) Implement panorama recognition. Given an unordered set of images, some of which might form panoramas, you need to automatically discover and stitch these panoramas together.

Livrables

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.

Plus précisément, la page devrait:

• Expliquer les algorithmes que vous avez implémentés. Illustrez toutes les étapes de l'algorithme.
• Montrer vos résultats sur les trois ensembles de photos dans le fichier images.zip. Pour les deux premiers ensembles ("panorama1" et "panorama2"), vous devez utiliser toutes les images. Pour "panorama3", utilisez 1/3 ou 1/2 des images. Attention, les images n'ont pas été prises avec un trépied.
• Si vous voulez expérimenter avec la projection cylindrique et que vous ne voulez pas prendre les images vous-mêmes, essayez avec les images dans ce fichier. Les distances focales des images sont disponibles dans l'entête EXIF de ces fichiers.
• Expliquer vos résultats.
• Expliquer les crédits supplémentaires que vous avez implémentés. Illustrez ces explications. Aussi, si cela s'applique, montrez correctement le "avant" et le "après".

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

• Votre rapport en format HTML dans un dossier tp4/web. Vos images doivent être dans un dossier tp4/web/images.
• Votre code matlab doit être dans un dossier tp4/code. De préférence, ne pas inclure les images que vous avez utilisées pour produire vos résultats dans ce dossier dans le but de ne pas alourdir le fichier.

Finalement, veuillez téléverser votre fichier tp4.zip sur pixel (http://pixel.fsg.ulaval.ca) avant la date limite. Bien entendu, 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 en tant que tel, envoyez vos questions à l'adresse courriel du cours.

Deliverables

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.

More precisely, the webpage should:

• Explain the algorithm you have implemented. Illustrate every step of the algorithm.
• Show your results on the three photo sets in the file images.zip. For the first two sets ("panorama1" and "panorama2"), you must use all the images. For "panorama3", use 1/3 or 1/2 of the images. Warning: the images were not taken with a tripod.
• If you want to experiment with cylindrical projection but don't want to capture your own images, use this set, where the images have their EXIF fields that you can use to look up the focal lengths.
• Explain your results.
• Explain all the bells and whistles you have implemented. Try to illustrate these explanations. Also, if applicable, show correctly the "before" and "after".

For this homework, you must create a tp4.zip file. In this file you'll put:

• Your report in the HTML format inside a folder named tp4/web. Your images for this web page should be inside a folder named tp4/web/images.
• Your matlab code should be put inside the folder tp4/code. Please do not include the images you have used to produce your results inside this folder.

Finally, you should upload the file tp4.zip on Pixel (http://pixel.fsg.ulaval.ca) before the deadline. Naturally, the late submission policy in the course plan will be applied. For any question regarding the submission process or the homework as such, send your question to the course's email address.

Évaluation

Ce travail est évalué sur 100 points. La répartition des points va comme suit:

• (50 pts, 35 pour les étudiants gradués) pour la partie 1: l'implémentation d'une mosaïque de photos avec appariement manuel (code, résultats, explications).
• (50 pts, 35 pour les étudiants gradués) pour la partie 2: l'implémentation d'assemblage de photos avec appariement automatique (code, résultats, explications).
• (N pts) pour les crédits supplémentaire. Rappel: les étudiants gradués doivent livrer au moins 30 pts de crédits supplémentaires.

Evaluation

This assignment is evaluated on 100 points, as follows:

• (50 pts, 35 pts for graduate students) for part 1: manual images stitching (code, results, explanation).
• (50 pts, 35 pts for graduate students) for part 2: automatic images stitching (code, results, explanation).
• (N pts) for any bells and/or whistles you've added in. Reminder: graduate students must add to their assignment at least 30 pts worth of bells and whistles.

Liens rapides

• Ébauche de page web;
• "Multi-Image Matching using Multi-Scale Oriented Patches" par Brown et coll.;
• Détecteur d'Harris;
• Distance euclidienne rapide;
• Images pour panorama.

Quick links

• Webpage template;
• "Multi-Image Matching using Multi-Scale Oriented Patches" by Brown et al.;
• Harris detector;
• Quick euclidean distance;
• Images for panorama.

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!