Image Processing

Image Warping, Compositing & Morphing

Tom Funkhouser Princeton University COS 426, Spring 2006

Quantization
Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither

Filtering
Blur Detect edges

Warping
Scale Rotate Warp

Pixel operations
Add random noise Add luminance Add contrast Add saturation

Combining
Composite Morph

Image Processing
Quantization
Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither

Image Warping
Filtering
Blur Detect edges

Move pixels of image

Mapping Resampling

Warping
Scale Rotate Warp

Pixel operations
Add random noise Add luminance Add contrast Add saturation

Combining
Composite Morph

Warp

Source image

Destination image

Image Warping
Mapping
Forward Reverse

Mapping
Define transformation
Describe the destination (x,y) for every location (u,v) in the source (or vice-versa, if invertible)

Resampling
Point sampling Triangle filter Gaussian filter

Example Mappings
Scale by factor:
x = factor * u y = factor * v

Example Mappings
Rotate by degrees:
x = ucos - vsin y = usin + vcos y

y v v

Scale 0.8
x u u

Rotate 30
x

Example Mappings
Shear in X by factor:
x = u + factor * v y=v v Shear X 1.3 y

Other Mappings
Any function of u and v:
x = fx(u,v) y = fy(u,v)

Shear in Y by factor:
x=u y = v + factor * u v Shear Y 1.3 y

Swirl
x

Fish-eye

Rain

Image Warping Implementation I

Forward mapping
Iterate over source image

Image Warping Implementation I

Forward mapping:
for (int iu = for (int iv float x = float y = ??? } } 0; iu < umax; iu++) { = 0; iv < vmax; iv++) { fx(iu,iv); fy(iu,iv);

f
y v

Rotate -30
u x

(u,v)

f (x,y)

Source image

Destination image

Image Warping Implementation I

Forward mapping:
for (int iu = 0; iu < umax; iu++) { for (int iv = 0; iv < vmax; iv++) { float x = fx(iu,iv); float y = fy(iu,iv); for (int ix = 0; ix <= xmax; ix++) { for (int iy = 0; iy <= ymax; iy++) { dst(ix,iy) += ??? } } (u,v) (x,y) } } f

Image Warping Implementation I

Forward mapping:
for (int iu = 0; iu < umax; iu++) { for (int iv = 0; iv < vmax; iv++) { float x = fx(iu,iv); float y = fy(iu,iv); for (int ix = xlo; ix <= xhi; ix++) { for (int iy = ylo; iy <= yhi; iy++) { dst(ix,iy) += k(x,y,ix,iy) * src(iu,iv); } } (u,v) (x,y) } }

(x,y)
Source image Destination image Source image Destination image

Image Warping Implementation I

Forward mapping:
for (int iu = 0; iu < umax; iu++) { for (int iv = 0; iv < vmax; iv++) { float x = fx(iu,iv); float y = fy(iu,iv); for (int ix = xlo; ix <= xhi; ix++) { for (int iy = ylo; iy <= yhi; iy++) { dst(ix,iy) += k(x,y,ix,iy) * src(iu,iv); } } (u,v) (x,y) } }

Image Warping Implementation I

Forward mapping:
for (int iu = 0; iu < umax; iu++) { for (int iv = 0; iv < vmax; iv++) { float x = fx(iu,iv); float y = fy(iu,iv); for (int ix = xlo; ix <= xhi; ix++) { for (int iy = ylo; iy <= yhi; iy++) { dst(ix,iy) += k(x,y,ix,iy) * src(iu,iv); ksum(ix,iy) += k(x,y,ix,iy); } (x,y) } } } for (ix = 0; ix < xmax; ix++) for (iy = 0; iy < ymax; iy++) dst(ix,iy) /= ksum(ix,iy)

Source image

Destination image

Destination image

Image Warping Implementation II

Reverse mapping
Iterate over destination image

Image Warping Implementation II

Reverse mapping
Iterate over destination image
Value at every dst pixel is weighted sum of src values

Rotate -30
u x u

Rotate -30
x

Image Warping Implementation II

Reverse mapping:
for (int ix = for (int iy float u = float v = ??? } } 0; ix < xmax; ix++) { = 0; iy < ymax; iy++) { fx-1(ix,iy); fy-1(ix,iy);

Image Warping Implementation II

Reverse mapping:
for (int ix = 0; ix < xmax; ix++) { for (int iy = 0; iy < ymax; iy++) { float u = fx-1(ix,iy); float v = fy-1(ix,iy); dst(ix,iy) = 0; for (int iu = ulo; iu < uhi; iu++) { for (int iv = vhi; iv < vhi; iv++) { dst(ix,iy) += ??? } } } (u,v) (x,y) f }

(u,v)

(x,y)

Source image

Destination image

Source image

Destination image

Image Warping Implementation II

Reverse mapping:
for (int ix = 0; ix < xmax; ix++) { for (int iy = 0; iy < ymax; iy++) { float u = fx-1(ix,iy); float v = fy-1(ix,iy); dst(ix,iy) = 0; for (int iu = ulo; iu < uhi; iu++) { for (int iv = vhi; iv < vhi; iv++) { dst(ix,iy) += k(u,v,iu,iv) * src(u,v); } } } (u,v) (x,y) f }

Image Warping Implementation II

Reverse mapping:
for (int ix = 0; ix < xmax; ix++) { for (int iy = 0; iy < ymax; iy++) { float u = fx-1(ix,iy); float v = fy-1(ix,iy); dst(ix,iy) = 0; float ksum = 0; for (int iu = ulo; iu < uhi; iu++) { for (int iv = vhi; iv < vhi; iv++) { dst(ix,iy) += k(u,v,iu,iv) * src(u,v); ksum += k(u,v,iu,iv); } (u,v) (x,y) f } dst(ix,iy) /= ksum; } } Source image Destination image

Source image

Destination image

Image Warping Implementation II

Reverse mapping:
for (int ix = 0; ix < xmax; ix++) { for (int iy = 0; iy < ymax; iy++) { float u = fx-1(ix,iy); float v = fy-1(ix,iy); dst(ix,iy) = 0; float ksum = 0; for (int iu = ulo; iu < uhi; iu++) { for (int iv = vhi; iv < vhi; iv++) { dst(ix,iy) += k(u,v,iu,iv) * src(u,v); ksum += k(u,v,iu,iv); } (u,v) (x,y) f } dst(ix,iy) /= ksum; } } Source image Destination image

Image Warping Implementation II

Reverse mapping:
float Resample(src, u, v, w) { float dst = 0; float ksum = 0; int ulo = u - w; etc. for (int iu = ulo; iu < uhi; iu++) { for (int iv = vhi; iv < vhi; iv++) { dst += k(u,v,iu,iv) * src(u,v) ksum += k(u,v,iu,iv); } } (u,v) (x,y) f return dst / ksum; } Source image Destination image

Image Warping Implementation II

Reverse mapping:
Warp(src, dst) { for (int ix = 0; ix < xmax; ix++) { for (int iy = 0; iy < ymax; iy++) { float u = fx-1(ix,iy); float v = fy-1(ix,iy); dst(ix,iy) = Resample(src,u,v,w); } } } (u,v) (x,y)

Image Warping
Mapping
Forward Reverse

Resampling
Point sampling Triangle filter Gaussian filter

Source image

Destination image

Point Sampling
Take value at closest pixel:
float Resample(src, u, v, w) { int iu = round(u); int iv = round(v); This method is simple, return src(iu,iv); but it causes aliasing }

Filtering
Compute weighted sum of pixel neighborhood
Weights are normalized values of kernel function Equivalent to convolution at samples

(u,v)

f (x,y)

(u,v)

Source image

Destination image
k(i,j) represented by gray value

Filtering
Compute weighted sum of pixel neighborhood
Weights are normalized values of kernel function Equivalent to convolution at samples s = 0; for (i = -w; i <= w; i++) for (j = -w; j <= w; j++) s += k(i,j)*I(u+i, v+j);

Triangle Filtering
Kernel is triangle function

(u,v) (u,v)
w r

-w

Tent Function

k(i,j) represented by gray value

Filter Width = 2

Triangle Filtering
Kernel is triangle function

Triangle Filtering (with width = 1)

Bilinearly interpolate four closest pixels
a = linear interpolation of src(u1,v2) and src(u2,v2) b = linear interpolation of src(u1,v1) and src(u2,v1) dst(x,y) = linear interpolation of a and b w -w Tent Function

(u,v) w

(u1,v2)

(u2,v2)

(u,v)
Width of filter affects blurriness

(u1,v1)
Filter Width = 1

Filter Width = 1

(u2,v1)

Gaussian Filtering
Kernel is Gaussian function

Filter Size
How choose w?
Warp(src, dst) { for (int ix = 0; ix < xmax; ix++) { for (int iy = 0; iy < ymax; iy++) { float u = fx-1(ix,iy); float v = fy-1(ix,iy); dst(ix,iy) = Resample(src,u,v,w); } } (u,v) (x,y) }

(u,v)
r

w3

w -w Gaussian Function

Filter Width = 2

Source image

Destination image

Filter Size
Scale (src, dst, sx, sy):
float w max(1.0/sx,1.0/sy); for (int x = 0; x < xmax; x++) { for (int y = 0; y < ymax; y++) { float u = x / sx; float v = y / sy; dst(x,y) = Resample(src,u,v,w); } v (u,v) } y (x,y)

Filtering Methods Comparison

Trade-offs
Aliasing versus blurring Computation speed

Scale 0.5
u x

Point

Bilinear

Gaussian

Example: Rotate
Rotate (src, dst, theta):
for (int x = 0; x < xmax; x++) { for (int y = 0; y < ymax; y++) { float u = x*cos(-) - y*sin(-); float u = x*sin(-) + y*cos(-); dst(x,y) = Resample(src,u,v,w); } y } (x,y) (u,v) v

Example: Fun
Swirl (src, dst, theta):
for (int x = 0; x < xmax; x++) { for (int y = 0; y < ymax; y++) { float u = rot(dist(x,xcenter)*theta); float v = rot(dist(y,ycenter)*theta); dst(x,y) = Resample(src,u,v,w); } } v (u,v) y

f
x = ucos - vsin y = usin + vcos u

(x,y)

Rotate 45
x u

Swirl 45
x

COS426 Examples

Image Processing
Quantization
Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither

Filtering
Blur Detect edges

Warping
Scale Rotate Warp

Randy Carnevale

Jonathan Heinberg

Pixel operations
Add random noise Add luminance Add contrast Add saturation

Combining
Composite Morph

Sid Kapur

Philip Wei

Image Compositing
Combine images
Separate image into elements Generate independently Composite together

Blue-Screen Matting
Composite foreground and background images
Create background image Create foreground image with blue background Insert non-blue foreground pixels into background Problem: no partial coverage!

Applications
Cel animation Chroma-keying Blue-screen matting

Alpha Channel
Encodes pixel coverage information
= 0: no coverage (or transparent) = 1: full coverage (or opaque) 0 < < 1: partial coverage (or semi-transparent)

Compositing with Alpha

Controls the linear interpolation of foreground and background pixels when elements are composited.

Example: = 0.3 or
Partial Coverage SemiTransparent

=0 =1 0<<1 0<<1

Semi-Transparent Objects
Suppose we put A over B over background G
A B G

Opaque Objects
How do we combine 2 partially covered pixels?
3 possible colors (0, A, B) 4 regions (0, A, B, AB)

AB
How much of B is blocked by A?

A A 0 B
??? ???

A
How much of B shows through A

(1-A )
How much of G shows through both A and B?

(1-A )(1-B )

Composition Algebra
12 reasonable combinations

Example: C = A Over B
Consider the areas covered:
C = A A + (1-A) B B = A + (1-A) B

clear

A over B

B over A

A in B

A
B in A A out B B out A A atop B B atop A A xor b A over B Porter & Duff `84

(1-A) B
Assumption: coverages of A and B are uncorrelated for each pixel

Image Composition Example

Image Composition Example

[Porter&Duff Computer Graphics 18:3 1984]

[Porter&Duff Computer Graphics 18:3 1984]

Image Composition Example

Image Composition Example

[Porter&Duff Computer Graphics 18:3 1984]

Jurassic Park

COS426 Examples

Even CG folks Can Win an Oscar

Darin Sleiter

Smith
Kenrick Kin

Duff

Catmull

Porter

Image Processing
Quantization
Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither

Image Morphing
Filtering
Blur Detect edges

Animate transition between two images

Warping
Scale Rotate Warp

Pixel operations
Add random noise Add luminance Add contrast Add saturation

Combining
Composite Morph
H&B Figure 16.9

Cross-Dissolving
Blend images with over operator
alpha of bottom image is 1.0 alpha of top image varies from 0.0 to 1.0

Image Morphing
Combines warping and cross-dissolving
src
warp warp

blend(i,j) = (1-t) src(i,j) + t dst(i,j) (0 t 1)

src blend dst

cross-dissolve

warp

warp

dst
t = 0.0 t = 0.5 t = 1.0

t = 0.0

t = 0.5

t = 1.0

Image Morphing
The warping step is the hard one
Aim to align features in images

Feature-Based Warping
Beier & Neeley use pairs of lines to specify warp
Given p in dst image, where is p in source image?

Mapping
u v v

p How specify mapping for the warp?

H&B Figure 16.9

u Destination image
Beier & Neeley SIGGRAPH 92

Source image

u is a fraction v is a length (in pixels)

10

Warping with One Line Pair

What happens to the F?

Warping with One Line Pair

What happens to the F?

Translation!

Scale!

Warping with One Line Pair

What happens to the F?

Warping with One Line Pair

What happens to the F?

In general, similarity transformations Rotation!

What types of transformations cant be specified?

Warping with Multiple Line Pairs

Use weighted combination of points defined by each pair of corresponding lines

Warping with Multiple Line Pairs

Use weighted combination of points defined by each pair of corresponding lines Mapping p p

Source image
Beier & Neeley, Figure 4

Destination image

p is a weighted average

11

Weighting Effect of Each Line Pair

To weight the contribution of each line pair, Beier & Neeley use:

Warping Pseudocode
WarpImage(Image, L[], L[]) begin foreach destination pixel p do psum = (0,0) wsum = 0 foreach line L[i] in destination do p[i] = p transformed by (L[i],L[i]) psum = psum + p[i] * weight[i] wsum += weight[i] end p = psum / wsum Result(p) = Image(p) end end

weight[i ] =

length[i ] p a + dist[i ]

Where: length[i] is the length of L[i] dist[i] is the distance from X to L[i] a, b, p are constants that control the warp

Morphing Pseudocode
GenerateAnimation(Image0, L0[], Image1, L1[]) begin foreach intermediate frame time t do for i = 1 to number of line pairs do L[i] = line t-th of the way from L0 [i] to L1 [i] end Warp0 = WarpImage(Image0, L0, L) Warp1 = WarpImage(Image1, L1, L) foreach pixel p in FinalImage do Result(p) = (1-t) Warp0 + t Warp1 end end

Beier & Neeley Example

Image0 Warp0

Result

Image1

Warp1

Beier & Neeley Example

Image0 Warp0

COS426 Examples

Result

CS426 Class, Fall98

Jon Beyer

Image1

Warp1

12

Summary
Image warping
Mapping Resampling

Image Processing
Quantization
Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither

Filtering
Blur Detect edges

Image compositing
Alpha channel Porter-Duff compositing algebra

Warping
Scale Rotate Warp

Pixel operations
Add random noise Add luminance Add contrast Add saturation

Image morphing
Specifying correspondences Warping Compositing

Combining
Composite Morph

Next Time: 3D Rendering

Misha Kazhdan

13