Historical:SoC2007 project Feature Matching

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.

Image stitching is the process of combining multiple images to produce a panorama or a larger image. Computer software is often used to interpolate the final image where the component images are not in precise alignment. Image stitching can be performed in two steps. The first step refers to detecting the features which do not depend on scale, rotation and other parameters (invariant features) in the images that are going to be stitched. The second step is finding the correspondence between detected features in different pictures. The correspondence problem is to find a set of attributes in two images which can be identified as being the same. For panoramic images the proposed solution must be adapted to the problem. Using heuristic methods, such as EXIF timestamps or previously known approximate orientation of the images, results can be improved. The suggested solution needs to be robust and efficient.

Required knowledge or interest

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

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 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. Brown's paper is the starting point of the project.

Project parts short description

The first part of the matching will use a nearest neighbor 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 [2]. To implement this algorithm represents an advantage.It is saving time for implementation and testing.

Another part of the project 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:RANSAC 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.

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.

The nearest neighbour matching and RANSAC outlier pruning could be combined into an integrated algorithm that considers both the feature vector as well as the feature position at the same time. This requires knowledge of the focal length and distortion parameters of the images, which could be read from a lens database file. This combined algorithm could reduce considerably the time required for the feature matching.

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[4]. 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. For the normalization, a text file containing a list with camera parameters can be used. 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 heuristic methods has its own advantages:

• Speed of the feature/image matching;
• False matches can be better avoided.

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, passed as a parameter to the corresponding project method.

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

Schedule

Describing the parts of the project leads to the implementation schedule. The schedule I have in mind is based on the SoC schedule. There are 3 parts that need to be done:

1. Research of the needed algorithms
2. Implementation
3. Test and improvement

• April 9th - Start the research part
• May 14th - The implementation of the algorithms should start
• July 9th - Students upload code to code.google.com/hosting; mentors begin mid-term evaluations
• July 10th - Main testing and fine tuning the solution period.
• August 20th - Final report (Google Deadline for all student work)

Detailed timeschedule

The total amount of time allocated for project completion is about 20 weeks. This period of time will be divided corresponding to the three major parts of the project.

Also there will be some time left for unexepected things (2 weeks), meaning that 18 weeks will be reserved for the parts presented below. Also a weekly status report will be presented to the mentor. The day of the week must be settled together with him.

Research

   start date: April 9th
   duration: 6 weeks
   end date: May 13th

Planned actions:

• Getting used to panorama making and finding the associated problems in a practical way;
• Gathering representative test panoramas from the community;
• Reading scientific papers describing the problems encountered by other people and the way they solved them;
• Discussions with the mentor about the already existing code and ways to use or improve it;
• Interactions with the person responsible for the feature detection in order to make the projects work seamlessly together;
• Analyzing for a very detailed understanding of all the algorithms' implementations and ways of working with them. This stage represents the starting point of the part where the algorithms must be combined.

Implementation

   start date: May 14th
   duration: 9 weeks
   end date: July 9th

Planned actions:

• Phase A - Existing algorithms:
  • Using the existing RANSAC implementation available in hugin;
  • Using the existing cover tree implementation;
  • Adapting the existing algorithms for the project.

• Phase B - Heuristic algorithm:
  • Autopano and autopano-sift describe the way they use the EXIF information. This can be viewed as hints in the developing of the heuristic part.
  • For the beginning, the heuristic part must work on a low level. It must be a integral part of the project. This part must be modular built to allow future improvements.

• Phase C - Preparing the deliverables

Testing

    start date: July 10th
    duration: 4 weeks
    end date: August 5th

Planned actions:

• Using the existing SIFT and SURF test data. The project must work independently from the feature detection algorithm and must return valid output.
• Testing by using a large number of images and by offering the code for public review. It would be really helpful for us if people could try to use the existing application and could report whatever problems they might encounter. Working in an open-source environment: this represents a great advantage because more people can view the source codes and identify a larger number of errors (if the errors exist).
• Improving the code and the results.

In the open-source projects seems to be a never-ending process of software development, in which new features are added to the software and corrections are made. This process is not to be characterized as maintenance though and is analogous to what may be referred to as versioning (evolution). That is why, tests will be done also during the implementation part. To be able to get a correct evaluation and to have valid tests, a test set is going to be prepared at the beginning of the research part. This test set is going to contain images relevant for the project goal.

Note: All the dates are less exact, but the time frames allowed should indicate the way the project is about to be completed.

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

Mentor

• Pablo d'Angelo
• ?

Additional mentor

Being a graduate student of University of Applied Sciences Wiesbaden, Prof. Dr. D. Richter can also assist me in succesfully developing this project.

Students planning to apply

• Alexandru Paler
• Aman Parnami

Resources

• Fast nearest neighbour matching using cover trees