Résumé

Maintenant que vous êtes en mesure de créer une mosaïque d'images à partir de points de correspondance (calculés manuellement), il est temps d'automatiser le processus et de développer une méthode de détection de points d'intérêt et d'appariement automatiques.

Overview

Now that you can create an image mosaic from a set of manually identified correspondance points, it is time to automate the process and implement a way to automatically detect and match interesting features in images.

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 point d'intérêt par une méthode automatique. Cette méthode peut être décrite en quelques étapes simples:

1. Détection de coins dans une image
2. Extraire un descripteur pour chaque point d'intérêt
3. Apparier les descripteurs entre les deux images
4. 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.

1. Détection de coins dans une image

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 qui l'implémente (voyez aussi la démo du détecteur de Harris sur PAX). 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.

Automatic features matching

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:

1. Detecting corner features in an image
2. Extracting a feature descriptor for each feature point
3. Matching these feature descriptors between two images
4. 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.

1. 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 code (see also the Harris detector demo on PAX). Do not worry about muti-scale feature detection: just do it on a single scale.

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.

2. Extraire un descripteur pour chaque point d'intérêt

Centrez une fenêtre de $40 \times 40$ autour du point d'intérêt (coin), et échantillonnez ensuite une petite image de taille $8 \times 8$. 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).

3. Apparier ces descripteurs de caractéristiques entre les deux images

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.

4. 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. Vous devez implémenter RANSAC vous-même (c'est très simple).

3. Extracting a feature descriptor for each feature point

On each feature points, extract axis-aligned $8 \times 8$ patches. Do not worry about rotation-invariance. Note that it’s extremely important to sample these patches from the larger $40 \times 40$ window to have a nice big blurred descriptor. Don’t forget to bias/gain-normalize the descriptors (see the article).

4. 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. 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. Note: you must implement RANSAC yourself (it's very easy).

Crédits supplémentaires

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

• (jusqu'à 20%) 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 et assemblez-les 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 trépied vous est fortement suggérée si vous voulez capturer vos propres images). Le répertoire « 3-ProjCylindrique » dans le fichier qui vous est donné contient deux séries d'images pouvant être utilisées pour cet exemple. Les distances focales des images sont disponibles dans l'entête EXIF de ces fichiers.
• (jusqu'à 5%) Ajoutez la détection de coins caractéristiques et leur description sur plusieurs échelles et démontrez son utilité.
• (jusqu'à 10%) Ajouter de l'invariance en rotation aux descripteurs et démontrez son utilité.
• (jusqu'à 15%) Implémentation de l'algorithme de 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 (comme dans cet article de Brown et Lowe).

Extra credit

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

• (up to 20%) 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). The "3-ProjCylindrique" folder in the file provided contains two image series you can used to perform this. The focal lengths are available inside the EXIF headers of the images.
• (up to 5%) Add multiscale processing for corner detection and feature description and demonstrate its usefulness.
• (up to 10%) Add rotation invariance to the descriptors and demonstrate its usefulness.
• (up to 15%) 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. This is described in this Brown and Lowe paper.

Comme lors des travaux précédents, celui-ci sera remis dans un format page Web et il 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.

Partie A (50% de la note totale)

• Réchauffement (20%) : décrivez brièvement votre approche et affichez le résultat de l'application des deux homographies H1 et H2 sur l'image pouliot.jpg.
• Appariement manuel (80% pour 4105, 60% pour 7105) : décrivez brièvement votre approche et affichez le résultat de votre algorithme de génération de mosaïques sur les 3 groupes d'images dans le répertoire « 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.
  Affichez les points que vous avez sélectionnés et illustrez les étapes de votre algorithme. Commentez vos résultats.
• (N%) Expliquer les crédits supplémentaires que vous avez implémentés. Illustrez ces explications. De plus, si cela s'applique, montrez correctement le « avant » et le « après » et démontrez l'avantage de l'approche que vous aurez essayée.

Partie B (50% de la note totale)

• Appariement automatique (80% pour 4105, 60% pour 7105) : décrivez brièvement votre approche et affichez le résultat de votre algorithme automatique de génération de mosaïques sur les 3 groupes d'images dans le répertoire « 2-PartieAutomatique ». Affichez les points appariés automatiquement, et illustrez brièvement les étapes de votre algorithme. Commentez vos résultats.
• Vos images (20%): affichez les résultats de votre algorithme automatique appliqué sur les deux scènes que vous aurez capturées vous-même. Affichez également les images individuelles ainsi que les points appariés automatiquement. Commentez vos résultats.
• (N%) Expliquer les crédits supplémentaires que vous avez implémentés. Illustrez ces explications. De plus, si cela s'applique, montrez correctement le « avant » et le « après » et démontrez l'avantage de l'approche que vous aurez essayée. Par exemple, si vous expérimentez avec la robustesse du descripteur, démontrez l'impact de ces modifications.

Idées pour les discussions

L'objectif des discussions dans vos rapports est que vous nous fassiez part de vos réflexions sur vos résultats. Tentez d'être précis(es) dans vos descriptions. Voici quelques idées :

• Commentez sur la qualité des résultats. Sont-ils à la hauteur de vos attentes? Y a-t-il des régions du panorama où les problèmes sont plus visibles?
• Quand ça fonctionne, commentez tout de même sur ce qui fait que ça fonctionne.
• Si vous avez rencontré des problèmes sur certaines scènes, décrivez ces problèmes et expliquez comment vous avez tenté de les résoudre. Tentez d'expliquer pourquoi ça fonctionne mieux sur certaines scènes plutôt que d'autres.
• Si vos algorithmes échouent sur certaines images, décrivez les problèmes et expliquez pourquoi ils surviennent selon vous;
• Décrivez, le cas échéant, les ajustements que vous avez apportés à l'approche proposée.

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.

Part A (50% of the total grade)

• Warmup (20%): briefly describe your approach and show the result of applying the two homographies H1 and H2 on the image pouliot.jpg.
• Manual matching (80% for 4105, 60% for 7105): briefly describe your approach and show the results of your mosaicking algorithm on the 3 image groups from the folder "1-PartieManuelle".
  • For images from "Serie1", use the points provided.
  • For the other sets, manually click on corresponding points.
  Show the points you have selected, and illustrate the steps of the algorithm. Explain your results.
• (N%) Explain all the extra credit you have implemented. Illustrate these explanations. Also, if applicable, show correctly the "before" and "after" and show the advantage of your approach.

Part B (50% of the total grade)

• Automatic matching (80%, 60% for grads): briefly describe your approach and show the results of your automatic mosaicking algorithm on the 3 image sets from the "2- PartieAutomatique" folder. Show the points that were matched automatically, and briefly illustrate the steps of the algorithm. Comment on your results.
• Your images (20%): show the results of you automatic algorithm applied on the two scenes you have captured yourself. Comemnt on your results.
• (N%) Explain all the extra credit you have implemented. Illustrate these explanations. Also, if applicable, show correctly the "before" and "after" and show the advantage of your approach. For example, if you experiment with improving the invariance of the descriptor, demonstrate the impact of this invariance on your results.

Ideas for discussions

The main objective is that you share your thoughts on your results with us. No need to write a novel, just try to be precise. Here are some ideas:

• Comment on the quality of the results. Do they live up to your expectations? Are there any regions of the panorama where the problems are more visible?
• If you have encountered problems on some scenes, describe describe these problems and explain how you tried to solve them. Try to explain why it works better on some scenes than others.
• If your algorithms fail on some scenes, describe the problems and explain why they occur in your opinion;
• Describe, if applicable, the adjustments you made to the proposed approach.

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 et votre page principale doit être tp4/web/index.html.
• Votre code doit être dans un dossier 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.py, main_manuel.py, main_automatique.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 report in an HTML format inside a folder named tp4/web. Your images for this web page should be inside a folder named tp4/web/images and your main page should be tp4/web/index.html.
• Your code should be put inside the folder tp4/code. Do not include the images you have used to generate your results inside this folder, as this will likely generate huge files.

You should clearly identify the "entry points" to your code (ex: main_warmup.py, main_manual.py, main_automatic.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!