Project 2: Local Feature Matching

Hybrid Image of Dog and Cat

For project 2, we were required to implement a local feature matching algorithm using a simplified version of the SIFT pipeline. This includes interest point detection, initially through a cheating method based on the given eval file and then through harris interest point detection. Next is local feature description, first through normalized image patches and then through the SIFT pipeline. Last is feature matching using a nearest neighbor ratio test.

Feature Matching

  1. Calculate distances between features to determine 2 closest neighbors
  2. Find ratio of nearest neighbors
  3. Calculate confidences from the inverse of the distance ratio
  4. Return 100 best matches and associated confidences

Feature Descriptors

  1. Blur the image
  2. Find the x and y gradient of the image using a sobel filter
  3. Determine the orientation angles by using atan2 on the x and y gradients
  4. Determine the magnitude of the gradients
  5. For each interest point, select the orientation angle and magnitude of the 16*16 patch of pixels surrounding it
  6. Break the patch into 4x4 cells and create a histogram of the magnitudes (aka: the feature)

Harris Interest Point Detection

  1. Compute x and y gradient of the image using gaussian and sobel filter
  2. Compute 
    harris = (ixx .* iyy) - (ixxiyy .* ixxiyy) - alpha * (ixx + iyy) .* (ixx + iyy);
  3. Suppress points that are near the edges
  4. Ensure points are at a loal maximum or cornerness using colfilt 
    result = colfilt(corner, [3 3], 'sliding', @max);
  5. Return (x,y) interest points

Results

Interest Points
Matches
Evaluation

The results of my implementation went roughly as expected for the Notre Dame image set. As I developed I managed to get to 71% with cheat interest points and then to 94% with the harris interest points. I managed to break the interaction between cheat interest points and the mount rushmore image near the end of my development process. I'm not really sure what happened but my Harris interest points works really well on it. Lastly, I didn't check the Episcopal Gaudi image set as much when developing as I received pretty eratic results all the way through but I feel like a more refined interest point selector would help my percentages.