Computer Vision Project

Project 2: Local Feature Matching

In this assignment we create a local feature matching algorithm which is a simplified version of the SIFT pipeline.

Obtaining Interest Points

We use the Harris Corner Detection algorithm for keypoint detection and localization. Basically we evaluate the cornerness score for each point in the image. We discard points for which the cornerness score is less than 0.001. We also discard points which are within the feature_width/2 pixels of the boundaries. Further we use a sliding window on each corner point to check if it is the maximum within a neighborhood ([3 3], [feature_width/2 feature_width/2]). If it is not, it is discarded. The keypoints are then sorted in decreasing order of cornerness and the best 1500 are returned.

Extracting Features

We use the standard gradient orientation histogram in 8 bins as features. The feature length is 128.

Feature Matching

We use the nearest neighbor distance ratio to estimate confidence of matches.
Bells & Whistles:

KD-Tree based nearest neighbor search
We use the knnsearch function to do a KDTree based nearest 2 neighbor search in features2 for every entry in features1. Thereafter we use obtained values to compute the NNDR.
Principal Components Analysis to reduce descriptor dimension
To reduce the dimensionality of the features from 128 to 32, I generate a PCA basis from the 90 or so images in the extra_data.zip provided on the project page. The combined percentage variance for 32 dimensions comes out to be about 62.38%. We also extract a global mean feature mu. I have created a separate function match_feature_pca() which first uses the computer PCA basis, W to reduce the dimensionality of the features to 32 and then perform the matching algorithm (kNN).

Tweaks & Results

#interest points	feature_width	non-max suppression win size	PCA	% Notre Dame	% Mt. Rushmore	% Episcopal Gaudi
<=1500	32	[8 8]	yes	80	65	7
<=1500	32	[8 8]	no	85	88	5
as many avbl	32	[8 8]	yes	90	100	13
as many avbl	32	[8 8]	no	92	99	17

Using 16 feature_width, I was getting about 88% accuracy which dropped to just under 80% when using PCA as well. Hence I switched to using 32 feature_width. Understandably, using PCA reduces the accuracy by a few percentage points in each case. Also, if we finally return only the top 1500 keypoints based on cornerness score (after all the eliminations and nonmax suppression) as compared to returning all these points, the former is considerably faster but is slightly less accurate. The latter however is far more accurate but is slower because of the many more comparisons that are being done.