Feature detection/ matching Flashcards
Describe the steps in the RANSAC algorithm
- Calculate model parameters from n random data points, where n is the minimum required points
- Evaluate inlier percentage for this model with a distance threshold t
- If inlier percentage is the current max, save this model
- Repeat N times
- Use the inliers from the best model and create a better model using least squares or similar methods
Describe RANSAC in one sentence
RANSAC is a robust (handles outliers) method for estimating the parameters of a mathematical from observed data
What should the RANSAC threshold be if the noise in the data has a normal distribution
Around 2 sigma
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
p is usually set to 0.99
w is approximated for each run.
What is the full name of RANSAC
RANdom SAmple Consensus
How is the canonical orientation of a feature point normally decided
The local patch is rotated so that the direction of the maximum gradient is pointing upwards.
Describe the steps from feature detection to feature matching
- Detect feature points in the image
- Define a local patch around the feature
- Extract and normalize the local patch
- Create a local descriptor
- Match features by calculating the distance between the descriptors.
What is SIFT short for
Scale Invariant Feature Transform
What type of descriptor do the SIFT and SURF algorithms use
HoG (Histogram of Gradients).
The other type of descriptors are binary descriptors.
Describe the steps in the SIFT algorithm
- Use LoG pyramids to determine the canonical scale and HoG to determine the canonical orientation.
- Normalize the patch to 16x16 pixels, compute the gradients and apply a Gaussian weighting to the gradients.
- Divide the 16x16 patch into 4x4, compute 8 gradient directions in each square and concatenate these gradients into a 128 feature vector.
- Normalize to unit length, threshold to 0.2 and renormalize.
What is the main advantage of binary descriptors, and how is this achieved
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.
Name some binary descriptor algorithms
BRIEF, ORB, BRISK, FREAK
Name some distance functions used for feature matching
L1, L2, Hamming(XOR)
Explain the ROC curve
The ROC curve measures true positive rate( true positives/matched features) vs. false positive rate( false postivies/ unmatched features)
Explain the ratio test
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.
What is the minimum number of corresponding data points in two images required to calculate a homography
4, where no 3 points are collinear
Describe the DLT (direct linear transform) for finding homographies.
- Transform the problem to a matrix equation on the form Ah = 0.
- Normalize
- Obtain the SVD of A.
- If S is diagonal with positive values in descending order, h is the last column of V
- Denormalize and reconstruct the homography H from h.
Why are the parameters often normalized in the DLT.
The DLT performs best when all parameters are of similar scale.
What different kind of errors can be used when using RANSAC to determine Homographies
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)
How is the SVD used to solve matrix equations on the form: Ah=0
The nullspace of A is a linear combination of the singular vectors with singular value equal to 0 or no singular value.
How can we detect lines in images
Using the Hough transform
What are the important characteristics of good feature points
- Distinct
- Local
- Efficient
- Reprodusable
What is the interpretation of the eigenvalues and vectors of the M matrix in corner detection?
The eigenvalues describe the max/min change and the vectors describe the direction of the max/ min change
What is an important property for edge features
Small movements in any direction should equal large changes in the feature point. This is equal to the smallest eigenvalue of M being large.
