CS 143 / Project 2 / Local Feature Matching

In this project, I implemented harris corner detector, SIFT feature descriptor and normalized patch descriptor, and feature matching algorithm by using nearest neighbour distance ratio test. Local feature matching is done by first extracting interest points with harris corner detector, then calculate a SIFT descriptor for every interest points, and finally matching these interest points using their descriptors.

Getting interest points

I implemented harris corner detector by taking the following steps:

  1. Blur the image using gaussian filter with sigma1 = 0.5.
  2. Get partial derivatives of the image Ix, Iy along x, y using sobel filter.
  3. Calculate Ix*Ix, Ix*Iy, Iy*Iy and apply gaussian filter on them with sigma2 = 3.
  4. Generate the harris corner response image by using the formula in the slides with alpha = 0.04.
  5. Remove the interest points near the edge, so that there will be enough pixels for descriptors.
  6. Threshold the response image with threshold = 0.02.
  7. Perform non-maximum suppression using a 3x3 window.
  8. Return the maximum points as interest points.

The above parameters: sigma1, sigma2, alpha, threshold, and sliding windows size can have huge influence on the final result. After some experiments, I found the above values can produce reasonably well results as shown below.

Generating feature descriptors

I implemented two methods for generating feature descriptors, one is normalized patches and another is SIFT descriptor. For normalized patches, I just take the pixels in a square region around the interest points, normalize them, and use them as descriptors. For SIFT descriptors, I took the following steps:

  1. Get partial derivatives of the image Ix, Iy along x, y using sobel filter.
  2. Compute the magnitute image using Ix and Iy.
  3. Compute the gradient image using Ix, Iy and atan2, and map the gradients into angles.
  4. For each interest point, take the pixels around it according to feature width and compute SIFT descriptor for it by using the data from the magnitute image and gradient image.
  5. Normalize the SIFT descriptor.

According the results shown below, SIFT descriptor performs much better than normalized patches. For the baseline images, SIFT descriptor can achieve 51 total good matches and 6 total bad matches, while normalized patches can only get 15 total good matches, 6 total bad matches.

Feature width can also have impact on the results. According to experiments, feature width 16 can get 44 total good matches, 8 total bad matches, while feature width 32 can get 51 total good matches, 6 total bad matches.

Left: Normalized patches. Right: SIFT

Matching features

I implemented nearest neighbour ratio test for matching features. First I calculate distances for each feature descriptor in image1 to all the feature descriptors in image2, then for each feature descriptor in image1, if the ratio between two least distances with feature descriptors of image2 is less than 0.76, a correspondence is found.

The value of ratio can have huge impact on the result. If the value is increased, more wrong correspondence will be found. If the value is descreased, less correct correspondence will be found.

Other results

According to results, if the scale or orientation of the two images differs greatly, the results wouldn't be ideal.