1 of 30

Keypoint Application: Panorama

Juan Carlos Niebles and Adrien Gaidon

Stanford Vision and Learning Lab

Slides by Anooshree Sengupta

Linear Algebra Review

Stanford University

27-Sep-2018

1

2 of 30

Outline

  • Quick review of keypoints and RANSAC
  • Panorama formulation
  • Matching corresponding keypoints
  • Stitching images together with affine transformation

Linear Algebra Review

Stanford University

27-Sep-2018

2

3 of 30

Outline

  • Quick review of keypoints and RANSAC
  • Panorama formulation
  • Matching corresponding keypoints
  • Stitching images together with affine transformation

Linear Algebra Review

Stanford University

27-Sep-2018

3

4 of 30

What are keypoints?

Reliable, unique points in images which can be used to find corresponding regions in different images of the same scene

Linear Algebra Review

Stanford University

27-Sep-2018

4

5 of 30

Finding keypoints

Harris Corner Detector

Use gradient Eigenvalues to find corners at a certain scale

Harris-Laplacian

Find keypoints using Harris and scale using Laplacian filter

DoG

Use DoG filters to find keypoints across space and scale

SCALE INVARIANT

Linear Algebra Review

Stanford University

27-Sep-2018

5

6 of 30

Describing keypoints

SIFT Descriptor

Keypoints as histogram of normalize gradient orientation

HoG

Region (or image) as histograms of local gradients

ROT. + SCALE INVARIANT

Linear Algebra Review

Stanford University

27-Sep-2018

6

7 of 30

RANSAC – algorithm for model fitting

  • Repeat n times:
    • Sample and form hypothesis
    • Find number of inliers
    • If max_inliers, save model
  • Recompute model on inliers

Linear Algebra Review

Stanford University

27-Sep-2018

7

8 of 30

RANSAC – algorithm for model fitting

  • Repeat n times:
    • Sample and form hypothesis
    • Find number of inliers
    • If max_inliers, save model
  • Recompute model on inliers

Linear Algebra Review

Stanford University

27-Sep-2018

8

9 of 30

RANSAC – algorithm for model fitting

  • Repeat n times:
    • Sample and form hypothesis
    • Find number of inliers
    • If max_inliers, save model
  • Recompute model on inliers

Linear Algebra Review

Stanford University

27-Sep-2018

9

10 of 30

RANSAC – algorithm for model fitting

  • Repeat n times:
    • Sample and form hypothesis
    • Find number of inliers
    • If max_inliers, save model
  • Recompute model on inliers

Linear Algebra Review

Stanford University

27-Sep-2018

10

11 of 30

RANSAC – algorithm for model fitting

  • Repeat n times:
    • Sample and form hypothesis
    • Find number of inliers
    • If max_inliers, save model
  • Recompute model on inliers

Linear Algebra Review

Stanford University

27-Sep-2018

11

12 of 30

Outline

  • Quick review of keypoints and RANSAC
  • Panorama formulation
  • Matching corresponding keypoints
  • Stitching images together with affine transformation

Linear Algebra Review

Stanford University

27-Sep-2018

12

13 of 30

Panorama

Linear Algebra Review

Stanford University

27-Sep-2018

13

14 of 30

Panorama

Linear Algebra Review

Stanford University

27-Sep-2018

14

15 of 30

Key insight: leverage corresponding keypoints

Linear Algebra Review

Stanford University

27-Sep-2018

15

16 of 30

Problem 1: how to match keypoints?

Linear Algebra Review

Stanford University

27-Sep-2018

16

17 of 30

Problem 2: how to fit images?

Linear Algebra Review

Stanford University

27-Sep-2018

17

18 of 30

Outline

  • Quick review of keypoints and RANSAC
  • Panorama formulation
  • Matching corresponding keypoints
  • Stitching images together with affine transformation

Linear Algebra Review

Stanford University

27-Sep-2018

18

19 of 30

How to know if keypoints are “the same”?

Use keypoint descriptors!

Linear Algebra Review

Stanford University

27-Sep-2018

19

20 of 30

Matching algorithm

  • For every keypoint in image_1:
    • Compute the euclidean distance from every keypoint in image_2
    • Sort keypoints by distance
    • If the first keypoint’s distance is significantly smaller than the second keypoint’s, it’s a match!
  • Return all eligible matches for keypoints in image_1

Try this with one for-loop!

Linear Algebra Review

Stanford University

27-Sep-2018

20

21 of 30

Matching result

Linear Algebra Review

Stanford University

27-Sep-2018

21

22 of 30

Outline

  • Quick review of keypoints and RANSAC
  • Panorama formulation
  • Matching corresponding keypoints
  • Stitching images together with affine transformation

Linear Algebra Review

Stanford University

27-Sep-2018

22

23 of 30

Easy case: pictures taken from same angle

Linear Algebra Review

Stanford University

27-Sep-2018

23

24 of 30

Hard case: pictures taken from diff angles

Linear Algebra Review

Stanford University

27-Sep-2018

24

25 of 30

Find transformation between matches

  •  

​

​

1

​

​

1

​

​

1

​

​

1

​

​

1

​

​

1

​

​

1

​

​

1

 

 

Linear Algebra Review

Stanford University

27-Sep-2018

25

26 of 30

What if we have noisy matches?

Refine transformation matrix with RANSAC!

Linear Algebra Review

Stanford University

27-Sep-2018

26

27 of 30

Pick subset

Linear Algebra Review

Stanford University

27-Sep-2018

27

28 of 30

Fit affine matrix and find inliers

Linear Algebra Review

Stanford University

27-Sep-2018

28

29 of 30

Recompute matrix with all inliers and stitch!

Linear Algebra Review

Stanford University

27-Sep-2018

29

30 of 30

Outline

  • Quick review of keypoints and RANSAC
  • Panorama formulation
  • Matching corresponding keypoints
  • Stitching images together with affine transformation

Linear Algebra Review

Stanford University

27-Sep-2018

30