Description
Project 2: Feature Detection and Matching
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, scale, 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 1: Hybrid Images 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 3×3 neighborhood.
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.
2
Project 1: Hybrid Images CENG 414/514
For starters, try using a small square window (say 5×5) 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 prject should be completed on Jupyter notebooks and should provide a brief overview
with an illustration of your results. In addition, your notebook will need to detail the entire
project, discussing your proposed approach to description, matching, and correspondence,
and illustrating the success and failures in your approach.
As for the output, I will provide a set of “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
3
Project 1: Hybrid Images CENG 414/514
with colored lines drawn between the features in each image showing that they do indeed
correspond.
Rubric
• +50 pts: Working implementation of feature detection and feature description.
• +25 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.
• +05 pts: Writeup.
• -05*n pts: Where n is the number of times that you do not follow the instructions.
Extra Credit:
Here are some possible extra credit extensions (feel free to come up with your own variants
to make your program more robust and efficient) document these if you do them in your
notebook:
• 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