 |
 |
Figure 1: correspondence(left) and matching accuracy(right) of the example
image
In this project, I’ll be implementing SIFT-like feature matching algorithm, following [4] chapter 4.1 and the idea of SIFT[3] by David Lowe
For a quick example, cd to code/, and run
imname1 = '../data/Notre Dame/921919841_a30df938f2_o.jpg';
imname2 = '../data/Notre Dame/4191453057_c86028ce1f_o.jpg';
feature_width = 16;
radius = 5;
vis = 1;
accuracy = 1;
[x1, y1, x2, y2, matches, confidences] = ...
sift_like_detector(imname1, imname2, feature_width, radius, vis, accuracy);
The script will visualize the feature correspondence and compute the matching accuracy on this test image, (Figure 1) which have 83 total good matches, 17 total bad matches
Following the pipeline of Harris corner detector described in [4] section 4.1.1. We implement
where im is the grey scale image from imread, radius controls the window size for non-maximum suppression, and feature_width controls the border size of the image that we want to eliminate. The returning value x and y are the coordinates of the interesting points.
First of all, we blur the image using a gaussian filter with σ = 1 and size 6 × 6. Then, using filters of dx = [−1, 0, 1],dy = dxT , we get the I x and Iy map of the image. After that we can simply get Ix2,I y2,I xIy maps accordingly. As proposed in [1], we use the harmonic mean
 | (1) |
which can be computed easily.
Then we’ll perform non-maximum suppression, using a slightly modified version of [2], we have the function
function [r, c] = non_maximum(cim, radius, feature_width)
where cim is the harmonic mean map following equation 1. The mechanism of this function is: for each interesting point, we look at the neighboring window with radius size, if it’s indeed has the maximum value, we preserve it. Also, we want to make sure that the harmonic mean of this point is above the median of that of all points. Finally, since we are going to extract features with window size feature_width, we don’t want to preserve points that lies at the border of the image. And this concludes our interest point selection part. An visualization of the detected interesting points are shown in figure 2
If we don’t perform non-maximum suppression but only thresholding on the harmonic mean, we’ll get more than 380000 points to compute, and the computational cost is too large. After implementing the non-maximum suppression, we get about 2500 points for each image. Therefore, non-maximum suppression is indeed helpful in choosing the most informative points.
Given interesting points, the next step is to get features for each point. Here, we follow the idea of SIFT[3], which briefly described in Figure 3
In our implementation below
function [features] = get_features(im, x, y, feature_width)features is a n by 128 matrix, where n is the number of interesting points. After getting Ix and Iy matrices like before, we loop through all the interesting points: first we extract the patch with size feature_width × feature_width that covers the interesting point and convolve its Ix and Iy maps with a gaussian filter. As a consequence, the points that close to the center will contribute more in the feature vector. Then for each pixel on this patch, their orientation and scale are computed by equation 2
 | (2) |
A gradient orientation histogram is then computed in each subregion. Figure 3 only shows a 8 × 8 pixel patch and 2 × 2 descriptor array, while in our implementation, a 16 × 16 patch is computed and producing a 4 × 4 array of eight-bin histogram.
Now that every interesting point has a feature vector, we can match them using simple techniques, such as nearest neighbor classifier. The distance between any two pixels is defined as the L2 norm of their feature vectors. After we computed the minimum distance of each points in image1 to those in image2, we only preserve those that is smaller than the mean of all the minimum distances. We also compute the nearest neighbor distance ratio[1] as
 | (3) |
where d1 and d2 are the nearest and second nearest neighbor distances, we manually choose 0.75 as the threshold. Intuitively, the smaller this value is, the more confident we can be about this match.
A user interface is created for people to label pixel correspondence for every image:
function construct_gt(imname1, imname2, add)A snapshot is shown in figure 5
Here we only manually labeled three pair of images:
Capricho Gaudi/36185369_1dcbb23308_o.jpg to Capricho Gaudi/3689167599_fcc448cc47_o.jpg
House/IMG_0485.JPG to /House/IMG_0488.JPG
Pantheon Paris/6005180348_c465ccf905_o.jpg to Pantheon Paris/4872728253_3e73bd436b_o.jpg
feature_width turn out to be a really important parameter to tune. If we use 48 instead of 16, we’ll get 94 total good matches, 6 total bad matches on the Notre Dame image match, a 10% increase in accuracy. Also, the radius turns out to be important too: if we decrease the size of the radius, we'll get more interesting points as candidates, thus potentially increase the performance. If radius=8, we'll actually get 73 good matches and 27 bad matches, a 10% decrease in accuracy.
We also tested the implemented sift-like detectors on other image pairs, and the results are shown below. It's pretty clear that if there's a big change in view/scale, the performance of our implementation is poor.
 |
 |
| 31 total good matches, 29 total bad matches |
 |
 |
| 44 total good matches, 20 total bad matches |
 |
 |
| 30 total good matches, 71 total bad matches |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
[1] M. Brown, R. Szeliski, and S. Winder. Multi-image matching using multi-scale oriented patches. In Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, volume 1, pages 510–517. IEEE, 2005.
[2] P. D. Kovesi. MATLAB and Octave functions for computer vision and image processing. Centre for Exploration Targeting, School of Earth and Environment, The University of Western Australia. Available from: <http://www.csse.uwa.edu.au/∼pk/research/matlabfns/>.
[3] D. G. Lowe. Distinctive image features from scale-invariant keypoints. International journal of computer vision, 60(2):91–110, 2004.
[4] R. Szeliski. Computer vision: algorithms and applications. Springer, 2011.