Feature detection/ matching

Question 1

Describe the steps in the RANSAC algorithm

Answer 1

1. Calculate model parameters from n random data points, where n is the minimum required points
2. Evaluate inlier percentage for this model with a distance threshold t
3. If inlier percentage is the current max, save this model
4. Repeat N times
5. Use the inliers from the best model and create a better model using least squares or similar methods

Question 2

Describe RANSAC in one sentence

Answer 2

RANSAC is a robust (handles outliers) method for estimating the parameters of a mathematical from observed data

Question 3

What should the RANSAC threshold be if the noise in the data has a normal distribution

Answer 3

Around 2 sigma

Question 4

The formula used for deciding N(Number of runs) in the RANSAC algorithm is log(1-p)/log(1-w^n). p is the probability of sampling at least one set without outliers, n is the number of data points used to estimate parameters and w is the er probability of a data point being an inlier. How is p and w usually decided

Answer 4

p is usually set to 0.99

w is approximated for each run.

Question 5

What is the full name of RANSAC

Answer 5

RANdom SAmple Consensus

Question 6

How is the canonical orientation of a feature point normally decided

Answer 6

The local patch is rotated so that the direction of the maximum gradient is pointing upwards.

Question 7

Describe the steps from feature detection to feature matching

Answer 7

1. Detect feature points in the image
2. Define a local patch around the feature
3. Extract and normalize the local patch
4. Create a local descriptor
5. Match features by calculating the distance between the descriptors.

Question 8

What is SIFT short for

Answer 8

Scale Invariant Feature Transform

Question 9

What type of descriptor do the SIFT and SURF algorithms use

Answer 9

HoG (Histogram of Gradients).

The other type of descriptors are binary descriptors.

Question 10

Describe the steps in the SIFT algorithm

Answer 10

1. Use LoG pyramids to determine the canonical scale and HoG to determine the canonical orientation.
2. Normalize the patch to 16x16 pixels, compute the gradients and apply a Gaussian weighting to the gradients.
3. Divide the 16x16 patch into 4x4, compute 8 gradient directions in each square and concatenate these gradients into a 128 feature vector.
4. Normalize to unit length, threshold to 0.2 and renormalize.

Question 11

What is the main advantage of binary descriptors, and how is this achieved

Answer 11

The main advantage is computational speed. The descriptors are binary strings and the hamming distance (XOR) can be used for matching. The XOR function is computationally very efficient.

Question 12

Name some binary descriptor algorithms

Answer 12

BRIEF, ORB, BRISK, FREAK

Question 13

Name some distance functions used for feature matching

Answer 13

L1, L2, Hamming(XOR)

Question 14

Explain the ROC curve

Answer 14

The ROC curve measures true positive rate( true positives/matched features) vs. false positive rate( false postivies/ unmatched features)

Question 15

Explain the ratio test

Answer 15

Keep the two best matches. if distance of the first divided by distance of the second is larger than some threshold (0.8) throw away the match.

Question 16

What is the minimum number of corresponding data points in two images required to calculate a homography

Answer 16

4, where no 3 points are collinear

Question 17

Describe the DLT (direct linear transform) for finding homographies.

Answer 17

1. Transform the problem to a matrix equation on the form Ah = 0.
2. Normalize
3. Obtain the SVD of A.
4. If S is diagonal with positive values in descending order, h is the last column of V
5. Denormalize and reconstruct the homography H from h.

Question 18

Why are the parameters often normalized in the DLT.

Answer 18

The DLT performs best when all parameters are of similar scale.

Question 19

What different kind of errors can be used when using RANSAC to determine Homographies

Answer 19

Algebraic error:
e_i = ||A_i*h||

Geometric errors:
e_i = d(Hu_i, u_i2) + d(u_i, (H^-1)u_i2) (Reprojection error)
e_i = d(Hu_i, u_i2)
e_i = d(u_i, (H^-1)u_i2)

Question 20

How is the SVD used to solve matrix equations on the form: Ah=0

Answer 20

The nullspace of A is a linear combination of the singular vectors with singular value equal to 0 or no singular value.

Question 21

How can we detect lines in images

Answer 21

Using the Hough transform

Question 22

What are the important characteristics of good feature points

Answer 22

1. Distinct
2. Local
3. Efficient
4. Reprodusable

Question 23

What is the interpretation of the eigenvalues and vectors of the M matrix in corner detection?

Answer 23

The eigenvalues describe the max/min change and the vectors describe the direction of the max/ min change

Question 24

What is an important property for edge features

Answer 24

Small movements in any direction should equal large changes in the feature point. This is equal to the smallest eigenvalue of M being large.

Question 25

What operator is often used to score corner features

Answer 25

The Harris operator (det(M) - alpha*trace(M))

Question 26

Is the Harris detector invariant to affine changes in pixel intensity?

Answer 26

Only partially (Yes to additive changes, no to scaling)

Question 27

Why is the Harris detector invariant to additive changes in pixel intensity

Answer 27

Only the derivatives are used.

Question 28

How can we solve the problem that the Harris detector isn’t invariant to image scaling?

Answer 28

We can compute the Harris score for several scales, and choose the largest. This is the canonical scale.

Question 29

When will the Laplace operator have the maximum response for a binary circle?

Answer 29

When the zeros of the Laplace align perfectly with the circle edge.

Question 30

Why is the Laplace pyramid used in blob detection?

Answer 30

To detect blobs at different scales.

Question 31

Name some methods used for edge detection

Answer 31

Canny, Laplace, Sobel

Question 32

What is the idea behind binary feature detectors

Answer 32

A local neighborhood is divided into points. These points are connected to each other and score of 1 is assigned if a point has a larger value than the previous point, else 0.

Question 33

What is the M matrix in edge feature detection?

Answer 33

The M matrix describes changes if the local patch is slightly moved.

Question 34

When are two images related by a homography?

Answer 34

If the images are captured from a planar scene

Question 35

What is a canonical affine transformation?

Answer 35

A local patch normalization using affine transforms. This allows rotated planes etc. to be matched.

Question 36

Describe the cross check test (Alternative to the ratio test)

Answer 36

Measures the projection both ways. Matches are accepted only if fa is the best match for fb AND fb is the best match for fa.

Question 37

What is: Invariance and Covariance?

Answer 37

– Invariance: image is transformed and corner locations do not change
– Covariance: if we have two transformed versions of the same image, features should be detected in corresponding locations