CPSC 525: Homework 2

Instructor: David Lowe
January 2014.

Due Date: Tuesday, Feb 11, 2014.

The purpose of this assignment is to learn how to perform object recognition and image matching using local invariant features.

The assignment

There is some test data and a sample Matlab program in the following zip file: hw2.zip. See the README file in that directory for further information. This directory contains some sample images and files of SIFT features that have been precomputed for the images.

The sample program draws lines connecting keypoint locations in one image to their matching location in the other. The matches are identified by finding the 2 nearest neighbors for each keypoint from the first image among those in the second image. A match is selected for display only if the distance to the nearest neighbor is less than 0.8 times that to the second-nearest neighbor.

Many of the matches produced in this initial selection are wrong. Your task to to design and implement methods for removing the incorrect matches while leaving as many as possible of the correct ones. If only correct matches are left, then recognition has been achieved.

  1. You will implement the method know as semi-local constraints. This assumes that correct matches will usually have other nearby features that provide consistent matches, while incorrect matches are unlikely to be consistent with many neighbors. By consistent, we mean that the matches vote for the same object and same object pose (location, scale, and orientation).

  2. To implement semi-local constraints, you should consider separately each match from the first image to the second image. For each such match, check the N other closest matched features in the first image (close in terms of their image location in the first image), and check that at least K of them are consistent with the first match. Typical values to try might be N of 10 and K of 3, but you should experiment with other values.

  3. You will need to be able to compare orientations correctly. Start by writing a function AngleDiff(angle1, angle2) that returns the unsigned difference between two angles measured in radians. For example, AngleDiff(-pi, 3*pi) should return 0, and AngleDiff(-pi/2, pi) should return pi/2.

  4. To check whether two matches are locally consistent, you should use the row, column, scale, and orientation parameters of each keypoint. The row and column specify the location of the keypoint in the image. The orientation gives its orientation in radians from -PI to PI. The scale is proportional to the size of the keypoint region in the image (the units do not matter as only relative scale is used).

    For example, if the keypoints in the first matched pair have an orientation difference of 0.8 radians, that means the object has rotated by 0.8 radians from one image to the next. Therefore, any other consistent matches should also have an orientation difference close to this (say within pi/8 radians). In the same manner, the ratios of scales for each match should be similar (say within a factor of 1.5). Also check that the separation of points in each image is consistent with the scale change. Describe the checks that you perform in your report.

Test your results on the three given pairs of images. You should also write a short report of about 1 page that describes your approach to checking for consistency, the parameter values that you found to work well (the same parameters should be used for all images), and your conclusions. As no ground truth is given to identify correct matches, you may need to just count the obvious errors by hand. Include a commented copy of your source code, which should include a definition of AngleDiff.