CS 143 / Project 2 / Local Feature Matching

Notre Dame images matched with 90% accuracy (30 features matched).

The point of the project was to demonstrate local feature matching by implementing a working version of the SIFT pipeline. The pipeline consists of 3 seperate parts:

  1. A corner detector.
  2. A technique for extracting features from the corners.
  3. A technique to match the extracted features.

For the corner detector, the Harris corner detector algorithm was chosen. For extracting features, the SIFT-like local feature was chosen. Lastly, for matching the extracting features, the "ratio test" algorithm was chosen.

The Harris Corner Detector

The Harris corner detector was implemented, and the results can be seen in the following grayscale images. The detector does a pretty good job of detecting keypoints in the images.

However, the ones above have been thresholded at a certain value, which was found by trial and error. The same images, thresholded at some other value (a higher value) are shown below. Notice how some of the detail is lost.

SIFT-like local features

SIFT-like features were implemented by doing the following:

  1. First, the image is filtered once with a sobel filter to highlight horizontal edges, in effect calculating the x gradient. Subsequently, the image was filtered with the transpose of a sobel filter to highlight vertical edges, which was an approximation of the y gradient. 
    
sobel_f = fspecial('sobel');
dxs = imfilter(image, sobel_f);
dys = imfilter(image, sobel_f');
  2. Second, for each keypoint, a 16*16 window, centered on the keypoint was extracted from each of the sobel filtered images. Then, from these 16*16 windows, 4*4 windows were extracted.
  3. Since tan(A) = dy/dx => A = atan(dy/dx), the 4*4 windows were divided element-wise (dy ./ dx) and each element was inputted into the atan function to calculate the direction of each pixel. 
    
gradients = atan2(16_dy(1:4, 1:4), 16_dx(1:4, 1:4));
gradients = rad2deg(gradients);
gradients = mod(gradients, 360);
  4. Then each direction was binned into one of 8 bins corresponding to [0-45, 45-90, 90-135, 135-180. 180-225, 225-270, 270-315, 315-360] degrees. In effect, for each 16*16 window, we were left with a 4*4*8 = 128 dimension feature vector.
  5. To complete the feature, the 128 dimension vector was normalized to unit length, effectively completing the formation of the feature. 
    
feature(i) = features(i) ./ norm(features(i));

Ratio test for matching features

The simple ratio test was implemented by doing the following:

  1. Compute the euclidean distance between each pair of features.
  2. Sort the distances in ascending order and take the nearest distance = D1 and the second nearest distance = D2.
  3. Compute the ratio between D1 and D2: D1/D2. If the ratio is less than a certain threshold (say 0.8), then there is match, otherwise reject the pair.

Results in a table

With the above thresholds and constraints, the pipline was run, and the following results were achieved: (First and second rows are the images, third row shows the matches).


Therefore, the SIFT filter seems to work for a range of images.