CS 143 Project

CS 143 / Project 2 / Local Feature Matching

An example result of local feature matching using SIFT feature descriptor.

1. The Goals of the Project

There are three main goals of this project:

Implement interest point detection.
Implement local feature description.
Implement Feature Matching algorithm

2. My Work

Wrote a Harris corner detector algorithm to extract interest points from images.
Implement or simulated major parts of SIFT local features to describe interest points in 128D vectors.
Write the nearest neighbor distance ratio test.

3. Implementation

3.1 Harris Feature Detector

The implementation of Harris Feature Detector follows instructions on slides and codebase. The steps are:

Prepossing on the image - using Gaussian filter to smooth the image to remove noisy, unwanted information.
Generate gradient images of the original image in X and Y directions.
Using the gradient images got in the previous step, make their "product images" Ix2, Iy2 and IxIy.
Using the images matrices above, calculate the harris response image.
Do non-maxima suppression. My method is first setting pixels near the corner and image edge to zero (these points are not reliable actually), then using colflit() get all max values in 3*3 windows, and finally in the harris response image selecting all max pixels.
For pixels selected out in the previous step, putting them in vectors as return values.

3.2 SIFT-like feature descriptor implementation

I implemented the core meat of SIFT feature descriptor algorithm. The input of the feature descriptor function is the coordinates of interest points got from the Harris stage, the output is the 128 dimension feature descriptor for each interest point. Besides the get_features.m provided, I wrote up two other functions as sub functions:

get_window.m: Given x and y coordinates of an interest point and the feature width, calculate the feature_width*feature_width descriptor window for this interest point. The reason I specially create this function is because the interest point which is treated as the center of the window is not a "point" but a pixel, so it could not be put in the absolute "center" of the window, so some trivial processing should be done to generate the window.
get_feature.m: The core function. Given the x and y coordinates of an interest point, feature width and 8 matrix presenting the response of the original image over 8 gradients (which are the original image filtered by 8 different sobel-like kernels), the function calculates the 128d normalized feature descriptor of the interest point. So actually get_features() is calling get_feature() for each interest point.

Here I pick the some of the most important snapshots of code of the above two functions.

The code to get feature descriptor window of an interest point:


%pass in a row/col coordinates, then return the range of its window.
cellWidth = feature_width / 4;
rowMin = row - cellWidth * 2 + 1;
rowMax = row + cellWidth * 2;
colMin = col - cellWidth * 2;
colMax = col + cellWidth * 2 - 1;

The code to calculate 128D feature descriptor of a given interest point.


[rowMin, rowMax, colMin, colMax] = get_window(row, col, feature_width);
feature = zeros(1, 128);
gaussian = fspecial('gaussian', feature_width, 0.8);
for gradientIndex = 1 : 8
    %calculate gaussion for this window
    gradientWindow = filteredImages(rowMin : rowMax, colMin : colMax, gradientIndex);
    gaussianed = imfilter(gradientWindow, gaussian, 'same');
    %for each cells, do the count and adding.
    for i = 0 : 3
        for j = 0 : 3
            %now we entered the cell
            cell = gaussianed(i * feature_width / 4 + 1 : (i+1) * feature_width / 4, ...
                j * feature_width / 4 + 1 : (j + 1) * feature_width / 4);
            %add up all values
            cellGradient = mean(cell(:));
            %assign it to its position in feature vector.
            featureIndex = 8 * (i * 4 + j) + gradientIndex;
            feature(1, featureIndex) = cellGradient;
        end
    end
end
feature = feature / norm(feature);

Besides the coding stuff, another important work I did is to tune the best parameters. The major parameteres tuned here are the sigma value of gaussian kernel, and the 8 orientation kernels. For the given example, I found 0.8 and sobel-like filters performs relatively better.

3.3 Ratio Test feature matching implementation

Finally I wrote up a ratio testing based feature matching algorithm with O(M*N) time complexity. The idea is pretty straightforward. For each interest point in one image, compute the distance of its feature descriptor and all feature descriptors of itnerest points of another image and pick the nearest two and calculate their ratio. The value of the ratio shows the confidence of the matching.

The code to pick two smallest distances and calculate NNDR is:


   for j = 1 : num_features2
        distance = sum((features1(i,:)-features2(j,:)).^2);
        if distance < min1
            min2 = min1;
            min1 = distance;
            minJ = j;
        elseif distance > min1 && distance < min2
            min2 = distance;
        end
    end

4. Experiments

Here I give some examples of feature matching results on pairs real-world photos. Since I did not implement the scale invariance feature, I didn't zoom in/out between two different pictures.