CS549-Homework 7 Solved

1.Singular Value Decomposition (4 pts): This is an important tool that allows us to solve systems of equations 𝐴𝑥⃗ ≈ ⃗0⃗,|𝑥⃗| = 1. This is useful in camera calibration, where we get such a system of equations and want a non-zero parameter vector 𝑥⃗. See Szeliski for an introduction to SVD.

You can think of the SVD as follows:

It takes the component of input 𝑥⃗ in the 𝑢1 direction, scales it by 𝜎1 and outputs it in the 𝑣1
Repeat for all 𝑢𝑖, 𝜎𝑖, and 𝑣𝑖.
The output vector is the sum of all the contributions
 

Suppose that 2×2 matrix M has singular value decomposition
𝑈 ]]
Without computing M, predict the value of 𝑀𝑥⃗ for 𝑥⃗  and 𝑥⃗  based on the SVD properties. Hint: Note that in both cases 𝑉𝑇𝑥⃗ has a simple form, so does

𝐷𝑉𝑇𝑥⃗, and finally, so does 𝑈𝐷𝑉𝑇𝑥⃗. Now compute M and use it to verify 𝑀[1] and

1

1 .

                         𝑀[      ]

−1
 

Let matrix 𝑁 have singular value decomposition 𝑁 = 𝑈𝐷𝑉𝑇. Show that matrix 𝑁𝑇𝑁 has SVD 𝑁𝑇𝑁 = 𝑉𝐷2𝑉𝑇.
 

Camera Calibration (10 pts): One restriction in camera calibration is that the world points chosen must not lie in a single plane, that is, they cannot be co-planar, otherwise calibration will fail. To see this, suppose that there are K world points 𝑥⃗𝑖𝑊,1 ≤ 𝑖 ≤ 𝐾. We know that we need at least 6 points for calibration, 𝐾. Consider what happens if all world points lie in a single plane represented by 𝑝̃ (𝑎,𝑏,𝑐,𝑑), defined by 𝑥̃𝑊  (Szeliski, eqn.  2.7). 
 

                                             Plane containing 𝑥⃗𝑖𝑊

 

The calibration equation is given by 𝐴𝑚⃗⃗⃗ = ⃗0⃗, written out as

                         𝑥𝑊             𝑦𝑊 𝑧𝑊                     𝑦𝑊 𝑥1𝑃𝑧1𝑊 𝑥 𝑚

𝑦𝑊 𝑦1𝑃𝑧1𝑊 𝑦

                                                                                                                           𝑦𝐾𝑊 𝑦𝐾𝑃𝑧𝐾𝑊 𝑦𝐾𝑃] 𝑚

 

Ideally, there should be a single vector 𝑚⃗⃗⃗ such that 𝐴𝑚⃗⃗⃗  (or ).  This is the 𝑚⃗⃗⃗ that we hope to find through the singular value decomposition of 𝐴. The key concept here is the rank of a matrix, which is the number of independent rows, also the number of independent columns. For this 𝑚⃗⃗⃗ to exist and be unique, 𝐴 must have rank = 11 (or 12 with a very small value for the smallest singular value 𝜎12.  Show that if all world points are co-planar, then 𝐴 cannot have rank greater than 9 by finding 3 independent non-zero vectors 𝑚⃗⃗⃗ such that

𝐴𝑚⃗⃗⃗ = ⃗0⃗. (These independent vectors establish that the nullspace of 𝐴 has rank at least 3; hence 𝐴’s rank cannot exceed 12-3=9.) In this case, it is not possible to find a unique 𝑚⃗⃗⃗ such that 𝐴𝑚⃗⃗⃗ = ⃗0⃗ and the calibration procedure fails.

Hint: The non-zero vectors 𝑚⃗⃗⃗ are mostly 0s. Use the fact that if all world points are coplanar, then 𝑥̃𝑖𝑊 . 

 

Focus of Expansion (8 pts): Suppose that the viewer (camera) is moving. We can model this in the imaging equations as
2

𝐶 = 𝑅𝑋⃗𝑊 +𝑇⃗⃗ and 𝑋⃗𝐼 |𝑓⃗| 𝑋⃗𝐶

𝑋⃗
𝑓⃗𝑋⃗𝐶

by letting R and 𝑇⃗⃗ depend on time, 𝑅 . Assume that the camera is

      translating with velocity 𝑉⃗⃗𝐶 𝑑 𝑇⃗⃗ and that there is no rotation, 𝑑 𝑅(𝑡) = 0 . As we know

𝑑𝑡𝑑𝑡

from experience, points in the image will seem to move. As we saw in class, image points will appear to move with velocity

                                                               𝐼                                  𝑑 𝑋⃗𝐼(𝑋⃗𝐼 ×𝑉⃗⃗𝐶)×𝑓⃗).

𝑉⃗⃗

                                                                       𝑑𝑡               𝑓⃗𝑋⃗𝐶
The Focus of Expansion (FOE) is the point in the image toward which the camera appears to be moving, given by the projection of 𝑉⃗⃗𝐶 into the image.  That is,  

                                                                                         𝐼                       |𝑓⃗|𝑉⃗⃗𝐶.

𝑋⃗ FOE
𝑓⃗𝑉⃗⃗𝐶

Show that for any world point 𝑋⃗𝑊, its image point 𝑋⃗𝐼 will appear to move with velocity

𝑉⃗⃗𝐼 = 𝑘(𝑋⃗𝐼 −𝑋⃗𝐼FOE),

proving that image points appear to move toward or away from the FOE. What is k?