Automatic Image Alignment, Part 3

with a lot of slides stolen from

Steve Seitz and Rick Szeliski

© Mike Nese

CS180: Intro to Comp. Vision and Comp. Photo

Alexei Efros, UC Berkeley, Fall 2024

Feature-space outliner rejection

Can we now compute H from the blue points?

• No! Still too many outliers…
• What can we do?

​

Matching features

What do we do about the “bad” matches?

RAndom SAmple Consensus

Select one match, count inliers

RAndom SAmple Consensus

Select one match, count inliers

Least squares fit

Find “average” translation vector

RANSAC for estimating homography

RANSAC loop:

1. Select four feature pairs (at random)
2. Compute homography H (exact)
3. Compute inliers where dist(p_i’, H p_i ) < ε
4. Keep largest set of inliers
5. Re-compute least-squares H estimate on all of the inliers

RANSAC

Example: Recognising Panoramas

M. Brown and D. Lowe,

University of British Columbia

Why “Recognising Panoramas”?

Why “Recognising Panoramas”?

1D Rotations (θ)

• Ordering ⇒ matching images

Why “Recognising Panoramas”?

1D Rotations (θ)

• Ordering ⇒ matching images

Why “Recognising Panoramas”?

1D Rotations (θ)

• Ordering ⇒ matching images

Why “Recognising Panoramas”?

1D Rotations (θ)

• Ordering ⇒ matching images

Why “Recognising Panoramas”?

1D Rotations (θ)

• Ordering ⇒ matching images

Why “Recognising Panoramas”?

1D Rotations (θ)

• Ordering ⇒ matching images

Why “Recognising Panoramas”?

RANSAC for Homography

RANSAC for Homography

RANSAC for Homography

Probabilistic model for verification

Finding the panoramas

Finding the panoramas

Finding the panoramas

Finding the panoramas

Homography for Rotation

Parameterise each camera by rotation and focal length

​

​

​

​

​

​

This gives pairwise homographies

Bundle Adjustment

New images initialised with rotation, focal length of best matching image

​

Bundle Adjustment

New images initialised with rotation, focal length of best matching image

​

Results

Bad panorama?

Output of Brown & Lowe software

No geometrically consistent solution

The Chair

David Hockney (1985)

Joiners are popular

4,985 photos matching joiners.

4,007 photos matching Hockney.

41 groups about Hockney

Thousands of members

Flickr statistics:

Main goals: ���Automate joiners�� Generalize panoramas to general image collections

Zelnik-Manor & Perona (2007)

Objectives

For Artists:�Reduce manual labor

​

Manual: ~40min.

Fully automatic

Objectives

For Artists:�Reduce manual labor

​

For non-artists:�Generate pleasing-to-the-eye joiners

​

​

Objectives

For Artists:�Reduce manual labor

​

For non-artists:�Generate pleasing-to-the-eye joiners

​

For data exploration:�Organize images spatially

​

What’s going on here?

A cacti garden

Principles

Principles

Convey topology�

​

Correct

Incorrect

Principles

Convey topology�

A 2D layering of images

Blending:

blurry

Graph-cut:

cuts hood

Desired joiner

Principles

Convey topology�

A 2D layering of images�

Don’t distort images�

rotate

scale

translate

Principles

Convey topology�

A 2D layering of images�

Don’t distort images�

Minimize inconsistencies

Good

Bad

Algorithm

Step 1: Feature matching

Brown & Lowe, ICCV’03

Step 2: Align

Large inconsistencies

Brown & Lowe, ICCV’03

Step 3: Order

Reduced inconsistencies

Ordering images

Try all orders: only for small datasets

Ordering images

Try all orders: only for small datasets�

complexity: (m+n)α�m = # images�n = # overlaps�α = # acyclic orders

​

Ordering images

Observations:

• Typically each image overlaps with only a few others
• Many decisions can be taken locally

​

Ordering images

Approximate solution:

• Solve for each image independently
• Iterate over all images

Can we do better?

Step 4: Improve alignment

Iterate Align-Order-Importance

Iterative refinement

Initial

Final

Iterative refinement

Initial

Final

Iterative refinement

Initial

Final

What is this?

That’s me reading

Anza-Borrego

Tractor

Art reproduction

Paolo Uccello, 1436

Art reproduction

Paolo Uccello, 1436

Zelnik & Perona, 2006

Art reproduction

Single view-point

Zelnik & Perona, 2006

Manual by Photographer

Our automatic result

Homage to David Hockney

This Class Project

http://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/f07/proj_final/www/echuangs/

Limitations of Alignment

​

​

​

​

We need to know the global transform (e.g. affine, homography, etc)

​

​

​

Optical flow

Will start by estimating motion of each pixel separately

Then will consider motion of entire image

Why estimate motion?

Lots of uses

• Track object behavior
• Correct for camera jitter (stabilization)
• Align images (even if no global transform)
• 3D shape reconstruction
• Special effects

Problem definition: optical flow

How to estimate pixel motion from image H to image I?

• Solve pixel correspondence problem
• given a pixel in H, look for nearby pixels of the same color in I

Optical flow constraints (grayscale images)

Let’s look at these constraints more closely

• brightness constancy: Q: what’s the equation?

• small motion: (u and v are less than 1 pixel)
• suppose we take the Taylor series expansion of I:

Optical flow equation

Combining these two equations

In the limit as u and v go to zero, this becomes exact

​

Optical flow equation

Q: how many unknowns and equations per pixel?

Intuitively, what does this constraint mean?

​

• The component of the flow in the gradient direction is determined
• The component of the flow parallel to an edge is unknown

Aperture problem

Aperture problem

Solving the aperture problem

How to get more equations for a pixel?

• Basic idea: impose additional constraints
• most common is to assume that the flow field is smooth locally
• one method: pretend the pixel’s neighbors have the same (u,v)
• If we use a 5x5 window, that gives us 25 equations per pixel!

RGB version

How to get more equations for a pixel?

• Basic idea: impose additional constraints
• most common is to assume that the flow field is smooth locally
• one method: pretend the pixel’s neighbors have the same (u,v)
• If we use a 5x5 window, that gives us 25*3 equations per pixel!

Lukas-Kanade flow

Prob: we have more equations than unknowns

Conditions for solvability

• Optimal (u, v) satisfies Lucas-Kanade equation

When is This Solvable?

• A^TA should be invertible
• A^TA should not be too small due to noise
• eigenvalues λ₁ and λ₂ of A^TA should not be too small
• A^TA should be well-conditioned
• λ₁/ λ₂ should not be too large (λ₁ = larger eigenvalue)

A^TA is solvable when there is no aperture problem

​

Local Patch Analysis

Edge

• large gradients, all the same
• large λ₁, small λ₂

Low texture region

• gradients have small magnitude
• small λ₁, small λ₂

High textured region

• gradients are different, large magnitudes
• large λ₁, large λ₂

Observation

This is a two image problem BUT

• Can measure sensitivity by just looking at one of the images!
• This tells us which pixels are easy to track, which are hard
• very useful later on when we do feature tracking...

Errors in Lukas-Kanade

When our assumptions are violated

• Brightness constancy is not satisfied
• The motion is not small
• A point does not move like its neighbors
• window size is too large
• what is the ideal window size?

Iterative Refinement

Iterative Lukas-Kanade Algorithm

• Estimate velocity at each pixel by solving Lucas-Kanade equations
• Warp H towards I using the estimated flow field

- use image warping techniques

• Repeat until convergence

Revisiting the small motion assumption

Is this motion small enough?

• Probably not—it’s much larger than one pixel (2^nd order terms dominate)
• How might we solve this problem?

Reduce the resolution!

Coarse-to-fine optical flow estimation

Coarse-to-fine optical flow estimation

run iterative L-K