Description

1. Answer the following questions pertaining to the essential/fundamental matrix in a binocular stereo system:
(a) Consider two cameras with parallel optical axes, with the optical center of the second camera at a location (a,0,0) as measured in the first camera’s coordinate frame. What is the essential matrix of this stereo system?
(b) Suppose I gave you the fundamental matrix of a stereo system, how will you infer the left and right epipoles in pixel coordinates?
(c) Prove that any essential matrix will have one singular value which is zero, and that its other two singular values are identical. Derive a relationship between these singular values and the extrinsic parameters of the stereo system (i.e., the rotation matrix R and/or the translation vector t between the coordinate frames of the two cameras). [Hint: Show that if E is the essential matrix, then we can write ETE ) where α is some scalar which you should express in terms of R and/or t, I3×3 is the identity matrix with 3 rows and 3 columns, and tu is a vector of unit magnitude in the direction of t].
(d) In the noiseless case, what is the minimum number of corresponding pairs of points you must know in order to estimate the essential matrix? Or in other words, how many degrees of freedom does an essential matrix have? Justify your answer. (Think carefully).
(e) We have studied the eight-point algorithm in class for estimating the essential/fundamental matrix. There exist algorithms that require only 7 pairs of corresponding points. In robust estimation, what main advantage will a 7-point algorithm have over the 8-point version?
[1 + 1 + 5 + 1 + 2 = 10 points]
2. A very beautiful aspect of compressive sensing is the rigorous mathematical basis – in the form of concrete error bounds on reconstruction results. While using regularization to solve ill-posed problems is a known technique in computer vision and image processing, the existence of error bounds is a unique feature for compressive sensing problems. What is more, the proof of these stunning results is actually not super-hard, and any (motivated) graduate or undergraduate student with a basic knowledge of properties of vectors, and (more than) a little bit of patience, can easily follow the proofs. The purpose of this exercise is to take you through the proof of the following theorem proved by Emmanuel Candes: [20 points]
Theorem: Let y = Ax + η be a vector of noisy compressed measurements where the matrix√ A ∈
has restricted isometry constant δ2s < 2 − 1. Let the noise magnitude be upper bounded
as . Let x? be the solution to the problem minxkxk1 such that ky − Af . Then x? obeys
where C0 and C1 are small-valued constants and xs is a vector obtained
by nullifying all entries of x except the s entries with the largest absolute value.
The proof is given below. Your job is to trace through it, verifying every step, and then answering the questions presented in blue colored font. Ideally, edit the latex file itself and write your answer in blue colored font. You will need to use the following properties assuming vectors x, y: the triangle inequality (kxk2 + kyk2 ≥ kx + yk2), the reverse triangle inequality (kx − yk2 ≥ kxk2 − kyk2), the Cauchy-Schwartz inequality (the dot product |hx,yi| ≤ kxk2kyk2) for vectors x and y, and the restricted isometry property
q for A. Also remember that kxk1 = Pi |xi|, kxk2 = Pi xi and kxk∞ = maxi|xi|. Proof:
(a) We can write the following result: (How is this derived?)
(b) Let us define vector h = x? − x. Let us denote vector hT as the vector equal to h only on an index set T and zero at all other indices. Let T0 the set of indices containing the s largest entries of x (in terms of absolute value), T1 be the set of indices of the s largest entries of h be the set of indices of the next s largest entries of h after T1, and so on. We will now decompose h as the sum of hT0,hT1,hT2,…. We will denote the complement of an index set T as Tc. Our aim will be to prove that both khT0∪T1k2
and kh(T0∪T1)ck2 are upper bounded by sensible and intuitive quantities.
(c) We will first prove the bound on kh(T0∪T1)ck2, in the following way, using simple vector properties and the fact that x + h is the minimum of the objective function subject to the given constraint.
i. We have khTjk2 ≤ s1/2khTjk∞ ≤ s−1/2khTj−1k1. (Prove both these inequalities. Note that any element of Tj−1 is greater than or equal to any element of Tj for any j ≥ 1). ii. Therefore Pj≥2 khTjk2 ≤ s−1/2kh(T0)ck1. (Prove this inequality). iii. Hence we have kh(T0∪T1)ck2 = kPj≥2 hTjk2 ≤ Pj≥2 khTjk2 ≤ s−1/2kh(T0)ck1 (Prove both inequalities).
iv. Now it turns out that kh(T0)ck1 is not very large in value. Why so? As x? is the minimum, we have kxk1 ≥ kx + hk1 = Pi∈T0 |xi + hi| + Pi∈(T0)c |xi + hi| ≥ kxT0k1 − khT0k1 + kh(T0)ck1 − kx(T0)ck1 Prove the last inequality.
v. Rearranging the terms now gives us kh(T0)ck1 ≤ kh(T0)k1 + 2kx(T0)ck1 = kh(T0)k1 + 2kx − xsk1. vi. Combining everything, we now have kh(T0∪T1)ck2 ≤ s−1/2(kh(T0)k1 + 2kx − xsk1) ≤ kh(T0)k2 + 2s−1/2kx − xsk1. (Prove the last inequality).
(d) We will now prove the bound on kh(T0∪T1)k2, in the following way.
i. We observe that AhT0∪T1 = Ah − Pj≥2 AhTj.
Hence kAhT AhT0∪T1,Ahi − hAhT0∪T1,Pj≥2 AhTji.
ii. Now, we have (Prove both these inequalities, one of which uses the restricted isometry property of A).
iii. We also have |hAhT0,AhTji| ≤ δ2skhT0k2khTjk2. To prove this, observe that hT0 and hTj are vectors with disjoint support. |hAhT0,AhTji| = khT0k2khTjk2|hAhˆT0,AhˆTji| where hˆT0 and hˆTj are
kA(hˆT0+hˆTj)k2−kA(hˆT0−hˆTj)k2 unit-normalized vectors. This further yields |hAhT0,AhTji| = khT0k2khTjk2 4

= δ2skhT0k2khTjk2. Analogously, |hAhT1,AhTji| ≤ δ2skhT1k2khTjk2. iv. Now, we have (1 .
(Prove this). Furthermore, we can write (1
because√ hT0 and hT1 are vectors with disjoint sets of non-zero indices and hence khT0k2 +khT1k2 ≤
v. Rearranging the above equation, and using one of the previous results (which one?), we get
.
Further rearranging gives us where C0 and C00 are constants that depend only on δ2s (note in particular that they do not depend on n).
(e) Now, we combine the upper bounds on kh(T0∪T1)k2 and kh(T0∪T1)ck2 to yield the final result as follows: khk2 ≤ khT0∪T1k2 + kh(T0∪T1)ck2 ≤ khT0∪T1k2 + khT0k2 + 2s−1/2kx − xsk1
(Justify all these inequalities. Write the√

final expression for C0 and C1 and explain where the sufficient condition δ2s ≤ 2 − 1 arises).
3. In this section, you will implement the orthogonal matching pursuit (OMP) algorithm for reconstruction from compressive measurements. For this, first extract all overlapping patches of size 8×8 from the barbara image in the homework folder. Generate a n × n matrix Φ where n = 64 with all entries sampled from a zero-mean Gaussian distribution of unit standard deviation. Let Φm denote a submatrix consisting of the first m (m ≤ n) rows of Φ.
Generate compressive measurements for each patch in the form yi = Φmxi where i is a patch index. Add zero mean Gaussian noise with standard deviation = 0.05 times the mean absolute value of all elements from the (non-noisy) coded patches. Your job is to recover xi given yi and Φm for all i using OMP. Since image patches are not sparse in the spatial domain, but sparse (or compressible) in the DCT domain, we will represent each patch as xi = Uθi where U is the 2D DCT matrix , and recover θi first, thereafter reconstructing xi = Uθi. The final image should be reconstructed by averaging the overlapping patches in a sliding window fashion.
You should repeat this experiment for m = ceiling(fn) where f ∈ {0.9,0.8,0.7,0.6,0.5,0.4,0.3,0.2,0.1,0.05} and record the mean squared patch error (MSPE) and mean squared image error (MSIE) each time. MSPE is given as the average of the mean squared error between the original and reconstructed patches. MSIE is the mean squared error between the original and reconstructed image. Plot a graph of both errors w.r.t. m.
Repeat this experiment but using pseudo-inverse (the backslash operator in MATLAB) instead of OMP and plot the same errors. Comment on your observations.
[20 points].
(Important tip: Generate the 2D DCT matrix in MATLAB as follows: U = kron(dctmtx(8)0,dctmtx(8)0) and not as U = dctmtx(64)0. This is because the latter generates a 1D DCT matrix, and images are not sparse in that basis.)