0
1
Problem 1 Personal Information (1 credit)
Please enter your matriculation number with leading zero. (1 credit(s))
– Page 2 / 20 –
Problem 2 MATLAB Operations (14 credits)
Let ?1?A?2? and ?3?B?4? be given, where ?5?size(A) = [m,n]?6? and ?7?size(B) = [n,p]?8? . Assume ?9?m,n,p?10? are mutually
different dimensions.
a) How can we compute ?11?norm(A(:))*norm(A(:))?12? ? (2 credit(s))
?15?sum(sum(A’*A))?16?
?19?trace(A’.*A)?20?
?21?sum(sum(A*A’))?22?
?23?trace(A’*A)?24?
The expression will lead to an error
?13?trace(A.*A)?14?
?17?trace(A.*A’)?18?
b) How was ?25?C?26? obtained if ?27?size(C) = [m*p,n*n]?28? ? (2 credit(s))
?41?C = kron(B,A’)?42?
?33?C = kron(A’,B)?34?
?39?C = kron(B,A)’?40?
?29?C = kron(A,B)?30?
?37?C = kron(B,A)?38?
?31?C = kron(A,B)’?32?
?35?C = kron(A’,B)’?36?
c) What is the dimension of the output of ?43?kron(A(:),B(:)’)?44? ? (2 credit(s))
?45?[m*n, n*p]?46?
?49?[m*m*n*p, 1]?50?
?47?[m*n*n*p, 1]?48?
?57?[m*n, m*p]?58?
?53?[m*n*p*p, 1]?54?
?55?[m*p, n*n]?56?
?51?[m*n*p*p, 1]?52?
The expression will lead to an error
?59?[n*p, m*n]?60?
— The problem continues on the next page —
– Page 3 / 20 –
d) What is the dimension of the output of ?61?kron(A(:),B(:))?62? ? (2 credit(s))
?77?[n*p, m*n]?78?
?73?[m*p, n*n]?74?
?75?[m*n, m*p]?76?
?65?[m*m*n*p, 1]?66?
?71?[m*n, n*p]?72?
?67?[m*n*p*p, 1]?68?
?69?[m*n*p*p, 1]?70?
The expression will lead to an error
?63?[m*n*n*p, 1]?64?
e) How many scalar multiplication operations are necessary to compute ?79?A(:)*B(:)’?80? for dense ?81?A,B?82? ?
(2 credit(s))
?85?m*m*n*p?86?
The expression will lead to an error
?91?2*m*n*p?92?
?83?m*n*n*p?84?
?89?m*n*p*p?90?
?87?m*n*p*p?88?
?95?2*m*m*n*p?96?
?93?m*m*p*p?94?
f) How many scalar multiplication operations are necessary to compute ?97?A.*B?98? for dense ?99?A,B?100? ? (2 credit(s))
The expression will lead to an error
?111?m*m*p*p?112?
?113?2*m*m*n*p?114?
?101?m*n*n*p?102?
?109?2*m*n*p?110?
?107?m*n*p*p?108?
?105?m*n*p*p?106?
?103?m*m*n*p?104?
g) Let ?115?P = kron(eye(n),eye(m))?116? . What does ?117?kron(A(:),A(:))’*P(:)?118? compute? (2 credit(s))
?125?sum(sum(A*A’))?126?
?127?trace(A*A’)?128?
The expression will lead to an error
?119?sum(sum(A’*A))?120?
?123?trace(A’.*A)?124?
?121?trace(A.*A’)?122?
– Page 4 / 20 –
Problem 3 Matrix Algebra in MATLAB (12 credits)
a) Write down a symmetric matrix ?129?Q?130? of size ?131?[2,2]?132? such that ?133?Q’*Q = eye(2)?134? . (2 credit(s))
b) Write down a symmetric orthogonal matrix ?135?Q?136? of size ?137?[2,2]?138? with negative determinant. (2 credit(s))
c) Let ?139?[U,S,V] = svd(D)?140? . Which of the following holds for any choice of ?141?D?142? with ?143?size(D) = [n,n]?144? (up to
numerical precision)? (2 credit(s))
?155?U*V’*det(U*V’)?156? is an element of SO(n)
?153?expm(U*V’)?154? is an element of SO(n)
?151?U*V’?152? is an element of SE(n)
?149?U*V?150? is an element of SO(n)
?145?U*det(U)?146? and ?147?V?148? are both elements of SO(n)
None
d) Let ?157?A?158? with ?159?size(A) = [n,n]?160? and ?161?b?162? with ?163?size(b) = [n,1]?164? be given. Which of the following statements
is true in general (up to numerical precision)? (2 credit(s))
?179?x = pinv(A)*b?180? is the only solution to ?181?A*x = b?182? if ?183?det(A) ~= 0?184?
?171?pinv(A)*b?172? is equal to ?173?A\b?174?
?165?x = pinv(A)*b?166? is the only solution to ?167?A*x = b?168? if ?169?det(A) == 0?170?
None
?175?x = A\b?176? gives a solution to ?177?A*x = b?178?
— The problem continues on the next page —
0
1
2
0
1
2
– Page 5 / 20 –
e) Let ?185?[U,S,V] = svd(E)?186? . Which of the following holds for any choice of ?187?E?188? with ?189?size(E) = [3,3]?190? (up to
numerical precision)? (2 credit(s))
?199?expm(U*V’)?200? is an element of SO(3)
?197?U*V’?198? is an element of SE(3)
?195?U*V?196? is an element of SO(3)
?191?U*det(U)?192? and ?193?V?194? are both elements of SO(3)
None
?201?U*V’*det(U*V’)?202? is an element of SO(3)
f) Let ?203?[x,y] = eig(rand(3))?204? . Which of the following holds for any random seed? (2 credit(s))
None
?205?x, y?206? are real matrices
?209?x, y?210? are symmetric matrices
?207?x, y?208? are orthogonal matrices
?211?x, y?212? have orthogonal columns
– Page 6 / 20 –
Problem 4 Definitions (15 credits)
a) Let A œ Rn◊n, b œ Rn and c œ Rn with c = 0. Consider the set that contains all matrices of the form
3
A b
c
€ 1
4
.
We denote ¶ as the matrix multiplication. Is (G, ¶) a group? If so, give the name of this group. If no, why
not? (2 credit(s))
b) Let M = [c1, … , cn] œ Rm◊n. State the name of the following quantity: dim(span({c1, … , cn})). (2 credit(s))
c) Let r : Rn æ Rm and Jr : Rn æ Rm◊n be its Jacobian. We consider the following optimization problem
min
xœRn
1
2
Îr(x)Î2 .
State the name of the algorithm whose update is given by:
x
(k+1) = argmin
xœRn
1
2
(x ≠ x (k ))€J€
r
Jr (x ≠ x (k )) + (x ≠ x (k ))€J€r r , where r and Jr are evaluated at x
(k ). (2 credit(s))
d) Let E = {A œ Rn◊n | A€ = A}. What is the dimension of this space? (2 credit(s))
e) Let A œ Rm◊n, b œ range(A ) and let S = {x œ Rn | Ax = b}. Write down (without justification) the solution of
x
ú = argmin
xœS
ÎxÎ2 .
(2 credit(s))
f) Let L : Rn æ Rn such that ’x œ Rn, L (x) = Ax where A œ Rn◊n. Let {ei}i be the canonical basis of Rn and
{eÕ
i
}i be another basis of Rn. We define B = P≠1AP where P =
#
e
Õ
1, … , e
Õ
n
$
. Describe briefly how B is related to
L . (2 credit(s))
g) Tick the wrong statement. (1 credit(s))
SL(n) µ O(n)
E(n) µ A(n)
SO(n) µ O(n)
SE(n) µ GL(n + 1)
— The problem continues on the next page —
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
– Page 7 / 20 –
h) Let R = (rij) œ SO(3), which represents a rotation by an angle ◊ œ (0, fi) around an axis spanned by a unitary
vector ų. Which of the following corresponds to the correct expressions of theta and ų? (2 credit(s))
◊ = cos
3
trace(R) ≠ 1
2
4
and ų =
1
sin(◊)
(r32 ≠ r23, r13 ≠ r31, r21 ≠ r12)€
◊ = cos≠1
3
trace(R) ≠ 1
2
4
and ų =
1
sin(◊)
(r32 ≠ r23, r21 ≠ r12, r13 ≠ r31)€
◊ = cos≠1
3
trace(R)
2
4
and ų =
1
2 sin(◊)
(r32 ≠ r23, r21 ≠ r12, r13 ≠ r31)€
◊ = cos≠1
3
trace(R) + 1
2
4
and ų =
1
2 sin(◊)
(r32 + r23, r13 + r31, r21 + r12)
€
◊ = cos≠1
3
trace(R) ≠ 1
2
4
and ų =
1
2 sin(◊)
(r32 ≠ r23, r13 ≠ r31, r21 ≠ r12)€
– Page 8 / 20 –
Problem 5 Linear Algebra I (8 credits)
a) Let USV€ be the singular value decomposition of A œ Rn◊n, and let XLX€ denote the eigenvalue decomposition
of AA€. How can you compute X and L from U, S, V? Write down the solution as well as a derivation. (4 credit(s))
b) Show that if Y œ R3◊3 is a skew-symmetric matrix, then z€Yz = 0 for every z œ R3. (4 credit(s))
0
1
2
3
4
0
1
2
3
4
– Page 9 / 20 –
0
1
2
0
1
0
1
2
0
1
2
0
1
2
3
Problem 6 Linear Algebra II (10 credits)
The Euclidean projection Rú of the matrix A œ Rn◊n onto the set SO(n) = {Q œ Rn◊n | Q€Q = In◊n, det(Q) = 1} is
defined as
R
ú = argmin
RœSO(n)
ÎA ≠ RÎf ,
i.e. we seek a minimiser Rú of ÎA≠RÎf subject to R œ SO(n). It can be computed as Rú = U diag(1, … , 1, det(UV€))V€
for U⌃V€ being the singular value decomposition of A with ⌃ = diag(‡1, … , ‡n) where ‡1 Ø ‡2 Ø … Ø ‡n.
a) What is the difference between the sets O(n) and SO(n)? (2 credit(s))
b) How many different values can the inner term diag(1, … , 1, det(UV€)) take? (1 credit(s))
c) Explain your answer in b) and list the cases. (2 credit(s))
d) Explain the effect of the different cases identified in c) on U diag(1, … , 1, det(UV€))V€. (2 credit(s))
e) Explain why S = U diag(det(UV€), 1, … , 1)V€ does not necessarily compute a Euclidean projection onto SO(n)
for general A? (3 credit(s))
– Page 10 / 20 –
Problem 7 Image Formation (12 credits)
A 3D point is given in the camera coordinate frame by P = (≠1, 1, 8)€ . The intrinsic parameter matrix K is given by
Q
a
640 0 320
0 480 240
0 0 1
R
b . (1)
Calculate the pixel-position of the projected point in the image and tick the correct answer.
a) What is the value of u? (2 credit(s))
u = 310
u = 240
u = 150
u = 550
b) What is the value of v? (2 credit(s))
v = 130
v = 300
v = 490
v = 910
Given is the transform
gCamToWorld =
Q
cc
a
0 0 1 4
≠1 0 0 2
0 ≠1 0 3
0 0 0 1
R
dd
b œ SE(3)
that transforms a point given in camera coordinates X to the point given in world coordinates X0 = gCamToWorldX .
Consider the point P0 = (8, ≠1, 1)€ given in world coordinates. Considering the transform gCamToWorld and the
intrinsic matrix from Equation 1, calculate the pixel-position of the projected point in the image.
c) Explain how you calculate the pixel-position of the projected point in the image. Do not give numeric values, only
the derivation counts. (2 credit(s))
d) What is the value of u? (3 credit(s))
u = 800
u = 120
u = 230
u = 210
— The problem continues on the next page —
0
1
2
– Page 11 / 20 –
e) What is the value of v? (3 credit(s))
v = 480
v = 400
v = 160
v = 830
– Page 12 / 20 –
Problem 8 Lucas-Kanade Algorithm: The Structure Tensor (14 credits)
The black and white boxes in the image below are annotations used within this exercise and were not present in the
image used to calculate the structure tensors.
In Equation 2 you are given the eigenvalues ⁄(1)
i
, … , ⁄(5)
i
and eigenvectors v (1)
i
, … , v (5)
i
for five structure tensors
M
(1), … , M(5). For each tensor you have to choose the corresponding image patch A – E. The neighborhood used
to compute the structure tensor W (x) is set to be the same as the inside of the corresponding annotation box.
A uniform weight is used throughout the window. There is a one-to-one correspondence between tensors and
patches. (To obtain readable numbers, the values below are scaled and rounded.)
M
(1) : ⁄(1)1 = 1.38 , ⁄
(1)
2 = 0.86 v
(1)
1 = (≠0.08, 1.00)
€ , v (1)2 = (≠1.00, ≠0.08)
€
M
(2) : ⁄(2)1 = 0.86 , ⁄
(2)
2 = 0.05 v
(2)
1 = ( 0.04, 1.00)
€ , v (2)2 = (≠1.00, 0.04)
€
M
(3) : ⁄(3)1 = 0.01 , ⁄
(3)
2 = 0.01 v
(3)
1 = (≠1.00, 0.06)
€ , v (3)2 = (≠0.06, ≠1.00)
€
M
(4) : ⁄(4)1 = 0.40 , ⁄
(4)
2 = 0.06 v
(4)
1 = ( 0.44, 0.90)
€ , v (4)2 = (≠0.90, 0.44)
€
M
(5) : ⁄(5)1 = 0.55 , ⁄
(5)
2 = 0.04 v
(5)
1 = (≠1.00, 0.03)
€ , v (5)2 = (≠0.03, ≠1.00)
€
(2)
a) Choose the correct image patch for the structure tensor M(1) and explain your choice. (4 credit(s))
b) Choose the correct image patch for the structure tensor M(2) and explain your choice. (4 credit(s))
— The problem continues on the next page —
0
1
2
3
4
0
1
2
3
4
– Page 13 / 20 –
c) Choose the correct image patch for the structure tensor M(3). (2 credit(s))
A
E
B
D
C
d) Choose the correct image patch for the structure tensor M(4). (2 credit(s))
C
E
B
D
A
e) Choose the correct image patch for the structure tensor M(5). (2 credit(s))
D
B
C
E
A
– Page 14 / 20 –
Problem 9 3D Geometry I (8 credits)
a) We assume that there are three cameras whose rotations and intrinsics are all the identity matrix I3◊3. Let
(Fij)16i