Overview

In this project I implemented a local feature matching algorithm which uses harris corener derector to find interest points and SIFT descriptor to describe local features. Except from the baseline implementation, I detected interest points at different scales and used laplacian of gaussian to find scale-invariant points.I also added a simple verification step to filter out outliers.

The detection accuracy on the Notre Dame picture is 99% percent when test ratio is 0.7. We can see that the only mistake point is actually a very close match.



Result of top 100 most confident local features, 99 are correct, 1 is wrong.

Interest point detection

I used harris coner detector as the base corner detector. As expirimented in the prject, for notre dame picture, if number of corners detected is less than 500, the result is poor because most strong corners are symmetric parts of the building. So there will be many similar points in the image.



Harris corner results with threshold = max harmonic mean * 0.01

To make detected interest points scale-invariant, I used a simplified version of harris-lapalcian detector, which searches for scale space extrema of a scale-normalized Laplacian-of-Gaussian. I used 8 scale levels, each is increased by 1.4 and 8 local scale levels, each is increased by 0.7.

  1. Use Harris dectector to detect interest points at each scale levels.
  2. For every detected points, compute it's LoG response at every local scales to check if each points attains an extremum at detected scale.
  3. Non-maximum suppression.
  4. Downsampling the image.
  5. Back to step 1.
Non-maximum suppression is done by selecting the maximum value of a sliding window. The window size is 0.02 of the image width and height.

Local Feature description

My implementation of SIFT descriptor mostly follows David Lowe's paper Distinctive image features from scale-invariant keypoints.The following is my steps of computing SIFT feature.

  1. Find the image patch around interest point accoring to feature width at the scale this point is detected.
  2. Compute gradient magnitude and direction of this patch.
  3. Use a gaussian to weight the magnitude.
  4. Decide the dominant direction. In each cell, put every pixel into 8 bins according to its direction relative to the dominant direction, weighted by it's magnitude.
  5. Normalize the feature vector to unit length. Chop off values over 0.2 and normalize again.
The feature width parameter has a big influence on the matching result. In the Notre Dame picture, the feature width with best matching result is 64.

Feature Matching

I used ratio test to find the match between two images. This method works fine but will allow many outliers exist. Setting the threshold higher will have move matches but also more wrong matches. Setting the threshold lower will allow less wrong matches, but the total number of matches is also reduced. I used an extra verification step to filter out most of the outliers.

In the simple verification step, for every matched points, I calculated the averge pixel distance between two matched points near this pixel. If the distance of this point is 1.5 greater than the averge distance, consider this point as a wrong match.



Result without verification
We can see that without verification, some points will match to points that are very far away from the correct location. For example, the blue and purple points in the right side of left figure matched to the left side of right figure. This is because these two places are symmetric in the image.

Other Results

  • Ferrari




  • House




  • Beaver




  • Triumphal arch




    The key points are too close together in third and fourth image so I can not use the matlab tool to collect ground truth. But we can see that most points are correctly matched.

    • Shortcomings

    The algorithm works fine with object scaling and rotation. But often has a poor result on images with multiple similar objects or with strong symmetric. Another shortcoming is that in order to have a optimal result, we have to change parameters like feature width, corner threshold and ratio test threshold. This work is time consuming and is not easy to do for people with limited knowledge about the algorithm.