Project 2: Local Feature Matching

Matches by the SIFT like pipeline on two images of Notre Dame.

Problem description

In this project we attempted to build a SIFT-like pipeline for matching feature points between images. In order to do this we had to implement:

  1. Finding interest points
  2. Constructing local features
  3. Matching the features

More information can be found in the project spec here



Finding Interest Points

Circled corners after non-max suppression.

I used a the Harris corner detector to detect corners in the image and then extracted maximum points to be used as interest points. More information on calculating the Harris corners can be found here on slide 7. The method used to detect Harris corners in my code uses the longer/clearer method of calculating derivatives and Gaussian blurring described at the above link. After calculating the Harris values I then performed non-maximum suppression by taking the max over a small neighborhood of pixels (3x3).



Extracting SIFT like features

Extracting SIFT like features is simple if you follow the basic recipe:

  1. Compute the direction of the gradient at each pixel in the image
  2. Create a grid of 4x4 histograms with 8 bins each for each interest point
  3. Iterate through the pixels in the local neighborhood of each interest point and add their magnitude (of the gradient) to the bin that is the closest direction match
  4. Compress the histograms into a single 128 dimensional vector
  5. Normalize this vector
  6. Profit

Following this method you end up with a feature for each interest point

Matching features

Matches between interest points in two images of Notre Dame (n=100 points).

For matching features we calculated euclidean distance between all pairs of features (128 dimensional vectors). We then sorted the points by relative distance between their features (closest being the best) and took the ratio of the top two matches for each point. If this ratio is high (near 1) then the best two matches are similar "distances" away indicating that this point is not unique and should not be used as an interest point. On the other hand points that had a small ratio between their top two contestants (near 0) are good interest points. From there we pick the top n matches sorted by the lowest ratio.

Accuracies

Image name Accuracy for top 100 points Accuracy for top 200 points Accuracy for top 500 points
Notre Dame 94% 86% 60%
Mount Rushmore 84% 61% 33%
Episcopal Gaudi 4% 3% 2%

NOTE: Higher scores were achieved for Episcopal Gaudi when we used the image patch as the feature or when we increased the size of the non-max neighborhood, but the numbers in the table should be representative of the default accuracy when you run this pipeline.