Optical Flow MethodsCISC 489/689Spring 2009University of DelawareOutline• Review of Optical Flow Constraint, Lucas-Kanade, Horn and Schunck Methods• Lucas-Kanade Meets Horn and Schunck•3D Regularization•3D Regularization• Techniques for solving optical flow• Confidence Measures in Optical FlowOptical Flow Constraint),,(),,(),,(),,(=∂∂+∂∂+∂∂+=+++tyxftftyfyxfxtyxftyxftttvytuxfδδδδδδ0limit takingand by Dividing →ttδδ),( tvytuxδδ++),( yx),,( tyxf00=++=∂∂+∂∂+∂∂tyxfvfuftfdtdyyfdtdxxf),,( ttyxfδ+InterpretationConstraint LinetTtyxfvuffvfuf−=∇=++ 0vtfvf−=∇()yxff ,u[ ]01=vuffftyxLucas-Kanade Method*=JK ∗ρJ=22201ttytxtyyyxtxyxxvufffffffffffffff=1*),( vuJKvuELKρ=2221ttytxtyyyxtxyxxttytxfffffffffffffffJfffffLucas-Kanade Method• Local Method, window based• Cannot solve for optical flow everywhere• Robust to noise5.7=ρ15=ρFigures from Lucas/Kanade Meets Horn/Schunck: Combining Local and Global OpticFlow Methods ANDR´ES BRUHN AND JOACHIM WEICKERT, 2005Dense optical Flow?)(),( Minimize2∫Ω++=tyxfvfufvuELacks SmoothnessFigures from Lucas/Kanade Meets Horn/Schunck: Combining Local and Global OpticFlow Methods ANDR´ES BRUHN AND JOACHIM WEICKERT, 2005Horn and Schunck MethoddxdyvufvfufvuEtyxHS)()(),(222∇+∇+++=∫ΩαEuler-Lagrange EquationsHorn and Schunck Method• Global Method • Estimates flow everywhere• Sensitive to noise• Oversmooths the edges510=α610=αFigures from Lucas/Kanade Meets Horn/Schunck: Combining Local and Global OpticFlow Methods ANDR´ES BRUHN AND JOACHIM WEICKERT, 2005Why combine them?• Need dense flow estimate• Robust to noise• Preserve discontinuitiesCombining the two…=1*),( vuJKvuELKρdxdyvufvfufvuE)()(),(222∇+∇+++=∫αdxdyvufvfufvuEtyxHS)()(),(222∇+∇+++=∫ΩαdxdyvuvuJKvuECLG)(1*),(22∇+∇+=∫ΩαρCombined Local Global MethoddxdyvuvuJKvuECLG)(1*),(22∇+∇+=∫ΩαρEuler-Lagrange EquationsAverageErrorStandard DeviationLucas&Kanade4.3(density 35%)Horn&Schunk9.8 16.2Combining local and global4.2 7.7Table: Courtesy - Darya Frolova, Recent progress in optical flowPreserving discontinuities• Gaussian Window does not preserve discontinuities• Solutions–Use bilateral filtering –Use bilateral filtering – Add gradient constancydxdyvuvuJKvuEbilbil)(1*),(22∇+∇+=∫ΩαdxdyffvuvuJKvuEtgrad2122)()(1*),(+Ω∇−∇+∇+∇+=∫βαρBilateral support windowImages: Courtesy, Darya Frolova, Recent progress in optical flowRobust statistics Robust statistics –– simple examplesimple exampleFind “best” representative for the set of numbersmin2→−=∑iixxEL2:min→−=∑iixxEL1:xixiInfluence of xion E:xi → xi+ )mean(ixx=Outliers influence the mostixx −proportional to()∆⋅−+≅xxEEioldnew2)median(ixx=Majority decidesequal for all xi∆+≅oldnewEESlide: Courtesy - Darya Frolova, Recent progress in optical flowCombination of two flow constraintsCombination of two flow constraintsrobust: L1usual: L2 robust regularized()()∫∇−∇+−videowarpedwarpedIIII minαφφ),,( ; )1,,( tyxIItvyuxIIwarped=+++=x robust in presence of outliers– non-smooth: hard to analyze easy to analyze and minimize– sensitive to outliers2x smooth: easy to analyze robust in presence of outliers22ε+xε[A. Bruhn, J. Weickert, 2005] Towards ultimate motion estimation: Combining highest accuracy with real-time performanceSlide: Courtesy - Darya Frolova, Recent progress in optical flowRobust statistics3D Regularization• accounted for spatial regularization• If velocities do not change suddenly with time, can we regularize in time as well?)(22vu ∇+∇αcan we regularize in time as well?3D Regularizationtvyvxvvtuyuxuu∂∂+∂∂+∂∂=∇∂∂+∂∂+∂∂=∇33udxdydtvuvuJKvuETXCLG)(1*),(2323],0[3∇+∇+=∫ΩαρMultiresolution estimationrun iterative estimationwarp & upsample20image Iimage JGaussian pyramid of image 1 Gaussian pyramid of image 2Image 2image 1run iterative estimation...Multi-resolution Lucas KanadeAlgorithmCompute Iterative LK at highest level•For Each Level i•Take flow u(i-1), v(i-1) from level i-1•Upsample the flow to create u*(i), v*(i) matrices of twice resolution for level i.resolution for level i.•Multiply u*(i), v*(i) by 2•Compute Itfrom a block displaced by u*(i), v*(i)•Apply LK to get u’(i), v’(i) (the correction in flow)•Add corrections u’(i), v’(i) to obtain the flow u(i), v(i) at the ithlevel, i.e., u(i)=u*(i)+u’(i), v(i)=v*(i)+v’(i)Comparison of errorsFor Yosemite sequence with cloudsTable: Courtesy - Darya Frolova, Recent progress in optical flowSolving the systemSolving the systemfAu=How to solve?Start with some initial guessand apply some iterative methodinitialu2 components of success:fast convergencegood initial guessand apply some iterative methodRelaxation schemes have smoothingsmoothing property:. . . . . . . . . . . . Relaxation smoothes the errorRelaxation smoothes the errorOnly neighboring pixels are coupled in relaxation schemeIt may take thousands of iterations to propagate information to large distance. . . . . . . . . . . .Relaxation smoothes the error Relaxation smoothes the error ExamplesExamples1D case:2D case:Error of initial guessError after 5 relaxationError after 15 relaxationsIdea: coarser gridIdea: coarser gridOn a coarser grid low frequencies become higherHence, relaxations can be more effective initial grid – fine gridcoarse grid – we take every second pointMultigrid 2Multigrid 2--Level VLevel V--CycleCycle1. Iterate ⇒ error becomes smooth2. Transfer error equation to the coarse 4. Transfer error to the fine level5. Correct the previous solution6. Iterate ⇒ remove interpolation artifacts2. Transfer error equation to the coarse level ⇒ ⇒ ⇒ ⇒ low frequencies become high3. Solve for the error on the coarse level ⇒ good error estimation4. Transfer error to the fine levelmake iteration process faster (on the coarse grid we can effectively minimize the error)obtain better initial guess (solve directly on the coarsest grid) Coarse grid