Data-driven methods: Video15-463: Computational PhotographyAlexei Efros, CMU, Fall 2007© A.A. 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 Chain⎟⎟⎟⎠⎞⎜⎜⎜⎝⎛4.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 CAKEMark 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 TechStill photosStill photosVideo clipsVideo clipsVideo texturesVideo texturesProblem statementProblem statementvideo clip video textureOur 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 jMarkov chain representationMarkov chain representation2341Similar frames make good transitionsTransition 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-1ij→Di+1, jTransition probabilitiesTransition probabilities•Probability for transition Pi→jinversely related to cost:•Pi→j~exp ( –Ci→j/ σ2)high σlow σPreserving dynamicsPreserving dynamicsPreserving dynamics Preserving dynamicsPreserving dynamics Preserving dynamics • Cost for transition i→j• Ci→j= wkDi+k+1, j+kΣk = -NN-1ijj+1i+1i+2j-1j-2ij→Di, j-1DDi+1, ji+2, j+1i-1Di-1, j-2Preserving 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 sequence2341Future 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→k2341Future 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→k2341• Propagate future transition costs backward• Iteratively compute new cost• Fi→j= Ci→j+ αminkFj→k• Q-learningFuture costFuture costFuture cost – effectFuture cost – effectFinding good loopsFinding good loops• Alternative to random transitions• Precompute set of loops up frontVisual discontinuitiesVisual discontinuities• Problem: Visible “Jumps”CrossfadingCrossfading• Solution: Crossfade from one sequence to the other. Ai-2Ai-2Bj-215……312213444444+++Ai-1Ai-1/Bj-2Ai-1/Bj-2Ai-1/Bj-2Bj-1AiBjAi+1Bj+1Bj+1Morphing Morphing • Interpolation task:A25B25C15++Morphing 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++Results – crossfading/morphingResults – crossfading/morphingResults – crossfading/morphingResults – crossfading/morphingJump Cut Crossfade MorphCrossfadingCrossfadingFrequent jump & crossfadingFrequent jump & crossfadingVideo portraitVideo portrait• Useful for web pages• Combine with IBR techniquesVideo portrait – 3DVideo portrait – 3DRegion-based analysisRegion-based analysis• Divide video up into regions• Generate a video texture for each regionAutomatic region analysisAutomatic region analysisUser selects target frame rangeUser-controlled video texturesUser-controlled video texturesslow variable fastVideo-based animationVideo-based animation• Like spritescomputer games• Extract spritesfrom real video• Interactively control desired motion©1985 Nintendo of America Inc.Video sprite extractionVideo sprite extractionblue screen mattingand velocity estimationCij = + angle αβCij→→vector tomouse pointerSimilarity term Control termvelocity vectorAnimationVideo sprite controlVideo sprite control• Augmented transition cost:Fij→Fij→Fij→Fij→Fij→Fij→Fij→SWWNWNNEESESGoalVideo sprite controlVideo sprite control• Need future cost computation• Precompute future costs for a few angles.• Switch between precomputed angles according to user input• [GIT-GVU-00-11]Interactive fishInteractive fishSummary Summary • Video clips → video textures• define Markov process• preserve dynamics• avoid dead-ends• disguise visual discontinuitiesDiscussion Discussion • Some things are relatively easyDiscussion Discussion • Some are hardA final exampleA final exampleMichel Gondry train
View Full Document