Emily Wu (eswu) (your cs id)

Feature Matches of the Notre Dame. 93/37

Determining Interest Points

On any particular image, certain points are more distinctive than others. Corner points are often more distinct, as they are located at the intersection of two lines. The Harris Corner Detector was implemented for this reason.

The Harris Corner Detector involves first finding the horizontal and vertical gradients of the image, obtained by filtering the image with a Sobel filter. This gives horizontal and vertical edges. Using the following formula, the horizontal and vertical edges are eliminated leaving only the corners:

G(I_x²)G(I_y²) - [G(I_xI_y]² - α[G(I_x²) + G(I_y²)]²

where G(x) is the gaussian filter applied to x, and I_x is the x gradient of the image. α is a constant, determined to provide the best performance at α = 0.04.

This algorithm produces regions with high degrees of "cornerness". To resolve these regions into a single pixel, non-maxima surpression was used. Specifically, MATLAB's bwlabel to find regions and pick the maximum value within the region.

Creating Image Descriptors

Once the points of interest are found, they must be described in such a way that the matching algorithm can find distance in feature space. The feature chosen for this project is the SIFT descriptor. At each pixel within an image patch around a particular interest point, the gradients in the x and y direction are taken, and the arctan calculated to determine the discretized direction of the gradient (here, into eight directions) and its magnitude. The patch is then divided into sixteen grid squares. In each grid square, the sum of the magnitudes of the gradients at each pixel within the grid square is recorded for each of the discrete directions. With sixteen squares and eight directions for each, this creates a 128-dimensional vector for each image patch. The width of this feature was determined to perform more optimally at higher values, though the descriptors then took longer to compute.

After these vectors are found, they are normalized. After noramlization, all values over a certain threshold, which I will refer to as the renormalization threshold, are set to the threshold value. For example, if a normalized feature vector has a value > 0.15, that value is reset to 0.15. The vector is normalized again. This improves performance slightly, as exaggerated values increase the distance to other matches unnecessarily.

Another optimization made was to raise each vector to a power, pow = 0.8 prior to normalization.

Matching Features

Once two sets of feature vectors have been obtained, one per image, the features must be matched. My approach performs a quadratic euclidean distance comparison in feature space using the matlab function pdist2. However, to eliminate false positives, which are rife when the images contain repeated textures, if the closest and next-closest neighbors are too similar (i.e., the ratio of their distances is close to one), the match is discarded. If the euclidean distance of the nearest neighbor is too high, the match is again discarded. This first threshold, referred to as the ratio threshold was set to 0.93. The latter threshold, which I call the distance threshold, was set to 0.6.

Results

feature size	α	pow	renormalization threshold	ratio threshold	distance threshold	results(good/bad)
60	0.04	1	0.15	0.93	0.6	67/23
60	0.03	1	0.15	0.93	0.6	89/33
60	0.03	0.8	0.15	0.93	0.6	91/37
60	0.03	0.5	0.15	0.93	0.6	84/39
60	0.03	0.8	0.15	1	0.6	164/125
60	0.03	0.8	0.15	0.93	1	91/37
60	0.03	0.8	0.15	1	1	167/150

Other Images

Capricho Gaudi

Pantheon Paris