Scott Kidd (shkidd)

81% Matching.

Identifying Features(get_inerest_points.m)

The idea here was to identify points in the image which would be easily identifiable from other perspectives. Taking a page out of human decision making, we opted for corners, as they represent a fixed location that can't be ambiguous. The way to find corners is the Harris corner detector algorithm. This works by taking two gradients of horizontal and vertical intensity and finding points where they coincide. There wasn't much to figure out for this part, since we were given a formulaic version of the algorithm in lecture slides. Instead, the difficult part was finding and surpressing insignificant data points. For one, it would be useless to have data that were too close together, as they might represent parts of the same corner, so we used non-maxima suppression(non_max.m) to remove adjacent points if they weren't the most significant within a certain range (here we used feature_width). As well as that, we thresholded the image to remove insignificant points that would have been maxima, even though they were insignificant. This helps to avoid patches that aren't corners but have some non-zero score being used. Finally, we sorted and found the most significant of these points based on their score as calculated by the algorithm of cornerness, and returned the most useful points.

non_max.m

Here is the function I used to apply non-maxima suppression, it finds the highest valued index and sets all others to zero. I used blkproc to apply this function across the image.

function [ surpressed ] = non_max( image )
    filter_size = size(image);
    [row_max col_max ] = find(image==max(image(:)));
    filter = zeros(filter_size);
    filter(row_max, col_max) = 1;
    surpressed = image .* filter;

end

Describing The Features (get_features.m)

The goal here is to document a set of data regarding a given point, such that the data gives useful information about the point's surroundings so that the point can later be matched on a corresponding image. The way we went about this is using a simplified version of a SIFT filter. The idea behind a SIFT filter is to create a collection (histogram, even though ours was entirely non-graphical), of scalars that represent the direction response for a given patch of image. The direction response was calculated using something similar to a sobel filter, except one-sided. Using 8 such filters(each 3x3, oriented 45 degrees from the previous), we calculated the response of a cell of pixels. Then we built a 4x4 matrix of these cells, centered on the feature point in question. This 4x4 patch represented 128 dimensions of information surrounding any given pixel, exactly what we need to use as a description. Finally, we normalized the 128 values, so that they would be useful relative to eachother.

Matching Features (match_features.m)

The last task, and potentially the easiest was matching features between the two images. This was easily achieved by using the k-nearest-neighbors algorithm as implemented by matlab in knnsearch(X,Y). This was the right algorithm to use because it searches along all 128 dimensions and finds the (k) point(s) nearest to the given target(s). After that, all that's left to do is sort based on confidence of the match. Again, thanks to matlab's implementation of knnsearch, it was trivial to discover the "distance" as calculated by the algorithm of not just the match, but the second-nearest match as well. Using that, I was able to calculate a confidence ratio by looking at the distance between the target and the match, divided by the distance between the target and the runner up. Finally, I sorted on confidence and returned the 100 points I was most confident about matching.

Parameter tweaking

There are a lot of numbers in this program whose optimal value requires investigation. Threshold for removing from cornerness was important, as I found it dictated the number of points I was able to consider for matching. Too high a threshold would cause points to be ignored, while too low would include insignificant points. Another important value was alpha, which I settled on to equal 0.02, as it seemed to produce the best results. Having used the formula for the lecture slides, I understand less about why this affected the data so severely, but it sure did, and tweaking it improved performance significantly. Finally, I had a lot of trouble passing the proper amount of points to the feature matcher, since if I passed any point with cornerness==0, it would be an insignificant patch. To handle this, in get_interest_points.m, I only returned interest points whose cornerness score was greater than zero.