CSE 455 Autumn 2014: HW5
Feature Detection and Matching

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 a color descriptor 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.

Software

We are providing the UI and C++ skeleton code so that you can load in a set of images, view the detected features, and visualize the feature matches that your algorithm captures.

1. Image sets:

   Download image sets: leuven and bikes. Included with these images are

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

2. FLTK library, GUI and the skeleton code:

   Fast Light Toolkit is a cross-platform C++ GUI toolkit for Unix/Linux (X11), Microsoft Windows® and MacOS X®. FLTK provides modern GUI functionality without the bloat and supports 3D graphics via OpenGL® and its built-in GLUT emulation. For more information visit FLTK website. The GUI we provide was developed using FLTK-1.

   • Windows users: Download GUI and the skeleton code.
   • Linux users: Download GUI and the skeleton code.

     If you are using one of the department servers, the FLTK library is installed on most of them and you don't need to do anything.If you are using your own machine, you need to install FLTK. You can install a fresh copy from the FLTK website but we didn't test the skeleton code on the latest version. Here is the version we used in development: local copy of FLTK. 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. Running the program

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

   • cse455
     with no command line options starts the GUI. To use the GUI:

     • Load a query image: File > Load Query Image
     • Load its corresponding feature file: File > Load Query Features
     • Load feature database: File > Load Image Database
     • You can select a subset of features to use in the query by right clicking on a point and dragging over a rectangular region. You can also select/deselect all features: Image > Select All Features
     • You can then search the database for the image which best matches the query features: Image > Perform Query

   • cse455 computeFeatures imagefile featurefile [featuretype]
     uses your feature detection routine to compute the features for imagefile, and writes them to featurefile. featuretype can be used to specify different types of features to compute (optional). We suggest that you name feature files as feature1.f, feature2.f, ..., feature6.f for the convenience of database query, otherwise you should change the link in the corresponding database file.

   • cse455 testMatch featurefile1 featurefile2 homographyfile [matchtype]
     uses your feature matching routine added to "dummyMatchFeatures" function in "features.cpp" (default is SSD) to match the features in featurefile1 with the features in featurefile2. homographyfile contains the correct transformation between the points in the two images, specified by a 3-by-3 matrix. matchtype can be used to specify different matching algorithms to use (optional). This function returns the percentage of correct matches (number of inliers / number of feature matches).

   • cse455 testSIFTMatch featurefile1 featurefile2 homographyfile [matchtype]
     is the same as above, but uses the SIFT file format.

   • cse455 benchmark imagedir [featuretype matchtype]
     tests your feature finding and matching for all of the images in one of the four above sets. imagedir is the directory containing the image (and homography) files. This command will return the average percentage of correct matches when matching the first image in the set with each of the other five images.

What You Should Do

The project has three parts. First, you will write the interest point detection function. Next you will form descriptor vectors for each of 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.

The Harris operator works with gray-scale images, so the input images will need to be converted. The skeleton code has the function ConvertToGrey in features.cpp to convert the images to grayscale. The following instructions are guidelines; you should feel free to experiment, too.

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.

Interest point detection

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

1. Convert the RGB image into a grey-level image.
2. Apply the following 9 x 9 Gaussian filter to the whole image

   0.0008 0.0018 0.0034 0.0050 0.0056 0.0050 0.0034 0.0018 0.0008
   0.0018 0.0044 0.0082 0.0119 0.0135 0.0119 0.0082 0.0044 0.0018
   0.0034 0.0082 0.0153 0.0223 0.0253 0.0223 0.0153 0.0082 0.0034
   0.0050 0.0119 0.0223 0.0325 0.0368 0.0325 0.0223 0.0119 0.0050
   0.0056 0.0135 0.0253 0.0368 0.0417 0.0368 0.0253 0.0135 0.0056
   0.0050 0.0119 0.0223 0.0325 0.0368 0.0325 0.0223 0.0119 0.0050
   0.0034 0.0082 0.0153 0.0223 0.0253 0.0223 0.0153 0.0082 0.0034
   0.0018 0.0044 0.0082 0.0119 0.0135 0.0119 0.0082 0.0044 0.0018
   0.0008 0.0018 0.0034 0.0050 0.0056 0.0050 0.0034 0.0018 0.0008

   Calling the function ConvolveGaussian(greyImage, img_blurred, 2.0f) given in "features.cpp" should blur greyImage with this mask to img_blurred.
3. For each point in the image, consider a 5 X 5 window W of pixels around that point. Compute the Harris Matrix M for that point, defined as
   
   where the summations are over all pixels (x,y) in the window W. (See slide 18 of Harris lecture.) To find interest points, compute the corner response R.
   
   (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 a 3x3 neighborhood. (Start with a threshold of 0.001, but this is a sensitive threshold, so you need to experiment.) You can test that your features are firing in sensible locations by loading the featurefile generated from cse455 computeFeatures into the GUI (see Testing section).

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. For the feature description, please go back to RGB color space.
2. Take a 45 x 45 window centered at a feature point.
3. Divide the 45 x 45 window evenly into 9 x 9 = 81 squares of size 5 x 5. For every 5 x 5 square, apply the following 5 x 5 mask

   0.0369 0.0392 0.0400 0.0392 0.0369
   0.0392 0.0416 0.0424 0.0416 0.0392
   0.0400 0.0424 0.0433 0.0424 0.0400
   0.0392 0.0416 0.0424 0.0416 0.0392
   0.0369 0.0392 0.0400 0.0392 0.0369
   

   to each color channel. A 3-dimensional vector is obtained from summing up all entries in this 5 x 5 square for each color channel separately. Concatenating all 81 such 3-dimensional vectors from all individual 5 x 5 squares in the whole 45 x 45 window, a 9 x 9 x 3 dimensional vector is constructed. Now take that 243-dimensional vector and produce a 243-dimensional normalized feature vector, which is the original feature vector divided by the L2 norm of the original vector. The L2 norm of a vector x = (x1,...,xn) is the square root of the sum of the squares of its components, ie. L2-norm = sqrt(Σ xi^2, i=1,...,n).

4. Get feature vectors for all other feature points in the same way and write them to a data file. (Note: the skeleton code does the I/O for you.)

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 another image.

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 its 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 Software section).

Extra Credit

• Try to develop a better descriptor that might select the best scale at an interest point, use multiple scales at once, or be invariant to rotations. In order to demonstrate this work, please try other two image sets also graf; wall. You need to change necessary lines from the "computeFeatures" function in "features.cpp" file to call your own function. You can copy "dummyComputeFeatures" and "ExtractDescriptor" methods in "features.cpp" file and use them as skeletons to start writing your own descriptor.
• Try to develop a better evaluation of matching between different feature points. You may declare no matches found for a feature point if (score of the best feature match)/(score of the second best feature match) is larger than a threshold. However, please make sure there are at least 20 matches found between images for comparison. Also, even if you've implemented another evaluator, the evaluation function in the skeleton code should also be enabled in your program and matching results coming from the original evaluation function should be included in the report. You need to change necessary lines from the "matchFeatures" function in "features.cpp" file to call your own function. You can copy "dummyMatchFeatures" method in "features.cpp" file and use it as a skeleton to start writing your own matching algorithm.

What You Should Turn In

Download the .doc template for the report here. You are free to use other text processing tools like latex etc, however make sure that you have the same sections in your report.

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

• Describe your feature descriptor in enough detail that someone could implement it from your write-up. If your descriptor is exactly the one given in the assignment, you may say so.
• Explain why you made the design choices that you did.
• Report the performance on the provided benchmark image sets. Show the data for each of the pairs. Results quality are expected to decline for higher image numbers; consider graphing this decline.
• Compare the performance of the simple window descriptor and SIFT features (provided)
• Describe strengths and weaknesses
• Describe any extra credit items that you did (if applicable)

This report can be a Word document or PDF document.

Please keep your homework package in reasonable size. Your working folder for this project can be very large, so please don't upload everything. Make sure that Debug folders (including the one in ImageLib folder), images, descriptor files and cse455.ncb are not included. It is highly recommended that your code folder is smaller than 1MB. You can upload only the files you've changes, such as "features.cpp". Please put the images you want to show in your report, do not upload them separately.

Evaluation

• Working implementation of all the required parts: 11 points
  • Harris operator: 4 points
  • Feature descriptor: 5 points
  • Feature matching: 2 points
• Quality of code including code structure, comments and documentation: 4 points
• Completion and quality of the report: 5 points
• Qualilty of results: 5 points
  • Harris operator: 2 points
  • Simple descriptor: 3 points
• Extra credit:
  • Advanced way of match finding: 3 points
    e.g. thresholding the ratio between smallest and second smallest distance of feature vectors as described on instruction page. Please show results based on both SIFT and your feature.
  • Advanced descriptor: Rotation invariant descriptor only: 7 points
  • Advanced descriptor: Rotation and scale invariant descriptor: 10 points
    In order to show your advanced descriptor, you need to demonstrate convincing image and numerical results on graf and wall images.

Dropbox

Upload your report and code to the homework dropbox HERE.

Homework is due on November 18 (Tuesday) by 11:59 PM. Please plan your work early. You can submit until November 22 but you will lose 5% of your grade for every late day.

This is a one-person assignment. You may discuss it, but please turn in your own individual work.