Answers

This note is my answers of 16-385 Computer Vision take-home quiz. I’d appreciate it if you could point out the errors in my answers. If there are any mistakes, please send an email to yubinliu925@gmail.com . I will not type the original questions, because you can find them on the course website. I jumped the quiz 7 because I think it is quiet difficult for self-studied students.

1. Quiz 1

Question 1

Actually, when $X$ and $Y$ are mutually independent random variables, the distribution function of $X+Y$ is the convolution of density functions $f_x$ and $f_y$:

Without prove, we have that the sum of two mutually independent Gaussian variables $N_i\sim(\mu_i, \sigma^2_i)$ is also a Gaussian variable which satisfy:

So the convolution of one Gaussian with another produces a third Gaussian with scale equal to their sum. For more details, you can check the Wikipedia.

Question 2

We can use Lagrange polynomial to approximate the function, and the error of the approximation is $O(h^n)$, where $n$ is the number of points.

Using five points $(x_{i}, f(x_{i}))$ where $i={[-2, -1, 0, 1, 2]}$, we have:

where $L(x)$ is the Lagrange polynomials function using these five points.

So the corresponding convolution kernel is:

2. Quiz 2

Question 1

For the following covariance metric:

Because the $u$ and $v$ are small perturbations, we can rewrite the formula as:

where $\mathcal{M}_w(x,y)$ is the covariance matrix:

Using the definition of convolution, the covariance matrix can be written equivalently as:

The code of Harris Corner Detection in Python is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def harris_corners(img, window_size=3, k=0.04):
    """
    Compute Harris corner response map. Follow the math equation
    R=Det(M)-k(Trace(M)^2).

    Args:
        img: Grayscale image of shape (H, W)
        window_size: size of the window function
        k: sensitivity parameter

    Returns:
        response: Harris response image of shape (H, W)
    """

    H, W = img.shape
    window = np.ones((window_size, window_size))

    response = np.zeros((H, W))

    # Compute x and y derivatives (I_x, I_y) of an image
    dx = filters.sobel_v(img)
    dy = filters.sobel_h(img)
    
    dxx_conv = convolve(dx * dx, window, mode='constant', cval=0)
    dxy_conv = convolve(dx * dy, window, mode='constant', cval=0)
    dyy_conv = convolve(dy * dy, window, mode='constant', cval=0)
    
    R = np.zeros((H, W))
    for i in range(H):
        for j in range(W):
            M = np.array([[dxx_conv[i, j], dxy_conv[i, j]], 
                          [dxy_conv[i, j], dyy_conv[i, j]]])
            response[i, j] = np.linalg.det(M) - k * (np.trace(M) ** 2)

    return response

Question 2

The answer mostly come from this blog, which is a very meticulous article focused on Hessian matrix in corner detection. It also has more details on scale normalization which can adapt different scales of blobs.

For the Hessian matrix :

the eigenvector $e_1$ points in the direction of the highest curvature with the magnitude $\lambda_1$. Similarly, $e_2$ corresponds to the direction of lowest curvature with the strength of $\lambda_2$. Here are three cases to consider for the second order derivative:

1. We have a maximum in both directions, i.e. $\lambda_1>0$ and $\lambda_2>0$ .
2. We have a minimum in both directions, i.e. $\lambda_1<0$ and $\lambda_2<0$ .
3. We have a minimum in one and a maximum in the other direction, e.g. $\lambda_1>0$ and $\lambda_2<0$ .

If both eigenvalues are large, then the corresponding position is a corner. So one way to detect these cases based on the eigenvalues is by using the Gaussian curvature:

The main observation is that this product is only large when both eigenvalues are large. We can now detect blobs at each image position by calculating the Hessian matrix via image derivatives, their eigenvalues and then the Gaussian curvature $K$. Wherever $K$ is high we can label the corresponding pixel position as a blob.

The code of Hessian Corner Detection in Python is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def Hessian_matrix(img, window_size, sigma):
    """
    Compute Hessian corner response map. Follow the math equation
    R=Det(H)

    Args:
        img: Gray scale image of shape (H, W)
        window_size: size of the window function
        sigma: the param of the gaussian mask

    Returns:
        response: Hessian response image of shape (H, W)
    """
	
  H, W = img.shape
  response = np.zeros((H, W))

  # generate the convolution kernel
	g, g_1d, g_2d = gaussian_mask(sigma, window_size)

	# smoothen the image
	Igx, Igy = gaussian_conv(img, g)

	# convoluting Image with 1st and 2nd derivative of I
	Ix, Iy = gaussian_1derv_conv(Igx, Igy, g_1d)
	Ixx, Iyy, Ixy = gaussian_2derv_conv(Ix, Iy, g_2d)

	for i in range(S[0]):
		for j in range(S[1]):
			Hessian = np.array([[Ixx[i][j], Ixy[i][j]], [Ixy[i][j], Iyy[i][j]]])
			response[i, j] = np.linalg.det(Hessian)
	return response

3. Quiz 3

Question 1

For the heterogeneous least-square problem, we have:

So then we can derive the $\textbf{x}$:

The visual interpretation of the residue can be got from this link. When we fit a line in the image, the parameters of slope or intercept may become zero, thus we should use Hough transform instead of this method.

For the homogeneous least-squares problem, we have:

where we have:

which means $\sqrt{a^2 + b^2} = 0$. Therefore, when choosing this constraint, the residuals are orthogonal to the line. For more details of homogeneous least-squares problem, you can refer this link.

The problem can be solved using the generalized eigenvalue decomposition.

For finding a point that comes ‘closest’ to lying at the lines common intersection, we prefer tp choose the homogeneous least-squares method, since the residuals are orthogonal to the line, which are the definition of the distance between point and lines.

Question 2

By the definition, we can find the least squares estimation as:

It only need 5 points to determine a unique solution for $\textbf{c}$. For the proof, you can refer this link.

By making the substitutions $x\rightarrow x_1/x_3$ and $y\rightarrow x_2/x_3$, the conic can be write as:

So it can be formulated as $\textbf{x}^T\textbf{C}\textbf{x}=0$, where:

By applying a projective transformation $\textbf{x}_i’=\textbf{Hx}_i$, the transformed conic can be written as:

, which is still a symmetric matrix.

4. Quiz 4

Question 1

First, we define the camera coordinates and pixel coordinates, a 3D point in camera coordinates $\textbf{p}$ is :

, and the projection of $\textbf{p}$ to pixel coordinates $\textbf{q}$ is that:

, where $\textbf{K}$ is the intrinsic camera matrix:

For a point $p$ in camera coordinates $a$ and $b$, we have:

, where $R_{ba}$ is the orientation of $a$ coordinate in $b$, and $\textbf{t}_{ba}$ is the position of $a$ coordinate in $b$. After transfer into pixel coordinates, we have:

Suppose we have a plane $\pi$ in $a$ coordinate with normal vector $\textbf{n}_a$ and distance to the original point $d_a$, for point $p$, we have:

Therefore, we have:

So we can derive that:

Since we are in homogeneous coordinates, we can remove the coefficient, then we have:

This means we have a homographic matrix $\textbf{H}$ satisfy the equation. Here the $\textbf{P}_1$ and $\textbf{P}_2$ are denoted as $\textbf{K}_a$ and $\textbf{K}_b$.

If there is pure rotation for the camera, with the equation 1, we can find that:

If the camera is rotating about its center $\textbf{C}$, we have:

Therefore, we have:

So $\textbf{H}^2$ is the homographic matrix corresponding to a rotation of $2\theta$.

If $p_0$ on $I_0$ be an image captured by a camera of point $p$, and $p_1$ on $I_1$ be an image of $I_0$ captured by another camera, we have:

If $p_2=\textbf{0}^T$ is the camera center of $I’$, because the null space of an $n \times n$ invertible matrix $\textbf{A}$ is empty, we have $\textbf{p} = \textbf{0}^T$. This means the apparent camera center of $I’$ is the same as that of $I_0$.

I am not sure about this question, if you want to know more, you can check the first question in this link.

Question 2

When the camera location is known, we only need to estimate 8 parameters, which means we need 4 pairs. And when the camera location and complete orientation are known, we only need to estimate 5 intrinsic parameters, so we only need 3 pairs.

5. Quiz 5

Question 1

Suppose the two camera centers are denoted by $A$ and $B$, since they differ only by a translation of their origins along a direction that is parallel to either the $x$ or $y$ axis of the coordinate systems, we may find that line $AB$ is parallel to the camera image plane. Therefore, the epipolar line on both image plane and plane $ABP$ where $P$ is the object point is parallel with the line $AB$. Therefore the epipolar lines of a rectified pair are parallel to the axis of translation.

Since we have $ \textbf{E} = \textbf{R}[\textbf{t}_{\times}]$ and $ \textbf{R} = \textbf{I} $, without loss of general, we assume the translation is parallel with the $x$ axis, then $\textbf{t} = [x_0\ 0\ 0]^T$. Therefore, we have:

Question 2

Since the coordinates of both $\textbf{x}$ and $\textbf{x}’$ in image coordinate is $[0\ 0\ 1]^T$, we have:

Therefore, $\textbf{F}_{33}=0$

Question 3

Using $\textbf{x}’^T\textbf{F}\textbf{x} = 0$, we have:

If the two rows of the matrix are not linear independent, then we can’t solve the inverse matrix, which means the point $\textbf{x}_3$ cannot be uniquely determined by this expression.

6.Quiz 6

Question 1

We have:

Using the solid angle above, we can find the irradiance $E$ onn the plain at points $X_1$ and $X_2$ as:

Question 2

For Lambertian surface, $\forall \hat{\textbf{v}}_i$, $f_r(\hat{\textbf{v}}_i, \hat{\textbf{v}}_o)$ are the same. Obviously we have $\rho\geq 0$, we want to derive that $\rho \leq 1$, which means we just need to prove:

Using the conservation of energy, we have:

Then we can prove the formula above.

For a specular surface, as described in the slides, the BRDF is a delta function:

Question 3

Suppose $i\in {1,2,3}$, We have :

Then we can solve $\rho \hat{\textbf{s}}$ using:

Since $\hat{\textbf{s}}$ is an unit vector, we can do normalization to find $\hat{\textbf{s}}$ and $\rho$.

Question 4

Obviously, we have:

Since $\hat{\textbf{n}}$ is an unit vector, we can solve the equations above and get $\hat{\textbf{n}}$.

7. Quiz 7

We will not finish this quiz. Please refer some courses or materials of physics-based methods in vision. The questions in this quiz is quiet difficult for self-studied students.

8. Quiz 8

Question 1

Obviously, the $\textit{p-norms}$:

for all values of $p\geq 1$ satisfy the non-negativity, reflexivity and symmetry. We just need to prove the triangle inequality:

Therefore, we just need to prove the Minkowski inequality:

We can prove this theory using Holder’s inequality. For more details, you can refer this link.

Question 2

For clarity, let $v_i$ where $i\in{1,\cdots,k}$ denote the Voronoi sites and $x_a$ and $x_b$ be arbitrary points in a particular Voronoi cell associated with site $v_i$. When $x$ and $v_i \in \mathbb{R}^N$, We need to prove that:

where $i\in{2,\cdots,k}$ and $0\leq t\leq 1$.

From the constrains, we can get that:

Similarly, we have:

We notice that:

thus we prove the theory.

9. Quiz 9

Question 1

If we have a linear activation function $f(x) = W’x + b’$, then a network with one hidden layer can be write as:

So we can use a non hidden layer network with $W = W_2W’W_1$ and $b = W_2(W’b_1+b’) + b_2$ to replace the original network.

For the sigmoid function $\sigma(x)$, we have:

When the absolute value of $x$ increases, the gradient of the sigmoid activation function changing slowly. When the sigmoid is used as the activation function for many layers, it will suffer Vanishing Gradient Problem. For more details, you can refer this link.

For the $tanh$ function, we have:

The output range of sigmoid function is $(0, 1)$, and the range of the hyperbolic tangent function is $(-1, 1)$. About which function is better in different cases, you can refer this link.

Question 2

The second-order expansion of $L$ around a point ${x}^t \in \mathbb{R}^d$ is:

Combine the gradient descent iteration equation and the Taylor expansion above, we have:

So we can get that:

If we calculate the derivative of the Taylor expansion directly, we can get:

Let $\nabla L(x^{t+1}) = 0$, we have：

This alternative gradient-descent procedure is often called Newton’s algorithm. It need to calculate the inverse of the Hessian matrix.

For choosing an optimization algorithm in different situations, you can refer this link.

10. Quiz 10

Question 1

Convolution is not naturally equivalent to some other transformations, such as changes in the scale or rotation of an image. Other mechanisms are necessary for handling these kinds of transformations. Actually it is the max pooling layer that introduces such invariants.

The convolution layer is translation equivalent instead of invariant.

Question 2

After the ReLU layer, all the score will in the range $[0, +\infty]$, so the next $tanh$ layer will only has the input greater than zero. Therefore, the output of the network will always be greater than zero, which means the predicted label is $+1$. So the classification accuracy of the network is $50\%$.

Question 3

We assume the flow is locally smooth, so the surrounding patch (say $5\times5$) has ‘constant flow’, which means:

for all the pixels $x,y$ in the patch $W$ of size $N\times N$.

So we have:

With multiplication of $\textbf{A}$, we can solve this heterogeneous linear system:

where we have:

So solving this heterogeneous linear system in the least-squares sense requires inverting the covariance matrix.

Actually the Harris Corner Detector is $\textbf{A}^T\textbf{A}$. When the Lucas-Kanade optical flow works well, $\textbf{A}^T\textbf{A}$ should be invertible, and $\lambda_1$ and $\lambda_2$ should not be too small, which means the patch $W$ is a corner. Corners are regions with two different directions of gradient, so they are good places to compute flow.

11. Quiz 11

Question 1

In the Lucas-Kanade (or forward-additive) image alignment algorithm, the loss function is

The first-order Taylor expansion of the composite function $I(\textbf{W}(\textbf{x};\textbf{p}))$ with respect to $\textbf{p}$ around the value $\textbf{p}^t$ is:

So the approximation for $I(\textbf{W}(\textbf{x};\textbf{p}^t))$ is:

Therefore, the optimization problem can be rewritten as:

where we have:

Here we need to derive the solution of the least squares problem first, then we can solve the optimization problem. The least squares problem is solved by:

Then we have:

Using the equation above, we can derive the solution of the optimization problem:

The algorithm procedure is:

1. Warp image $I(\textbf{W}(\textbf{x};\textbf{p}))$
2. Compute error image $[T(\textbf{x}) - I(\textbf{W}(\textbf{x};\textbf{p}^t))]$
3. Compute gradient $\nabla I(\textbf{x})$
4. Evaluate Jacobian $\frac{\partial \textbf{W}}{\partial \textbf{p}}$
5. Compute Hessian $\textbf{H} = \sum_\textbf{x} [\nabla \textbf{I} \frac{\partial \textbf{W}}{\partial \textbf{p}^t}]^T [\nabla \textbf{I} \frac{\partial \textbf{W}}{\partial \textbf{p}^t}]$
6. Compute $\Delta \textbf{p}$
7. Update parameters $\textbf{p} \leftarrow \textbf{p} + \Delta \textbf{p}$

Question 2

The first-order Taylor expansion of the composite function $I(\textbf{W}^t(\textbf{W}(\textbf{x}, \Delta \textbf{p})))$ with respect to $\Delta \textbf{p}$ around the value $0$ is:

Similarly as the question 1, the optimization problem can be rewritten as the least-squares form:

where we have:

The solution and algorithm procedure is also similarly as question 1. However, the Jacobian matrix $\frac{\partial \textbf{W}(\textbf{x},\textbf{0})}{\partial {\textbf{p}}}$ can be precomputed, which can speed up the algorithm.

Question 3

The first-order Taylor expansion of the composite function $ T(\textbf{W}(\textbf{x}, \Delta \textbf{p})) $ with respect to $\Delta \textbf{p}$ around the value $0$ is:

Similarly as the question 1, the optimization problem can be rewritten as the least-squares form:

where we have:

The solution and algorithm procedure is also similarly as question 1. However, the Jacobian matrix, the gradient of template and the Hessian matrix can be precomputed, which makes this algorithm become the most efficient one.

• Previous
  My First Blog
• Next
  Lie Theory for the Roboticist