Feature points

Question 1

Name three methods for Image Matching.

Answer 1

1) By pixels
2) By edges
3) By feature (interest) points

Question 2

How can we detect corners by looking at the neighborhood of a pixel in an image?

Answer 2

If we have a corner and move the neighborhood in any direction, the pixel values in the neighborhood should change a lot. (High gradient in all direction)

Question 3

How can we approximate E(u,v) the error when shifting the neighborhood by u,v pixels?

Answer 3

E(u,v) = [u,v] M [u, v]^T where M is the matrix:

M = [Ix^2 Ixy
Iyx Iy^2]

and Ix, Iyx, Iy are the derivatives.

Question 4

If l1, l2 are the eigenvalues of the M matrix, what kind of image structures are we looking at when:

1) l1&raquo_space; l2
2) l1 and l2 are small
3) l1 and l2 are large

Answer 4

1) An edge
2) A flat region
3) A corner

Question 5

Given the M matrix, what metrics can be used to determine if we have a corner?

Answer 5

1) R = min(lambda_1, lambda_2)
2) R = lambda_1lambda_2 /(lambda_1 + lambda_2 + epsilon)
3) R = lambda_1lambda_2 - k(lambda_1 + lambda_2)^2
4) R= det(M) - k*trace(M)^2

where lambda_1 and lambda_2 are the eigenvalues

Question 6

Describe the Harris Corner Detector

Answer 6

1) compute Ix and Iy
2) Create M
3) calculate eigenvalues lambda_1, lambda_2
4) Calculate the Respons R = lambda_1lambda_2 + k(lambda_1 + lambda_2)^2
5) Threshold and Non-Maxima repression with respect to R

Question 7

What other structures than corners can the Harris detector detect?

Answer 7

Textures and blobs

Question 8

Is the Harris detector invariant to rotation?

Answer 8

Yes

Question 9

How can we make the Harris detector invariant to scale?

Answer 9

Perform Gaussian filtering at different scales and use the highest response. (The image has to be multiplied by sigma to make the derivatives comparable.)

Question 10

What is the Harris Laplace detector?

Answer 10

For each pixel, use find the optimal scale using the LoG response and calculate the Harris Respons at that scale.

Question 11

How are DoG and LoG filters correlated

Answer 11

DoG(x,y,k,sigma) = I * G(ksigma) - I *G(sigma) 
approx= (k-1)sigma^2Log(x,y,sigma)

Question 12

How does the SIFT algorithm find the optimal response

Answer 12

By using DoGs with different scales and downsampling the image. The extremum indicates the optimal scale for each pixel.

Question 13

Describe the difference between the Harris/ Laplace detector and the SIFT detector

Answer 13

Harris/ Laplace:

1. Use the LoG at different scales to find an optimal scale
2. Find local maxima by using the Harris response

SIFT:

1. Use DoG at different scales to find the optimal scale
2. Find local maxima using the DoG response

Question 14

What is the simplest feature descriptor, and what are the disadvantages?

Answer 14

Use pixel value.

Sensitive to brightness and a lot of pixels will have the same descriptor.

Question 15

What are the disadvantages of using a local patch to describe feature points?

Answer 15

1) Sensitive to brightness

2) Sensitive to rotation

Question 16

What are the advantages/disadvantages of using a local patch of gradients to describe feature points?

Answer 16

Advantage: Not sensitive to (additive) brightness
Disadvantage: Still sensitive to other brightness changes and not rotation invariant.

Question 17

What are the advantages/disadvantages of using a histogram of a local patch of gradients to describe feature points?

Answer 17

Advantage: Rotation invariant
Disadvantage: Sensitive to changes in brightness.

Question 18

Describe the SIFT algorithm for keypoint detection

Answer 18

1) Find scale/ space extrema using DoG response
2) Fit a quadratic function over space to the extremes and estimate a refined new keypoint (can be in between pixels…)
3) Threshold keypoint responses

Question 19

Describe how we can determine the canonical orientation of each patch in the SIFT algorithm

Answer 19

1) Create a histogram of 36 bins for degrees from 0-360
2) Each pixel in a neighborhood vote for an orientation weighted by gradient magnitude.
3) The keypoint is assigned an orientation corresponding to the largest bin.

Question 20

How is the SIFT descriptor created?

Answer 20

1) Take a small window around the keypoint
2) weigh gradients near the center more.
3) Calculate the gradient orientation and magnitude after using a Gaussian filter.
4) Calculate the canonical orientation
5) Rotate all gradient directions relative to the canonical orientation
6) Create a histogram of gradient orientations for each subregion in the local window (Originally 16 subregions and 8 direction histogram).
7) These 16 histograms form a 128-feature vector and are used as a descriptor.

Question 21

How can we determine what keypoints match in different images?

Answer 21

use the nearest neighbor or approximations of the nearest neighbour (FLANN)

Question 22

How can we use keypoints to match images?

Answer 22

Create an affine equation for each keypoint use least squares solution

Question 23

How can we make image matching more robust to outliers?

Answer 23

Use RANSAC ( RANdom SAmple Consensus).

1) Choose the minimal amount of points needed to determine the transformation
2) Check how many points are inliers
3) If this model has the most inliers, save this model.
4) Continue until termination.

Question 24

Describe the main advantages of SIFT

Answer 24

1) Robust to intensity changes
2) Invariant to scale
3) Invariant to rotation

Question 25

What is the main difference between SURF and SIFT?

Answer 25

SURF is faster since it only considers horizontal and vertical gradients using the Haar wavelet. It uses 4 descriptors for each subregion, (sum dx, sum dy, sum |dx| , sum |dy|) and the total descriptor is of length 16*4=64.

Question 26

Shortly describe the main idea behind Binary descriptors

Answer 26

All points in a neighborhood are only compared to one other point. The descriptor value i is 0 if the first point is largest and 1 if the second point is largest. We can use the Hamming metric (XOR) for matching, making it extremely fast and we only need 1 byte for each element in the descriptor.