CS 143 / Project 2 / Local Feature Matching

Local Feature Matching involves three steps:

  1. feature detection,
  2. feature description,
  3. feature matching/tracking.

In this project, we implement Harris Corner Detection for feature detection, SIFT for feature description, and Nearest Neighbor Distance Ratio(NNDR) for feature matching.

Harris Corner Detector

I followed the Algorithm 4.1 in Szeliski book:

  1. Compute the horizontal and vertical derivatives of the image Ix and Iy.
  2. Compute Ix^2, Iy^2 and IxIy.
  3. Convolve three images above with a Gaussian.
  4. Compute the cornerness function by using the following formula:
  5. Find local maxima above a certain threshold using colfilt function and report them as detected feature point locations.

Here are the results of Harris Corner Detector:

SIFT

With the interest points, we can get image patch around the points, and apply SIFT to each patch. There are two ways to implement SIFT feature description. The first way is to build 8 orientation histogram for 4x4 cells using gradient at each pixel. The second way is to use 8 orientation filters to find the responsive edges at each orientation, and sum the edge responsiveness of each 4x4 cell. I used the second method by filtering the image with 8 Kirsch Compass Masks.

Here are the results of the Kirsch orientation filters. The pseudo code for computing SIFT histogram using orientation filter is the following:


for i=1:8        
    orientation(i) = convolve image with i_th Kirsch filter;
end

for each interest point i
	patch = get feature width patch centered at the interest point
	% for each of the 8 orientations
	for each orientation o
		%for each of the 4x4 cells
		for each cell in the patch c
			ignore negative/non-contributing cell values;
			descriptor(o,c) = sum of all pixel values in the cell;

    feature(i) = threshold_normalize(descriptor(:))

The gradient based SIFT also works, but slightly worse than using the orientation filters (about 5 fewer matches).

Nearest Neighbor Distance Ratio (NNDR)

The last step in the local feature matching pipeline is to match features from image A with features from image B using nearest neighbor distance. We use NNDR to make the match robust. Suppose d1 and d2 are the nearest and second nearest neighbor distances. We accpet the match if d1/d2 is small and rejects the match if d1/d2 is large. Using NNDR, we could abstract the top 100 strongest matches.

Result

Combining Harris Corner, SIFT and NNDR, my program is able to match 94 features correctly.