CS 143 Project

In this project, I'll implement feature matching algorithm to match the same points across different image. This will consist of;

Algorithm

Interest point detection

So the first step in this local feature matching is, obviously, to find potential keypoint that can be used to match between images(unless we want to compare every pixel!). These points need to be distinctive enough that the detector will find these same point over all possible image. Harris corner detector is one of the widely used method and will be the baseline algorithm for keypoint detection in this project. The Harris's score of being a corner can be computed by;

Here is the detail step of my implementation

Compute image gradient Ix and Iy (convolve with horizontal and vertical derivative of Gaussian), then Ix^2, Iy^2 and IxIy, convolve these terms with Gaussian filter, and plug into the equation to get cornerness score
Threshold out points below certain score.
After (hopefully) strong point survive the threshold, I then used BWCONNCOMP function in Matlab to group connected points together, and take the only the point with maximum value of score in each group

Analysis

Threshold : Figure 2 shows results of interest points from using different threshold value, I end up using the last one since it gives me a lot of points thus a lot of chance to get the match. Although after increasing more than this, the accuracy on Norte Dame Image start to decrease, so larger is not always better(but always more runtime though). In my code I computed this threshold with regard to the maximum value of cornerness score.

Figure 2 : Results from keypoint detection algorithm using small, medium, large, threshold respectively.

BWCONNCOMP : Figure 3 shows before and after using this function. To put it simply, it reduce clusters (to some extent). I tried using COLFILT, but I think BWCONNCOMP is more flexible and give out better results.

Figure 3 : Comparison between using only threshold to choose point (left) and apply BWCONNCOMP function then choose the maximum in each group(right). (same threshold)

Local feature description

After getting some points from the previous step, we then have to give them a description, so that we can compare the similarity across different images. At first I just directly compare the intensity around the keypoint. This give out pretty bad result (Figure 4)

Figure 4: Results from using simple intensity comparison (66 total good matches, 34 total bad matches ).

Which is only 66% accurate. After changing to SIFT feature description(figure 1), and tweaking some parameters, I improve the accuracy in this particular images to 97%.

Sift descriptor in this implementation is created by forming 8 orientation histogram bins for each 4x4 cell around keypoint, which will be computed by filter the image with each oriented filter.

Feature matching

The matching process is pretty straight forward. I just compare the distant between each pair of keypoint, according to how different their feature is and then choose matches that are above some certain threshold. In this project, I'll use distant ratio between 2 nearest neighbor as a confident level, which will be sorted before output as the 100 most confident matches(or less if there are less matches after thresholding)

I also prevent the matching between the same keypoint by choosing the pair that have greater confident when that happen. So each point will have exactly one match.

Results

After tuning all the parameters, the following is the (seem to be) successful results from using this algorithm.

Norte Dame

97% accuracy (97 right, 3 wrong)

Norte Dame image image pair gives out the most accurate result since they are really similar and easy to match. This is the only test images that we'll know the precise accuracy (green circle represent correct match, while red is wrong matches). Note that the wrong match here are pretty forgivable, since it is matching between repeated pattern which look pretty much the same.