Image Warping and Morphing: Olivier Gondry's Visit

Download as pdf or txt
Download as pdf or txt
You are on page 1of 18

Olivier Gondry's visit

6.098 Digital and Computational Photography 6.882 Advanced Computational Photography

Thursday Friday Contact Peter Sand: [email protected]

Image Warping and Morphing


Frdo Durand Bill Freeman MIT - EECS

Important scientific question


How to turn Dr. Jekyll into Mr. Hyde? How to turn a man into a werewolf? Powerpoint cross-fading?

Important scientific question


How to turn Dr. Jekyll into Mr. Hyde? How to turn a man into a werewolf? Powerpoint cross-fading?

or Image Warping and Morphing?

From An American Werewolf in London

Digression: old metamorphoses


http://en.wikipedia.org/wiki/The_Strange_Case_of_Dr._Jekyll_and_Mr._Hyde http://www.eatmybrains.com/showtopten.php?id=15 http://www.horror-wood.com/next_gen_jekyll.htm Unless Im mistaken, both employ the trick of making already-applied makeup turn visible via changes in the color of the lighting, something that works only in black-and-white cinematography. Its an interesting alternative to the more familiar Wolf Man time-lapse dissolves. This technique was used to great effect on Fredric March in Rouben Mamoulians 1932 film of Dr. Jekyll and Mr. Hyde, although Spencer Tracy eschewed extreme makeup for his 1941 portrayal.

Averaging images
Cross-fading Pretty much the compositing equation C= F +(1-) B

Averaging vectors
V= P + (1-) Q
P V Q

Warping & Morphing combine both


For each pixel Transform its location like a vector Then linearly interpolate like an image

Morphing
Input: two images I0 and IN Expected output: image sequence Ii, with i 1..N-1

Morphing
For each intermediate frame It Interpolate feature locations Pti= (1- t) P0i + t P1i Perform two warps: one for I0, one for I1
Deduce a dense warp field from the pairs of features Warp the pixels

Linearly interpolate the two warped images User specifies sparse correspondences on the images Pairs of vectors {(P0j, PNj)}

Intelligent design & image warping

Warping

D'Arcy Thompson
http://www-groups.dcs.st-and.ac.uk/~history/Miscellaneous/darcy.html http://en.wikipedia.org/wiki/D'Arcy_Thompson

Importance of shape and structure in evolution

Warping
Imagine your image is made of rubber warp the rubber

Careful: warp vs. inverse warp


How do you perform a given warp: Forward warp Potential gap problems

Inverse lookup the most useful For each output pixel


Lookup color at inversewarped location in input No prairie dogs were harmed when creating this image

Image Warping non-parametric


Move control points to specify a spline warp Spline produces a smooth vector field

Warp specification - dense


How can we specify the warp? Specify corresponding spline control points
interpolate to a complete warping function

But we want to specify only a few points, not a grid


Slide Alyosha Efros Slide Alyosha Efros

Warp specification - sparse


How can we specify the warp? Specify corresponding points
interpolate to a complete warping function How do we do it?

Triangular Mesh

How do we go from feature points to pixels?


Slide Alyosha Efros

1. Input correspondences at key feature points 2. Define a triangular mesh over the points Same mesh in both images! Now we have triangle-to-triangle correspondences 3. Warp each triangle separately from source to destination
Slide Alyosha Efros

Problems with triangulation morphing


Not very continuous only C0
Fig. L. Darsa

Warp as interpolation
We are looking for a warping field A function that given a 2D point, returns a warped 2D point We have a sparse number of correspondences These specify values of the warping field This is an interpolation problem Given sparse data, find smooth function

Folding problems

Interpolation in 1D
We are looking for a function f We have N data points: xi, yi Scattered: spacing between xi is non-uniform We want f so that For each i, f(xi)=yi f is smooth Depending on notion of smoothness, different f

Radial Basis Functions (RBF)


Place a smooth kernel R centered on each data point xi f (z) = i R(z, xi)

Radial Basis Functions (RBF)


Place a smooth kernel R centered on each data point xi f (z) = i R(z, xi) Find weights i to make sure we interpolate the data for each i, f(xi)=yi

Kernel
Many choices In Assignment 4, we simply use inverse multiquadric

where c controls falloff Lazy way: set c to an arbitrary constant (pset 4) Smarter way: c is different for each kernel. For each xi, set c as the squared distance to the closest other xj

Enforcing interpolation
f (z) = i R(z, xi) N equations for each j, f(xj) = yj i R(xj, xi) = yj N unknowns i Just inverse the matrix

Important note
f (z) = i R(z, xi) for each j, i R(xj, xi)=yj Note that the influence of each function is non-zero everywhere at a data point, the value of the other bases is not zero In contrast to e.g. various interpolation splines

Variations of RBF
Lots of possible kernels 2 Gaussians e-r /2 Thin-plate splines r2 log r Sometimes add a global polynomial term

Recap: 1D scattered data interpolation


Sparse input/output pairs xi, yi non-uniformly sampled RBFs (Radial Basis Functions) Weighted sum of kernels R centered on data points xi f (z) = i R(z, xi) Compute the weights i by enforcing interpolation f(xj)=yj Simple linear system

Recap: 1D scattered data interpolation


Sparse input/output pairs xi, yi non-uniformly sampled RBFs (Radial Basis Functions) Weighted sum of kernels R centered on data points xi f (z) = i R(z, xi) Compute the weights i by enforcing interpolation f(xj)=yj Simple linear system

RBF for warping: 2D case


Instead of f:R R, we now deal with f:R2 R2 For each 2D point, f gives us another 2D warped point We have N data points Pairs of input 2D vector, output 2D vector Careful: xi is now a 2D vector, so is yi Don't be confused with coordinates (x,y) Place 2D kernels at each data point The weights i are now 2D vectors Solve a linear system of 2N equations and 2N unknowns

QUESTION?

Applying a warp: USE INVERSE


Forward warp: For each pixel in input image
Paste color to warped location in output

Example

Problem: gaps Inverse warp For each pixel in output image


Lookup color from inverse-warped location

Example
Fold problems Oh well

1D equivalent of folds
There is no guarantee that our 1D RBF is monotonic Yes, it means that the notion of inverse of the warp is questionable.
input

result (remember, inverse warp)

Hardcore Photoshop for portrait

Morphing

Input images

Feature correspondences

The feature locations will be our yi

Interpolate feature location


Provides the xi

Warp each image to intermediate location


Two different warps: Same target location, different source location i.e. the xi are the same (intermediate locations), the yi are different (source feature locations) Note: the yi do not change along the animation, but the xi are different for each intermediate image Here we show t=0.5 (the yi are in the middle)

Warp each image to intermediate location

Interpolate colors linearly

Interpolation weight are a function of time:

C= (1-t)f0t(I0)+t f1t(I1)

Recap
For each intermediate frame It Interpolate feature locations yti= (1- t) x0i + t x1i Perform two warps: one for I0, one for I1
Deduce a dense warp field from the pairs of features Warp the pixels

Movie time

Linearly interpolate the two warped images

The sampling problem

Resampling

Parts are magnified Parts are minified Sometimes anisotropic Same problem for 3D texture mapping

Intuition
Plain lookup is bad
(But good news: that's all we ask for pset 4)

Similar case: texture aliasing


Aliasing is the under-sampling of a signal, and it's especially noticeable during animation

In magnified regions, not smooth enough In minified regions, it creates aliasing What we want In magnified regions, smooth interpolation In minified regions, take the average We need good signal processing framework to do this

point sampling

mipmaps & linear interpolation

The Bible
http://www-2.cs.cmu.edu/~ph/texfund/texfund.pdf

Resampling
2D texture space

warp due to perspective

2D screen space

Notations
Input signal f(u) Forward mapping (texture-to-screen) x=m(u) Output signal g(x)
Warning: I sloppily changed my notations: f is signal, warp is m

Resampling
What do we need to do?

m f(u) g(x) g(x)

m f(u)

Resampling
1. Reconstruct the continuous signal from the discrete input signal 2. Warp the domain of the continuous signal 3. Prefilter the warped continuous signal 4. Sample this signal
m f(u) g(x)

Resampling

Resampling: progression
Discrete input texture f(u) for integer u m Reconstructed input texture g(x) fc(u) = f(u) r(u) = f(k) r(u-k) Warped texture gc(x)=fc(m-1(x)) Band-limited output gc(x) = gc(x) h(x) = gc(t) h(x-t) dt Discrete output g(x) = g(x) i(x)
f(u)

Resampling
source space resampling with prefiltering [Heckbert 89] destination space

discrete input reconstruct warp prefilter

discrete output sample

reconstructed input

warped input

continuous output

Put it together
Discrete input texture f(u) for integer u Reconstructed input texture fc(u) = f(u) r(u) = f(k) r(u-k) Warped texture gc(x)=fc(m-1(x)) Band-limited output gc(x)=gc(x) h(x) = gc(t) h(x-t) dt Discrete output g(x) = g(x) i(x)

Put it together
Discrete input texture f(u) for integer u Reconstructed input texture fc(u) = f(u) r(u) = f(k) r(u-k) Warped texture gc(x)=fc(m-1(x)) Band-limited output gc(x)=gc(x) h(x) = gc(t) h(x-t) dt Discrete output g(x) = g(x) i(x)

g(x)

= gc(x) = gc(t) h(x-t) dt = fc(m-1(t)) h(x-t) dt = h(x-t) f(k) r(m-1(t)-k) dt = f(k) (x, k)

g(x)

= gc(x) = gc(t) h(x-t) dt = fc(m-1(t)) h(x-t) dt = h(x-t) f(k) r(m-1(t)-k) dt = f(k) (x, k)

Where (x,k) = h(x t) r (m-1(t) k) dt

Where (x,k) = h(x t) r (m-1(t) k) dt

10

Resampling convolution view


Ignoring normalization

Resampling

g ( x) = f ( xi )ri (m 1 ( x)) h( x)
i

color

reconstructed input reconstruction kernels position irregular spacing

resampling filter

The image space resampling filter combines a warped reconstruction filter and a low-pass filter

Resampling
Source Space Destination Space

Resampling
Source Space Destination Space
sum of resampling filters

4. Sample

Destination Space

Destination Space

Destination Space
warped reconstruction kernel

Destination Space
resampling filters

3. Filter

low-pass filter

convolution

3. Filter

Resampling convolution view


Ignoring normalization

Resampling
Use local affine approximation of warp Elliptical Gaussian kernels [Heckbert 89] Closed under affine mappings and convolution

g ( x) = f ( xi )ri (m 1 ( x)) h( x)
i

~ 1 ( x)) h( x) g ( x) = ci ri (m i
i

resampling filter

The image space resampling filter combines a warped reconstruction filter and a low-pass filter

= ci Gi ( x)
i

This is great, but how do we warp reconstruction filters?

Gaussian resampling kernel (EWA resampling kernel)

4. Sample

2. Warp

2. Warp

11

Resampling filter
Depends on local warp For perspective, approximated by local affine at center of kernel Not bad approximation because filter small at periphery

Resampling Filter
warped reconstruction kernel low-pass filter resampling filter minification

magnification

EWA resampling

Image Quality Comparison


Trilinear mipmapping

EWA

trilinear mipmapping

Morphing & matting

Bells and whistles

Extract foreground first to avoid artifacts in the background

12

Uniform morphing

Non-uniform morphing

http://www-cs.ccny.cuny.edu/~wolberg/pub/cgi96.pdf

Video
Lots of manual work

View morphing

Problem with morphing


So far, we have performed linear interpolation of feature point positions But what happens if we try to morph between two views of the same object?

View morphing
Seitz & Dyer
http://www.cs.washington.edu/homes/seitz/vmorph/vmorph.htm

Interpolation consistent with 3D view interpolation

13

Main trick
Prewarp with a homography to "prealign" images So that the two views are parallel Because linear interpolation works when views are parallel
morph morph

prewarp

prewarp

input homographies

output

input

Extensions

14

Shape Vector

The Morphable face model


Again, assuming that we have m such vector pairs in full correspondence, we can form new shapes Smodel and new appearances Tmodel as:
m
m

S model = ai S i
i =1

Tmodel = bi Ti
i =1

If number of basis faces m is large enough to span the face subspace then:

Provides alignment!

43

Slide Alyosha Efros

Any new face can be represented as a pair of vectors

The Morphable Face Model


The actual structure of a face is captured in the shape vector S = (x1, y1, x2, , yn)T, containing the (x, y) coordinates of the n vertices of a face, and the appearance (texture) vector T = (R1, G1, B1, R2, , Gn, Bn)T, containing the color values of the mean-warped face image.
Shape S

Subpopulation means
Examples: Happy faces Young faces Asian faces Etc. Sunny days Rainy days Etc. Etc.

Average female

Appearance T
Average male

Deviations from the mean

Using 3D Geometry: Blanz & Vetter, 1999

X X = X - X

+ = + 1.7

show SIGGRAPH video

15

Morphable face models

Manipulating Facial Appearance through Shape and Color


Duncan A. Rowland and David I. Perrett St Andrews University IEEE CG&A, September 1995

http://citeseer.ist.psu.edu/cache/papers/cs/704/http:zS zzSzwww.ai.mit.eduzSzprojectszSzcbclzSzpublication szSzpszSzICCV98matching2.pdf/jones98multidimensional.pdf http://www.kyb.mpg.de/publication.html?user=volke r

EigenFaces
First popular use of PCA on images was for modeling and recognition of faces [Kirby and Sirovich, 1990, Turk and Pentland, 1991] Collect a face ensemble Normalize for contrast, scale, & orientation. Remove backgrounds Apply PCA & choose the first N eigen-images that account for most of the variance of the mean data.
face lighting variation

The average face


http://www.uniregensburg.de/Fakultaeten/phil_Fak_II/Psychologie/ Psy_II/beautycheck/english/index.htm

Figure-centric averages

Jason Salavon

Antonio Torralba & Aude Oliva (2002) Averages: Hundreds of images containing a person are averaged to reveal regularities in the intensity patterns across all the images.

Slide Alyosha Efros

More at: http://www.salavon.com/

16

100 Special Moments by Jason Salavon

3D morphing
Feature-Based Volume Metamorphosis Lerios, Garfinkle, and Levoy.
http://www-graphics.stanford.edu/~tolis/toli/research/morph.html

Why blurry?

Slide Alyosha Efros

3D morphing
Feature-Based Volume Metamorphosis Lerios, Garfinkle, and Levoy.
http://www-graphics.stanford.edu/~tolis/toli/research/morph.html

Automatic morphing
http://ccc.inaoep.mx/~fuentes/zanella.pdf

Recap

Recap & Significance

Idea that linear interpolation introduces blur Separation of shape and color Idea of non-rigid alignment of different images Applications to medical data Applications, related to Special effects Face recognition Video frame interpolation MPEG Scattered data interpolation

17

Refs

References

http://portal.acm.org/citation.cfm?id=134003&coll= GUIDE&dl=GUIDE&CFID=72901489&CFTOKEN =24335444 http://www.visgraf.impa.br/cgibin/morphQuery.cgi?output=html http://www.cg.tuwien.ac.at/research/ca/mrm/ http://w3.impa.br/~morph/sites.html http://w3.impa.br/~morph/sig-course/slides.html http://www.owlnet.rice.edu/~elec539/Projects97/mor phjrks/morph.html http://www.fmrib.ox.ac.uk/~yongyue/thinplate.html http://www.uoguelph.ca/~mwirth/PHD_Chapter4.pd f

Software
http://www.morpheussoftware.net/ http://www.debugmode.com/winmorph/ http://www.stoik.com/products/morphman/mm1_main.htm http://www.creativecow.net/articles/zwar_chris/morph/index.h tml http://meesoft.logicnet.dk/SmartMorph/ http://www.asahi-net.or.jp/~FX6M-FJMY/mop00e.html http://morphing-software-review.toptenreviews.com/ http://www.freedownloadscenter.com/Search/morphing.html

Next time: Panoramas

18

You might also like