CSE 455, Winter 2007

Project 3:  Feature Detection and Matching

Due:  Tuesday, Feb 20 by 11:50pm.

Synopsis

In this project, you will write code to detect discriminating features in an image and find the best matching features in other images.  You will use the Harris corner detector to find features and will try 2 variations of descriptors for matching.

To help you visualize the results and debug your program, we provide a working user interface that displays detected features and best matches in other images.  We also provide sample feature files that were generated using SIFT, the current best of breed technique in the vision community, for comparison. You are NOT expected to implement SIFT.

Description

The project has three parts. Firstly you will write the interest point detection function. Next you will form descriptor vectors for each your interest points. Finally, using the skeleton code provided, you will use your feature detector/descriptor to find matches in an image database, and evaluate the results.

NOTE that the Harris operator and the descriptors work with gray-scale images, so you'll need to convert. Both detection and description use gray tones. You'll also notice that the package we give you converts the input images to a different representation needed by the user interface. That part is done for you.

Interest point detection

In this step, you will identify points of interest in the image using the Harris corner detection method. 

For each point in the image, consider a 5 X 5 window of pixels around that point.  Compute the Harris matrix M for that point, defined as

M = Sum over x,y of w(s,y)[I_x^2 I_xI_y; I_xI_y I_y^2 ]
where the summations are over all pixels (x,y) in the window w.   For the weights w(x,y) you can use a 5x5 Gaussian mask, or the function ConvolveGaussian() provided in the skeleton code (try sigma = 3.0). Ix and Iy indicate the partial derivatives in x and y, which you can approximate using the Sobel operator. Alternatively, you can pre-smooth the image using ConvolveGaussian (sigma = 2.0), and then use supplied kernels dxKernel() and dyKernel() in the Convolve() function.

To find interest points, compute the corner response R
R = det M - k(trace M)^2
(Try k = 0.05)

Once you've computed R for every point in the image, choose points where R is above a threshold and is a local maximum in at least a 3x3 neighborhood.

You can test that your features are firing in sensbile locations by loading the featurefile generated from cse455 computeFeatures into the GUI (see Testing section)

If you wish to know the reasoning behind this corner detecting algorithm, read the Harris paper .

Feature description

Now that you've identified points of interest, the next step is to implement a descriptor for the feature centered at each interest point.  This descriptor will be the representation you'll use to compare features in different images to see if they match.

  1. First, try using a small square window (say 5x5) as the feature descriptor.  This should be very easy to implement and should work OK when the images you're comparing are related by a translation. Normalize the brightness values by dividing by the length of the descriptor vector (square root of the sum of the squares).
  2. Next, you will try to improve your descriptor and also use multiple sizes. The improvement is to sample the pixels from a blurred version of the image (use ConvolveGaussian()). You will try three different sizes in this step.
    1. Sample every other pixel from a 9 X 9 window about the feature point in the convolved image to obtain a 5 X 5 descriptor.
    2. Sample every other pizel from a 13 X 13 window about the feature point in the convolved image to obtain a 7 X 7 descriptor.
    3. Sample every other pixel from a 17 X 17 window about the feature point in the convolved image to obtain a 9 X 9 descriptor.
    Now, for every feature point, you will have 3 different descriptors. Try them in separate experiments for this part, but see the Extra Credit for ideas for modifications.

Feature matching

Now that you've detected and described your features, the next step is to match them, i.e., given a feature in one image, find the best matching feature in one or more other images.

Skeleton code has been provided that finds the SSD between all feature descriptors in a pair of images. The code declares a match between each feature and it's best match (nearest neighbour) in the second image. We have also provided ground truth homographies between the images, so that you can test how well your matching is working using cse455 testMatch (see Testing section).

Testing

Now you're ready to go!  Using the UI and C++ skeleton code that we provide, you can load in a set of images, view the detected features, and visualize the feature matches that your algorithm computes.

We are providing a set of benchmark images to be used to test the performance of your algorithm as a function of different types of controlled variation (i.e., rotation, scale, illumination, perspective, blurring).  For each of these images, we know the correct transformation and can therefore measure the accuracy of each of your feature matches.  This is done using a routine that we supply in the skeleton code.

  1. Download some image sets: leuven, bikes
    Included with these images are

    • SIFT feature files, with extension .key
    • database files used by the skeleton code, .kdb
    • homography files, containing the correct transformation between each pair of images, named HXtoYp where X and Y are the indeces of the images. For example, the transformation between img2.ppm and img3.ppm is found in H2to3p.

  2. Get access to FLTK. (Here are local copies for windows and linux, but see below about using it on linux.) **disclaimer** the skeleton code was designed to be used with FLTK-1. It has not been tested with FLTK-2.
    On Windows you'll need to install it yourself. Unzip it to the directory above your project directory; in other words if your homework is in C:\CSE455\project3, then put FLTK in C:\CSE455\fltk-1.1.4. Otherwise you'll have to change the project settings to look for the include and library files in the correct location.
    If you're using Linux on one of the CSE department machines, you don't need to download FLTK, since you can just use the libraries already installed and accessible from your machine at the location specified in the Makefile. If you already have FLTK or are installing it in /usr/local, here are fltk installation instructions and an alternate Makefile for the skeleton code.

  3. Download the C++ skeleton code:
    For Visual Studio 2003
    For Visual Studio 2005
    For Linux

After compiling and linking the skeleton code, you will have an executable cse455. This can be run in several ways:

To Do

The only code you need to write is for your feature detection and description methods. You only need modify the functions ComputeHarris() and ExtractDescriptor() at the end of the file "features.cpp". These functions are called from "dummyComputeFeatures()" in the same file. 

Extra Credit

If you get the regular work done the first week, you might want to try some creative additions for extra credit. Extra credit ideas include, but are not limited to: For extra credit parts, you may want to also try our other two image sets. graf; wall

What to Turn In

In addition to your source code and executable, turn in a report describing your experiments and results.  In particular:

This report can be a Word document or pdf document. Email Masa your writeup and your source code by Tuesday Feb 20 at 11:59pm. Please include "455 project 3" in the subject of the email. Please include your name in the name of your writeup file.