CS 143 / Project 2 / Local Feature Matching

Overview from the project description: "The goal of this assignment is to create a local feature matching algorithm using techniques described in Szeliski chapter 4.1. The pipeline we suggest is a simplified version of the famous SIFT pipeline. The matching pipeline is intended to work for instance-level matching -- multiple views of the same physical scene."

Algorithm Explanation

How I Find Interest Points:

  1. Calculate the X and Y derivatives of the image using a Sobel filter.
  2. Take the second derivative of each initial derivative (again using a Sobel filter) and the derivative of the initial X derivative in terms of Y.
  3. Convolve the images from Step 2 with a Gaussian filter. I found that a 7 x 1 filter works well because it eliminates the keypoints that aren't important.
  4. Compute a scalar interest measure. I use the formula from the lecture slides with alpha set to 0.06.
  5. Set values less than the threshold to 0. I calculate the threshold to be 5% of the maximum value in the Harris corner matrix.
  6. Find local maxima. I compute the components using bwlabel and take the maximum value of each component.

Notre Dame Harris Corner Detector Output After Step 5

How I Create Feature Descriptors:

  1. For each keypoint, I start by calculating the sub-matrix around that interest point.
  2. Calculate the gradients (X and Y derivatives) of the pixels in the sub-matrix using a Sobel filter.
  3. Find the gradient orientation of the pixels in the sub-matrix by taking the arctan of the X and Y derivatives. NOTE: atan2 returns values between -pi and pi and my bin values go from 0 to 2pi so I subtract the absolute value of all the negative values from 2pi so that they can be put in my bins correctly.
  4. Find the gradient magnitude by taking the square root of the sum of each derivative squared.
  5. Diff the orientation sub-matrix with each bin value (bin values: pi/2, pi/4, 0,(7*pi)/4, (3*pi)/2, (5*pi)/4, pi, (3*pi)/4).
  6. For each pixel in the sub-matrix, find the three minimum values across the diff matrices.
  7. Find the correct quadrant of this pixel and add the magnitude of the pixel to the correct bins (see Optimizations for more details).
  8. Normalize the descriptor when all values have been added.
  9. Clip the values to .2 and renormalize.
  10. Add finalized descriptor to output list and go on to next keypoint.
  11. NOTE: If a pixel is close enough to the edge that part of the sub-matrix will be outside the frame of the image, the pixel is skipped and a feature of all zeros is added to the output list.

How I Match Features:

  1. I have a double "for" loop so that each feature is compared with every other feature.
  2. The comparison tracks the two closest features (their index and distance).
  3. The ratio of the distance to the two closest neighbors is calculated.
  4. If the ratio is below 0.8, the match is kept.
  5. The ratio is stored as the confidence and the current index and closest neighbor index are stored as the match.

Notre Dame with Matched Points, 75 Good Matches, 25 Bad Matches (209 good matches and 138 bad matches if not limited to 100)

Optimizations

I added a couple of optimizations to improve matches. When creating the descriptor, I sum the magnitudes in the bins instead of just keeping track of how many pixels fell into that bin. I also add a weighted pixel magnitude to the three best bins (100% of the magnitude goes in the best match and 20% in each of the next best matches). After creating the descriptor, in addition to normalizing it, I clip the values to .2 and renormalize. Each of these optimizations improved correct matches by about 5%.

Additional Sample Interest Points and Matching