##
This **preview** shows page *1-2-3-21-22-23-43-44-45*
out of 45 **pages**.

*View Full Document*

End of preview. Want to read all 45 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

1Texture Synthesis15-463: Rendering and Image ProcessingAlexei EfrosWeather Forecasting for Dummies™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 Chain24.04.02.03.03.04.01.06.03.0Markov ChainWhat if we know today and yestarday’s weather?Text Synthesis[Shannon,’48] proposed a way to generate English-looking text using N-grams:• Assume a generalized Markov model• Use a large text to compute prob. distributions of each letter given N-1 previous letters • Starting from a seed repeatedly sample this Markov chain to generate new letters • Also works for whole wordsWE NEED TO EAT CAKE3Mark V. Shaney (Bell Labs)Results (using alt.singles corpus):• “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”Video TexturesVideo TexturesArno SchödlRichard SzeliskiDavid SalesinIrfan EssaMicrosoft Research, Georgia Tech4Still photosStill photosVideo clipsVideo clips5Video texturesVideo texturesProblem statementProblem statementvideo clip video texture6Our approachOur approach•How do we find good transitions?Finding good transitions Finding good transitions •Compute L2distance Di, jbetween all framesSimilar frames make good transitions frame ivs.frame j7Markov chain representationMarkov chain representation2341Similar frames make good transitions Transition costs Transition costs • Transition from i to j if successor of i is similar to j• Cost function: Ci→j= Di+1, j•iji+1j-1i j→Di+1, j8Transition probabilitiesTransition probabilities•Probability for transition Pi→jinversely related to cost:•Pi→j~ exp ( – Ci→j/ σ2)high σlow σPreserving dynamicsPreserving dynamics9Preserving dynamics Preserving dynamics Preserving dynamics Preserving dynamics •Cost for transition i→j•Ci→j= wkDi+k+1, j+kΣk = -NN-1ijj+1i+1i+2j-1j-2i j→Di, j-1DDi+1, ji+2, j+1i-1Di-1, j-210Preserving dynamics – effect Preserving dynamics – effect •Cost for transition i→j•Ci→j= wkDi+k+1, j+kΣk = -NN-12341Dead endsDead ends•No good transition at the end of sequence112341Future costFuture cost•Propagate future transition costs backward•Iteratively compute new cost•Fi→j= Ci→j+ αminkFj→k2341Future costFuture cost•Propagate future transition costs backward•Iteratively compute new cost•Fi→j= Ci→j+ αminkFj→k122341Future costFuture cost•Propagate future transition costs backward•Iteratively compute new cost•Fi→j= Ci→j+ αminkFj→k2341Future costFuture cost•Propagate future transition costs backward•Iteratively compute new cost•Fi→j= Ci→j+ αminkFj→k132341•Propagate future transition costs backward•Iteratively compute new cost•Fi→j= Ci→j+ αminkFj→k•Q-learningFuture costFuture costFuture cost – effectFuture cost – effect14Finding good loopsFinding good loops•Alternative to random transitions•Precompute set of loops up frontVisual discontinuitiesVisual discontinuities•Problem: Visible “Jumps”15CrossfadingCrossfading•Solution: Crossfade from one sequence to the other. Ai-2Ai-2Bj-215……3122 134444 44+++Ai-1Ai-1/Bj-2Ai-1/Bj-2Ai-1/Bj-2Bj-1AiBjAi+1Bj+1Bj+1Morphing Morphing •Interpolation task:A25B25C15++16Morphing Morphing •Interpolation task:•Compute correspondencebetween pixels of all framesA25B25C15++Morphing Morphing •Interpolation task:•Compute correspondence between pixels of all frames•Interpolate pixel position andcolor in morphed frame•based on [Shum 2000]A25B25C15++17Results – crossfading/morphingResults – crossfading/morphingResults – crossfading/morphingResults – crossfading/morphingJump Cut Crossfade Morph18CrossfadingCrossfadingFrequent jump & crossfadingFrequent jump & crossfading19Video portraitVideo portrait•Useful for web pagesRegion-based analysisRegion-based analysis•Divide video up into regions•Generate a video texture for each region20Automatic region analysisAutomatic region analysisVideo-based animationVideo-based animation•Like spritescomputer games•Extract spritesfrom real video•Interactively control desired motion©1985 Nintendo of America Inc.21Video sprite extractionVideo sprite extractionblue screen mattingand velocity estimationCi j = + angle α βCi j→ →vector tomouse pointerSimilarity term Control termvelocity vectorAnimation{{Video sprite controlVideo sprite control•Augmented transition cost:22Interactive fishInteractive fishLord of the FliesLord of the Flies23Summary Summary •Video clips → video textures•define Markov process•preserve dynamics•avoid dead-ends•disguise visual discontinuitiesTexture• Texture depicts spatially repeating patterns• Many natural phenomena are texturesradishes rocks yogurt24Texture Synthesis• Goal of Texture Synthesis: create new samples of a given texture• Many applications: virtual environments, hole-filling, texturing surfaces The Challenge• Need to model the whole spectrum: from repeated to stochastic texturerepeatedstochasticBoth?25Efros & Leung Algorithm• Assuming Markov property, compute P(p|N(p))– Building explicit probability tables infeasible ppSynthesizing a pixelnon-parametricsamplingInput image– Instead, we search the input image for all similar neighborhoods — that’s our pdf for p– To sample from this pdf, just pick one match at randomSome Details• Growing is in “onion skin” order– Within each “layer”, pixels with most neighbors are synthesized first– If no close match can be found, the pixel is not synthesized until the end• Using Gaussian-weighted SSD is very important– to make sure the new pixel agrees with its closest neighbors– Approximates reduction to a smaller neighborhood window if data is too sparse26Neighborhood WindowinputVarying Window SizeIncreasing window size27Synthesis Resultsfrench canvas rafia weaveMore Resultswhite bread brick wall28Homage to ShannonHole Filling29ExtrapolationSummary• The Efros & Leung algorithm–

View Full Document