Title Page
Contents
JJ II
J I
Page1of23
Go Back
Full Screen
Sharat Chandran
Computer Science & Engineering Department, Indian Institute of Technology,
Title Page
Contents
JJ II
J I
Page2of23
Go Back
Full Screen
Close
The Top Ten Algorithms of the Century
•
Metropolis Algorithm for Monte Carlo•
Simplex Method for Linear Programming•
Krylov Subspace Iteration Methods•
The Decompositional Ap- proach to Matrix Computa- tions•
QR Algorithm for Computing Eigenvalues•
The Fortran Optimizing Com- piler•
Quicksort Algorithm for Sort- ing•
Fast Fourier Transform•
Integer Relation Detection•
Fast Multipole MethodTitle Page
Contents
JJ II
J I
Page3of23
Go Back
Full Screen
Overview
1. Sample problems from computer vision (fade out computer vision gurus)
•
The problem of shape•
The problem of obtaining 3D information•
The problem of motion2. The beauty of mathematics (fade out math gurus)
•
The method of the calculus of variations•
Allied mathematical methods: Singular Value Decomposition, and the Method of Lagrange Multipliers3. Sample solution to problems posed (or how computer scientists teach/cheat)
Title Page
Contents
JJ II
J I
Page4of23
Go Back
Full Screen
Close
Shape
•
When placed out of context, images can be quite involved•
What you get is not what you see (WYGINWYS)•
What you want to compute: A contour (useful for obtaining properties such as size)•
Key mathematical concept:parametric curve
x(s), y(s)
Idealized image
Title Page
Contents
JJ II
J I
Page5of23
Go Back
Full Screen
Motion
•
Optical flow is an intensity- based approximation to image motion from sequential time- ordered images•
Key mathematical concept:Two functions:
u(x, y)
andv(x, y)
•
What does it look like?•
How do we compute optical flow?Title Page
Contents
JJ II
J I
Page6of23
Go Back
Full Screen
Close
Application of Optical Flow
A short video segmentSpecifications tohelp.
Title Page
Contents
JJ II
J I
Page7of23
Go Back
Full Screen
Two Problems
•
Determine the equation of the curve joining two points(x
1, y
1)
and(x
2, y
2)
on the plane such that the length of the curve joining them is minimum(x1, y1)
(x2, y2)
•
Goal: Prove that your answer is correct•
Similar problem: Determine the equation of the support so that a ball placed at(x
1, y
1)
reaches (due to gravity)(x
2, y
2)
in the least possible timeTitle Page
Contents
JJ II
J I
Page8of23
Go Back
Full Screen
Close
Functions and Functionals
•
Differential segment length is( dx
2+ dy
2)
1/2 wheredx
anddy
are infinitesimal lengths in the x and y directions along the curve.•
Therefore the length of the curve joining the two end points(x
1, y
1)
and(x
2, y
2)
isJ =
Z
x2 x1p (1 + y
0) dx
=
Z
x2x1
F (x, y, y
0) dx
•
For the first problem, what should the functiony
be so thatJ
is mini- mized?•
Compare: Findx
0 such thaty = f (x)
is minimum.• J
is a functional, a quantity that depends on functions rather than depen- dent variables.Title Page
Contents
JJ II
J I
Page9of23
Go Back
Full Screen
Solution to the Shortest Length Problem
•
The Euler-Lagrange equation is a necessary condition for minimisingJ F
y− d
dx F
y0= 0
(1)•
In our problem,F = p
1 + y
0. Applying Equation 1 we getd
dx ( y
0√ 1 + y
0) = 0
•
Solution:y
0 is a constant.•
The shortest distance curve is a straight line.Title Page
Contents
JJ II
J I
Page10of23
Go Back
Full Screen
Close
Detour: Why the Euler equation
• J = R
x2x1
F (x, f, f
0) dx
with boundary conditionsf (x
1) = f
1 andf (x
2) = f
2.•
Letη(x)
be a test function. Deformf
byη(x)
. Then,dJ/ d = 0
at the “right” place.•
This is true for all test functionsη(x)
. The boundary conditions assertη(x
1) = η(x
2) = 0
•
Iff (x)
is replaced byf (x) + η(x)
thenf
0(x)
will be replaced byf
0(x) + η
0(x)
.•
The integral then becomesJ =
Z
x2 x1F (x, f + η, f
0+ η
0) dx
Title Page
Contents
JJ II
J I
Page11of23
Go Back
Full Screen
Detour: Why the Euler equation
•
IfF
is differentiable, expand the integrand in a Taylor series•
Differentiate with respect to and set to zero•
Apply integration by parts to getZ
x2x1
η
0(x)F
f0dx = [η(x)F
f0]
xx21− Z
x2x1
η (x) d(F
f) dx dx,
•
The first term is zero due to the boundary conditions•
HenceZ
x2x1
η(x)(F
f− dF
f0dx )dx = 0
Title Page
Contents
JJ II
J I
Page12of23
Go Back
Full Screen
Close
Bottom Line Euler Equations
•
Various generalizations are possible – Higher order derivatives:J = R
x2x1
F (x, f, f
0, f
00, ...)dx
– Integrand may depend on several functions instead of only one – Finding functions that have two independent variables
J = Z Z
F (x, y, f, f
x, f
y)dxdy
•
The bottom lineFunction to optimize The Euler-Lagrange equations
R F (x, u
x)dx F
u−
dxdF
ux = 0R F (x, u
x, u
xx)dx F
u−
dxdF
ux−
dxd22F
uxx = 0R F (x, u
x, v
x)dx F
u−
dxdF
ux = 0F
v−
dxdF
vx = 0R R F (x, y, u
x, u
y)dxdy F
u−
dxdF
ux−
dydF
uy = 0Title Page
Contents
JJ II
J I
Page13of23
Go Back
Full Screen
The Snake Formulation
•
Start with any old curve (a “snake”).Mathematically deform it to be the de- sired shape (based on image data).
•
Curve isv(s) = (x(s), y(s))
. Define en- ergy of the curve to beE(v(s)) = Z
10
E
snake(v(s)) ds
(2) whereE
snake= E
int+ E
ext•
Find the curve that minimizes Equation 2Remember, actual im- age is not so clean!
Title Page
Contents
JJ II
J I
Page14of23
Go Back
Full Screen
Close
More on Formulation
•
The energy functional is given byE = R
10
(E
int(v(s)) + E
img(v(s)) + E
con(v(s))) ds
• E
int= (α(s) | v
s(s) |
2+ β(s) | v
ss(s) |
2)/2
• E
con= − k(v(s) − x) ¯
2• E
img= w
lineE
line(v(s)) + w
edgeE
edge(v(s)) + w
termE
term(v(s))
– Line energy isE
line(v(s)) = I (x, y)
– Edge energy is
E
edge(v(s)) = − |∇I (x, y) |
2Title Page
Contents
JJ II
J I
Page15of23
Go Back
Full Screen
Applying Euler-Lagrange to Snakes
We minimizeJ
1= Z
(α(s)x
2s+ β (s)x
2ss)/2 + E
x(s)ds = Z
X (s, x, x
0, x
00)ds
andJ
2= Z
(α(s)y
s2+ β (s)y
2ss)/2 + E
y(s)ds = Z
Y (s, y, y
0, y
00)ds
ForX (s, x, x
0, x
00)
the Euler equation isX
x− d
ds X
x0+ d
2ds
2X
x00= 0
Title Page
Contents
JJ II
J I
Page16of23
Go Back
Full Screen
Close
More on Application
• X
x=
∂E∂s,X
x0= α(s)x
0(s)
, andX
x00= β (s)x
00(s)
– dsdX
x0= α
0x
0+ αx
00 and– dsd
(X
00(s)) = β
0x
00+ βx
000 and– dsd22
(X
00(s)) = β
00x
00+ 2β
0x
000+ βx
0000•
For purpose of illustration use only two terms: ∂E∂s− α
0x
0− αx
00= 0
•
Numerically approximating we have – ∂E∂x' E
i+1− E
i at location i –α
0(s) ' α
i+1− α
i–
x
0(s) ' x
i+1− x
i–
α
0x
0= (α
i+1− α
i)(x
i+1− x
i) = (α
i+1− α
i)x
i+1− (α
i+1− α
i)x
i –x
00(s) ' x
i+1− 2x
i+ x
i−1Title Page
Contents
JJ II
J I
Page17of23
Go Back
Full Screen
Reducing Snakes To A Matrix Equation
− 1 1 . . . 0 0 − 1 . . . 0
... ... . . . ...0 0 . . . − 1
E
1E
2 ...E
n
−
− (α
2− α
1) (α
2− α
1) 0 . . . 0 0 − (α
3− α
2) (α
3− α
2) . . . 0
... ... ... . . . ...
0 0 0 . . . − (α
n+1− α
n)
x
1x
2 ...x
n
−
α
1α
2 ...α
n
T
− 2 1 0 . . . 0 0 1 − 2 1 . . . 0 0
... ... ... ... ... ...0 0 0 . . . − 2 1
x
1x
2 ...x
n
= 0
This can be written asAx = B
, and solved using SVD.Title Page
Contents
JJ II
J I
Page18of23
Go Back
Full Screen
Close
The Method of Lagrange Multipliers
Minimize a functionf (x, y)
subject tog(x, y) = 0
.•
For example, find a point on the linex sin θ − y cos θ + p = 0
closest to origin•
That is, minimizex
2 +y
2 subject to the given constraint.In MOLM, we generate a new function
E = f + λg
and set the partial derivatives with respect tox
,y
andλ
to zero.In the example
• 2x + λ sin θ = 0
• 2y + λ cos θ = 0
• x sin θ − y cos θ + p = 0
The solution is the obvious one
• x = − p sin θ
• y = +p cos θ
The method can be generalized to larger number of constraints.Title Page
Contents
JJ II
J I
Page19of23
Go Back
Full Screen
Formulation for Motion
•
LetE(x, y, t)
be the intensity value at point(x, y)
in the image•
Due to motion, let this point correspond to a point(x + δx, y + δy )
at time instancet + δt
•
Key assumption:E(x, y, t) = E(x + δx, y + δy, t + δt)
•
Two parts to determineu(x, y)
andv (x, y)
– Use Taylor’s theorem to get
E
xu + E
yv + E
t= 0
– Introduce a smoothness constraint:
f (u, v, u
x, v
x, u
y, v
y) = u
x2+ u
y2+ v
x2+ v
y2•
Using MOLM we have a functional that needs to be minimizedZ Z
f (u, v, u
x, v
x, u
y, v
y) + λg(u, v, t)
2dxdy
Title Page
Contents
JJ II
J I
Page20of23
Go Back
Full Screen
Close
Applying Euler-Lagrange for Optical Flow
•
We haveF
u−
∂x∂F
ux−
∂y∂F
uy= 0 F
v−
∂x∂F
vx−
∂y∂F
vy= 0
•
Applying these we getF
u= 2λE
x(E
xu + E
yv + E
t)
F
ux= 2u
x, ∂x∂F
ux= 2u
xxF
uy= 2u
y, ∂y∂F
uy= 2u
yy•
AndF
v= 2λE
x(E
xv + E
yv + E
t)
F
vx= 2v
x, ∂x∂F
vx= 2v
xxF
vy= 2v
y, ∂y∂F
vy= 2v
yy•
This implies a coupled system of equations∆
2u = λ(E
xu + E
yv + E
t)E
x∆
2v = λ(E
xu + E
yv + E
t)E
yTitle Page
Contents
JJ II
J I
Page21of23
Go Back
Full Screen
Solution using Euler Lagrange
Discretizing we have• u
k,l,u
k+1,lu
k,l+1u
k−1,lu
k,l−1:u
component of the velocity at points(k, l)
,(k + 1, l)
,(k, l + 1)
,(k − 1, l)
and(k, l − 1)
respectively.• v
k,l,v
k+1,lv
k,l+1v
k−1,lv
k,l−1:v
component of the velocity at points(k, l)
,(k + 1, l)
,(k, l + 1)
,(k − 1, l)
and(k, l − 1)
respectively.u
k,l= u
k,l− λE
xE
t1 + ˜ λE
x2− v
k,lE
xE
t1 + ˜ λE
x2v
k,l= v
k,l− λE
xE
t1 + ˜ λE
x2− u
k,lE
xE
t1 + ˜ λE
x2Title Page
Contents
JJ II
J I
Page22of23
Go Back
Full Screen
Close
Uses of Euler Lagrange
P roblem Regularization principle
Contours R
Esnake(v(s))ds Area based Optical f low R
[(ux2
+uy2
+vx2
+vy2
) +λ(Exu+Eyv+it)2)]dxdy
Edge detection R
[(Sf−i)2+λ(fxx)2]dx Contour based Optical f low R
[(V ·N−VN)2+λ(δVδx)2] Surf ace reconstruction R
[(S·f−d2+λ(fxx+ 2fxy2
+fyy2
)]dxdy Spatiotemporal approximation R
[(S·f−i)2+λ(∇f·V +f t)2]dxdydt Colour kIy−Axk2+λkP zk2
Shape f rom shading R
[(E−R(f, g))2+λ(fx2
+fy2
+gx2
+gy2
)]dxdy
Stereo R
{[∇2G∗(L(x, y)−R(x+d(x, y), y))]2+λ(∇d)2}dxdy
Title Page
Contents
JJ II
J I
Page23of23
Go Back
Full Screen
