Video TextureWeather Forecasting for Dummies™Markov ChainText SynthesisMark V. Shaney (Bell Labs)Video TexturesStill photosVideo clipsVideo texturesProblem statementOur approachFinding good transitionsMarkov chain representationTransition costsTransition probabilitiesPreserving dynamicsPreserving dynamicsSlide 18Preserving dynamics – effectDead endsFuture costSlide 22Slide 23Slide 24Slide 25Future cost – effectFinding good loopsVisual discontinuitiesCrossfadingMorphingSlide 31Slide 32Results – crossfading/morphingSlide 34CrossfadingFrequent jump & crossfadingVideo portraitRegion-based analysisAutomatic region analysisVideo-based animationVideo sprite extractionVideo sprite controlInteractive fishLord of the FliesSummaryMotion Analysis & Synthesis [Efros ’03]Gathering action dataFigure-centric RepresentationRemembrance of Things PastHow to describe motion?Motion DescriptorComparing motion descriptorsRecognizing Tennis“Do as I Do” Motion SynthesisSmoothness for Synthesis“Do as I Do”“Do as I Say” Synthesis“Do as I Say”Application: Motion RetargetingContext-based Image CorrectionActor ReplacementVideo Texture15-463: Computational PhotographyAlexei Efros, CMU, Fall 2005© 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 Chain4.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 L2 distance Di, j between 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: Cij = Di+1, j• iji + 1j - 1i jDi + 1 , jTransition probabilitiesTransition probabilities•Probability for transition Pij inversely related to cost:•Pij ~ exp ( – Cij / 2 )high low Preserving dynamicsPreserving dynamicsPreserving dynamics Preserving dynamicsPreserving dynamics Preserving dynamics •Cost for transition ij•Cij = wk Di+k+1, j+kk = - NN - 1ijj + 1i + 1i + 2j - 1j - 2i jDi , j - 1DDi + 1 , ji + 2 , j + 1i - 1Di - 1 , j - 2Preserving dynamics – effect Preserving dynamics – effect •Cost for transition ij•Cij = wk Di+k+1, j+kk = - NN - 12341Dead endsDead ends•No good transition at the end of sequence2341Future costFuture cost•Propagate future transition costs backward•Iteratively compute new cost•Fij = Cij + mink Fjk2341Future costFuture cost•Propagate future transition costs backward•Iteratively compute new cost•Fij = Cij + mink Fjk2341Future costFuture cost•Propagate future transition costs backward•Iteratively compute new cost•Fij = Cij + mink Fjk2341Future costFuture cost•Propagate future transition costs backward•Iteratively compute new cost•Fij = Cij + mink Fjk2341•Propagate future transition costs backward•Iteratively compute new cost•Fij = Cij + mink Fjk•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”Crossfading Crossfading •Solution: Crossfade from one sequence to the other. Ai - 2Ai - 2Bj - 21 5……3122 134444 44+++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 pagesRegion-based analysisRegion-based analysis•Divide video up into regions•Generate a video texture for each regionAutomatic region analysisAutomatic region analysisVideo-based animationVideo-based animation•Like spritescomputer games•Extract spritesfrom real video•Interactively control desired motion©1985 Nintendo of America Inc.Video sprite extractionVideo sprite extractionb l u e s c r e e n m a t t i n ga n d v e l o c i t y e s t i m a t i o nCi j = + a n g l e Ci j v e c t o r t om o u s e p o i n t e rS i m i l a r i t y t e r m C o n t r o l t e r mv e l o c i t y v e c t o rA n i m a t i o n{{Video sprite controlVideo sprite control•Augmented transition cost:Interactive fishInteractive fishLord of the FliesLord of the FliesSummary Summary •Video clips video textures•define Markov process•preserve dynamics•avoid
View Full Document