Video 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 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 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 extractionblue screen mattingand velocity estimationCij = + angle αβCij→→vector tomouse pointerSimilarity term Control termvelocity vectorAnimationVideo 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 dead-ends• disguise visual discontinuitiesMotion Analysis & Synthesis [Efros ’03]• What are they doing?– Activity recognition, surveillance, anti-terrorism• Can we do the same?– Motion retargeting, movies, video games, etc.Gathering action data• Low resolution, noisy data• Moving camera• OcclusionsFigure-centric Representation• Stabilized spatio-temporal volume– No translation information– All motion caused by person’s limbs• Good news: indifferent to camera motion• Bad news: hard!• Good test to see if actions, not just translation, are being capturedinput sequenceRemembrance of Things Past• “Explain” novel motion sequence with bits and pieces of previously seen video clipsChallenge: how to compare motions?motion analysisrunwalk leftswingwalk rightjogmotion synthesissynthetic sequenceHow to describe motion?• Appearance – Not preserved across different clothing• Gradients (spatial, temporal)– same (e.g. contrast reversal)• Edges– Too unreliable• Optical flow– Explicitly encodes motion – Least affected by appearance – …but too noisyMotion DescriptorImage frameOptical flow yxF,yxFF ,+−+−yyxxFFFF ,,,blurred+−+−yyxxFFFF ,,,Comparing motion descriptorstmotion-to-motionsimilarity matrixblurry I…………frame-to-framesimilarity matrixΣI matrixRecognizing Tennis• Red bars show classification
View Full Document
Unlocking...