Project 2: Feature Detection and Matching

CSC/CENG 414/514
Project 2: Feature Detection and Matching
Logistics
• Download the datasets from D2L that contain images of overlapping information from
several locations.
• D2L: Submit your PDF writeup answering questions, illustrating methods, and
ample examples of feature detection and matching along with the processes you
used to generate them.
– Insert all code snippets within your document.
• Tennetive Due Date: Wednesday Mar. 18, 2019
Project Goals: Develop your own Python functions to compute image pyramids (you should
have done this in project 1), extract features and edges, and correspond said features between
successive image frames. The features that you detect and descriptors you develop should be
at least minimally invariant to rotation and illumination changes. The project has been
broken into different steps for your convenience.
Step 1: Feature extraction.
To help you display each feature in an image, you should first write a Python function (named
ShowFeatures) to display a red square depicting the dominant orientation. Your function
should take three input parameters, the (x, y) location in the image where a feature has been
detected, the scale that the feature was detected at, and a dominant orientation as determined
by your feature descriptor. Your function will not return anything but rather overlay your
feature locations on top of the image. An example of the output of such a function in action
is illustrated in Fig. 1.
1
Project 2: Feature Detection and Matching CSC/CENG 414/514
Figure 1: Example image showing features extracted at different scales and orientations.
The first step in this project (after you have a proper display function working) is to detect
interest points in an image. For this purpose, we will use the Harris corner detection method.
We will proceed as follows: For each point p = (x, y) in the image we consider a window of
pixels around this point and compute the Harris matrix H for the point defined as
H = w(x, y) ∗

I
2
x
IxIy
IxIy I
2
y

,
where the weighting function w should be chosen to be circularly symmetric for rotation
invariance. A common choice is a 3 × 3 or 5 × 5 Gaussian mask similar to
w =
1
273






1 4 7 4 1
4 16 26 16 4
7 26 41 26 7
4 16 26 16 4
1 4 7 4 1






.
Note that for each point p = (x, y), the matrix H is only 2×2. Therefore, to find the interest
points, we first need to compute the corner strength function
c(H) = λ1λ2
λ1 + λ2
=
det(H)
trace(H)
.
Once you’ve computed c(H) ∀p ∈ I, choose points where c(H) is above a user defined
threshold. You also want c(H) to be a local maximum in at least a 3x3 neighborhood.
2
Project 2: Feature Detection and Matching CSC/CENG 414/514
Note: Similar to the previous projects, you should NOT need to loop through every pixel in
the image to compute c(H)!
Step 2: Feature description.
Now that you’ve identified points of interest, the next step is to come up with a descriptor for
the feature centered at each interest point. This descriptor will be the representation you’ll
use to compare features in different images to see if they match.
For starters, try using a small square window (say 5x5) as the feature descriptor. This should
be very easy to implement and should work well when the images you’re comparing are
related by a translation.
Next, try implementing a better feature descriptor. You can define it however you want, but
you should design it to be robust to changes in position, orientation, and illumination. You
are welcome to use techniques described in lecture (e.g., detecting dominant orientations,
using image pyramids), or come up with your own ideas.
Step 3: Feature matching.
Now that you’ve detected and described your features, the next step is to write code to match
them, i.e., given a feature in one image, find the best matching feature in one or more other
images. This part of the feature detection and matching component is mainly designed to
help you test out your feature descriptor. You will implement a more sophisticated feature
matching mechanism in the second project when you do image alignment for the mosaicing.
The simplest approach is the following: write a Python function that compares two features
and outputs a distance between them. For example, you could simply sum the absolute value
of differences between the descriptor elements. You could then use this distance to compute
the best match between a feature in one image and the set of features in another image by
finding the one with the smallest distance. You are required to implement the following
two distance metrics and compare their performance:
(a) Use a threshold on the match score. This is called the SSD distance.
(b) Compute (score of the best feature match)/(score of the second best feature match). This
is called the “ratio test”.
Deliverables:
Your project should be completed using the IDE of your choice and documented using a
single PDF write-up (from the template provided). You should provide a brief overview
with an illustration of your results. In addition, your write-up will need to detail the entire
3
Project 2: Feature Detection and Matching CSC/CENG 414/514
project, discussing your proposed approach to description, matching, and correspondence,
and illustrating the success and failures in your approach.
As for the output, the Project 2 Dataset contains “benchmark” images for you to test your
algorithm on. At a minimum: For step 1 you are required to show images with your features
being overlaid on them using your ShowFeatures function you wrote. For step 2 you are
required to describe the feature descriptor you came up with and justify why you believe it is
invariant to image transformations. Further, if your descriptor uses a dominant orientation
direction (and it should), you should “zoom” in on a few of your feature locations to illustrate your orientation direction. Finally, you are required to display two (or more) images
side-by-side with colored lines drawn between the features in each image showing that they
do indeed correspond.
Rubric
• +40 pts: Working implementation of feature detection and feature description.
• +20 pts: Working implementation illustrating your detector and descriptor matching
features across images.
• +20 pts: Illustrate invariance to at least some changes in orientation and perspective.
• +20 pts: Writeup.
• -05*n pts: Where n is the number of times that you do not follow the instructions.
Extra Credit:
You can earn at MOST two from this list of possible extra credit extensions (10pts each) (feel
free to come up with your own variants to make your program more robust and efficient)
document these in your writeup if you decide to embark on them:
• Implement a version of adaptive non-maximum suppression.
• Implement automatic scale selection.
• Implement a scale invariant feature detector.
• Implement a better test for determining if two features match.
• Implement a better search method to speed up the matching process.
Some suggestions:
This is a big project. Therefore, I suggest that you divide and conquer. You should write
modular code so you can reuse it for future projects (i.e., functionalize everything if possible).
I would also recommend you write some helper functions to compute image gradients,
derivatives of Gaussians, Laplacians, image pyramids, etc.
4