SoC2007 project Feature Matching

From PanoTools.org Wiki
(Difference between revisions)
Jump to: navigation, search
(Tasks)
Line 2: Line 2:
 
This is a [[SoC2007_projects | Google Summer of Code project]]. Its goal is to develop a robust and efficient matching method of local image features. The image features detection is treated by another project [[SoC2007_project_Feature_Descriptor|Feature Detection]].
 
This is a [[SoC2007_projects | Google Summer of Code project]]. Its goal is to develop a robust and efficient matching method of local image features. The image features detection is treated by another project [[SoC2007_project_Feature_Descriptor|Feature Detection]].
  
==Tasks==
+
==Details==
  
* Implementation of the matching step, including geometry based outlier pruning (for example using RANSAC) and nearest neighbour matching, possibly using a fast algorithm such as cover trees. For the panoramic imaging use case, several heuristics could be used to improve the matching behaviour, including using the EXIF timestamps, or previously known approximate orientation of the images. The source code must be licensed under the GPL license.
+
The project title is "Automatic feature matching for panoramic images". It is a logical follow-up of the "Automatic feature detection for panoramic images". The output of the first phase will be part of the input of the second set.
 +
The results of the first phase are the extracted image features. These features are presumed to be invariant. Using this features, the second step, the project I am applying for, will stitch the images together by matching the points between the images.
 +
 
 +
Standard algorithms and data structures combined with heuristic methods will form the core of the suggested project solution.
 +
 
 +
The Recognizing panoramas paperwork written by M. Brown and D.G. Lowe [http://www.cs.ubc.ca/~lowe/papers/brown03.pdf] describes the process of panorama creation from the algorithms' perspective.
 +
The first step implies that the RANSAC algorithm is used to compute the matches between the images. The following step is to compute if the matches are really correct by using a probabilistic model, also described in the above mentioned document. The third step is to join the images one by one. The result image that is going to be joined is the one with the most matches available.
 +
 
 +
The method described in Brown's paper refers to noise-proof images and it avoids working with images that don't belong to panoramas.
 +
I consider Brown's paper the starting point of the project.
 +
 
 +
===Project parts short description===
 +
 
 +
The first one is  RANSAC (Random Sample Consensus Algorithm). This is an algorithm used for robust fitting the models in the presence of many data outliers.
 +
The wikipedia[http://en.wikipedia.org/wiki/RANSAC] article describing this algorithm is offering its pseudo code. There is also a paper[http://www.tu-chemnitz.de/etit/proaut/paperdb/download/fischler81.pdf] describing this algorithm which offers a helpful and proper understanding and implementation
 +
 
 +
Another part of the matching will use a nearest matching algorithm, more precisely cover trees. A cover tree is a data structure helpful in calculating the nearest neighbor of points given only a measure. There are papers documenting this data structure and the code implementation [http://hunch.net/~jl/projects/cover_tree/cover_tree.html]. To implement this algorithm represents an advantage.It is saving time for implemetation and testing.
 +
 
 +
Cover trees together with RANSAC can return good results, these results however can be improved by using heuristics. Image stitching can be improved by using information that is associated with the images. This information can be found in the EXIF structure that many cameras can append to the shots taken. There are some habits involved with taking panorama images. Panoramas can be built out of multiple images that are organized in one or multiple rows. Still some panoramas are difficult to automatically stitch because of the similarity between the feature points. That is why, knowing or assuming the order the images were taken can improve the results of this final and important stitching step. Determining the habits of photographers and introducing it in an algorithm is an important part of this project.
 +
 
 +
===EXIF heuristics===
 +
 
 +
There may be images that do not contain the EXIF information. If the EXIF data is present, the heuristics based on it can be applied. If it's not present, the application must neglect the heuristics step. Autopano Pro is making a normalization of the EXIF data between camera formats[http://en.wiki.autopano.net/FAQ_-_Frequently_Asked_Questions#EXIF_Data]. Since these cameras use different sensor types and lenses, their EXIF data cannot directly be compared. As an example, while the Canon G3’s focal length of its zoom lens is 7.2 – 28.8mm, its equivalent in 35mm terms is 35-140mm, so a 28.8mm shot on a Canon G3 is not a wide-angle, but a tele shot. If available, the EXIF data must be normalized. The generated image, after the stitching process is finished, should also contain a relevant EXIF information, based on the information gathered from the stitched images.
 +
 
 +
Heuristics can be improved by:
 +
* Panorama shooting - this can be done using methods that, when the process is completed, return images that contain overlapping fields. This represents a feature that heuristics can benefit from;
 +
* Using the focal distance and the camera orientation;
 +
* Knowing the time a picture was shot;
 +
* Using the information regarding the heuristic methods implied on the pages of the automatic panorama stiching tools, like autopano[http://www.autopano.net/] or autopano-sift[http://user.cs.tu-berlin.de/~nowozin/autopano-sift/]. These pieces of information are useful to create a better understanding of the starting point.
 +
 
 +
===Input parameters===
 +
The project is going to be implemented in a modular manor. It will be developed as a library and, due to this particular aspect, there will be two methods to pass the input parameters to the project:
 +
*a text file (maybe XML) containing a list;
 +
*an object list
 +
 
 +
Both lists will contain the features detected by the feature detector project.
  
 
==Expected result==
 
==Expected result==

Revision as of 14:30, 24 March 2007

Contents

Goal

This is a Google Summer of Code project. Its goal is to develop a robust and efficient matching method of local image features. The image features detection is treated by another project Feature Detection.

Details

The project title is "Automatic feature matching for panoramic images". It is a logical follow-up of the "Automatic feature detection for panoramic images". The output of the first phase will be part of the input of the second set. The results of the first phase are the extracted image features. These features are presumed to be invariant. Using this features, the second step, the project I am applying for, will stitch the images together by matching the points between the images.

Standard algorithms and data structures combined with heuristic methods will form the core of the suggested project solution.

The Recognizing panoramas paperwork written by M. Brown and D.G. Lowe [1] describes the process of panorama creation from the algorithms' perspective. The first step implies that the RANSAC algorithm is used to compute the matches between the images. The following step is to compute if the matches are really correct by using a probabilistic model, also described in the above mentioned document. The third step is to join the images one by one. The result image that is going to be joined is the one with the most matches available.

The method described in Brown's paper refers to noise-proof images and it avoids working with images that don't belong to panoramas. I consider Brown's paper the starting point of the project.

Project parts short description

The first one is RANSAC (Random Sample Consensus Algorithm). This is an algorithm used for robust fitting the models in the presence of many data outliers. The wikipedia[2] article describing this algorithm is offering its pseudo code. There is also a paper[3] describing this algorithm which offers a helpful and proper understanding and implementation

Another part of the matching will use a nearest matching algorithm, more precisely cover trees. A cover tree is a data structure helpful in calculating the nearest neighbor of points given only a measure. There are papers documenting this data structure and the code implementation [4]. To implement this algorithm represents an advantage.It is saving time for implemetation and testing.

Cover trees together with RANSAC can return good results, these results however can be improved by using heuristics. Image stitching can be improved by using information that is associated with the images. This information can be found in the EXIF structure that many cameras can append to the shots taken. There are some habits involved with taking panorama images. Panoramas can be built out of multiple images that are organized in one or multiple rows. Still some panoramas are difficult to automatically stitch because of the similarity between the feature points. That is why, knowing or assuming the order the images were taken can improve the results of this final and important stitching step. Determining the habits of photographers and introducing it in an algorithm is an important part of this project.

EXIF heuristics

There may be images that do not contain the EXIF information. If the EXIF data is present, the heuristics based on it can be applied. If it's not present, the application must neglect the heuristics step. Autopano Pro is making a normalization of the EXIF data between camera formats[5]. Since these cameras use different sensor types and lenses, their EXIF data cannot directly be compared. As an example, while the Canon G3’s focal length of its zoom lens is 7.2 – 28.8mm, its equivalent in 35mm terms is 35-140mm, so a 28.8mm shot on a Canon G3 is not a wide-angle, but a tele shot. If available, the EXIF data must be normalized. The generated image, after the stitching process is finished, should also contain a relevant EXIF information, based on the information gathered from the stitched images.

Heuristics can be improved by:

  • Panorama shooting - this can be done using methods that, when the process is completed, return images that contain overlapping fields. This represents a feature that heuristics can benefit from;
  • Using the focal distance and the camera orientation;
  • Knowing the time a picture was shot;
  • Using the information regarding the heuristic methods implied on the pages of the automatic panorama stiching tools, like autopano[6] or autopano-sift[7]. These pieces of information are useful to create a better understanding of the starting point.

Input parameters

The project is going to be implemented in a modular manor. It will be developed as a library and, due to this particular aspect, there will be two methods to pass the input parameters to the project:

  • a text file (maybe XML) containing a list;
  • an object list

Both lists will contain the features detected by the feature detector project.

Expected result

A desired result of the projects would be:

  • Standalone program for the feature matching part, which at the end should accept the features found by the automatic feature detection task. Preliminary studies can be done using the existing SIFT and SURF detector/descriptors.
  • Integration into hugin and a standalone executable similar to Autopano-sift or Autopano

Required knowledge or interest

  • signal or image processing background
  • C or C++ development skills.

Deliverables

By the end of the project, August 20th, the deliverables implementation and testing should be completed.

The deliverables will contain the following items:

  • a library like application that will use the matching feature method developed during the project development time;
  • a standalone application that will use the library;
  • the source control of the hugin application that is going to use the library;
  • all the source code will be commented and a documentation will be created using the doxygen tool, the hugin documentation tool of choice


Resources

Mentor

  • Pablo d'Angelo
  •  ?

Students planning to apply

Personal tools
Namespaces

Variants
Actions
Navigation
tools
Tools