Week 7 –

Pyramid
Image
Processing
 Agenda for this class

1-d pyramid matrices

Multi-resolution image pyramids
Gaussian
Application: object detection

Laplacian
Application: image blending

Steerable pyramids Gaussian Laplacian Steerable

Application: texture synthesis

Detecting a pattern in an image

Pattern to detect
 Input patch

Template No match
matching

“Training”
example

Input patch

Template Match
matching

“Training”
example

Input patch

Template Match
matching
Motivation for translation invariance!

“Training”
example
 “Training”
example

Match

No match

No match

No match

…
We need translation and scale inv
Method 1 for handling
scale: adjust detector “Training”
example

scale Match

No match

No match

…
Adjust scale

Match

Consider all patch location and sizes

 Method 2 for handling
scale:
scale image using multi- Multiscale image pyramid

scale pyramids

Template

A fast & efficient way to provide scale & translation invariance!

Subsampling and aliasing

1/2 1/2
Gaussian Pyramid

1/2

1/2

1/2

1/2
 Image Pyramids

Image Pyramid = Hierarchical representation of an image

Low No details in image -

Resolution (blurred image)
low frequencies

High Details in image -

Resolution low+high frequencies

A collection of images at different resolutions.

Image Pyramid
Low resolution

High resolution
Image Pyramid
Frequency Domain
Low resolution

High resolution
 Image Pyramid
Low resolution

High resolution
 Laplacian Pyramid
Motivation = Compression, redundancy removal, compression rates are higher for
predictable values.

G0, G1, .... = the levels of a Gaussian Pyramid.

Predict level Gl from level Gl+1 by Expanding Gl+1 to G’l

Gl+1
Expand
Reduce
Gl G’l

Denote by Ll the error in prediction:

Ll = Gl - G’l

L0, L1, .... = the levels of a Laplacian Pyramid.

 Laplacian Pyramid

Gaussian Laplacian
Pyramid Pyramid

- =
- =

- =
Gaussian Frequency
Laplacian
Pyramid Domain Pyramid
Laplace Pyramid -
No scaling

50

100
50
150
100
200
150
50
250
50 100 150 200 250
200
100

250
150
50 100 150 200 250

200

250
50 100 150 200 250
50

100

50
150

100
200

150
250
50 100 150 200 250
200

250
50 100 150 200 250
 Reconstruction of the original image from the Laplacian
Pyramid
Laplacian Gl = Ll + G’l
Pyramid
expand

+ =
expand

+ =
expand

+ =
Original
= Image
 Band Pass Filter
• A band-pass filter is a device that passes
frequencies within a certain range and rejects
(attenuates) frequencies outside that range.
Image Blending (Mosaicing)

Registration
Image Blending
Blending
 Multiresolution Spline
When splining two images, transition from one image to
the other should behave:

High Frequencies

Middle Frequencies

Low Frequencies
Multiresolution Spline

High Frequencies

Middle Frequencies

Low Frequencies
Multiresolustion Spline - Using Laplacian Pyramid
Multiresolution Spline - Example
Left Image Right Image

Left + Right Narrow Transition

Wide Transition Multiresolution Spline

(Burt & Adelson)

Multiresolution Spline - Example

Original - Left Original - Right

Glued Splined
laplacian level 4

laplacian level 2

laplacian level 0

left pyramid right pyramid blended pyramid

Multiresolution Spline
Pyramid Blending
 Pyramid Blending
1

0
1

Left pyramid blend Right pyramid

laplacian
level
4

laplacian
level
2

laplacian
level
0

left pyramid right pyramid blended pyramid

 Laplacian Pyramid: Blending
• General Approach:
1. Build Laplacian pyramids LA and LB from images
A and B
2. Build a Gaussian pyramid GR from selected region
R
3. Form a combined pyramid LS from LA and LB
using nodes of GR as weights:
• LS(i,j) = GR(I,j,)*LA(I,j) + (1-GR(I,j))*LB(I,j)
4. Collapse the LS pyramid to get the final blended
image
Comparisons: Levin et al, 2004
Perez et al., 2003
 Perez et al, 2003

editing

• Limitations:
– Can’t do contrast reversal (gray on black -> gray
on white)
– Colored backgrounds “bleed through”
– Images need to be very well aligned
 Don’t blend, CUT!

Moving objects become ghosts

• So far we only tried to blend between two

images. What about finding an optimal seam?
 Minimal error boundary
overlapping blocks vertical boundary

2
_ =
overlap error min. error boundary
 Graphcuts
• What if we want similar “cut-where-things-
agree” idea, but for closed regions?
– Dynamic programming can’t handle loops
 Graph cuts
(simple example à la Boykov&Jolly, ICCV’01)

hard
t
n-links a cut
constraint

hard
constraint
s

Minimum cost cut can be computed in polynomial time

(max-flow/min-cut algorithms)
 Kwatra et al, 2003

Actually, for this example, DP will work just as well…

Lazy Snapping (Li el al., 2004)

Interactive segmentation using graphcuts