236861 Numerical Geometry of Images
Tutorial 2
Calculus of variations II
Guy Rosman
2010
c
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
The Euler-Lagrange equation (reminder)
Given the functional
Z x1
f (u) = F x, u(x), u 0 (x) dx
x0
with F C 3 and all admissible u(x) having fixed boundary values
u(x0 ) = u 0 and u(x1 ) = u 1 .
An extremum of f (u) satisfies the differential equation
d
Fu Fu 0 = 0
dx
with the boundary conditions u(x0 ) = u 0 and u(x1 ) = u 1 .
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Special cases of the E-L equation
If the integrand does not depend on the independent variable x,
Z x1
f (u) = F u(x), u 0 (x) dx,
x0
for a solution of the E-L equation, the first-order differential
equation
d
F u 0 Fu0 = 0,
dx
or
F u 0 Fu 0 = const,
must hold (Beltrami identity).
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Proof of the Beltrami Identity
Using the full derivative of F by x we obtain
dF F 0 F 00 F
= u + 0u +
dx u u x
F 0 dF F F
u = 0 u 00
u dx u x
Multiplying the E-L equation by u 0 we obtain:
F d F
u0 u0 = 0,
u dx u 0
or
F d F
u0 = u0
u dx u 0
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Plugging the obtained identity into the E-L equation, we get:
dF F F F 0
0 u 00 u =0
dx u x |u {z }
dF F F d F
0 u 00 u0 =0
dx u x dx u 0
F dF F d F
+ 0 u 00 u 0 =0
x |dx u {z dx u}0
F d 0 F
+ F u =0
x dx u 0
Using the assumption that F
x = 0 results in
d F
F u0 0 = 0
dx u
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Brachistochrone problem
I Formulation and first attempt to prove was done by Galileo,
1638. Brachistos - shortest. Chronos - time.
I John Bernoulli 1696 solved the problem
and challenged math world (Acta Eroditorium)
Solutions were presented by
- Leibniz (received letter 9/6/1696, sent back solution
16/6/1696)
- Newton - sent an anonymous answer the very night..
x1 x2
y1 A
y2 B
Figure: Brachistochrone
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
p
Let ds = 1 + y 0 2 dx be a length element.
Energy conservation
1 ds 2 m
m mgy E0 = V02 mgy
2 dt
| {z } |{z} 2
potential
kinetic
ds 2 V02
= 2g ( + y ), = y,
dt 2g
Our integral becomes:
Z Z p
dt x2
1 + y 0 2 dx
T = ds = p
ds x1 2g ( + y )
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Problem 1:
Z p
x2
1 + y 0 2 dx
min{ }
x1 y +
Fx = 0 then the Euler -Lagrange equation is:
H = y 0 Fy 0 F = c
02
p
y 1 + y 02
p
1 + y 02 y + y +
1
=p = c
1 + y 02 y +
1 1
p 02
= b>0
1+y y + 2b
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Or, more plainly:
0
( + y )(1 + y 2 ) = 2b (1)
Note: p
1 + y 02
Fy = 6= 0, (2)
( + y )3/2
so we cannot take a shortcut..
Note: = y 0 0 are not extremals of our functional because of
the physical problem we solve (kinetic energy..).
In order to solve ( 1), let us denote
y 0 (x) = tan , < < .
2 2 2 2
2b
= + y = . (3)
1 + y 02
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
2b 2b cos2 ( 2 )
= = (4)
1 + tan2 ( 2 ) cos2 ( 2 ) + sin2 ( 2 )
= b 2 cos2 = b(1 + cos ),
2
or
y = b(1 + cos ) .
dx dx dy 1
= = (b sin )
d dy d (4) tan 2
= b(1 + cos ) (5)
Integrating Eq. 5, we obtain
= x = a + b( + sin ) , .
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Problem 2: (Hyperbolic Geodesics)
Z p
2
1 + y 02
min dx
1 x
y (1) = 0 y (2) = 1
p
1 + y 02
F =
x
F is independent of y , and therefore we use
y0
Fy 0 = c p =c
x 1 + y 02
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
02 0
y = c 2 x 2 (1 + y 2 )
0
y 2 (1 c 2 x 2 ) = c 2 x 2
cx
y0 =
1 c 2x 2
1 c 2x 2
y = + c2
c
1
(y c2 )2 + x 2 = 2
c
1
boundary conditions = c = c2 = 2
5
And the solution is:
(y 2)2 + x 2 = 5
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Problem 3: Constrained maximum
Find a curve y (x) with fixed endpoints y (1) = 0 and perimeter
Z 1 q
S = 1 + y 0 2 dx,
1
which maximizes the area
Z 1
A(y ) = ydx.
1
Solution
Construct the Lagrangian
Z 1 Z 1 q
L(y ) = ydx + 0
1 + y dx S ,
2
1 1
and denote
q
F (x, y , y 0 ) = y + 1 + y 02.
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Problem 3: Constrained maximum (cont.)
The Euler-Lagrange equation
!
d d y 0
0 = Fy 0 Fy = p 1.
dx dx 1 + y 02
Integration w.r.t. x yields
y 0
p = x ,
1 + y 02
where = const. Substitute y 0 = tan :
y0 sin
p = q cos
1 + y 02 sin2
1 + cos2
sin
r
sin cos2
= q cos
= = sin ,
sin2 + cos2 cos 1
cos2
from where
x
sin = .
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Problem 3: Constrained maximum (cont.)
Substituting again
sin sin
y 0 = tan = = p
cos 1 sin2
(x ) (x )
= q = p .
1 (x)
2
2 (x )2
2
Integration w.r.t. x yields (table of integrals or Mathematica)
p
y = 2 (x )2 + ,
or
(x )2 + (y )2 = 2
where = const. The latter equation describes a part of a circle with
radius centered at (, ). The exact values of the constants are
determined using the endpoint conditions and the perimeter constraint.
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Problem 4
Note about the Beltrami identity: it merely states a necessary
condition for an extremum of the functional.
Q: Show that a solution of the Beltrami identity does not have to
solve the Euler Lagrange equation.
A: Look at Z
1 0 2
(u ) u dx
2
and the function u 1, for which the Beltrami identity holds
d
F u 0 Fu 0 =
dx
d 1 0 2
(u ) u u 0 (u 0 ) =
dx2
d 1 0 2
(u ) u = (u 0 )(u 00 ) u 0 = 0,
dx 2
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Problem 4 (Cont.)
and yet,
d
Fu Fu 0 =
dx
d 0
1 (u ) = 1 u 00 = 1.
dx
In fact, according to the E-L equation, extrema of the functional
are of the form
u(x) = x 2 + ax + b
This is physically not very surprising the integrand represents the
kinetic energy T of a mass plus its potential energy V , in 1D.
The resulting functions describe a free-fall behavior, subject to
initial position and velocity. The functional is known as the action
integral, or action.
Hamiltons principle states that the path of a particle (in a system
which conserves the total energy, E = T V ) must be such that
it describes an extremum of the action integral.
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
A practical example:
Optical flow Horn and Schuncks method
Given 2 images, we would like to find a field that translates pixels
from one image to the next
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Optical flow, Horn and Schuncks method (cont.)
In a 1D world, we would look at an image flow field u(x) that
moves pixels from I1 to I2 . We would like to preserve the
brightness between the two images. This is known as the
brightness constancy assumption.
Using 1st order Taylor approximation, we would get:
I1 (x + u) I1 (x) + I1,x u.
Using the brightness constancy assumption, we have
I1,x u + I1 I2 0
.. but this is only approximate, and our images are usually 2D..
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Optical flow, Horn and Schuncks method (cont.)
In a 2D image case, we denote the field at each point as
u(x, y ), v (x, y ). Taylor approximation of I now reads:
I1 (x + u, y + v ) I1 + I1,x u + I1,y v .
The brightness constancy assumption gives us the following
functional on u, v :
Z
(I1,x u + I1,y v + I1 I2 )2 d
.. but this is not enough! We need some way to propagate
information in the field.. Otherwise, the constraint
Ix u + Iy v = It
will not suffice (2 variables, 1 equation).
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Optical flow, Horn and Schuncks method (cont.)
Since using a single constraint is not enough to determine u and
v .. We therefore add regularization to the functional:
Z
(I1,x u + I1,y v + I1 I2 )2 + (|u|2 + |v |2 ) d
Denoting It = I2 I1 , We can write the equation as:
Z
(Ix2 u 2 + Iy2 v 2 + It2 + 2Ix Iy uv + 2Ix It u + 2Ix It v )
d
+(ux2 + uy2 + vx2 + vy2 )
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Optical Flow, Horn and Schuncks method (cont.)
Writing the two Euler-Lagrange equations (for u and v ), we get:
d d
2
(2Ix u + 2Ix Iy v ) + ux + uy = 2Ix It
dx dy
| {z }
u
d d
(2Ix Iy u + 2Iy2 v ) + vx + vy = 2Iy It
dx dy
| {z }
v
We see that this regularization boils down to diffusing the
components u, v of the field.. This is not a coincidence!
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
Optical Flow, Horn and Schuncks method (cont.)
If we add several more tricks, we can obtain a nice result, (after
some work...):
Figure: Optical flow ( taken from A. Bruhn and J. Weickert, IJCV05)
Guy Rosman 236861 - Tutorial 2 - Calculus of Variations II
