Nima Kalantari

CSCE 448/748 - Computational Photography

​

​

Texture Synthesis

Many slides from Alexei A. Efros

Texture

• Texture depicts spatially repeating patterns
• Many natural phenomena are textures

radishes

rocks

yogurt

Texture Synthesis

• Goal of Texture Synthesis: create new samples of a given texture
• Many applications: hole-filling, texturing surfaces

The Challenge

• Need to model the whole spectrum: from repeated to stochastic texture

Weather Forecasting

Let’s predict weather:

• Given today’s weather only, we want to know tomorrow’s
• Suppose weather can only be {Sunny, Cloudy, Raining}

​

The “Weather Channel” algorithm:

• Over a long period of time, record:
• How often S followed by R
• How often S followed by S
• Etc.
• Compute percentages for each state:
• P(R|S), P(S|S), etc.
• Predict the state with highest probability!
• It’s a Markov Chain

Markov Chain

What if we know today and yesterday’s weather?

Second Order Markov Chain

Observation

R,R

R,C

R,S

C,R

C,C

C,S

S,R

S,C

S,S

Markov Chains

Markov Chain

• a sequence of random variables

​

• is the state of the model at time t

​

​

​

• Markov assumption: each state is dependent only on the previous one
• dependency given by a conditional probability:

​

​

• The above is actually a first-order Markov chain
• An N’th-order Markov chain:

Text synthesis

Create plausible looking poetry, love letters, term papers, etc.

Most basic algorithm

• Build probability histogram
• find all blocks of N consecutive words/letters in training documents
• compute probability of occurance
• Given words
• compute by sampling from

Markov Chain Example: Text

“A dog is a man’s best friend. It’s a dog eat dog world out there.”

a

dog

is

man’s

best

friend

it’s

eat

world

out

there

dog

is

man’s

best

friend

it’s

eat

world

out

there

a

.

.

Mark V. Shaney (Bell Labs)

Results:

• “As I've commented before, really relating to someone involves standing next to impossible.”
• “One morning I shot an elephant in my arms and kissed him.”
• “I spent an interesting evening recently with a grain of salt”

Markov Random Field

A Markov random field (MRF)

• generalization of Markov chains to two or more dimensions.

First-order MRF:

• probability that pixel X takes a certain value given the values of neighbors A, B, C, and D:

Efros & Leung Algorithm

• Assuming Markov property, compute P(p|N(p))
• Building explicit probability tables infeasible

Synthesizing a pixel

Neighborhood Window

input

Varying Window Size

Increasing window size

Synthesis Results

french canvas

rafia weave

More Results

white bread

brick wall

Homage to Shannon

Hole Filling

Extrapolation

Summary

• The Efros & Leung algorithm
• Very simple
• Surprisingly good results
• …but very slow

​

Image Quilting [Efros & Freeman]

• Observation: neighbor pixels are highly correlated

Input image

non-parametric

sampling

Input texture

B1

B2

Random placement

of blocks

block

Minimal error boundary

overlapping blocks

vertical boundary

Our Philosophy

• The “Corrupt Professor’s Algorithm”:
• Plagiarize as much of the source image as you can
• Then try to cover up the evidence
• Rationale:
• Texture blocks are by definition correct samples of texture so problem only connecting them together

Portilla & Simoncelli

Wei & Levoy

Our algorithm

input image

Xu, Guo & Shum

Application: Texture Transfer

• Try to explain one object with bits and pieces of another object:

+

=

Texture Transfer

Constraint

Texture sample

• Take the texture from one image and “paint” it onto another object

Texture Transfer

Same as texture synthesis, except an additional constraint:

• Consistency of texture
• Similarity to the image being “explained”

=

+