Lab: Feature Descriptors

CSC 262- Computer Vision - Weinman

Summary:

You will implement a version of Brown et al.'s multi-scale oriented patches (MOPS), but without the multiscale and oriented bits.

Background:

You will need your kpdet.m function from the previous lab.

Deliverables

• The Matlab script used to make your comparisons and generate your report
• (10 points) Keypoint location reference image (B.9)
• (20 points) Small, large, and small normalized patch images (B.6, B.7, C.3)
• (10 points) Full-size and downsampled patch observations (B.8)
• (10 points) Patch normalization observations (C.4)
• (20 points) Descriptor extraction function kpfeat.m (D)
• (10 points) Professionalism of write-up

Extra Credit

• (10 points) Orientation-normalized version of kpfeat.m
• (10 points) Demonstration and observations

Preparation

Load one of the images from the feature detection lab to experiment with in this lab.

/home/weinman/courses/CSC262/images/kpdet1.tif

Don't forget to convert it to doubles for processing. While we will start by applying a feature descriptor algorithm to a specific image, you will end up transforming this into a function that calculates descriptors at detected 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. Processing for Descriptors

Our descriptors will be very coarsely sampled patches around the detected keypoints. Here we find the points and decimate the image to extract patches.

1. Before extracting the feature descriptors, you need to find the features. Run your kpdet procedure on the image to get the matrix of detected feature locations.
2. Use find to locate the rows and columns where the feature keypoints were detected.
3. The MOPS descriptors are 8×8 patches, so you will need a place to (potentially) put them all. Initialize an N×64 matrix, where N is the number of detected keypoints.
   Note: Your input image may change. Do not hard-code a number for N. Instead, calculate it from your previous results.
4. The MOPS descriptor requires a very coarse representation of the image. To safely get such a coarse image, we blur and then downsample. Create a Gaussian kernel with a scale (standard deviation) of 5 pixels (so the variance is 5²).
5. Apply the Gaussian kernel along both dimensions to blur the input image, and ask for a result the same size as the original image.
6. Downsample/decimate the image by a factor of 5 (That is, take every fifth row and column).

B. Extracting Patches

1. You have detected N key points and produced vectors containing their row and column in A.2. Assign a variable k to a value between 1 and N to index one of these keypoints. This will also correspond the row of the descriptor matrix you created in A.3.
   Eventually k will be a loop variable, but you may pick its value arbitrarily for now.
2. We need to find the appropriate 8×8 patch in the downsized image for the keypoint detected. To do this, you'll first need to find the index in the downsized image where the patch is centered. Find a scaled location by dividing the row and column (using the index variable k) of the feature by the subsampling factor.
   Note: because you need pixel indices, the result must be made into an integer.
3. The scaled row and column you calculated in the previous step indicate the center location of your patch. Subtract an offset from these so that you have the upper-left corner of the 8×8 patch. (It may help to draw a grid.)
   Reminder: You are doing this step in the downsized image.
4. Calculate (and save) the lower-right corner of your 8×8 patch from the downsized image.
5. Using the coordinates you calculated, extract the patch from your downsized image. Verify that it is 8×8 pixels. If it is not, adjust your math and try again.
   Note: If you get errors about your subscript indices (that they must be positive or exceed the matrix dimensions) choose a different value for k and try again. We'll fix that error in a moment.
6. Display your image patch. The following sequence of commands are a handy way to visualize very small images

   imagesc(img,[0 1]); % Display the image with black 0 and white 1

   colormap(gray);     % Render in grayscale

   axis equal off;     % Use square pixels and turn off borders

   colorbar;           % Indicate data range
7. Extract and display the corresponding 8·5×8·5 patch from the original image.
8. How do the two patches compare?
   Note: You may want to use subplot to render the two patches in the same figure window for the reader's easier visual analysis in your final report.
9. For reference, display your original image with a plus where the feature keypoint (patch center) location is.

C. Patch Processing

To match patches imaged under different illumination conditions we must normalize the overall bias and gain of the patch so that it has zero mean and unit variance.

1. To normalize the bias, calculate a new version of the 8×8 patch by subtracting the mean of all the pixels in the patch. (Remember the mean procedure expects a vector!)
2. To normalize the gain, calculate another version of the patch by dividing the bias-normalized version by its standard deviation. (The std procedure also expects a vector.)
3. Display your normalized patch. (If you omit the bounds for imagesc, it will automatically use the lowest and highest values in the image matrix as black and white, respectively).
4. How does the normalized patch compare visually to its corresponding un-normalized version? Note the actual values for both; how will the histograms compare?

D. Processing Keypoints

Now we will generalize the processing you've done to operate on any image and calculate features for (almost) all its keypoints.

1. Open a file called kpfeat.m in your Matlab editor of choice.
2. Add a declaration line to your function so that it takes two parameters, an image and its corresponding matrix of feature keypoint detections (i.e., the output of kpdet), and returns two values, the N×64 matrix of feature descriptors and a corresponding N×2 matrix of the features' row and column coordinates.
3. Add your initial code for processing the image to the file (e.g. A.2-A.6).
4. Add a for loop over all the N keypoints given by the second argument. Within your loop you should apply the steps from parts C and D to extract and normalize the patch.
   Note: You do not need visualize anything here or extract the larger patch.
5. Set the kth row of your N×64 matrix to the entries in your normalized patch. For instance,

   features(k,:) = norm_patch(:);
6. There is a possibility that the region you are trying to extract the patch from may fall outside the bounds of the image. Add a check to make sure that the upper-left corner and lower-right corner of the image all fall within bounds. If they fall outside of the bounds, set the entries in the kth row of your feature matrix to the Matlab value NaN (not a number) and use the keyword continue to advance the loop to the next iteration. We'll keep these entries around so that there is some agreement with the output of the kpdet function.
   Hint: The size command can tell you a variable's dimensions.
7. You should now have a procedure that extracts the feature descriptors from an image. Test it out! In the next lab, we'll implement a matcher.

Extra Credit: Putting the "O" back in MOPS

To normalize for the gradient orientation and make the descriptor robust to rotation, you can rotate the image before extracting the patch. However, the location of the image features changes with the rotation, so we need to control for that. In general, a 2×2 rotation matrix R describes the transformation of points in the space for a rotation of angle θ:

R= ⎡ ⎢ ⎢ ⎣ cosθ −sinθ sinθ cosθ ⎤ ⎥ ⎥ ⎦ .

The rotation from point x to point x^′ is done by a simple matrix-vector multiplication

x′=Rx

where x^′=[x^′,y^′]^T and x=[x,y]^T. You can use the built-in Matlab function function imrotate to rotate the image. However, because the origin for an image is not abitrary, we have to do a little bit more work to find the location of a rotated point in the result. Let c be the column vector of the center pixel in the original image and c^′ the same in the rotated image. In this scenario we shift by the old center before the transformation and the new center afterward:

x′=R(x−c)+c′,

or if you prefer the structure parallelism be reflected:

x′−c′=R(x−c).

1. Use imrotate and the mathematics above to extract orientation-normalized patches. Note that you will need to have a version of kpdet.m that produces the orientation (extra credit on the previous lab).
2. Demonstrate the functionality of your code by
   • extracting features from an image and its rotated version (even better if the object is rotated in real life, rather than synthetically)
   • manually matching one of the corresponding features between the two images
   • comparing the detected orientation of those features
   • visualizing the MOPS descriptors for the matched features
   • making brief observations comparing the descriptors