Week 6 and 7 - Local Features

Question 1

What is Exhaustive search in corner detection

Answer 1

Naive approach
Can change the scale (vary patch size) and compare surrounding features

Question 2

What is wrong with exhaustive search

Answer 2

Computationally inefficient
Unfeasible for large collections of data
Ineffective for recognition tasks

Question 3

How can we use Automatic scale selection

Answer 3

We need scale invariant feature detection
We want a function that is scale invariant when applied to a region
We consider the function to be any that involves all pixels in the region (eg intensity, texture)
We take the local maximum of this function
We scale the image (squish and expand along x axes)
x = region size
Again find the local maximum (will correspond to the same feature - not same coordinates)

Question 4

What is “blob detection”

Answer 4

The Laplacian of Gaussian

Question 5

What is The Laplacian of Gaussian for feature detection

Answer 5

it is scale invariant
Essentially the 2nd derivative of either x or y (partial second derivative)

Question 6

How do you carry out LoG on an image

Answer 6

Convolve the image with a Gaussian kernel followed by the Laplacian kernel, capturing regions of rapid intensity change

combine the two to make the Laplacian of gaussian kernel (one operation)

Question 7

What are the characteristics of LoG

Answer 7

Found using a single mask
Orientation information is lost
very noise sensitive (taking derivatives increases noise)

Question 8

What is the characteristic scale for LoG

Answer 8

The scale that produces the extreme value (peak) of the LoG response
Largest blob
The size of the blob is proportional to the characteristic scale

Question 9

How are blobs useful for local interest points

Answer 9

They give us the area to use

Question 10

How do we detect interest points at different scales

Answer 10

Image is convolved with the LoG filter at various levels of blur, determined by the standard deviation (σ) of the Gaussian kernel
Allows for feature detection at different scales

Question 11

What is the Harris-Laplace method

Answer 11

Multiscale harris corner detection: Identify points that are likely to be corners at different scales
Scale Selection based on Laplacian: Compute LoG at different scales

We do both because harris detection only finds corners and blob detection will find other interest points (combine to variety of interest points)

Question 12

How can we approximate LoG with DoG for efficient implementation

Answer 12

DoG = G(x, y, kσ)- G(x,y,σ)
(difference of gaussians - from two different levels of blur)
This is more efficient as we do not need to compute 2nd derivative
Gaussians are already automatically being computed in the gaussian pyramid

If we choose the correct values for sigma, we will get a very efficient computation

Question 13

How does a Gaussian pyramid work

Answer 13

The more Gaussian layers you use, the sigma adds up
large sigma -> more blurring
Increasing scale, lowers the resolution
So we subsample (do not need as many pixels to present a lower resolution image)

Question 14

How does interest point localisation with DoG work

Answer 14

construct DoG pyramid
detect local maxima in scale space
Thresholding, reject points with low contrast
edge elimination (ratio of principle curvatures)

Note: at this point we are still at candidate points and candidate patches -> have not actually begun to use interest regions

Question 15

What are the two strategies for scale-invariant detection

Answer 15

LoG
DoG as fast approximation

These can be used on their own or in combinations with single scale key-point detectors (eg harris corner detector)

Question 16

General Summary: Scale Invariant Detection

Answer 16

● Given: Two images of the same scene with a large scalemdifference between them.
● Goal: Find the same interest points independently in each image
● Solution: Search for maxima of suitable functions in scale and in space (over the image)

Question 17

What are the two main components of achieving feature invariance

Answer 17

1) Detector is invariant to translation, rotation and scale
Can find interest point and remove the effects of different scales

2) Design an invariant feature descriptor
This captures the information in a region around a detected interest point

Question 18

What is the simplest local feature descriptor

Answer 18

A square window of pixels
We write a region A as vector a and Region b as vector b
Each vector is a list of intensities within a patch (or some characteristic)
Calculate vector similarities

Question 19

What is the simplest local feature descriptor invariant to

Answer 19

Translation
but intensity, 3D viewpoint change and rotation will cause big differences

Question 20

How do detectors remove the effect of different scales for feature matching

Answer 20

Ensure they are scale invariant
use σ which is proportional to scale
normalise scales

Question 21

How do we use gradients as a feature descriptor

Answer 21

Take the intensity gradient of each pixel in the patch
Take the orientation (ignore magnitude as that is affected by illumination)
And build a histogram (after normalising using dominant direction)

Question 22

Why is it important to have rotation invariant descriptors

Answer 22

Want to find the dominant direction of gradient for the image patch
Then we rotate the patch according to this angle
This puts the patches into a canonical orientation (normalising)

Question 23

What is SIFT

Answer 23

Scale Invariant Feature Transform
A descriptor computation

Question 24

How does SIFT work

Answer 24

1) Localisation, uses DoG to find candidate interest points (takes note of scale)

2) Normalises to predefined size (16x16)

3) check if it is an edge and reject

4) Then finds the gradient orientation over a 16x16 pixel region around interest point

5) Computes histogram of image gradient orientations for all pixels within the patch

Question 25

How does Orientation Normalisation work

Answer 25

The resulting gradient orientation of the patch is quantised into 8 bins over 0-360 degrees

• compute orientation histogram
  -select dominant orientation
  -normalise: rotate to fixed orientation

Question 26

How does SIFT form vectors

Answer 26

It then divides the initial 16x16 window into 4x4 sub-patches: 16 cells each
compute histogram of gradient orientations for pixels in the sub patch ( 8 reference angles/bins)

Essentially for each sub patch, we have a vector of 8 dimensions (all invariant of scale and rotation)
We do this further sub patch computation to find finer details

(128 dimension: 4x4x8)

Question 27

What are the advantages of SIFT

Answer 27

• can handle changes in viewpoints up to ~60 degrees
  -can handle significant changes in illumination
  -fast and efficient

Question 28

What does one image computed with SIFT yield

Answer 28

n 128-dimensional descriptors
n scale parameters specifying size of each patch
n orientation parameters specifying angle of each patch
n 2D points giving positions of patches

Question 29

What are the two main components of match a features I1 to I2

Answer 29

1. Define a distance function that compares the two descriptors
2. Test all the features in I2, find the one with min distance

Question 30

How do we define a distance between two features f1, f2 (in descriptor I1, I2)

Answer 30

SSD(f1, f2)
sum of square difference between entries of two descriptors

Question 31

Why is SSD not good for distance calculating feature matching

Answer 31

Can give a very good score for a bad match (ambiguous)

Question 32

How to we improve SSD feature matching distance calculation

Answer 32

Ratio distance = SSD(f1, f2) / SSD(f1, f2’)

f2 = best SSD match to f1
f2’ = 2nd best SSD match to f1

Question 33

What will the ratio distance be for ambiguous matches

Answer 33

Large values (~1)

Question 34

How do we eliminate bad matches in feature matching

Answer 34

Thresholding
Throw out features with larger distance than threshold

high threshold -> more false positives
low threshold -> less true positives

Question 35

What is a ROC Curve

Answer 35

plots the true positive rate (y axis/recall) against the false positive rate (x axis/precision)

We want to maximise the area under the curve
useful for comparing different feature matching methods

Question 36

Advantages of local features

Answer 36

• Critical to find distinctive and repeatable local regions for multi-view matching
• Complexity reduction via selection of distinctive points.
• Describe images, objects, parts without requiring
  segmentation; robustness to clutter & occlusion.
• Robustness: similar descriptors in spite of moderate view changes, noise, blur, etc.