1 of 47

What year will anyone be able to buy a self-driving car?

ⓘ Start presenting to display the poll results on this slide.

2 of 47

Feature descriptors and feature matching

3 of 47

Local features: main components

  1. Detection: Identify the interest points

​

​

​

​

  • Description: Extract vector feature descriptor surrounding each interest point.

​

​

​

​

  • Matching: Determine correspondence between descriptors in two views

Kristen Grauman

4 of 47

Feature descriptors

We know how to detect good points

Next question: How to match them?

​

​

​

​

​

​

​

​

Answer: Come up with a descriptor for each point, find similar descriptors between the two images

​

​

​

​

​

​

​

?

5 of 47

We know how to detect good points

Next question: How to match them?

​

​

​

​

​

​

Lots of possibilities

    • Simple option: match square windows around the point
    • State of the art approach: SIFT

​

​

​

​

​

​

​

​

​

​

​

?

Feature descriptors

6 of 47

Invariance vs. discriminability

  • Invariance:
    • Descriptor shouldn’t change even if image is transformed

​

  • Discriminability:
    • Descriptor should be highly unique for each point

7 of 47

Image transformations revisited

  • Geometric

​

Rotation�

​

Scale��

  • Photometric

Intensity change

8 of 47

Invariance

Suppose we are comparing two images I1 and I2

    • I2 may be a transformed version of I1
    • What kinds of transformations are we likely to encounter in practice?

9 of 47

Invariant descriptors

  • We looked at invariant / equivariant detectors

​

  • Most feature descriptors are also designed to be invariant to:
    • Translation, 2D rotation, scale

​

  • They can usually also handle
    • Limited 3D rotations (SIFT works up to about 60 degrees)
    • Limited affine transforms (some are fully affine invariant)
    • Limited illumination/contrast changes

10 of 47

How to achieve invariance

Need both of the following:

  1. Make sure your detector is invariant

2. Design an invariant feature descriptor

    • Simplest descriptor: a single 0
      • What’s this invariant to?
    • Next simplest descriptor: a square, axis-aligned 5x5 window of pixels
      • What’s this invariant to?
    • Let’s look at some better approaches…

11 of 47

Rotation invariance for feature descriptors

  • Find dominant orientation of the image patch (this orientation should be equivariant to image rotation)
    • E.g., given by xmax, the eigenvector of the second moment matrix H corresponding to λmax (the larger eigenvalue)
    • Or (better) simply the orientation of the (smoothed) gradient
    • Rotate the patch according to this angle

Figure by Matthew Brown

12 of 47

Multiscale Oriented PatcheS descriptor

Take 40x40 square window around detected feature

    • Scale to 1/5 size (using prefiltering)
    • Rotate to horizontal
    • Sample 8x8 square window centered at feature
    • Intensity normalize the window by subtracting the mean, dividing by the standard deviation in the window (why?)

CSE 576: Computer Vision

8 pixels

40 pixels

Adapted from slide by Matthew Brown

13 of 47

Detections at multiple scales

14 of 47

Scale Invariant Feature Transform

Basic idea:

    • Take 16x16 square window around detected feature
    • Compute edge orientation (angle of the gradient - 90°) for each pixel
    • Throw out weak edges (threshold gradient magnitude)
    • Create histogram of surviving edge orientations
    • Shift the bins so that the biggest one is first

Adapted from slide by David Lowe

0

2π

angle histogram

15 of 47

SIFT descriptor

Full version

    • Divide the 16x16 window into a 4x4 grid of cells (2x2 case shown below)
    • Compute an orientation histogram for each cell
    • 16 cells * 8 orientations = 128 dimensional descriptor

​

​

Adapted from slide by David Lowe

16 of 47

Properties of SIFT

Extraordinarily robust matching technique

    • Can handle changes in viewpoint (up to about 60 degree out of plane rotation)
    • Can handle significant changes in illumination (sometimes even day vs. night (below))
    • Pretty fast—hard to make real-time, but can run in <1s for moderate image sizes
    • Lots of code available

17 of 47

Maximally Stable Extremal Regions

  • Maximally Stable Extremal Regions
    • Threshold image intensities: I > thresh�for several increasing values of thresh
    • Extract connected components�(“Extremal Regions”)
    • Find a threshold when region is “Maximally Stable”, i.e. local minimum �of the relative growth
    • Approximate each region with �an ellipse

J.Matas et.al. “Distinguished Regions for Wide-baseline Stereo”. BMVC 2002.

18 of 47

SIFT Example

sift

868 SIFT features

19 of 47

Other descriptors

  • HOG: Histogram of Gradients (HOG)
    • Dalal/Triggs
    • Sliding window, pedestrian detection

​

  • FREAK (Fast Retina Keypoint) or ORB features
    • Can run in real-time; used in Visual SLAM on-device

​

  • LIFT: Learned Invariant Feature Transform
    • Learned via deep learning – along with many other recent features

https://arxiv.org/abs/1603.09114

​

20 of 47

Questions?

21 of 47

Summary

​

  • Keypoint detection: repeatable and distinctive
    • Corners, blobs
    • Harris, DoG

​

  • Descriptors: robust and selective
    • spatial histograms of orientation
    • SIFT and variants are typically good for stitching and recognition
    • But, need not stick to one

​

​

​

22 of 47

Which features match?

23 of 47

Feature matching

Given a feature in I1, how to find the best match in I2?

    • Define distance function that compares two descriptors
    • Test all the features in I2, find the one with min distance

(can be accelerated with a nearest neighbors search data structure, like a kd-tree)

24 of 47

Feature distance

How to define the difference between two features f1, f2?

    • Simple approach: L2 distance, || f1 - f2 ||
    • can give small distances for ambiguous (incorrect) matches

I1

I2

f1

f2

25 of 47

f1

f2

f2'

Feature distance

How to define the difference between two features f1, f2?

    • Better approach: ratio distance = || f1 - f2 || / || f1 - f2’ ||
      • f2 is the best SSD match to f1 in I2
      • f2’ is the 2nd best SSD match to f1 in I2
      • gives large values for ambiguous matches

I1

I2

26 of 47

  • Does the SSD vs “ratio distance” change the best match to a given feature in image 1?
  • No, but it changes the distance, and it can change the ordering of matches from good to bad
  • After we compute a set of matches, we threshold by distance (that is, throw out matches with distance > threshold)

Feature distance

27 of 47

Feature matching example

58 matches (thresholded by ratio score)

28 of 47

Feature matching example

51 matches (thresholded by ratio score)

We’ll deal with outliers later

29 of 47

Evaluating the results

How can we measure the performance of a feature matcher?

50

75

200

feature distance

30 of 47

True/false positives

​

​

​

​

​

​

​

​

​

​

The distance threshold affects performance

    • True positives = # of detected matches that survive the threshold that are correct
    • False positives = # of detected matches that survive the threshold that are incorrect

50

75

200

false match

true match

feature distance

How can we measure the performance of a feature matcher?

31 of 47

True/false positives

​

​

​

​

​

​

​

​

​

​

Suppose we want to maximize true positives. How do we set the threshold? (Note: we keep all matches with distance below the threshold.)

50

75

200

false match

true match

feature distance

How can we measure the performance of a feature matcher?

32 of 47

True/false positives

​

​

​

​

​

​

​

​

​

​

Suppose we want to minimize false positives. How do we set the threshold? (Note: we keep all matches with distance below the threshold.)

50

75

200

false match

true match

feature distance

How can we measure the performance of a feature matcher?

33 of 47

Suppose we want to maximize true positives. How do we set the threshold? (We keep all matches with distance below the threshold.)

ⓘ Start presenting to display the poll results on this slide.

34 of 47

Suppose we want to minimize false positives. How do we set the threshold? (We keep all matches with distance below the threshold.)

ⓘ Start presenting to display the poll results on this slide.

35 of 47

Example

  • Suppose our matcher computes 1,000 matches between two images
    • 800 are correct matches, 200 are incorrect (according to an oracle that gives us ground truth matches)
    • A given threshold (e.g., ratio distance = 0.6) gives us 600 correct matches and 100 incorrect matches that survive the threshold
    • True positive rate = 600 / 800 = ¾
    • False positive rate = 100 / 200 = ½

36 of 47

Evaluating the results

0.7

0

1

1

false positive rate

true�positive�rate�

0.1

How can we measure the performance of a feature matcher?

recall

1 - specificity

# true positives surviving threshold

# total correct matches (positives)

# false positives surviving threshold

# total incorrect matches (negatives)

37 of 47

0.7

0

1

1

false positive rate

true�positive�rate�

# true positives surviving threshold

# total correct matches (positives)

0.1

# false positives surviving threshold

# total incorrect matches (negatives)

ROC curve (“Receiver Operator Characteristic”)

How can we measure the performance of a feature matcher?

recall

1 - specificity

Single number: Area Under the Curve (AUC)

E.g. AUC = 0.87

1 is the best

Evaluating the results

38 of 47

ROC curves – summary

  • By thresholding the match distances at different thresholds, we can generate sets of matches with different true/false positive rates
  • ROC curve is generated by computing rates at a set of threshold values swept through the full range of possible thresholds
  • Area under the ROC curve (AUC) summarizes the performance of a feature pipeline (higher AUC is better)

39 of 47

More on feature detection/description

http://www.robots.ox.ac.uk/~vgg/research/affine/

http://www.cs.ubc.ca/~lowe/keypoints/

http://www.vision.ee.ethz.ch/~surf/

​

40 of 47

Lots of applications

Features are used for:

    • Image alignment (e.g., mosaics)
    • 3D reconstruction
    • Motion tracking
    • Object recognition
    • Indexing and database retrieval
    • Robot navigation
    • … other

41 of 47

Object recognition (David Lowe)

42 of 47

3D Reconstruction

Internet Photos (“Colosseum”)

Reconstructed 3D cameras and points

43 of 47

WildGaussians: first reconstruct cameras using feature matching, then create dense model

Kulhanek, et al. WildGaussians. NeurIPS 2024

44 of 47

Sony Aibo

​

SIFT usage:

​

  • Recognize

charging

station

​

  • Communicate

with visual

cards

​

  • Teach object

recognition

45 of 47

Augmented Reality

46 of 47

Learned feature matchers

LoFTR: Detector-Free Local Feature Matching with Transformers

CVPR 2021 [Sun, Shen, Wang, et al.]

47 of 47

Learned feature matchers

RoMa: Robust Dense Feature Matching, CVPR 2024