Image Processing and Computer

Vision

Assignment T6

Jan Hendrik Dithmar

2031259

Group T1: Tue, 14-16 (Sebastian Zimmer)

Assignment T6  Dithmar (2031259)

6.1 Mumford-Shah Cartoon Model

Unfortunately no solution. :-(

6.2 The Method of Bigün et al.

a. Based on

http://mathworld.wolfram.com/GershgorinCircleTheorem.html

I compute the Gershgorin circles.

(i)

λ_{1} = {z ∈ ℝ | |z − 5| ≤ 5} ⇒ [0, 10]
λ_{2} = {z ∈ ℝ | |z − 1| ≤ 3} ⇒ [2, 4]
λ_{3} = {z ∈ ℝ | |z − 1| ≤ 2} ⇒ [1, 3]

After a short calculation you can easily see that the eigenvalues are −1, 1, 7. This leads to rank(J_{ρ}) = 3. Since J_{ρ} is not symmetric where the spatiotemporal structure tensor is, the criterion is not fulfilled in this case.

(ii)

λ_{1} = {z ∈ ℝ | |z − 3| ≤ 2} ⇒ [1, 5]
λ_{2} = {z ∈ ℝ | |z − 6| ≤ 4} ⇒ [2, 10]
λ_{3} = {z ∈ ℝ | |z − 7| ≤ 4} ⇒ [3, 11]

Since all eigenvalues lie in the interval [1, 11], i.e. are ≥ 0, we have rank(J_{ρ}) = 3. Due to the fact that the matrix is symmetric and all eigenvalues are ≥ 0, the requirements for a spatiotemporal structure tensor are fulfilled.

(iii)

λ_{1} = {z ∈ ℝ | |z − 1| ≤ 2} ⇒ [1, 3]
λ_{2} = {z ∈ ℝ | |z − 3| ≤ 1} ⇒ [2, 4]
λ_{3} = {z ∈ ℝ | |z − 5| ≤ 3} ⇒ [2, 8]

Since one of the eigenvalues is negative (because of one negative element in the diagonal), this matrix cannot be a spatiotemporal structure tensor, because the matrix is not positive semidefinite. All eigenvalues are ≠ 0, so rank(J_{ρ}) = 3.

(iv) As one can easily see, rank(J_{ρ}) = 0. Since all eigenvalues are zero, this is not a semitemporal structure tensor.

b. Having three large eigenvalues means that either the grey value assumption is not fulfilled or the flow is not locally constant. Here is the explanation for that: If we have three large eigenvalues, we have a ”jump” also in the temporal direction that does not allow the estimation of a locally constant flow.

6.3 Variational Optic Flow Methods

a.

f_{x}(x, y, z, t)u + f_{y}(x, y, z, t)v + f_{z}(x, y, z, t)w + f_{t}(x, y, z, t) = 0

Since we have one equation with three unknowns and the possible solutions in a point (x, y, z) have to be orthogonal to ∇f = (f_{x}, f_{y}, f_{z})^{⊤}, we have the aperture problem.

b.

E(u, v, w) = ∫_{Ω} ((f_{x}u + f_{y}v + f_{z}w)^{2} + α (|∇u|^{2} + |∇v|^{2} + |∇w|^{2})) dx dy dz

c. To compute the Euler-Lagrange equations, I only have to look at the integrad of

E(u, v, w) = ∫_{Ω} F (x, y, z, u, v, w, u_{x}, u_{y}, u_{z}, v_{x}, v_{y}, v_{z}, w_{x}, w_{y}, w_{z})dx dy dz

which is

F = (f_{x}u + f_{y}v + f_{z}w)^{2} + α(u_{x}^{2} + u_{y}^{2} + u_{z}^{2} + v_{x}^{2} + v_{y}^{2} + v_{z}^{2} + w_{x}^{2} + w_{y}^{2} + w_{z}^{2}).

This leads to the partial derivatives

F_{u} = 2f_{x}(f_{x}u + f_{y}v + f_{z}w)
F_{v} = 2f_{y}(f_{x}u + f_{y}v + f_{z}w)
F_{w} = 2f_{z}(f_{x}u + f_{y}v + f_{z}w)
F_{u_{x}} = 2αu_{x}
F_{u_{y}} = 2αu_{y}
F_{u_{z}} = 2αu_{z}
F_{v_{x}} = 2αv_{x}
F_{v_{y}} = 2αv_{y}
F_{v_{z}} = 2αv_{z}
F_{w_{x}} = 2αw_{x}
F_{w_{y}} = 2αw_{y}
F_{w_{z}} = 2αw_{z}

This yields the Euler-Lagrange equations

Δu − \frac{1}{α}f_{x}(f_{x}u + f_{y}v + f_{z}w + f_{t}) = 0
Δv − \frac{1}{α}f_{y}(f_{x}u + f_{y}v + f_{z}w + f_{t}) = 0
Δw − \frac{1}{α}f_{z}(f_{x}u + f_{y}v + f_{z}w + f_{t}) = 0

with the boundary conditions

n^{⊤}∇u = 0
n^{⊤}∇v = 0
n^{⊤}∇w = 0

where n is the unit normal vector and all equations have been divided by 2α. Let’s approximate the Laplacian similar to the lecture

Δu|_{i} ≈ ∑_{j∈N (i)}(u_{j} − u_{i})

where N (i) are the neighbors of pixel i.

This yields the equations

0 = ∑_{j∈N (i)}(u_{j} − u_{i}) − \frac{1}{α}f_{xi}(f_{xi}u_{i} + f_{yi}v_{i} + f_{zi}w_{i} + f_{ti})

0 = ∑_{j∈N (i)}(v_{j} − v_{i}) − \frac{1}{α}f_{yi}(f_{xi}u_{i} + f_{yi}v_{i} + f_{zi}w_{i} + f_{ti})

0 = ∑_{j∈N (i)}(w_{j} − w_{i}) − \frac{1}{α}f_{zi}(f_{xi}u_{i} + f_{yi}v_{i} + f_{zi}w_{i} + f_{ti})

for all pixel (i = 1, ..., N). ⇒ This system of equations is linear.