Lucas Morduchowicz lmorduch

CS 143 / Project 2 / Local Feature Matching

My implementation of this project is fairly close to the baseline implementation. I have not implemented bells and whistles. I have however tried to adjust parameters within the baseline implementation to achieve a reasonably good matching score on the images provided. The following details my implementation and design choices at each step in the SIFT pipeline.

• Keypoint Detection

  First, I initialized my parameters. I decided to set the alpha used in the harris corner detection formula to .6, set my threshold for good keypoints to .00002, and to convert the image into a grayscale double matrix.

  Then I computed the gradient of the image in the x and y direction using the gradient function. I then computed the outer products of these (horizontal gradient squared, vertical gradient squared, and horizontal times vertical gradient). Afterwards, I filtered the products using a gaussian filter. Originally, I had it set to the default size (3x3) and default sigma. This was giving me about 44% matches for the top 100 confidence results. After testing extensively, I discovered that increasing this size to (6x6) and the sigma to .3, I could improve my matches to about 66%.

  After filtering the outer products of the gradients, I computed the harris result for the entire image by multiplying the filtered outer products as follows: gixs.*giys-(gixy.^2) - (alph * (gixs+giys).^2) where gixs is the gaussian filtered image of the horizontal gradient squared, giys is the gaussian filtered image of the vertical gradient squared, and gixy is the gaussian filtered image of the horizontal gradient times the vertical gradient

  After getting the harris corner detector result from the step above, I thresholded my results to only give my points with a harris result greater than .00002, a value I came to after extensive testing. Originally, I chose .00005, but reducing the value increased my match percentage for the top 100 confidence matches from 66% to 78%.

  Finally, I implemented non-maxima suppression using bwconncomp to find connected components. Once I had connected components, I found the max harris result within each component and choose that as the keypoint to return, throwing away the rest of the keypoints within that component. I also suppressed keypoints on the edges of the image.

• Feature detection

  My implementation interates over detected interest points. At each interest point, I iterate over a 4 x 4 grid of cells, each with size feature_width/4 * feature_width/4, with the keypoint in the center. I take the gradient of each cell in the x and y direction, then use the atan2 to find the direction of the gradient at each pixel within the cell.

  For each pixel, I look at the results of atan2 and divided them into 8 bins representing directions. Once I figured out which direction the pixel was pointing in, I incremented the bin by the magnitude of the gradient at that pixel. E.G. If the result was somewhere between 0 and pi/4, I incremented the corresponding bin by the magnitude of the gradient at that pixel.

  Once I had done this for all 16 cells, I normalized the feature by taking the square root of the result squared to account for variance in brightness. After the normalization, I placed the feature in the result set for the function.

• Feature Matching

  For feature matching, I implemented a simple ratio test.

  For each feature in list 1, I iterated over all features in list 2. For each pair, I computed the euclidean distance between the two features, saving the two smallest distances found for any feature in list 1.

  I took the nearest neighbor distance ratio to be the distance to the closest neighbor divided by the distance to the second closes neighbor.

  I then set the match for the feature in list 1 to the closest neighbor found, with a confidence equal to 1 divided by the nearest neighbor distance ratio.

  Finally, I sorted the list of all matches by confidence in descending order.

• Putting it all together

  In proj2.m, I modified close to nothing- the only thing I changed was to limit the number of matches shown to the top 100 confidence matches.

Results in a table

The following is a gallery of my results. Originals are in data.