CS 143 / Project 2 / Local Feature Matching
Figure 1: Two pictures of the Notre Dame from
different perspectives. Green circles represent correct matches,
where as
red circles represent incorrect matches. These results show an 80% accuracy
in match detection.
The goal of this project was to implement a local feature matching algorithm based on the Harris corner detector and a simplified version of the SIFT pipeline. This pipeline enables us to analyse two images and find similar interest points in both images, even if they were taken from different perspectives.
Figure 1 represents two pictures of the Notre Dame in Paris, France taken from two different perspectives. By using a corner detection algorithm to find points of interest and then using a SIFT pipeline we are able to detect similar corners in both images, which can then potentially be used to determine if the two images are of the same object.
The green outlined circles represent interest points that have been detected correctly on both images, where as the red outlined circles represent mismatched interest points. In these images we were able to correctly detect 80% of the interest points across images, which translates to 72 correctly matched interest points and 18 incorrect.
Algorithm Discussion
The algorithms can be broken down into three parts, interest point detection, feature creation and feature matching.
Interest point detection essentially boils down to the Harris corner detection algorithm. The Harris corner detection algorithm tries to find corners which significant change in the x and y directions.
Once interest points have been discovered, in this case corners, we must then find some uniqueness about the interest point so that we can match it with a similar interest point in a different image. This is done through the SIFT pipeline by finding 8 different gradients around a particular interest point. These 8 gradients are used to form a feature vector for the interest point that is (mostly) orientation agnostic and can be used to compare against other image interest points.
After each interest point (in each image) is given a feature vector we can then use a nearest neighbor ratio test to determine if the top two closest matches are unique. This means that by comparing the closest feature vector match for two images with the 2nd closest feature vector match we can determine its uniqueness and thus if its a "good" match.
Algorithm Improvements
During the process of developing the interest point and feature detection algorithms we made a few small improvements in terms of parameters that increased the overall matching accuracy.
During the feature matching phase of the algorithms we found that thresholding the matches based on the confidence values from the ratio test worked well in suppressing inaccurate matches. If a matches confidence was under 1.5 we would not consider it a match.
During interest point detection we determine a corner-ness score for a given point. Before reporting a point as a corner we threshold the point at a pre-defined value, in the final results we found that a threshold of >0.0025 worked quite well and helped to yield the 80% accuracy seen in Figure 1. However we previous experimented with higher and lower values resulting in different accuracies. Setting the threshold lower to >0 yielded a 72% match accuracy. Similarly we tried a higher threshold of >0.01 which yielded a 78% match accuracy and a lower overall match.
Lastly, during feature creation we found that by raising the normalized feature vector to an exponent of 0.75 we saw an increase in match accuracy of 5%. We also tried exponents of other values but saw found that 0.75 seemed to produce the best results on this data set.
Other Notre Dame Images
In the next two images we compare the original Notre Dame image to two other images and show interest point matches for both. However, it should be noted that these interest points are not verified like the previous Figure 1. By looking at the images it appears to match pretty decently through spot-check verification.
