Texture Synthesis
Texture SynthesisMichael Kazhdan(601.457/657)An Image Synthesizer. Perlin, 1985Texture Synthesis by Non-Parametric Sampling. Efros and Leung, 1999Image Quilting for Texture Synthesis and Transfer. Efros and Freeman, 2001Wang Tiles for Image and Texture Generation. Cohen et al., 2003
Assignment 2 (Hint)You can (but donβt have to) represent a sphereusing a quadratic polynomial in three variables.For example, you can define the polynomial:ππ π₯π₯, π¦π¦, π§π§ π₯π₯ 2 π¦π¦ 2 π§π§ 2 1by calling:Polynomial3D 2 P;P.coefficient(2u,0u,0u) 1;P.coefficient(0u,2u,0u) 1;P.coefficient(0u,0u,2u) 1.;P.coefficient(0u,0u,0u) -1.;
Assignment 2 (Hint)You can then intersect the polynomial P with aRay3D object, ray, to obtain a quadratic polynomialin one variable (the time along the ray):ππ π‘π‘ ππ ππππππ. οΏ½οΏ½π π‘π‘ ππππππ. οΏ½οΏ½πππππby calling:Polynomial1D 2 p P( ray );Then you can get the zero-crossings by calling thePolynomial1D::roots member function:double roots[2];unsigned int rootNum p.roots( roots );
Assignment 2 (Hint)You can then intersect the polynomial P with aRay3D object, ray, to obtain a quadratic polynomialin one variable (the time along the ray):ππ π‘π‘ ππ ππππππ. οΏ½οΏ½π π‘π‘ ππππππ. οΏ½οΏ½πππππby calling:Polynomial1D 2 p P( ray );Note:The younumbermay be less thansotheThencan ofgetrootsthe zero-crossingsby two,callingcheck the value of rootNum.Polynomial1D::rootsmember function:double roots[2];unsigned int rootNum p.roots( roots );
What is a texture?Courtesy Paul Bourke
What is a texture?Courtesy Paul Bourke
What is a texture?Courtesy Paul Bourke
What is not a texture?βPirates of the Caribbeanβ
What is not a texture?
What is not a texture?βLilo and Stitchβ
What is a texture?Texture is an image that exhibits: Stationarity β different regions βlook similarβCourtesy Paul Bourke
What is a texture?Texture is an image that exhibits: Stationarity β different regions βlook similarβ Locality β individual pixels related only to smallset of neighborsCourtesy Paul Bourke
What is a texture?Texture is an image that exhibits: Stationarity β different regions βlook similarβ Locality β individual pixels related only to smallset of neighborsNote:Any image can be texture-mapped.Courtesy Paul BourkeWe are focusing on images that are qualitatively textures.
How can we get textures? Photographs Manual texture synthesis Automatic texture synthesis Procedural generation Texture βextrapolationβ
PhotographsEasy and fast (if we can find the texture we want)! What if our photo is not big enough?Courtesy NVIDIA
PhotographsEasy and fast (if we can find the texture we want)! What if our photo is not big enough? Stretching changes scale, image qualityCourtesy NVIDIA
PhotographsEasy and fast (if we can find the texture we want)! What if our photo is not big enough? Stretching changes scale, image quality Tiling looks repetitive (and we need to worry aboutseams)
Manual Texture Synthesis There are βtexture paintersβ Time consuming Difficult
Automatic Texture SynthesisHow do wecreate thisEx nihiloHow do we gofrom this to this?Or from this to this?Ex materia
Procedural Textures Generated algorithmically instead of by an artist Good for certain natural phenomena: Wood grainMarbleFireEtc.
Perlin-noise TexturesKey Idea: Many natural objects have many levels of detail. We can create natural looking textures by addingup βnoisyβ functions at a range of different scales.
Perlin-noise Textures (Per Level)void init( float noise[] , int n ){for( int i 0 ; i n ; i ) noise[i] rand();}We need: Noise InterpolationNoisefloat sample( float x , const float noise[] , int n ){x * n;int ix (int)floor( x );return Interpolate( noise[ix] , noise[ix 1] , x-ix );}InterpolationCourtesy Hugo Elias
Perlin-noise Texturesvoid init( float noise[] , int n , float amp ){for( int i 0 ; i n ; i ) noise[i] rand() * amp;}We need: Noise InterpolationNoisefloat sample( float x , const float noise[] , int n ){x * n;int ix (int)floor( x );return Interpolate( noise[ix] , noise[ix 1] , x-ix );}InterpolationFrequency : Distance between Samples (1/ππ)Amplitude : Magnitude of the random numberCourtesy Hugo Elias
Perlin-noise TexturesSum noise at different frequencies/amplitudesvoid init( float noise[] , int n , float amp ){for( int i 0 ; i n ; i ) noise[i] rand() * amp;}float sample( float x , const float noise[] ){Courtesy Hugo Eliasx * n;int ix (int)floor( x );return Interpolate( noise[ix] , noise[ix 1] , x-ix );}
Perlin-noise TexturesSum noise at different frequencies/amplitudesvoid init( float noise[] , int n , float amp ){for( int i 0 ; i n ; i ) noise[i] rand() * amp;}float sample( float x , const float noise[] ){Courtesy Hugo Eliasx * n;int ix (int)floor( x );return Interpolate( noise[ix] , noise[ix 1] , x-ix );}
Perlin-noise TexturesSum noise at different frequencies/amplitudesHow much data would we need to store the texture?If we sample at n positions we need 2ππ values:void init( float noise[] , int n , float amp ) ππ at the finest level{for( int i 0 ; i n ; i ) noise[i] rand() * amp; ππ/2 at the next level,} etc.float sample( float x , const float noise[] )In ππ dimensions, ππππππ{.}x * n;int ix (int)floor( x );return Interpolate( noise[ix] , noise[ix 1] , x-ix );
Perlin-noise TexturesSum noise at different frequencies/amplitudesHow much data do we need to sample the texture?void init( float noise[] , int n , float amp ){for( int i 0 ; i n ; i ) noise[i] rand() * amp;}float sample( float x , const float noise[] ){x * n;int ix (int)floor( x );return Interpolate( noise[ix] , noise[ix 1] , x-ix );Courtesy Hugo Elias}
Perlin-noise TexturesSum noise at different frequencies/amplitudesHow much data do we need to sample the texture?If our random number generator alwaysvoid init( float, intn , float)floatnoise[]sample(floatx , intampn , floatamp ){{generate the same βrandom numberβ atfor( inti 0x; * i nn;; i ) noise[i] rand() * amp;index i, then we only need to know} theint ix (int)floor( x );float sample( floatx , constsrand(ix ); float noise[] )amplitudes.{float nx0 rand() * amp;}x * n;srand( ix 1);int ix (int)floor(x ); rand() * amp;float nx1return Interpolate(noise[ix] , noise[ix 1], x-ix););return Interpolate(nx0 , nx1 , x-ix}
Perlin-noise TexturesSum noise at different frequencies/amplitudesHow much computation is required to get the value at a point?Using linear interpolation, we need two values at each level.float sample( float x , int n , float amp )noise[] , int n , float amp )Assuming πΏπΏ levels, we need to: void init( float{{x * n; Generate 2πΏπΏ random valuesfor( int i 0int; i n) noise[i]x );rand() * amp;ix ; i (int)floor(}srand( ix ); Interpolate between πΏπΏ pairs of valuesfloat sample( floatx ,nx0constfloat noise[]float rand()* amp; ){srand( ix 1); Sum the πΏπΏ interpolationsIn ππ dimensions, ππ 2ππ πΏπΏ .}int ix (int)floor(x ); rand() * amp;float nx1return Interpolate(noise[ix] , noise[ix 1], x-ix););return Interpolate(nx0 , nx1 , x-ix}
Perlin-noise TexturesSame idea with 2D images Courtesy Hugo Elias
Perlin-noise TexturesAnd even 3D texturesNote:We can introduce anisotropy by using different amplitudes for theπ₯π₯-, π¦π¦-, and π§π§-directions.Hugo Elias
Procedural TexturesPros Constant memory overhead Can be computed efficiently ππ 2ππ πΏπΏCons Only good for certain natural phenomena
Automatic Texture SynthesisHow do wecreate thisEx nihiloHow do we gofrom this to this?Or from this to this?Ex materia
Markov Models: Text Assume we have: A fixed alphabet (ππ through π§π§) An input text such as π A 0th-order Markov Model: Assign probabilities to the characters based on thefrequency of their occurrence in the input text:238ππ ππ ππ ππ ππ ππ 131313 Assuming occurrence of a character is independent ofprevious characters, we can generate a new string byβflipping coinsβ.
Markov Models: TextBut each character is not independent of previouscharacters! A ππ th-order Markov Model: Assigns probabilities to a characterβs occurrence thatdepends on the previous ππ characters.
Markov Models: Text Assume we have input text with: 100 occurrences of π‘π‘π‘50 of which followed by ππ (π‘π‘π‘π‘π‘, π‘π‘π‘π‘π‘π‘π‘, etc.)25 of which followed by ππ (π‘π‘π‘π‘π‘π‘π‘, π‘π‘π‘π‘π‘π‘π‘, etc.)20 of which followed by ππ (π‘π‘π‘π‘π‘π‘π‘, π‘π‘π‘π‘π‘π‘π‘π‘π‘, etc.)5 of which followed by ππ (π‘π‘π‘π‘π‘π‘π‘π‘π‘π‘, π‘π‘π‘π‘π‘π‘π‘π‘π‘, etc.) 2nd-order Markov model predicts that:1ππ ππ π‘π‘π‘ 2111ππ ππ π‘π‘π‘ ππ ππ π‘π‘π‘ ππ ππ π‘π‘π‘ 4520 Given this probabilistic model and a seed, we cangenerate new text!
Markov Models: TextSnippet of original text: βAs You like itβ by Shakespeare:DUKE SENIOR:Now, my co-mates and brothers in exile,Hath not old custom made this life more sweetThan that of painted pomp? Are not these woodsMore free from peril than the envious court?Here feel we but the penalty of Adam,The seasons' difference, as the icy fangAnd churlish chiding of the winter's wind,Which, when it bites and blows upon my body,Even till I shrink with cold, I smile and say'This is no flattery: these are counsellorsThat feelingly persuade me what I am.β .
Markov Models: TextSnippet of generated text with 6th-order MarkovModel:DUKE SENIOR:Now, my co-mates and thus bolden'd, man, how now,monsieur Jaques, Unclaim'd of his absence, as the holly!Though in the slightest for the fashion of his absence, asthe only wear.
Markov Models: ImagesUse this asoriginal βtextβand this as seedto get this result!Figure out valuesof new pixelsbased onsurroundingknown pixels
Markov Models: ImagesUse this asoriginal βtextβand this as seedto get this result!Figure out valuesof new pixelsbased onsurroundingknown pixels
Markov Models: ImagesUse this asoriginal βtextβand this as seedto get this result!Figure out valuesof new pixelsbased onsurroundingknown pixels
Markov Models: ImagesUse this asoriginal βtextβand this as seedto get this result!Figure out valuesof new pixelsbased onsurroundingknown pixels
Markov Models: ImagesProblems: For a given neighborhood, might be only 1 exactmatch Resulting texture too obviously similar to the input For a given neighborhood, there may be no exactmatchesSolution: Randomly choose among best ππmatches with probability based onmatch quality
Markov Models: ImagesExamples:
Markov Models: ImagesPros: Conceptually simple/sound Often produces good results Never chooses a pixel/color NOT found in sourceCons: Need to choose correct window size
Markov Models: ImagesIncreasing window sizeCourtesy Alexei Efros
Markov Models: ImagesIncreasing window sizeCourtesy Alexei Efros
Markov Models: ImagesIncreasing window sizeCourtesy Alexei Efros
Markov Models: ImagesIncreasing window sizeCourtesy Alexei Efros
Markov Models: ImagesPros: Conceptually simple/sound Often produces good results Never chooses a pixel/color NOT found in sourceCons: Need to choose correct window size Very slow! (increasing window size makes this worse)Β» See [Barnes, β09] for acceleration techniques Doesnβt always work (can get stuck in a rut)
Markov Models: ImagesGrowing garbageVerbatim copyingCourtesy Alexei Efros
Markov Models: ImagesPros: Conceptually simple/sound Often produces good results Never chooses a pixel/color NOT found in sourceCons: Need to choose correct window sizeVery slow! (increasing window size makes this worse)Doesnβt always work (can get stuck in a rut)The size of the output texture is proportional to thesize of the output texture
Wang TilesCan we use a small amount of texture memory togenerate large textures? Tiling: discontinuities repetitive
Wang TilesKey Idea:Given a set of colors, and given a sufficiently largeset of square tiles whose edges are marked withone of these colors:
Wang TilesKey Idea:The plane can be tiled with edge-matching squares:Tiled ImageBase Tiles
How Wang Tile WorksApplication: Associate a single texture to each tileInput tilesSlide courtesy of:http://www.graphicshardware.org
How Wang Tile WorksApplication: Associate a single texture to each tile Given a Wang tiling of the plane we get a new texturetilingInput tilesSlide courtesy of:http://www.graphicshardware.org
How Wang Tile WorksApplication: Associate a single texture to each tile Given a Wang tiling of the plane we get a new texturetilingInput tilesSlide courtesy of:http://www.graphicshardware.org
How Wang Tile WorksApplication: Associate a single texture to each tile Given a Wang tiling of the plane we get a new texturetilingInput tilesSlide courtesy of:http://www.graphicshardware.org
How Wang Tile WorksApplication: Associate a single texture to each tile Given a Wang tiling of the plane we get a new texturetilingIf the tiles can be made to match on commonSlide courtesy of:Input tilescolor edges, the texture will be seamless.http://www.graphicshardware.org
Wang TilesTile Complexity:For the texture not to appear repetitive, we need tohave (random) choice in which tile we choose.How many tiles do we need, assuming ππ differentcolors on the edges?
Wang TilesTile Complexity:In general, we have two restrictions when weintroduce a new tile β the colors of the West andNorth edges.Tiled Image?
Wang TilesTile Complexity:In general, we have two restrictions when weintroduce a new tile β the colors of the West andNorth edges.For ππ colors, this means that we need to have atleast ππ 2 tiles to be able to find one that will fit.In order to be able to make a random choice eachtime, we need to have at least 2ππ 2 tiles.
Wang TilesTile Generation:To generate seamless textures, tiles must match oncommon color edges.Otherwise, discontinuityseams will become visible:
Wang TilesTile Generation: Associate a source diamond to each colored edgeSource
Wang TilesTile Generation: Associate a source diamond to each colored edge Given a tile, paste the diamonds onto the edgesSource
Wang TilesTile Generation: Associate a source diamond to each colored edge Given a tile, paste the diamonds onto the edgesSource
Wang TilesTile Generation: Associate a source diamond to each colored edge Given a tile, paste the diamonds onto the edgesSource
Wang TilesTile Generation: Associate a source diamond to each colored edge Given a tile, paste the diamonds onto the edgesSource
Wang TilesTile Generation: Associate a source diamond to each colored edge Given a tile, paste the diamonds onto the edgesSource
Wang TilesTile Generation: Associate a source diamond to each colored edge Given a tile, paste the diamonds onto the edges Quilt the overlap region by solving a graph-cut problemfor the minimum discontinuity pathSource
Wang TilesTile Generation: Associate a source diamond to each colored edge Given a tile, paste the diamonds onto the edges Quilt the overlap region by solving a graph-cut problemfor the minimum discontinuity pathSince the two-sides of an edgecome from the same diamond,they are guaranteed to meetseamlessly!
MidtermContent:Everything covered up to this point (except todayβs lecture): Image Processing Sampling Ray-Casting/Tracing Illumination Clipping Texture Mapping
MidtermFormat: Closed book Short answer questions only No essays No true/false No multiple choice
MidtermBreakdown:Six Sections: Image ProcessingSamplingRay TracingIlluminationTexture MappingMiscellany
Texture Synthesis Michael Kazhdan (601.457/657) An Image Synthesizer. Perlin, 1985 Texture Synthesis by Non- Parametric Sampling. Efrosand Leung, 1999 Image Quilting for Texture Synthesis and Transfer. Efros and Freeman, 2001 Wang Tiles for Image an
using some of the latest work in texture synthesis. Texture Synthesis is the process of taking a small sample of a texture and generating more of it. For example, in Figure 1, given the input image A, a good texture synthesis algorithm should be able to generate more of the texture to create an image lik
Standard quilting texture synthesis Input image Quilting texture synthesis with texture transfer Correspondence map. 11 Texture Transfer from Efros & Freeman One last example Example texture Correspondence map courtesy of A. Efros.
Image Quilting [Efros & Freeman] Observation: neighbor pixels are highly correlated . Texture Transfer Try to explain one object with bits and pieces of another object: Texture Transfer . Texture Transfer. Same as texture synthesis, except an additional constraint: 1. Consistency of texture
Index Termsβ texture transfer, texture matting 1. INTRODUCTION Previous approaches to image-based texture synthesis often treat a texture as a single-layer image consisting of a regu-lar pattern or some less regular but repeated image features [2, 5, 9, 12]. Algorithms for image-based texture
Take the texture from one image and βpaintβ it onto another object Same as texture synthesis, except an additional constraint: 1. Consistency of texture 2. Patches from texture should correspond to patches from constraint in some way. Typical example: blur luminance, u
Take the texture from one image and βpaintβ it onto another object Same as texture synthesis, except an additional constraint: 1. Consistency of texture 2. Patches from texture should correspond to patches from constraint in some way. Typical example: blur luminance, u
Take the texture from one image and βpaintβ it onto another object Texture Transfer Same as texture synthesis, except an additional constraint: 1. Consistency of texture 2. Simil
Scrum 1 Agile has become one of the big buzzwords in the software development industry. But what exactly is agile development? Put simply, agile development is a different way of executing software development teams and projects. To understand what is new, let us recap the traditional methods. In conventional software development, the product requirements are finalized before proceeding with .
