Graphcut Textures: Image and Video Synthesis Using Graph Cuts

visual table of contents

In this paper we introduce a new algorithm for image and video texture synthesis. In our approach, patch regions from a sample image or video are transformed and copied to the output and then stitched together along optimal seams to generate a new (and typically larger) output. In contrast to other techniques, the size of the patch is not chosen a-priori, but instead a graph cut technique is used to determine the optimal patch region for any given offset between the input and output texture. Unlike dynamic programming, our graph cut technique for seam optimization is applicable in any dimension. We specifically explore it in 2D and 3D to perform video texture synthesis in addition to regular image synthesis. We present approximative offset search techniques that work well in conjunction with the presented patch size optimization. We show results for synthesizing regular, random, and natural images and videos. We also demonstrate how this method can be used to interactively merge different images to generate new scenes.


Related publication:

Graphcut Textures: Image and Video Synthesis Using Graph Cuts

Vivek Kwatra , Arno Schödl , Irfan Essa , Greg Turk and Aaron Bobick
To appear in Proc. ACM Transactions on Graphics, SIGGRAPH 2003
Paper 23.2 MB | Paper 3.3 MB | SIGGRAPH Video (160 MB, 50 MB) | Video Results 87 MB | BibTex


Results:

Video texture results
Interactive image synthesis results
Rotation and perspective results
Image texture results
Credits


Video texture results:

Run your video player in loop mode

Clip

Thumbnails
Original Graph cut 
(Temporal)
Graph cut
(Spatio temporal)

Schödl et al.'00
(
Video textures)
Wei & Levoy'00 Bar-Joseph et al.'01
Soatto et al.'01
(
Dynamic textures)
Waterfall A
waterfall
1.8 MB
1.1 MB

9.3 MB


0.8 MB
Fountain fountain
1.4 MB 1.0 MB
1.4 MB


Grass grass
0.4 MB 0.3 MB
2.0 MB


Pond pond
1.7 MB 1.2 MB
1.6 MB


Sparkle sparkle
0.4 MB 0.6 MB




Flame
flame
0.4 MB
0.4 MB





Waterfall B
waterfal2
0.1 MB

0.2 MB


0.1 MB

Clouds
clouds
0.2 MB

0.3 MB


0.2 MB

River
river
0.3 MB

0.3 MB *




Fire
fire
0.1 MB
0.8 MB

0.1 MB
0.1 MB


Ocean
ocean
0.1 MB
0.5 MB
0.5 MB
0.1 MB
0.1 MB


Smoke
smoke
0.1 MB
0.3 MB
0.1 MB

0.1 MB


Beach
beach
4.8 MB
0.6 MB

1.6 MB




( * : The synthesized movie has increased spatial resolution )


Interactive image synthesis results:

hut
 mountain
Hut
Mountain
hut-mountain  hut-mountain-seam
Hut + Mountain
Hut + Mountain + Seam


raft  River
Raft
River
Raft-River  Raft-River-seam
R aft + River
Raft + River + Seam


banner-sources
Flowers and Leaves (click here for hi-resolution image)
siggraph
SIGGRAPH !! (click here for hi-resolution image)


Rotation and perspective results:

olive
 olive-rotmir  olive-quilt
Input (Olives)
Graph cut
(with rotation and mirroring)

Efros and Freeman'01
(Image Quilting)





bottles   bottles-out
lily-in   lily-out
people   people-persp
Input ( bottles, lilies, crowd)
Output (with perspective effects)


Image texture results:


11

3D-fish-school

7

AB_cuzco

AB_machu3

AB_pottery

AB_quito

AB_valley

akeyboard_small

beads

berry

blueberries

botawana_pink

bottles

bread

brussels_sprouts

cans_sc

cashews

chains

chains2

cherries

chesapeake

chickpeas

corral

cream

crowds1

crowds2

eggs

eschar2

eschar_horse

fish

fish_farm

fresh_blue_berries

gecko

grant_beads

grapes

grass

green

herd_of_sheep

jelly

leaf

leaves

lights2

lobelia

long_island

m&m_candy

nuts2

nuts3

nuts5

nuts6

ocean_image

olives

peanuts1

penguins

rainstone

red_peppers

ropenet

San_Diego

school

seals2

seaweed

sheep

sheep_big

strawberries2

test3

Thai_art

tomatoes

tuberous_begonia

vene3

watches_small

winged_lions

yarn



Credits:

Image Mountain
Erskine Wood
Image River
Tim Seaver
Image  Flowers (b) : Lilies
East West Photo
Image  Flowers (c) : Red
Jens Grabenstein
Image  Flowers (e) : Redbuckia
Olga Zhaxybayeva
Image Lilies (perspective  results)
Brad Powell
Images AB_cuzco, AB_machu3, AB_pottery, AB_quito and AB_valley
Adam Brostow
Images corral, rainstone and seaweed
Paul Maple Digital Gallery
Image chickpeas
Nature
Image nuts
Biotech and You
Videos River and Fire
MIT temporal texture database , Rupert Paget
Video Flame
Artbeats Digital Film Libtary
Videos Waterfall B and Clouds
Rupert Paget , Ziv Bar-Joseph
Videos  Smoke and Ocean
Li-Yi Wei ( Stanford University : Texture synthesis page )

Acknowledgements (from the paper):

We would like to thank Professor Ramin Zabih and his students at Cornell University for sharing their code for computing graph min-cut. Thanks also to the authors of  Image Quilting (Alyosha Efros and Bill Freeman), Li-Yi Wei and Marc Levoy, and Ziv BarJoseph et al. for sharing their raw footage and results via their respective web sites to facilitate direct comparisons. Thanks also to Rupert Paget for maintaining an excellent web page on texture research and datasets, and to Martin Szummer for the MIT temporal texture database. Thanks also to the following for contributing their images or videos: East West Photo, Jens Grabenstein, Olga Zhaxybayeva, Adam Brostow, Brad Powell, Erskine Wood, Tim Seaver and Artbeats Inc.. Finally, we would like to thank our collaborators Gabriel Brostow, James Hays, Richard Szeliski and Stephanie Wojtkowski for their insightful suggestions and help with the production of this work. Arno Schö dl is now at think-cell Software GmbH in Berlin, Germany.


This work was funded in part by grants from NSF (IIS-9984847, ANI-0113933 and CCR-0204355) and DARPA (F49620-001-0376), and funds from Microsoft Research.