Project 2: Local Feature Matching

Local Feature Matching

In this project, I implemented a local feature matching algorithm. There are already library functions available for performing feature matching such as SIFT, GIST etc. In this project, I used a simplified version of the SIFT pipeline. To perform the local feature matching, there are certain steps which need to be done as follows.

  1. Detect Interest Points
  2. Get Features
  3. Match Features

Detecting Interest Points

The Harris Corner detector is used to detect the points of interest. We take the X and Y gradients of the image and compute the outer product of these. Then, we calculate a factor R which is called the scalar interest measure. Using this scalar interest measure, we compute the feature locations as those which have a local maximum above a threshold.


gauss_filter = fspecial('Gaussian', 8, 1);
gauss_image = imfilter(gauss_image, gauss_filter);

[GX,GY] = gradient(gauss_filter);

%Compute the gradients of the image (x and y)
IX = imfilter(gauss_image,GX);
IY = imfilter(gauss_image,GY);

IXX=IX.*IX;
IYY=IY.*IY;
IXY=IX.*IY;

gauss_filter = fspecial('Gaussian', feature_width, 2);

IXX = imfilter(IXX, gauss_filter);
IYY = imfilter(IYY, gauss_filter);
IXY = imfilter(IXY, gauss_filter);

R = (IXX.*IYY - IXY.^2) - 0.01 * ((IXX + IYY).^2);               
Rmax = max(max(R));
R = R/Rmax;

R(R<0.001) = 0;                                           
Rmax = colfilt(R, [16 16], 'sliding', @max);

T = R.*(R==Rmax);
T(find(T))=1;

[y,x] = find(T);

Get Features

I implemented a local feature similiar to SIFT. For each key point, the mean gradient is obtained by using the surrounding region of the key point. Then, a weighted gradient orientation histogram is computed in each subregion using trilinear interpolation using 16x16 patches and 4x4 array of eight bin histograms.

Match Features

Features are mapped using nearest neighbor distance ratio test. The features for both the images are compared and a nearest neighbor distance is computed as the ratio of distance of 1st and 2nd nearest neighbor. The inverse of the distance gives the confidence measure. The matching is done if the confidence value is lesser than a threshold.


pairwise_distance = pdist2(features1, features2);

[A, Index] = sort(pairwise_distance, 2);
%nearest neighbor distance
nearest_neigh = A(:, 1) ./ A(:, 2);

matches = [];
matches(:,1) = find(nearest_neigh <= 0.89);
matches(:,2) = Index(matches(:, 1));

confidences = nearest_neigh(matches(:, 1)).^-1;

Accuracy and Results

83% accuracy. 76 Good matches, 16 bad matches
83% accuracy. 246 Good matches, 51 bad matches