1 of 30

Image alignment

CS5760: Computer Vision

http://www.wired.com/gadgetlab/2010/07/camera-software-lets-you-see-into-the-past/

2 of 30

Reading

  • Szeliski (2nd edition): Chapter 8.1

3 of 30

Announcements

  • Project 2 code due Wednesday February 26 by 8pm
    • Please get started now if you haven’t already!
    • Report due Friday, February 28 by 8pm on CMSX
  • Take-home midterm to be released next Thursday
    • To be released at 12:55pm Thursday, Feb 27 (end of class)
    • Due Tuesday, March 4 by 11:40am (beginning of class)
    • Open book, open note (but no Google, ChatGPT, Gemini, etc)
    • To be done on your own
    • No slip days possible

4 of 30

Computing transformations

  • Given a set of matches between images A and B
    • How can we compute a transform T from A to B (e.g., an affine transform)?

​

​

​

​

​

​

​

    • Find transform T that best “agrees” with the matches

5 of 30

Computing transformations

?

6 of 30

Simple case: translations

How do we solve for ?

7 of 30

Simple case: translations

Mean displacement =

Displacement of match i =

8 of 30

Another view

  • System of linear equations
    • What are the knowns? Unknowns?
    • How many unknowns? How many equations (per match)?

9 of 30

Another view

  • Problem: more equations than unknowns
    • “Overdetermined” system of equations
    • We will find the least squares solution

​

10 of 30

Least squares formulation

  • For each point

​

​

​

  • we define the residuals as

11 of 30

Least squares formulation

  • Goal: minimize sum of squared residuals

​

​

​

​

  • “Least squares” solution
  • For translations, is equal to mean (average) displacement

12 of 30

Least squares formulation

  • Can also write as a matrix equation

2n x 2

2 x 1

2n x 1

13 of 30

Least squares

  • Find t that minimizes

​

​

  • To solve, form the normal equations

14 of 30

Questions?

15 of 30

Least squares: linear regression

y = mx + b

(yi, xi)

16 of 30

Linear regression

residual error

17 of 30

Linear regression

18 of 30

Affine transformations

  • How many unknowns?
  • How many equations per match?
  • How many matches do we need?

19 of 30

Affine transformations

  • Residuals:

​

​

​

  • Cost function:

20 of 30

Affine transformations

  • Matrix form

2n x 6

6 x 1

2n x 1

21 of 30

Homographies

​

​

To unwarp (rectify) an image

    • solve for homography H given p and p’
    • solve equations of the form: wp’ = Hp
      • linear in unknowns: w and coefficients of H
      • H is defined up to an arbitrary scale factor
      • how many matches are necessary to solve for H?

p

p’

22 of 30

Minimum number of matches to compute homography = 4

23 of 30

Solving for homographies

Not linear!

Multiplying each equation by the denominator of the RHS:

24 of 30

Solving for homographies

25 of 30

Solving for homographies

Defines a least squares problem:

    • Since is only defined up to scale, solve for unit vector
    • Solution: = eigenvector of with smallest eigenvalue
    • Works with 4 or more points

2n × 9

9

2n

26 of 30

Recap: Two Common Optimization Problems

Problem statement

Solution

 

 

 

Problem statement

Solution

 

 

 

 

(matlab)

27 of 30

Computing transformations

28 of 30

Questions?

29 of 30

Image alignment algorithm

Given images A and B

​

  1. Compute image features for A and B
  2. Match features between A and B
  3. Compute homography between A and B using least squares on set of matches

​

What could go wrong?

30 of 30

Outliers

outliers

inliers