CV_HW3 (theory)

마감일
2022/11/07
제출자
전기정보공학부 2017-12433 김현우

Question 1: Compute Normals of a Sphere

Assume that there exists a chrome sphere with radius RR and the center of the sphere is (a,b)(a,b). In this situation, represent normal direction (nx,ny,nz)(n_x,n_y,n_z) of the highlight position (u,v)(u,v) on the chrome sphere by using aa, bb, uu, vv, RR. And justify your answer.
In general, the normal direction vector at a particular point on the surface of a sphere is the same as the vector from the center of the sphere to the particular point. To normalize the direction vector, we can divide it with the sphere radius RR, which is the distance of the vector.
Since the center of the sphere is (a,b)(a,b) and the highlight position is (u,v)(u,v), we can easily say xx and yy component of the direction vector is u−au-a and v−bv-b. These components can be normalized to u−aR\frac{u-a}{R} and v−bR\frac{v-b}{R} each. Thus we can say nx=u−aRn_x =\frac{u-a}{R} and ny=v−bRn_y = \frac{v-b}{R}.
We can find the remaining nzn_z by finding the value which satisfies nx2+ny2+nz2=1\sqrt{n_x^2 + n_y^2 + n_z^2} = 1. Thus, nz=1−(nx2+ny2)=1−((u−a)2+(v−b)2R2)n_z = \sqrt{1-(n_x^2 +n_y^2)} =\sqrt{1 -(\frac{(u-a)^2 + (v-b)^2}{R^2})} (We can consider nz>0n_z >0, the case of considering front point of sphere). To wrap up, we can represent normal direction of the highlight position as below.
nx=u−aRny=v−bRnx=1−((u−a)2+(v−b)2R2)\begin{align*} &n_x = \frac{u-a}{R} \\ &n_y = \frac{v-b}{R} \\ &n_x = \sqrt{1- (\frac{(u-a)^2 + (v-b)^2}{R^2})} \end{align*}

Question 2 : Computing Scene Normals

Assume that there exists NN images of a Lambertian object taken using different light sources with same intensity. Each direction of light source are notated as s1s_1, s2s_2, …, sNs_N, and the intensities of a image pixel are notated as I1I_1, I2I_2, …, INI_N. Describe the method to compute the normal direction and the (unnormalized) albedo of the pixel.
In case of dealing with lambertian object, we can generally say the image intensity as below. In below equation ρ\rho is surface albedo, nn is normal direction vector and ss is source direction vector.
Ii=ρn⋅siI_i=\rho n\cdot s_i
We can apply above equation on all images and light source direction, constructing matrix form equation as below.
[I1I1⋮IN]=[s1Ts2T⋮sNT]ρn\begin{bmatrix} I_1 \\ I_1 \\ \vdots \\ I_N \end{bmatrix} = \begin{bmatrix} s_1^T \\ s_2^T \\ \vdots \\ s_N^T \end{bmatrix} \rho n
Let’s substitude n~=ρn\tilde n = \rho n, I=[I1I1⋮IN]I = \begin{bmatrix} I_1 \\ I_1 \\ \vdots \\ I_N \end{bmatrix} , S=[s1Ts2T⋮sNT]S = \begin{bmatrix} s_1^T \\ s_2^T \\ \vdots \\ s_N^T \end{bmatrix}. Then we can focus on solving the least squares problem of minimizing ∥Sn~−I∥2\| S\tilde n - I\|^2. By applying the common solution of least square problem, we can obtain n~=(STS)−1STI\tilde n = (S^TS)^{-1}S^TI. Finally, we can compute the normal directon n=n~∣n~∣n = \frac{\tilde n}{|\tilde n|} and albedo ρ=∣n~∣\rho = |\tilde n| since nn is normal vector with ∣n∣=1|n| =1.

Question 3 : Homography

Consider two points pp and qq on planes Π1\Pi_1 and Π2\Pi_2. Let us assume that the homography that maps point qq to pp is given by SS.
p≡Sq\begin{equation} p\equiv Sq \end{equation}
Answer the following questions regarding SS:
(a)(a) What is the size rows × columns of the matrix SS? (Remember to use homogeneous coordinates.)
Since pp and qq are the points on image plane, which is 2-dimension in euclidean coordinate, we can say both of them are 3-dimension in homogeneous coordinate. The homography SS which maps qq to pp should be 3×33\times3 matrix to perform the transformation from 3-dimension vector to another 3-dimension vector.
(b)(b) What is the rank of the matrix SS? Explain.
Let’s assume there exists nonzero vector x≠0x \ne0 such that Sx=0Sx = 0.
Consider the intersection of the xx and plane Π2\Pi_2 as q′q'. Then, we can easily say q′q' is a vector that is the scalar multiple of xx which makes Sq′=0Sq' =0. Then p′p', the corresponding (transformed) point of q′q' on Π1\Pi_1 must be also 00 which makes contradiction that p′p' is both camera center and on image plane Π1\Pi_1.
Then, we can think of the case that xx and Π2\Pi_2 doesn’t have any intersection.
Consider the straight line ll that the vector xx represents. Then for all points in the line ll, we can make projection to the image plane Π2\Pi_2 to make projected line lql_q. Since the points on line ll can be expressed as the scalar multiplication of xx and the projection can be expressed as adding same size (β\beta) of image plane normal vectors on each points, we can express the point of l2l_2 using two scalar α\alpha, β\beta as below.
lq={αx+βn∣α∈R}l_q = \{\alpha x + \beta n |\alpha\in\R\}
For αix+βn\alpha_ix + \beta n, the specific points in l2l_2 (which is on plane Π2\Pi_2), we can apply transformation using homography.
S(αix+βn)=αiSx+βSn=βSnS(\alpha_i x + \beta n) = \alpha_i Sx + \beta Sn = \beta Sn
By above equation, we can know that for all points in l2l_2, the corresponding points in Π1\Pi_1 are same. This contradicts with collinearity of homography (line must be correspond to line, one-to-one mapping).
To wrap up, by assuming the existance of nonzero vector x≠0x \ne0 such that Sx=0Sx=0 makes contradiction in all possible cases and we can say the assumption is wrong. Thus, there isn’t any nonzero vector x≠0x \ne0 such that Sx=0Sx=0 and this means SS has nullity of 0, and has full rank of 3.
(c)(c) What is the minimum number of point correspondences (p,q)(p,q) required to estimate SS? Why?
Consider one correspondences pi=(xi,yi,1)Tp_i = (x_i, y_i,1)^T and qi=(xi′,yi′,1)Tq_i = (x_i', y_i', 1)^T is given. Then, we can think of the given homography satisfies an equation below.
[xi′yi′1]=S[xiyi1],    S=[h00h01h02h10h11h12h20h21h22]\begin{bmatrix} x_i' \\ y_i' \\ 1 \end{bmatrix} = S \begin{bmatrix} x_i \\ y_i \\ 1 \end{bmatrix}, \thickspace\thickspace S = \begin{bmatrix} h_{00} & h_{01} & h_{02} \\ h_{10} & h_{11} & h_{12} \\ h_{20} & h_{21} & h_{22} \\ \end{bmatrix}
Then, we can simply figure out the above equation (written in homogenous coordinate) can be changed to two equations below.
xi′=h00xi+h01yi+h02h20xi+h21yi+h22yi′=h10xi+h11yi+h12h20xi+h21yi+h22x_i' = \frac{h_{00}x_i + h_{01}y_i + h_{02}}{h_{20}x_i + h_{21}y_i + h_{22}} \\ y_i' = \frac{h_{10}x_i + h_{11}y_i + h_{12}}{h_{20}x_i + h_{21}y_i + h_{22}} \\
We can write these two equation again as matrix form.
[xiyi1000−xi′xi−xi′yi−xi′000xiyi1−yi′xi−yi′yi−yi′][h00h01h02h10h11h12h20h21h22]=[00]\begin{bmatrix} x_i & y_i & 1 & 0 & 0 &0 & -x_i'x_i & -x_i'y_i & -x_i' \\ 0 & 0 &0 &x_i & y_i & 1 & -y_i'x_i & -y_i'y_i & -y_i' \\ \end{bmatrix} \begin{bmatrix} h_{00} \\ h_{01} \\ h_{02} \\ h_{10} \\ h_{11} \\ h_{12} \\ h_{20} \\ h_{21} \\ h_{22} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}
We can find out one correspondences give two rows of first matrix. There are 9 unknowns in above equation (h00,h01,...,h22h_{00}, h_{01}, ..., h_{22}), but matrix SS is up-to-scale, so the final degree of the freedom is 8. It can be seen that a total of 4 correspondences are required to cover 8 degrees of the freedom by 2.
We can use homographies to create a panoramic image from multiple views of the same scene. This is possible when there is no camera translation between the views (e.g. only rotation about the camera center). In this case, corresponding points from two views of the same scene can be related by a homography:
p1i≡Hp2i\begin{equation} p_1^i \equiv Hp_2^i \end{equation}
where p1ip_1^i and p2ip_2^i denote the homogeneous coordinates (e.g., p1i≡(x,y,1)Tp_1^i \equiv (x,y,1)^T) of the 2D projection of the ii-th point in images 1 and 2 respectively, and HH is a 3×33\times 3 matrix representing the homography.
(d)(d) Given N point correspondences and using (2)(2), derive a set of 2N independent linear equations in the form Ah=bAh=b where hh is a 9×19\times 1 vector containing the unknown entries of HH. What are the expressions for AA and bb? How many correspondences will be needed to solve for hh?
Let’s assume pji=(xji,yji,1)Tp_j^i =(x^{i}_j,y_j^{i},1)^T for j∈{1,2}j \in \{1, 2 \}, i∈{1,2,…N}i \in \{1,2,\dots N\} and H=[h00h01h02h10h11h12h20h21h22]H = \begin{bmatrix} h_{00} & h_{01} & h_{02} \\ h_{10} & h_{11} & h_{12} \\ h_{20} & h_{21} & h_{22} \\ \end{bmatrix}.
Then, we can write down matrix equation for one correspondence point as below.
p1i=Hp2i→[x1iy1i1]=H[x2iy2i1]=[h00h01h02h10h11h12h20h21h22][x2iy2i1]p_1^i = Hp_2^i \rarr \begin{bmatrix} x_1^i \\ y_1^i \\ 1 \end{bmatrix} = H \begin{bmatrix} x_2^i \\ y_2^i \\ 1 \end{bmatrix} = \begin{bmatrix} h_{00} & h_{01} & h_{02} \\ h_{10} & h_{11} & h_{12} \\ h_{20} & h_{21} & h_{22} \\ \end{bmatrix} \begin{bmatrix} x_2^i \\ y_2^i \\ 1 \end{bmatrix}
As same as previous question (c)(c), we can simply figure out the above equation (written in homogenous coordinate) can be changed to two equations below.
x1i=h00x2i+h01y2i+h02h20x2i+h21y2i+h22y1i=h10x2i+h11y2i+h12h20x2i+h21y2i+h22x_1^i = \frac{h_{00}x_2^i + h_{01}y_2^i + h_{02}}{h_{20}x_2^i + h_{21}y_2^i + h_{22}} \\ y_1^i = \frac{h_{10}x_2^i + h_{11}y_2^i + h_{12}}{h_{20}x_2^i + h_{21}y_2^i + h_{22}} \\
We can write these two equation again as matrix form.
[x2iy2i1000−x1ix2i−x1iy2i−x1i000x2iy2i1−y1ix2i−y1iy2i−y1i][h00h01h02h10h11h12h20h21h22]=[00]\begin{bmatrix} x_2^i & y_2^i & 1 & 0 & 0 &0 & -x_1^ix_2^i & -x_1^iy_2^i & -x_1^i \\ 0 & 0 &0 &x_2^i & y_2^i & 1 & -y_1^ix_2^i & -y_1^iy_2^i & -y_1^i \\ \end{bmatrix} \begin{bmatrix} h_{00} \\ h_{01} \\ h_{02} \\ h_{10} \\ h_{11} \\ h_{12} \\ h_{20} \\ h_{21} \\ h_{22} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}
By changing total NN correspondences to above matrix equation form, we can get the final matrix equation form as below.
[x21y211000−x11x21−x11y21−x11000x21y211−y11x21−y11y21−y11x22y221000−x12x22−x12y22−x12000x22y221−y12x22−y12y22−y12⋮⋮⋮⋮⋮⋮⋮⋮⋮x2Ny2N1000−x1Nx2N−x1Ny2N−x1N000x2Ny2N1−y1Nx2N−y1Ny2N−y1N][h00h01h02h10h11h12h20h21h22]=[00⋮00]\begin{bmatrix} x_2^1 & y_2^1 & 1 & 0 & 0 &0 & -x_1^1x_2^1 & -x_1^1y_2^1 & -x_1^1 \\ 0 & 0 &0 &x_2^1 & y_2^1 & 1 & -y_1^1x_2^1 & -y_1^1y_2^1 & -y_1^1 \\ x_2^2 & y_2^2 & 1 & 0 & 0 &0 & -x_1^2x_2^2 & -x_1^2y_2^2 & -x_1^2 \\ 0 & 0 &0 &x_2^2 & y_2^2 & 1 & -y_1^2x_2^2 & -y_1^2y_2^2 & -y_1^2 \\ \vdots & \vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\ x_2^N & y_2^N & 1 & 0 & 0 &0 & -x_1^Nx_2^N & -x_1^Ny_2^N & -x_1^N \\ 0 & 0 &0 &x_2^N & y_2^N & 1 & -y_1^Nx_2^N & -y_1^Ny_2^N & -y_1^N \\ \end{bmatrix} \begin{bmatrix} h_{00} \\ h_{01} \\ h_{02} \\ h_{10} \\ h_{11} \\ h_{12} \\ h_{20} \\ h_{21} \\ h_{22} \\ \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ 0 \end{bmatrix}
The above equation is the form of Ah=bAh =b where
A=[x21y211000−x11x21−x11y21−x11000x21y211−y11x21−y11y21−y11x22y221000−x12x22−x12y22−x12000x22y221−y12x22−y12y22−y12⋮⋮⋮⋮⋮⋮⋮⋮⋮x2Ny2N1000−x1Nx2N−x1Ny2N−x1N000x2Ny2N1−y1Nx2N−y1Ny2N−y1N]A = \begin{bmatrix} x_2^1 & y_2^1 & 1 & 0 & 0 &0 & -x_1^1x_2^1 & -x_1^1y_2^1 & -x_1^1 \\ 0 & 0 &0 &x_2^1 & y_2^1 & 1 & -y_1^1x_2^1 & -y_1^1y_2^1 & -y_1^1 \\ x_2^2 & y_2^2 & 1 & 0 & 0 &0 & -x_1^2x_2^2 & -x_1^2y_2^2 & -x_1^2 \\ 0 & 0 &0 &x_2^2 & y_2^2 & 1 & -y_1^2x_2^2 & -y_1^2y_2^2 & -y_1^2 \\ \vdots & \vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\ x_2^N & y_2^N & 1 & 0 & 0 &0 & -x_1^Nx_2^N & -x_1^Ny_2^N & -x_1^N \\ 0 & 0 &0 &x_2^N & y_2^N & 1 & -y_1^Nx_2^N & -y_1^Ny_2^N & -y_1^N \\ \end{bmatrix} and b=[00⋮00]b = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ 0 \end{bmatrix}.
AA is 2N×92N\times 9 matrix and, bb is 2N×12N\times 1 zero vector.
hh has 9 unknowns, but it is up-to-scale, so the final degree of the freedom is 8. It can be seen that a total of 4 correspondences are required to cover 8 degrees of the freedom by 2.