CS 143 / Project 2 / Local Feature Matching
Algorithm
Finding Interest Points
For finding the interest points I converted the image to grayscale, blurred it with a gaussian, and computed the x and y gradients of the image using a sobel filter. To speed it up, I first filtered the gaussian with the sobel filters and then applied the resulting filters to the image. I combined these images, which detected the horizontal and vertical edges, to create a single image that shows the edges. An example of this image is shown below.
I then use colfilt to filter out values that are much lower than the values around them. In any given 2x2 block, if a value is less than 0.1 times the max value in that block it is set to 0. The idea is to avoid having multiple interest points that are almost on top of each other. However, when I tried removing this step and tested the program on the Notre Dame images, it did not change the results in terms of number of correct matches. This is perhaps because the block is so small (2x2). However, increasing the size of the block filtered out so many potential interest points that the algorithm no longer found more than 100. After using colfilt, I threshold all values at 0.7 times the max value in the image. I return all points that are above this threshold and not within feature_width/2 of the edges as the interest points.
Calculating Features
To calculate the feature for an interest point, I use a SIFT-like feature with 128 dimensions. I divide the feature (whose size is given) into a four by four grid and for each of the 16 elements of the grid I calculate the total gradient in each direction. To do this, I preprocess the image eight times by using a sobel filter and rotating it to the desired angle before applying it to the image. I sum the result in each direction over each pixel in one of the grid elements, giving me 8 descriptors per element. Since there are 16 elements, there are 128 descriptors for each feature. I finish each feature by normalizing the 128 dimension vector. I tried raising every element of the feature to a power less than 1 before normalizing, but this resulted in complex numbers in the vector.
Finding Matching Features
To find matching features, I compute the euclidian distance between every pair of features in the two images. I match every point in the first image with a point in the second image by choosing the point to which it is closest. I calculate a measure of confidence for the match by taking one minus the nearest neighbor distance ratio. Finally, I sort the matched features by confidence.Results
Notre Dame
These images show the top 100 interest points found. From the comparison with ground truth, only 16 were correct matches.