Transcript Introduction to the Calculus of Variations and Optical Flow

Introduction to the Calculus of
Variations and Optical Flow
Amir Yavariabdi
Agenda
1.
CALCULUS OFVARIATIONS
 Introduction
 Strong and Weak Extrema
 Mixed Partial Derivatives
 Chain Rule for Several Variables
 Statement of Problems
 Euler-Lagrange and Beltrami Identity
2.
Optical Flow
 Estimating the Partial Derivatives
 Estimating the Laplacian of the Flow Velocities
 Minimization
Introduction
 Calculus of variations is a field of mathematics that deals
with extremizing functionals, as opposed to ordinary
calculus which deals with functions.
 A functional is usually a mapping from a set of functions to
the real numbers and often formed as definite integrals
involving unknown functions and their derivatives.
Weak and Strong Extrema
 In order to define local optimality, we must select a norm.
 There are two natural candidates for the norms:
 Extrema of J with respect to the 0-norm are called strong
extrema and those with respect to the 1-norm are called
weak extrema.
 J: real value of functional defined on v
 v: vector space of functions equipped with a norm
Mixed Partial Derivatives
 Derivative of f(x) at x = a
 For a function of several variable the total derivative of a
function is:
 Mixed Partial Derivative
The Chain Rule
 Suppose f(x) is a differentiable function of x and x=x(t) is
differentiable of t. By the chain rule theorem, the composite
function z(t) is differentiable function of t
 By a chain rule theorem for functions of several variables
 The hypothesis for the chain rule theorem require the
function z = f(x; y) to have continuous partial derivatives and
for x(t) and y(t) to be differentiable.
Statement of Problem
 The arc length of the curve y(x) is given by integral
 If there are
no constraint, the curve which minimizes the
arc-length is the straight line. However, if the curve is
constrained to lie on a surface, then the solution is less
obvious (geodesics).
 It is not obvious what choice of y(x) will result in minimizing
this integral.
Statement of Problem
 the integrals can be viewed as special kinds of functions,
functions whose inputs are functions and whose outputs are
real numbers.
 F is actually called a functional and f is an ordinary function
of the variables x, y and y’.
 Suppose the functional F obtains a minimum (or maximum)
value. How do we determine the curve y(x) which produces
such a minimum (maximum) value for F?
Euler- Lagrange Equation
 If y(x) is a curve which minimizes the functional. then the
following differential equation must be satisfied:
 The proof of above equation relies on three things:
1)
2)
3)
The Leibniz rule
Integration by parts
Lemma 1
 Let M(x) be a continuous function on the interval [a; b]
Suppose that for any continuous function h(x) with h(a) =
h(b) = 0 we have
Then M(x) is identically zero3 on [a; b].
Beltrami Identity
 Often in applications, the function f which appears in the
integrand does not depend directly on the variable x
 Beltrami Identity:
Optical Flow
 The Horn–Schunck method of estimating optical flow is a
global method which introduces a global constraint
of smoothness to solve the aperture problem.
 Steps:
1.
2.
3.
Estimating the Partial Derivatives
Estimating the Laplacian of the Flow Velocities
Minimization
Estimating Partial Derivatives
 While there are many formulas for
approximate differentiation. They used
a set which gives them an estimate of
Ex, Ey and Et at a point in the centre of
a cube formed by eight measure.
Estimating the Laplacian of the Flow
Velocities
 The local average of u and v are defined as follows
Minimizing
 The flow is formulated as a global energy functional which
is then sought to be minimized. This function is given for
two-dimensional image streams as:
 V [u(x,y), v(x,y)] is the optical flow vector, and the
parameter α is a regularization constant. Larger values
of α lead to a smoother flow. This functional can be
minimized by solving the associated Euler–Lagrange
equations.
where L is the integrand of the energy expression
Minimizing
 where subscripts again denote partial differentiation and
denotes the Laplace operator.
where
is a weighted average of u calculated in a
neighbourhood around the pixel at location (x,y).
Minimizing
 which is linear in u and v and may be solved for each pixel
in the image. However, since the solution depends on the
neighbouring values of the flow field, it must be repeated
once the neighbours have been updated. The following
iterative scheme is derived:
 where the superscript k+1 denotes the next iteration, which
is to be calculated and k is the last calculated result.
Advantage and Disadvantage
 the Horn–Schunck algorithm include that it yields a high
density of flow vectors.
 it is more sensitive to noise than local methods.