---
title: SIFT and Feature Matching
categories: session
---

**Reading** 
[Szeliski (2022)](https://szeliski.org/Book/) Chapter 7;
[Lowe 2004](https://link.springer.com/article/10.1023/B:VISI.0000029664.99615.94)

Szeliski provides an alternative introduction to 
[Corner Detection]() in general, and also discusses feature descriptors
in some generality.  For the specifics of SIFT, the original paper by 
[Lowe 2004](https://link.springer.com/article/10.1023/B:VISI.0000029664.99615.94)
may prove easier to read and more useful.

This [tutorial](https://aishack.in/tutorials/sift-scale-invariant-feature-transform-features/)
also seems useful.  Note that there are several chapters, more or less practical.

**Briefing** [Feature Descriptors]()

# Exercises

In the exercise, you should use the OpenCV implementation of SIFT, and
test feature matching between pairs of imnages.

Start by finding one or more pairs of images.
There has to be an overlap (30-40%) where you expect to find corners in both images.
You can of course use two frames from the video you used in the previous exercise.
It may be a good idea to test different pairs, to learn what can and cannot be
matched.

## Exercise 1

Use one of the two images in this exercise.
We are going to compare the results of the Harris detector with the SIFT
detector.

1.  Detect and draw corners as you have done earlier, using the harris corner detector.
2.  Repeat using the SIFT detector implemented in opencv, e.g.:
    ```python
      sift = cv.SIFT_create()
      kps = sift.detect(img_gray)
    
      kps, desc = sift.compute(img_gray, kps)
    ```
    Compare the results, how does the keypoints correlate?
3.  Opencv has the function `cv.drawKeypoints` that can be used to 
    draw keypoints from the SIFT detector.
    Look up the documentation and test this funcion. 
4.  When the key points are drawn, the function will also visualize the
    "strength" of the keypoint with a larger circle,
    Does the strength affect the correlation?

## Exercise 2

Following is a code-snippet to print some information from one of the SIFT-keypoints:

```python
print(f"{kps[0].pt[0]}") # x: It is the position of the keypoint with respect to the x-axis
print(f"{kps[0].pt[1]}") # y: It is the position of the keypoint with respect to the y-axis
print(f"{kps[0].size}") # size: It is the diameter of the keypoint
print(f"{kps[0].angle}") # angle: It is the orientation of the keypoint
print(f"{kps[0].response}") # response: Also known as the strength of the keypoint, it is the keypoint detector response on the keypoint
print(f"{kps[0].octave}") # octave: It is the pyramid octave in which the keypoint has been detected
print(f"{desc[0]}") # keypoint-descriptor
```

Find a few keypoints and consider the meaning of the information from the snippet above.<br>
NB: The keypoints are not sorted, you can sort them by e.g. strength (descending) with the following code:

`kps_s, desc_s = zip(*sorted(list(zip(kps, desc)), key=lambda pt: pt[0].response, reverse=True))`

## Exercise 3

Apply SIFT to both images, where do you expect to find overlapping features?

Implement a brute-force feature matcher,
using the Euclidian distance between the keypoint descriptors.
In other words, for a given a point (descriptor) $X_1$ in image 1,
we calculate the Euclidean distance from this descriptor to each
of the point (descriptor) in image 2.
The point $X_1$ is matched with the point $X_2$ in image 2 that has the smallest
Euclidean distance.

The Euclidian distance can be calculated using the `cv.norm` with 
`normType=cv.NORM_L2`.<br>
More information on feature-matching can be found in chapter 7.1.3
of [Szeliski’s textbook](https://szeliski.org/Book/) textbook,

Combine/stack the two images horizontally and draw a line between the matching keypoints.

+ You can combine with e.g. `np.concatenate((img1, img2), axis=1)` (Only for gray-scale images of the same size)
+ You can draw a line with `cv.line`
+ Use the OpenCV documentation for details.

## Exercise 4

Let us now review what kind of errors we have in the matching from Exercise 3.

+ True Positive is a correctly matched feature point.
+ False Positive is an incorrectly matched feature point.
+ False Negative is a point falsely left unmatched
+ True Negative is a non-match correctly rejected.

+ Where do you have True-Positives, False-Positives, False-Negatives and True-Negatives?

If you do not have any false-positives/Negatives, try with a more complex image set.

## (Optional) Exercise 5

To remove false-positives we can use Lowe's ratio test, where we remove keypoints that have multiple possible matches.

From [StackOverflow](https://stackoverflow.com/questions/51197091/how-does-the-lowes-ratio-test-work):
<br>
"Short version: each keypoint of the first image is matched with a number of keypoints from the second image.
We keep the 2 best matches for each keypoint (best matches = the ones with the smallest distance measurement).
Lowe's test checks that the two distances are sufficiently different.
If they are not, then the keypoint is eliminated and will not be used for further calculations."

Implement this filtering function.

# Debrief