Chapter 7 - Variational Optical Flow

Variational methods are a class of approaches in computer vision where the solution we wish to find is given as the minimizer of a so-called energy functional, which is a real-valued function of the unknown object. The twist is that the unknown is typically a function itself, for example the optic flow field on an image domain. Indeed, optic flow was one of the first problems which was solved using a variational method, in a seminal paper by Horn and Schunck which is the main focus of this chapter. Since it is one of the first variational approaches, it is not too complex and can be discussed in detail using mostly fundamental ideas from calculus. To obtain a deeper understanding, we also build the foundations of the theory of variational calculus, which deals with these types of continuous functionals, without going into all the (difficult) details. The central object of interest is the Euler-Lagrange equation, a PDE whose solutions are the locations where the functional gradient is zero and are thus candidates for extrema. We give an elementary approach to solving the PDEs by discretization into a linear problem and subsequent application of the Jacobi method.

Note: this chapter is intended for two weeks, so take your time to digest the details.

Table of contents

Part 1 - The variational approach to optic flow by Horn and Schunck

Slides 1-15

We introduce the variational approach to optical flow by Horn and Schunck as a model example for a so-called variational approach. In these, we solve for the continuous flow field on the whole image domain at once in one global optimization framework. In particular, we do not make rigid assumptions about local constancy anymore such as in Lucas-Kanade, but instead only assume a slowly varying flow field, which is much more realistic. We show how we can cast the desired properties of the solution into an optimization problem on an infinite-dimensional vector space of functions.


Index

00:00 Introduction and chapter overview
02:31 Differences of the approach by Horn and Schunck compared to the previous local methods
07:30 Optional detour: The original paper in the Google scholar contest
11:10 Modeling assumptions of Horn and Schunck
16:30 The basic variational model for optical flow
22:30 Preview: example results, comparison to Lucas-Kanade
24:20 Discussion: key advantages and disadvantages of variational approaches, outlook


Part 2 - An introduction to variational methods

Slides 16-25

We introduce the basic principles of variational methods, together with the most important concept if you are interested in computing a minimizer of variational energies: their Euler-Lagrange equations. They are conceptually similar to setting the gradient to zero, and give a necessary constraint for the location of the minimum. However, in the infinite-dimensional setting, they are partial differential equations, and thus much more complex to solve than just a linear system of equations such as in the approach by Lucas-Kanade. We introduce a key theorem which allows to compute the Euler-Lagrange equations for a certain type of energy, where we integrate a so-called Lagrangian over the domain $\Omega$.


Index

00:00 Introduction to the calculus of variations
02:00 Remarks on the origins and other applications of variational methods
10:28 Continuing with the calculus of variations
12:30 The Euler-Lagrange equations of an energy functional, required form of the energy
17:40 Fitting the approach by Horn and Schunck in to this framework
22:30 What are the Euler-Lagrange equations?
26:00 Applying the theorem to Horn and Schunck's energy to compute the Euler-Lagrange equations
31:30 Discussion of the equations
33:20 Summary and outlook


Derivation of the Euler-Lagrange equations

This section is optional if you are only interesting in practical applications, but I believe highly informative. We derive the Euler-Lagrange equations from basic principles of calculus. A key is the comparison of the infinite-dimensional case to the finite-dimensional settting, which leads to the idea to compute the gradient of a functional via its directional derivatives. We continue with computing the directional derivatives for the type of functional in question, first for a simplified 1D setting, then in the more general case of an arbitrary rectangular domain. The fully general case requires integration by parts in higher dimensions, or the theorem of Gauss, for which we form an intuitive understanding.


Index

00:00 Introduction: review of the setting and what we actually need to show
02:30 Initial simplification of the setting to an easier case
05:40 Review of the finite-dimensional case
12:35 Comparison to the infinite-dimensional case, what do we need to generalize?
19:40 Computing the directional derivative of the functional
27:25 Integration by parts to arrive at the gradient of the functional
34:00 Generalization from the simple case to the actual form in the theorem
39:00 A note on the boundary conditions
41:10 A closer look on integration by parts in higher dimensions: the divergence
49:05 Interpreting the divergece: Gauss' theorem (or the "divergence theorem")
56:15 Obtaining the rule for integration by parts from Gauss' theorem
59:30 Closing the loop: what this means for deriving the Euler-Lagrange equation


Part 3 - Discretization of the Euler-Lagrange equations

Slides 26-34

In order to solve the Euler-Lagrange equations in practice, we need to discretize them, i.e. transfer them to the grid of pixels. This is done by replacing the derivative operators with their discrete counterparts. Since we have a linear system of PDEs, we arrive at a linear system of equations for our unknown flow field. The system matrix is very large and sparse, and it would be inefficient to apply a dense solver, such as the SVD, which we have used before. Instead, we need to rely on iterative schemes, which arrive at a solution by iterating matrix-vector products and other relatively cheap operations. As an example, we introduce the Jacobi method as a simple solver of this type, and apply it to the framework of Horn and Schunck.


Index

00:00 Reminder: the problem we are going to solve, idea of discretization
03:10 Discretization of the Laplace operator with mixed forward/backward differences
13:45 A compact notation of the Laplacian applied in a single pixel
19:37 The discrete form of the Euler-Lagrange equations
25:20 Explicit form as a linear system of equations with a sparse matrix
33:30 Remarks on the size of the system and inapplicability of SVD
36:00 A simple iterative numerical scheme: the Jacobi method
44:40 Application to the discrete system of PDEs from Horn and Schunck
47:20 Final iterative scheme to solve the model by Horn and Schunck
48:40 Example results and outlook

Remarks

32:00 I did not write down the second set of equations starting from row $N+1$ explicitly. Essentially, you get another copy of the first set of equations, but the left block and the right block are interchanged, as the unknowns $u_n$ and $v_n$ change roles.


Part 4 - Extensions and generalizations

Slides 35-45

We discuss improvements to the basic framework of optical flow computation, which address data term, smoothness term and the solver. More robustness can be achieved by replacing the squared norms by something less sensitive to outliers, such as just the norm, or use entirely different matching costs, such as the census transform. This requires different approaches to optimization, as the terms are not differentiable anymore. Improved solvers have to deal in particular with large displacements, which are handled with coarse-to-fine warping schemes. We discuss an award-winning landmark paper by Brox et al. published at ECCV 2004, which incorporates most of the approaches.


Index

00:00 Introduction, ideas for improving data and smoothness term
04:40 Example for an improved matching cost: the census transform
08:30 More ideas for how to improve the smoothness cost
11:00 Improvements of the solver for the partial differential equations
13:45 Illustration of coarse-to-fine warping approaches
18:17 Landmark paper with algorithm covering many of the suggested improvements (Brox et al. ECCV 2004)
23:00 Summary and outlook