CS 143 / Project 2 / Local Feature Matching

Example of feature matching on Notre Dame Cathedral with 89.5% precision

Interest point detection

In order to create features to match images against, interest points, the position of the features, must be selected. Corners are often good interest points to select since they are different than their neighboring points. To select interest points I used the Harris corner detector algorithm.

  1. Generate the second moment matrix by filtering the image.
  2. Calculate the cornerness scores of each point using the second moment matrix.
  3. Calculate the connected components of those scores and find the max point of each component.
  4. These max points will be the interest points of the image.

Local feature description

After interest points are selected, features must be created from those points. For local feature description I used SIFT-like features where each feature is described by a 4x4grid of histograms.

  1. Estimate the gradients of the image using filters, one filter for each of the eight gradient directions.
  2. For each interest point, create a 4x4 grid around it. Each of the cells contains a histogram made up of the gradients of the pixels in the cell.
  3. For simplicity, each pixel only contributes its gradient to the orientation it is closest to.
  4. This grid of histograms is flattened into a vector to be used as the feature for an interest point.

Feature matching

After the features are created I used the ratio test to find the features that were the best matches.

  1. Calculate the euclidean distance between all the features in image 1 and image 2.
  2. For each feature in image 1 get the two features from image to with the smallest distance.
  3. If the ratios of the distances fall below a threshold, then use the feature.

Results

Below are pairs of images labeled with matching features.