Historical:SoC 2008 Feature Matching

Feature Matching project

Hugin integration

Pablo is going to help us here.

Application

Problem

In a panorama photo stitcher software, an automatic feature matching algorithm needs to find the correspondence between feature points and images. The problem is to develop a robust and efficient matching algorithm.

Solutions

Using nearest neighbor matching and RANSAC outlier with EXIF heuristics seem to increase robustness and efficiency of the feature matching method.

Although the complexity of matching n images with a straight-forward approach is O(n^2), we can reduce it to O(nlogn) by using a nearest neighbor algorithm [1]. Cover tree [2] is a remarkably fast nearest neighbor algorithm, which have documentation and implementation in [3].

RANSAC (Random Sample Consensus Algorithm) is an iterative method for outlier pruning. Fischler and Bolles propose and discuss RANSAC model fitting with image analysis in [4]. There is also an overview and pseudo-code for RANSAC in wikipedia [5].

EXIF heuristics can also improve the efficiency and effectiveness of the method. If available, the time a picture was taken, its filename (like DSC_0001.jpg), camera orientation, etc. are useful informations which can both decrease the running time and increase its correctness. Geolocation information in EXIF format also give clues whether or not images belong to the same panorama. "Exchangeable image file format:wikipedia" document [6] gives details about the format.

Performance Measures

We need to be sure that applied algorithms really improves robustness and speed of the method. Therefore, some comparisons should be made on a dataset, which we manually give matching feature points. Correctly retrieved matching points (hit), retrieved but not correct ones (false positive), and the matching points we could not retrieve (miss) could be plotted to a ROC curve. By this way, we can improve the performance by selecting the right methods and adjusting parameters to the value which give highest hit rate. For example, we can compare k-d trees, which Brown and Lowe used in [7], with cover trees. Running time of the algorithm is also important for our purpose. This can be calculated both by analyzing the complexity of the algorithms, and recording running times in each test.

Time Schedule

I plan to invest at least 30h or more per week to this project. I will be on vacation for 4-5 days, and another week I will probably be busy with moving my house. But I will balance it by working hard in order not to fall behind schedule. My planned actions will be as follows:

• Before May 26
  • Getting to know the developers, mentors, reading documentation,
  • Getting used to hugin/panotools, your coding strategy, bug reporting and fixing,
  • Finding and/or generating representative datasets for testing and evaluation purposes,
  • Reading scientific material, understanding all the concepts of matching and pruning procedures,
  • Beginning documentation,
  • Deciding inputs and outputs of the project,
  • Making contact with the developer of Feature Detection part,
  • Making a survey to learn the habits of photographers for effective EXIF heuristics.

• May 26 to July 7-14 (midterm evaluations)
  • Combining algorithms by using and adapting existing cover tree and RANSAC algorithms,
  • Adding heuristic to implementation, test if it really improves efficiency and effectiveness,
  • Preparing the libraries, standalone applications,
  • Getting ready for mid-term evaluations.

• July 15 to August 11-18 or September 1 (final evaluations)
  • Testing with a large number of images, offering code for public review,
  • Improving heuristics and other parts with respect to the feedbacks and test results,
  • Completing documentations, preparing libraries, applications, etc.
  • Getting ready for final evaluations.

Deliverables

• A library for automatic feature matching which uses proposed algorithms,
• Documentation created by using the doxygen tool,
• Comparisons of the algorithms, test cases for running time analysis,
• A standalone application (works in cross-platform) that uses the library,
• Fully-commented source codes both for the library and Hugin application that uses the library.

Biography

[1] J.Beis, D. Lowe. "Shape indexing using approximate nearest-neighbor search in high-dimensional spaces." [2] A.Beygelzimer, S.Kakade, J.Langford. "Cover Trees for Nearest Neighbor." ICML 2006. [3] http://hunch.net/~jl/projects/cover_tree/cover_tree.html [4] M.A.Fischler, R.C.Bolles. "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography." Comm. of the ACM 24 [5] RANSAC, http://en.wikipedia.org/wiki/RANSAC [6] http://en.wikipedia.org/wiki/Exchangeable_image_file_format [7] M.Brown, D.G.Lowe. "Recognizing Panoramas." [8] Personal website, http://cs.bilkent.edu.tr/~onurk/