Lab: Feature Detection

CSC 262 - Computer Vision - Weinman



Summary:
You will implement an algorithm for detecting stable features (or keypoints) at a particular scale.

Deliverables

Extra Credit

Background

In this lab, as well as the next, you'll be recreating portions of the image matching system described by Szeliski in his book, but also in the following paper (which has some other details the book does not):
Matthew Brown, Richard Szeliski, and Simon Winder. Multi-image matching using multi-scale oriented patches. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'2005), volume I, pages 510-517, June 2005.

Preparation

Begin by loading your venerable cameraman and converting the image to doubles. While we will start by applying a feature detection algorithm to a specific image, you will end up transforming this into a function that detects keypoints. I therefore recommend that you give the image variable a rather generic name so that your converted result is both meaningful and painless to create.

Exercises

A. Filtering for Detection

The feature detection algorithm detailed in Szeliski Section 4.1.1 (summarized in Algorithm 4.1) requires Gaussian filters at two different scales: one for calculating the derivatives, and another for averaging the responses used to calculate the features. In the first part we will establish these filters.
  1. You will need to compute Gaussian partial derivatives for the matrix A. Using gkern, create a Gaussian and first derivative kernels of scale (standard deviation) 1. Thus, the scale of features we will be isolating will be nearly as small as possible.
  2. You also need a Gaussian kernel to average (blur) the quantities in the matrix A. Create a single Gaussian kernel of scale 1.5. We will therefore be averaging responses over a slightly larger area for robustness.
  3. Using conv2, create the partial derivatives of the image in each direction, Ix and Iy, with the separable filters you created in A.1. You should ask Matlab for responses that are the same size as the original image.
  4. Using conv2, create blurred versions of the entries in A using the larger (separable) kernel you created in A.2. That is,
    • calculate Ix2 and then blur it with the larger kernel
    • calculate Iy2 and blur it with the larger kernel, and
    • calculate IxIy and blur it with the larger kernel.
    Remember that your powers and multiplication should be component-wise! Likewise your convolution results here should be the same size as the input.
You should now have the three entries for the (blurred) "matrix"
A=
Ix2  
  IxIy
IxIy  
  Iy2.
(1)

B. Calculating Feature Strength

Recall that the determinant of a 2×2 matrix
a
b
c
d
is given by ad−bc and the trace of the matrix is the sum of the diagonal entries: a+d.
  1. Calculate an "image" where each entry contains the determinant of A (for each pixel) using the values computed in A.4 (that is, Equation 1).
  2. Display this image. It may be easier to visualize with a hot-cool colormap, which you can add with the command colormap(jet). Adding a colorbar may help you visualize the magnitudes .
  3. Where are the responses the strongest (i.e., at what sorts of image features; is just one or both of Ix, Iy responses required)? Explain this based on quantities used to calculate the determinant.
  4. Calculate an image where each entry contains the trace of A (for each pixel) using the values computed in A.4.
  5. Display this image. It, too, may be easier to visualize with the jet colormap. Adding a colorbar may help you visualize the magnitudes.
  6. Where are the responses the strongest (i.e., at what sorts of image features; ; is just one or both of Ix, Iy responses required)? Explain this based on quantities used to calculate the trace.
  7. Calculate an image containing the final measure of feature strength using Szeliski and Brown's quantity, the ratio of the determinant and the trace,
    det A
    tr A
    		 .
  8. Display this image. Once again, it may be easier to visualize with the jet colormap. Adding a colorbar may help you visualize the magnitudes.
  9. Where are the responses the strongest (i.e., at what sorts of image features)? Explain this based on the previous two images.

C. Finalizing Feature Detection

Feature selection is based on two criteria. First, they must be local maxima. That is, we want to chose the locally best responses of our interest measure. Second, they should be sufficiently strong. A local maxima that displays no response is probably not worth examining. In this section, we'll complete these two steps.
  1. Based on the values from the image B.8, choose a value to threshold your feature detection.
    My suggestion would be that you keep it rather low, making it just high enough to eliminate the truly flat areas. After all, we're trying to match images and we'll want as many potential features as possible. If you're unsure of your choice, feel free to ask.
  2. Next we need to find the locations that are local maxima. I have provided a Matlab function maxima in your local toolbox, which does this by finding locations in an image that are larger than all four of their neighbors
    M = maxima(X);
    where M is a binary (logical) matrix the same size as X. Use this to find the local maxima of the feature strength from B.7.
  3. Combine your results from the previous two exercises into one binary (logical) matrix the same size as your image. The location of a non-zero index in the matrix should indicate where there is a maxima that is above the threshold.

D. Making a Detection Function

As promised, it is time to abstract and generalize your commands into a Matlab function that you will be using in subsequent labs.
  1. Open a file called kpdet.m in your Matlab editor of choice.
  2. Add a declaration line to your function so that it takes one parameter, an image, and returns one value, the logical detection image.
  3. Copy/convert the commands you used in Parts A, B, and C to create the detection image using the function input, so that it can be returned by your function.

E. Estimating Repeatability

  1. Load two different images of the same scene from the MathLAN:
    /home/weinman/courses/CSC262/images/kpdet1.tif
    /home/weinman/courses/CSC262/images/kpdet2.tif
    Don't forget to convert them to doubles for processing.
  2. Use your kpdet function to find the keypoints in each of these images.
  3. Use find to locate the rows and columns of the keypoints detected in each of these images.
  4. Display both of these images and use hold on to indicate that you want to add more to each figure.
  5. Use plot to display plus symbols where your features are located in each image. (Don't forget that plot takes x and y coordinates, which are the columns and rows, respectively.)
  6. How do the feature locations look? Are they found in the places you expect? Are there any missing that you might have expected? Characterize the repeatability of the feature detection algorithm. (That is, how well does it find the same features in both images?)
    Note: If you are unsatisfied with your results, you may want to tweak your threshold.

Extra Credit 1: Orientation

Alter your method kpdet so that instead of returning a logical matrix, the values where the features are detected contain the gradient orientation of the image at that point. In order to do this robustly, the derivatives should be taken at a larger scale. Thus, you should blur the partial derivatives with a larger Gaussian of scale 4.5 before calculating the orientation. This would potentially allow us to orient a feature descriptor based on the local orientation of the image surface.

Extra Credit 2: Adaptive Non-Maximal Suppression

Modify your kpdet method so that it performs the ANMS technique described by Brown et al.

Acknowledgments

The kpdet1 and kpdet2 images were taken by Jerod Weinman in Curitiba, Brazil at the Pontifical Catholic University of Parana and are Copyright 2007, licensed under a Creative Commons Attribution-Noncommercial-Share Alike 4.0 International License.
Copyright © 2010, 2012, 2015, 2019, 2020, 2022 Jerod Weinman.
ccbyncsa.png
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 4.0 International License.