Angela Palm

Project Results

The Algorithm

SIFT-like local features

This part of the algorithm was implemented by first taking the image and finding the direction of each pixel. The method to find this result matrix is shown below:

h = fspecial('sobel');
transposed_sobel = h';
x_gradient = imfilter(image, h);
y_gradient = imfilter(image, transposed_sobel);
dir_matrix = atan2(y_gradient, x_gradient);

Then, each x,y pair is used to create a patch of feature_width by feature_width where the current pixel is in the center (or as close to the center as possible). Next, the patch is sliced into 16 cells. Each cell will have a histogram representing how many pixels have that direction in the cell. Each value will start out with a value from -pi to +pi, so this is converted into an index into the histogram so that that point may be icremented. Each features row ends up with a flattened cell_matrix. This will later be used to compare features.

Harris Corner Detector

Here, a Harris Corner Detector was implemented in order to find chagnes of intensity in the image. The first step is to find the image derivatives. This was done in a similar fashion as the earlier step - with a sobel filter. Next, these derivatives are squared and blurred. Last, the below formula is followed: where alpha is .06 and g represents taking the Gaussian of that value.

After finding this value matrix, the last steps are thresholding and non maxima suppression. Thresholding refers to the process by which only values over a certain threshold are kept - the rest are zeroed out. This will allow the non maxima suppression to be more meaningful. Finding a threshold, in my case, required a lot of trial and error. Non maximum suppression was performed by the MATLAB function: imregionalmax(matrix). After these operations, the indices of any spot in the matrix that has not been zeroed out are appended to the end of the x and y vectors. These coordinates represent the possible "interest points."

Ratio Testing

The nearest neighbor ratio test is used to match features. First, the MATLAB function pdist2 is used to find the distances between all points in features1 and features2. Each row can be sorted so that the smallest distance is at the front. The two best distances are compared to give the pairs of features1 and features2 coordinates a vote of confidence. 1 minus the best distance divided by the second best distance results in the confidence value. These confidence values are added to a confidence matrix which is later used to sort the matches from best to worst. The matches' indices are stores in the matches matrix and returned with the confidence matrix.

distances = pdist2(features1,features2);
[height, width] = size(distances);

best_matrix = zeros(height, 2);
confidence_matrix = zeros(height, 1);
for y=1:height
    row = distances(y, :);
    [B, I] = sort(row);
    best = B(1);
    second = B(2);
    
    ratio = best / second;
    confidence = 1 - ratio;
    
    best_matrix(y, 1) = y;
    best_matrix(y, 2) = I(1);
    confidence_matrix(y, 1) = confidence;
end

matches = best_matrix
confidences = confidence_matrix;

Other Examples of Local Feature Detection

Other Example of Local Feature Matching