Презентация, доклад на тему Image Stitching

Image Stitching

Ali Farhadi
CSE 455





Several slides from Rick Szeliski, Steve Seitz, Derek Hoiem, and Ira Kemelmacher

Combine two or more overlapping images to make one larger image

Add example

Slide credit: Vaibhav Vaish

How to do it?

Basic Procedure
Take a sequence of images from the same position
Rotate the camera about its optical center
Compute transformation between second image and first
Shift the second image to overlap with the first
Blend the two together to create a mosaic
If there are more images, repeat

1. Take a sequence of images from the same position

Rotate the camera about its optical center

2. Compute transformation between images

Extract interest points
Find Matches
Compute transformation

?

3. Shift the images to overlap

4. Blend the two together to create a mosaic

5. Repeat for all images

How to do it?

Basic Procedure
Take a sequence of images from the same position
Rotate the camera about its optical center
Compute transformation between second image and first
Shift the second image to overlap with the first
Blend the two together to create a mosaic
If there are more images, repeat

✓

Compute Transformations

Extract interest points
Find good matches
Compute transformation

✓

Let’s assume we are given a set of good matching interest points

✓

Image reprojection

The mosaic has a natural interpretation in 3D
The images are reprojected onto a common plane
The mosaic is formed on this plane

Example

Camera Center

Image reprojection

Observation
Rather than thinking of this as a 3D reprojection, think of it as a 2D image warp from one image to another

Motion models

What happens when we take two images with a camera and try to align them?
translation?
rotation?
scale?
affine?
Perspective?

Recall: Projective transformations

(aka homographies)

Parametric (global) warping

Examples of parametric warps:

translation

rotation

aspect

affine

perspective

2D coordinate transformations

translation: x’ = x + t x = (x,y)
rotation: x’ = R x + t
similarity: x’ = s R x + t
affine: x’ = A x + t
perspective: x’ ≅ H x x = (x,y,1) (x is a homogeneous coordinate)

Image Warping

Given a coordinate transform x’ = h(x) and a source image f(x), how do we compute a transformed image g(x’) = f(h(x))?

f(x)

g(x’)

x

x’

h(x)

Forward Warping

Send each pixel f(x) to its corresponding location x’ = h(x) in g(x’)

f(x)

g(x’)

x

x’

h(x)

What if pixel lands “between” two pixels?

Forward Warping

Send each pixel f(x) to its corresponding location x’ = h(x) in g(x’)

f(x)

g(x’)

x

x’

h(x)

What if pixel lands “between” two pixels?

Answer: add “contribution” to several pixels, normalize later (splatting)

Richard Szeliski

Image Stitching

Inverse Warping

Get each pixel g(x’) from its corresponding location x’ = h(x) in f(x)

f(x)

g(x’)

x

x’

h-1(x)

What if pixel comes from “between” two pixels?

Richard Szeliski

Image Stitching

Inverse Warping

Get each pixel g(x’) from its corresponding location x’ = h(x) in f(x)

What if pixel comes from “between” two pixels?

Answer: resample color value from interpolated source image

f(x)

g(x’)

x

x’

h-1(x)

Interpolation

Possible interpolation filters:
nearest neighbor
bilinear
bicubic (interpolating)

Motion models

Finding the transformation

Translation = 2 degrees of freedom
Similarity = 4 degrees of freedom
Affine = 6 degrees of freedom
Homography = 8 degrees of freedom

How many corresponding points do we need to solve?

Plane perspective mosaics

8-parameter generalization of affine motion
works for pure rotation or planar surfaces
Limitations:
local minima
slow convergence
difficult to control interactively

Simple case: translations

Simple case: translations

Simple case: translations

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

Simple case: translations

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

Least squares formulation

For each point



we define the residuals as

Least squares formulation

Goal: minimize sum of squared residuals




“Least squares” solution

For translations, is equal to mean displacement

Least squares

Find t that minimizes


To solve, form the normal equations

Solving for translations

Using least squares

Affine transformations

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

Affine transformations

Residuals:



Cost function:

Affine transformations

Matrix form

Solving for homographies

Solving for homographies

Direct Linear Transforms

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

Richard Szeliski

Image Stitching

Matching features

What do we do about the “bad” matches?

Richard Szeliski

Image Stitching

RAndom SAmple Consensus

Select one match, count inliers

Richard Szeliski

Image Stitching

RAndom SAmple Consensus

Select one match, count inliers

Richard Szeliski

Image Stitching

Least squares fit

Find “average” translation vector

RANSAC for estimating homography

RANSAC loop:
Select four feature pairs (at random)
Compute homography H (exact)
Compute inliers where ||pi’, H pi|| < ε
Keep largest set of inliers
Re-compute least-squares H estimate using all of the inliers

CSE 576, Spring 2008

Structure from Motion

Simple example: fit a line

Rather than homography H (8 numbers) fit y=ax+b (2 numbers a, b) to 2D pairs

Simple example: fit a line

Pick 2 points
Fit line
Count inliers

3 inliers

Simple example: fit a line

Pick 2 points
Fit line
Count inliers

4 inliers

Simple example: fit a line

Pick 2 points
Fit line
Count inliers

9 inliers

Simple example: fit a line

Pick 2 points
Fit line
Count inliers

8 inliers

Simple example: fit a line

Use biggest set of inliers
Do least-square fit

RANSAC

Red:
rejected by 2nd nearest neighbor criterion
Blue:
Ransac outliers
Yellow:
inliers

How many rounds?

If we have to choose s samples each time
with an outlier ratio e
and we want the right answer with probability p

Richard Szeliski

Image Stitching

Rotational mosaics

Directly optimize rotation and focal length
Advantages:
ability to build full-view panoramas
easier to control interactively
more stable and accurate estimates

Richard Szeliski

Image Stitching

Rotational mosaic

Projection equations
Project from image to 3D ray
(x0,y0,z0) = (u0-uc,v0-vc,f)
Rotate the ray by camera motion
(x1,y1,z1) = R01 (x0,y0,z0)
Project back into new (source) image
(u1,v1) = (fx1/z1+uc,fy1/z1+vc)

Computing homography

Assume we have four matched points: How do we compute homography H?

Normalized DLT
Normalize coordinates for each image
Translate for zero mean
Scale so that average distance to origin is ~sqrt(2)

This makes problem better behaved numerically

Compute using DLT in normalized coordinates
Unnormalize:

Computing homography

Assume we have matched points with outliers: How do we compute homography H?

Automatic Homography Estimation with RANSAC
Choose number of samples N
Choose 4 random potential matches
Compute H using normalized DLT
Project points from x to x’ for each potentially matching pair:
Count points with projected distance < t
E.g., t = 3 pixels
Repeat steps 2-5 N times
Choose H with most inliers

HZ Tutorial ‘99

Automatic Image Stitching

Compute interest points on each image

Find candidate matches

Estimate homography H using matched points and RANSAC with normalized DLT

Project each image onto the same surface and blend

RANSAC for Homography

Initial Matched Points

RANSAC for Homography

Final Matched Points

RANSAC for Homography