CS6476-Project 2 SIFT Local Feature Matching Solved

The goal of this assignment is to create a local feature matching algorithm using techniques described in Szeliski chapter 7.1. The pipeline we suggest is a simplified version of the famous SIFT pipeline. The matching pipeline is intended to work for instance-level matching – multiple views of the same physical scene.

Details
For this project, you need to implement the three major steps of a local feature matching algorithm (detecting interest points, creating local feature descriptors, and matching feature vectors). We’ll implement two versions of the local feature descriptor, and the code is organized as follows:

•   Interest point detection in part1_harris_corner.py (see Szeliski 7.1.1)

•   Local feature description with a simple normalized patch feature in part2_patch_descriptor.py (see Szeliski 7.1.2)

•   Feature matching in part3_feature_matching.py (see Szeliski 7.1.3)

•   Local feature description with the SIFT feature in part4_sift_descriptor.py (see Szeliski 7.1.2)

1         Interest point detection (part1_harris_corner.py)
You will implement the Harris corner detection as described in the lecture materials and Szeliski 7.1.1.

The auto-correlation matrix A can be computed as (Equation 7.8 of book, p. 404)

                                                                                             (1)

where we have replaced the weighted summations with discrete convolutions with the weighting kernel w (Equation 7.9, p. 405).

The Harris corner score R is derived from the auto-correlation matrix A as:

                                                                            R = det(A) − α · trace(A)2                                                                                                (2)

with α = 0.06.

 

Algorithm 1: Harris Corner Detector

 

Compute the horizontal and vertical derivatives Ix and Iy of the image by convolving the original image with a Sobel filter;

Compute the three images corresponding to the outer products of these gradients. (The matrix A is symmetric, so only three entries are needed.);

Convolve each of these images with a larger Gaussian.;

Compute a scalar interest measure using the formulas (Equation 2) discussed above.;

Find local maxima above a certain threshold and report them as detected feature point locations.;

 

To implement the Harris corner detector, you will have to fill out the following methods in part1_harris_corner .py:

•   compute_image_gradients(): Computes image gradients using the Sobel filter.

•   get_gaussian_kernel_2D_pytorch(): Creates a 2D Gaussian kernel (this is essentially the same as your Gaussian kernel method from project 1).

•   second_moments(): Computes the second moments of the input image. You will need to use your get_gaussian_kernel_2D_pytorch() method.

•   compute_harris_response_map(): Gets the raw corner responses over the entire image (the previously implemented methods may be helpful).

•   maxpool_numpy(): Performs the maxpooling operation using just NumPy. This manual implementation will help you understand what’s happening in the next step.

•   nms_maxpool_pytorch(): Performs non-maximum suppression using max-pooling. You can use PyTorch max-pooling operations for this.

•   remove_border_vals(): Removes values close to the border that we can’t create a useful SIFT window around.

•   get_harris_interest_points(): Gets interests points from the entire image (the previously implemented methods may be helpful).

The starter code gives some additional suggestions. You do not need to worry about scale invariance or keypoint orientation estimation for your baseline Harris corner detector. The original paper by Chris Harris and Mike Stephens describing their corner detector can be found here.

2         Part 2: Local feature descriptors (part2_patch_descriptor.py)
To get your matching pipeline working quickly, you will implement a bare-bones feature descriptor in part2_patch_descriptor.py using normalized, grayscale image intensity patches as your local feature. See Szeliski 7.1.2 for more details when coding compute_normalized_patch_descriptors()

Choose the top-left option of the 4 possible choices for center of a square window, as shown in Figure

2.

 

Figure 2: For this example of a 6 × 6 window, the yellow cells could all be considered the center. Please choose the top left (marked “C”) as the center throughout this project.

3         Part 3: Feature matching (part3_feature_matching.py)
You will implement the “ratio test” (also known as the “nearest neighbor distance ratio test”) method of matching local features as described in the lecture materials and Szeliski 7.1.3 (page 421). See equation 7.18 in particular. The potential matches that pass the ratio test the easiest should have a greater tendency to be correct matches – think about why this is. In part3_feature_matching.py, you will have to code compute_feature_distances() to get pairwise feature distances, and match_features_ratio_test() to perform the ratio test to get matches from a pair of feature lists.

4         Part 4: SIFT Descriptor (part4_sift_descriptor.py)
You will implement a SIFT-like local feature as described in the lecture materials and Szeliski 7.1.2. We’ll use a simple one-line modification (“Square-Root SIFT”) from a 2012 CVPR paper (linked here) to get a free boost in performance. See the comments in the file part4_sift_descriptor.py for more details.

Regarding Histograms SIFT relies upon histograms. An unweighted 1D histogram with 3 bins could have bin edges of [0,2,4,6]. If x = [0.0,0.1,2.5,5.8,5.9], and the bins are defined over half-open intervals [eleft,eright) with edges e, then the histogram h = [2,1,2].

A weighted 1D histogram with the same 3 bins and bin edges has each item weighted by some value. For example, for an array x = [0.0,0.1,2.5,5.8,5.9], with weights w = [2,3,1,0,0], and the same bin edges ([0,2,4,6]), hw = [5,1,0]. In SIFT, the histogram weight at a pixel is the magnitude of the image gradient at that pixel.

In part4_sift_descriptor.py, you will have to implement the following:

•   get_magnitudes_and_orientations(): Retrieves gradient magnitudes and orientations of the image.

•   get_gradient_histogram_vec_from_patch(): Retrieves a feature consisting of concatenated histograms.

•   get_feat_vec(): Gets the adjusted feature from a single point.

•   get_SIFT_descriptors(): Gets all feature vectors corresponding to our interest points from an image.