CS 143 / Project 2 / Local Feature Matching

The goal of the project is to design a image matching algorithm that match two similar images. The matching pipe line then is divided into three parts. First, we find the interesting points that are representative or more meaningful in the image. Second, we build up the feature descriptor around the interesting points. Then, we use the matching algorithm to find the best matches based on the feature descriptors.


Interest point detection

Using Harris corner detector to get the interest points. As you can see in the following figures, Adaptive Non-Maximal Suppression give us much more even distributed interest points compare to 3x3 local maximum suppression. Further, by using ANMS, I went from 89% good matches to 94% good matches out of Top 100.




Local feature descriptor

Implement a sift-like feature descriptor(did not consider the orientation and scale). Normalize the vector to unit length and truncate each bin at 0.2 to avoid sudden larger change in relative gradients. There are several parameters (ex: feature width, orientation) for tuning the feature descriptor, see the below benchmarks table for the performances.

Feature matching

Use 1-NN euclidean distance algorithm for matching the feature descriptors.
Take the ratio of "d1 = first nearest distance" to "d2 = second nearest distance", and only it is a match if the ratio less than the threshold (0.3 ~ 0.8). Otherwise there is no match. Sort these matches based on the confidence; here we define each feature's confidence as: d2 - d1.

Benchmarks


Feature width Orientations Truncate at 0.2 Ratio test Non-Maximal Suppression Accuracy Note
16 8 No 0.75 3x3 grid local maximum 87% baseline
16 8 No 0.75 ANMS 91%
16 8 Yes 0.80 ANMS 91%
16 8 Yes 0.75 ANMS 94%
16 16 Yes 0.75 ANMS 95%
32 8 Yes 0.75 ANMS 95%
32 16 Yes 0.75 ANMS 99%


Results

Notre Dame
Pantheon Paris
Capricho Gaudi
Episcopal Gaudi
House
Sleeping Beauty Castle Paris