\newif\ifsolution
\newif\ifgrading

\newenvironment{CourseTitle}{
\huge \Huge CS 231A Computer Vision Sample Midterm\\ \ \\ 
\ifgrading
\ \\ \ \\ \large\bf Master Set
\else
    \ifsolution
    \ \\ \ \\ \large\bf Solution Set
    \fi
\fi
}

%\solutiontrue
\solutionfalse
%\gradingtrue
\gradingfalse

\documentclass[11pt]{article}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{.125in}
\setlength{\textwidth}{6.25in}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{subfig}
\usepackage{graphicx}
\usepackage{enumerate}
\newcommand{\argmax}{\operatornamewithlimits{arg \ max}}
\newcommand{\maximize}{\operatornamewithlimits{maximize}}
\newcommand{\minimize}{\operatornamewithlimits{minimize}}
\newcommand{\comment}[1]{{\textcolor{red}{[[{#1}]]}}}

\begin{document}
\title{\CourseTitle}
\date{}
\maketitle

% Hide this part for solution set
\ifsolution
\else
\Large
Full Name: \makebox[2in]{\hrulefill}
\\
\LARGE
\begin{center}
    \begin{tabular}{ | l  l | l | p{5cm} |}
\hline
    Question & & Score  \\ \hline
    \hline
    Multiple Choice &(22 pts)& \ \ \\ \hline
    RANSAC &(10 pts)& \ \  \ \ \  \ \ \ \  \\ \hline
    Fundamental Matrix &(10 pts) &  \ \ \\ \hline
    Linear Filter &(10 pts)  &  \ \ \\ \hline
    Perspective Projection &(10 pts) &  \ \ \\ \hline
    Short Answer &(38 pts) &  \ \ \\ \hline
    \hline
    Total  &(100 pts) & \ \ \\
    \hline
    \end{tabular}
\end{center}
\large
\
\\
Welcome to the CS 231A Midterm Exam!
\begin{itemize}
	\item The exam is 75 minutes.
	
	\item The exam is open book and open notes. No calculators, cell phones, or any kind of internet connections are allowed.

\end{itemize}

\noindent
\\
I understand and agree to uphold the Stanford Honor Code during this exam. \\
\\
\begin{center}
Signature: \makebox[2in]{\hrulefill} \ \ \ \ \ \ Date:  \makebox[1in]{\hrulefill}  \\
\vspace{10mm}
\end{center}

\LARGE
\begin{center}
Good luck!
\end{center}
\normalsize

\pagebreak
\fi

\section{Multiple Choice (22 points)}

Each question has \textbf{ONLY ONE CORRECT OPTION} and is worth \textbf{2 points}. To discourage random guessing, \textbf{0.5 points will be deducted} for a wrong answer on multiple choice questions! Please draw a circle around the option to indicate your answer. No credit will be awarded for unclear/ambiguous answers.

\begin{enumerate}

\item In Canny edge detection, we will get more discontinuous edges if we make the following change to the hysteresis thresholding:
\begin{enumerate}[(a)]
        \item increase the high threshold
        \item decrease the high threshold
        \item increase the low threshold
        \item decrease the low threshold
        \item decrease both thresholds
\end{enumerate}

\ifsolution
\textbf{Solution} c \\
\fi
\item Mean-shift is a nonparametric clustering method. However, this is misleading because we still have to choose
\begin{enumerate}[(a)]
        \item the number of clusters
        \item the size of each cluster
        \item the shape of each cluster
        \item the window size
        \item the number of outliers to allow
\end{enumerate}

\ifsolution
\textbf{Solution} d \\
\fi
	\item Which of the following actions is often applied to eliminate aliasing?
	\begin{enumerate}[(a)]
		\item low-pass filtering
		\item high-pass filtering
		\item subtracting out the image mean
		\item better focusing
		\item PCA
	\end{enumerate}

\ifsolution
\textbf{Solution} a \\
\fi
        \item If you are unsure of how many clusters you have in your data, the best method to use to cluser your data would be
        \begin{enumerate}[(a)]
                \item mean-shift
                \item k-means
                \item expectation-maximization
                \item markov random field
                \item none of the above are good methods
        \end{enumerate}
\ifsolution
        \textbf{Solution} a \\
\fi
\item Normalized cuts is an NP-hard problem. To get around this problem, we do the following:
\begin{enumerate}[(a)]
        \item apply k-means as an initialization
        \item allow continuous eigenvector solutions and discretize them
        \item converting from a generalized eigenvalue problem to a standard one
        \item constraining the number of cuts we make
        \item forcing the affinities to be positive
\end{enumerate}
\ifsolution
        \textbf{Solution} b or c \\
\fi
	
	\item To decrease the size of an input image with minimal content loss, we should
	\begin{enumerate}[(a)]
		\item  High-pass filter and down-sample the image
		\item  Crop the image
		\item  Apply a hough transform
		\item  Down-sample the image
		\item  Low-pass filter and down-sample the image
	\end{enumerate}
\ifsolution
  \textbf{Solution} e\\
\fi
  \item When applying a Hough transform, noise can be countered by
  \begin{enumerate}[(a)]
    \item a finer discretization of the accumulator
    \item increasing the threshold on the number of votes a valid model has to obtain
    \item decreasing the threshold on the number of votes a valid model has to obtain
    \item considering only a random subset of the points since these might be inliers
  \end{enumerate}

\ifsolution
  \textbf{Solution} b\\
\fi
	\item In which of the following scenarios can you use a weak perspective camera model for the target object?
	\begin{enumerate}[(a)]
		\item A squirrel passing quickly in front of you.
		\item An airplane flying at a very high attitude.
\item The Hoover tower when you are taking a photo of it right in front of it.
		\item A car beside you when you are driving.
	\end{enumerate}
	
\ifsolution
  \textbf{Solution} b\\
\fi
  \item What is the biggest benefit of image rectification for stereo matching?
  \begin{enumerate}[(a)]
    \item Image contents are uniformly scaled to a desirable size.
    \item All epipolar lines intersect at the vanishing point.
    \item All epipolar lines are perfectly vertical.
    \item All epipolar lines are perfectly horizontal.
    \item Epipoles are moved to the center of the image.
  \end{enumerate}

\ifsolution
  \textbf{Solution} d\\
\fi
  \item Which of the following factor does not affect the intrinsic parameters of a camera model?
  \begin{enumerate}[(a)]
    \item Focal length
    \item Offset of optical center
    \item Exposure
    \item Image resolution
  \end{enumerate}

\ifsolution
  \textbf{Solution} c\\
\fi
  \item What are the degrees of freedom of the essential matrix and why?
  \begin{enumerate}[(a)]
    \item 5; 3 dof for rotation, 3 dof for translation. Up to a scale, so 1 dof is removed.
    \item 6; 3 dof for rotation, 3 dof for translation.
    \item 7; a $3\times3$ homogeneous matrix has eight independent ratios and $det(E) = 0$ removes 1 dof.
    \item 7; 3 dof for rotation, 3 dof for translation. Up to a scale, so 1 dof is added.
  \end{enumerate}

\ifsolution
  \textbf{Solution} a\\
\fi

\end{enumerate}
\pagebreak

\setcounter{section}{1}
\section{Long Answer (40 points)}

\begin{enumerate}
\setcounter{enumi}{11}

\item \textbf{\large (10 points) Fitting Circles with RANSAC}

RANSAC is a powerful method for a wide range of model fitting problems as it is easy to implement. In class, we've seen how RANSAC can be applied to fitting lines. However, RANSAC can handle more complicated fitting problems as well, such as fitting circles. In this problem we will solve for the steps needed to fit circles with RANSAC.

\begin{enumerate}[(a)]
\item (1 point)
What is the minimum number of points we must sample in a seed group to compute an estimate for a uniquely defined circle?
\ifsolution
\\
\\
\large \textbf{Solution} \normalsize \\
3 points, as there are 3 degrees of freedom in a circle, the (x,y) coordinates of the center and the radius. \\
\else
\vspace{50mm}
\fi
\item (5 points)
If we obtain a good solution that has few outliers, we want to refit the circle using all of the inliers, and not just the seed group. For speed purposes, we would like to keep the same center of the estimated circle from the seed group, and simply refit the radius of the circle. The equation for our circle is given as:
\begin{center}
$(x - x_c)^2 + (y - y_c)^2 = r^2$ \\
\end{center}
where $(x_c,y_c)$ are the coordinates of the center of the circle, and $r$ is the radius. \\
The error we would like to minimize is given by:
\begin{center}
$E(x_c, y_c, r) = \sum\limits_{i=1}^m (\sqrt{(x_i - x_c)^2 + (y_i - y_c)^2} - r)^2$
\end{center}
where $m$ is the number of inliers. Derive the new radius $r$ that minimizes this least squares error function.
\ifsolution
\\
\\
\large \textbf{Solution} \normalsize \\
\begin{center}
$\frac{\partial E}{\partial r} = -2 \sum\limits_{i=1}^m(\sqrt{(x_i - x_c)^2 + (y_i - y_c)^2} - r)$
\end{center}

\begin{center}
$r = \frac{1}{m} \sum\limits_{i=1}^m(\sqrt{(x_i - x_c)^2 + (y_i - y_c)^2})$
\end{center}

\else
\vspace{90mm}
\fi

\item (4 points)
One of the benefits to RANSAC is that we are able to calculate the failure rate for a given number of samples. Suppose we know that 30\% of our data is outliers. How many times do we need to sample to assure with probability 20\% that we have at least one sample being all inliers? You can leave your answer in terms of $\log$ functions.
\ifsolution
\\
\\
\large \textbf{Solution} \normalsize \\
\begin{center}
$1-0.2 = (1 - (0.7)^3)^k$
\end{center}
\begin{center}
$k = \frac{\log(1-0.2)}{\log(1 - (0.7)^3)}$
\end{center}

\else
\pagebreak
\fi
\end{enumerate}


\item \textbf{\large (10 points) Fundamental Matrix}

When you show your friend around Stanford campus, he takes a picture $I$ of the Hoover tower. Later he wants to take a bigger picture of the Hoover tower, but his camera has no zoom-in function, so he walks forward for a short distance and takes a new picture $I'$. Assume there is only a forward translation of the camera perpendicular to the image plane and the movement distance is $d$.
\begin{enumerate}
\item (5 points) Find the essential matrix $F$ between $I$ and $I'$ in terms of $d$.
\ifsolution
\ \\ \ \\
\textbf{Solution} \\
In general, $E = \hat{t}R$, where $\hat{t}$ is a skew-symmetric matrix related to translation vector. For a forward translating camera, we have
\[
R=I, \hat{t}=
\left [
 \begin{matrix}
    0 & -d & 0\\
    d & 0 & 0\\
    0 & 0 & 0
 \end{matrix}
 \right ]
\]
therefore,
\[
E=
\left [
 \begin{matrix}
    0 & -d & 0\\
    d & 0 & 0\\
    0 & 0 & 0
 \end{matrix}
 \right ]
\]
\else
\vspace{80mm}
\fi
\item (5 points) The tip of the Hoover tower on $I$ is $p=(x\ y)$, what is its corresponding epipolar line $l$ in $I'$? Express $l$ in terms of $x$, $y$ and $d$.
\ifsolution
\ \\ \ \\
\textbf{Solution} \\
From $l=Ep$, the epipolar line for point $p=[x\ y\ 1]$ is
\[
l=
\left [
 \begin{matrix}
    0 & -d & 0\\
    d & 0 & 0\\
    0 & 0 & 0
 \end{matrix}
 \right ]
\left [
 \begin{matrix}
    x\\
    y\\
    1
 \end{matrix}
 \right ]
=
\left [
 \begin{matrix}
    -yd\\
    xd\\
    0
 \end{matrix}
 \right ]
\]
\else
\pagebreak
\fi
\end{enumerate}

\item \textbf{\large (10 points) Linear Filter} \\
In this problem, you will explore how to separate a 2D filter kernel into two 1D filter kernels. Matrix $K$ is a discrete, separable 2D filter kernel of size $k\times k$. Assume $k$ is an odd number. After applying filter $K$ on an image $I$, we get a resulting image $I_K$.
\begin{enumerate}[(a)]
\item (1 point) Given an image point $(x,y)$, find its value in the resulting image, $I_K(x,y)$. Express your answer in terms of $I$, $k$, $K$, $x$ and $y$. You don't need to consider the case when $(x,y)$ is near the image boundary.
\ifsolution
\ \\ \ \\
\textbf{Solution} \\
$I_{K}(x,y) = \sum_{i=1}^{k}\sum_{j=1}^{k}K_{ij}I(x-i+\frac{k}{2},y-j+\frac{k}{2})$\\
\else
\vspace{60mm}
\fi
\item (5 points) One property of this separable kernel matrix $K$ is that it can be expressed as the product of two vectors $g\in \mathbb{R}^{k\times 1}$ and $h\in \mathbb{R}^{1\times k}$, which can also be regarded as two 1D filter kernels. In other words, $K = gh$. The resulting image we get by first applying $g$ and then applying $h$ to the image $I$ is $I_{gh}$. Show that $I_K = I_{gh}$.
\ifsolution
\ \\ \ \\
\textbf{Solution}
\begin{align*}
I_{K}(x,y) &= \sum_{i=1}^{k}\sum_{j=1}^{k}K_{ij}I(x-i+\frac{k}{2},y-j+\frac{k}{2}) \\
	   &= \sum_{i=1}^{k}\sum_{j=1}^{k}g_ih_jI(x-i+\frac{k}{2},y-j+\frac{k}{2}) \\
	   &= \sum_{j=1}^{k}h_j\sum_{i=1}^{k}g_iI(x-i+\frac{k}{2},y-j+\frac{k}{2}) \\
	   &= \sum_{j=1}^{k}h_jI(x,y-j+\frac{k}{2}) \\
	   &= I_{gh}(x,y).
\end{align*}
\else
\pagebreak
\fi
\item (4 points) Suppose the size of the image is $N\times N$, estimate
the number of operations (an operation is an addition or multiplication of two numbers) saved if we apply the 1D filters $g$ and $h$ sequentially instead of applying the 2D filter $K$. Express your answer in terms of $N$ and $k$. \emph{Ignore the image boundary cases so you don't need to do special calculations for the pixels near the image boundary. } \\
\ifsolution
\ \\ \ \\
\textbf{Solution}\\
For the 2D filter, there are $k^2$ multiplication operations and $k^2-1$ addition operations for each pixel. In total, $N^2(2k^2-1)$.\\

For each of the 1D filters, there are $k$ multiplication operations and $k-1$ addition operations for each pixel. In total, $N^2(4k-2)$.\\

So the number of operations saved is $N^2(2k^2-4k+1)$ \\
\else
\pagebreak
\fi
\end{enumerate}

\item \textbf{\large (10 points) Perspective Projection}

In figure \ref{fig:stereo}, there are two parallel lines $l_1$ and $l_2$ lying on the same plane $\Pi$. $l_1'$ and $l_2'$ are their projections through the optical center $O$ on the image plane $\Pi'$.
Let's define plane $\Pi$ by $y = c$, line $l_1$ by equation $ax+bz=d_1$, and line $l_2$ by equation $ax+bz=d_2$.

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.8\linewidth]{perspective.pdf}
\caption{Perspective Projection}
\label{fig:stereo}
\end{center}
\end{figure}

\begin{enumerate}[(a)]
\item (3 points) For any point $P=(x,y)$ on $l_1$ or $l_2$, use the perspective projection equation below to find the projected point $P'=(x',y')$ on the image plane. $f'$ is the focal length of the camera. Express your answer in terms of $a$, $b$, $c$, $d$, $z$ and $f'$.
\begin{align}
\left \{
\begin{array}{l}
x' = f' \frac{x}{z}\\
y' = f' \frac{y}{z}
\end{array}
\right.
\end{align}
\ifsolution
\ \\ \ \\
\textbf{Solution} \\
According to the perspective projection equation, a point on $l$ projects onto the image point defined by
\[
\left \{ \begin{array}{l}
x' = f' \frac{x}{z}=f'\frac{d-bz}{az},\\
y' = f' \frac{y}{z}=f'\frac{c}{z}.
\end{array}
\right.
\]
\else
\pagebreak
\fi
\item (7 points) It turns out $l'_1$ and $l'_2$ appear to converge on the intersection of the image plane $\Pi'$ given by $z=f'$ and the plane $y=0$. Explain why.
%Prove geometrically that $l_1'$ and $l_2'$ appear to converge on a horizontal line $H$, which is formed by the intersection of the image plane with the plane parallel to $\Pi$ and passing through the pinhole $O$.
\ifsolution
\ \\ \ \\
\textbf{Solution} \\
This is a parametric representation of the image $\delta$ of the line $\Delta$ with $z$ as the parameter. This image is
in fact only a half-line since when $z \rightarrow -\infty$, it stops at the point $(x',y')=(-f'\frac{b}{a},0)$ on the
$x'$ axis of the image plane. This is the vanishing point associated with all parallel lines with slope $-\frac{b}{a}$ in the
plane $\Pi$. All vanishing points lie on the $x'$ axis, which is the horizon line in this case.\\
\else
\pagebreak
\fi
\end{enumerate}


\setcounter{section}{2}
\section{Short Answer (38 points)}
\item \textbf{(5 points)} Given a dataset that consists of images of the Hoover tower, your task is to learn a classifier to detect the Hoover tower in new images. You implement PCA to reduce the dimensionality of your data, but find that your performance in detecting the Hoover tower significantly drops in comparison to your method on the original input data.  A sample of your input training images are given in Fig.~\ref{fig:cranes}.  Why is the performance suffering?

\begin{figure}[h!]
\centering
\subfloat{\includegraphics[width=2in]{hoover2.jpg}}
\subfloat{\includegraphics[width=2in]{hoover1.jpg}}
\subfloat{\includegraphics[width=2in]{hoover3.jpg}}
\caption{Example of input images}
\label{fig:cranes}
\end{figure}
\ifsolution
\ \\ \ \\
\large
\textbf{Solution}
\normalsize

The Hoover tower in the images are not aligned, thus applying PCA to reduce the dimensionality here will not preserve the performance of the algorithms since we are trying to extract some signal out of the tower.\\

\else
\pagebreak
\fi

\item \textbf{(5 points)} You are using k-means clustering in color space to segment an image. However, you notice that although pixels of similar color are indeed clustered together into the same clusters, there are many discontiguous regions because these pixels are often not directly next to each other. Describe a method to overcome this problem in the k-means framework.
\ifsolution
\ \\ \ \\
\large
\textbf{Solution}
\normalsize
\\
Concatenate the coordinates $(x, y)$ with the color features as input to the k-means algorithm.\\

\else
\pagebreak
\fi

\item \textbf{(5 points)} To do face detection on your webcam, you implement boosting to learn a face detector using a variety of rectangle filters similar to the Viola-Jones detector. Some of the weak classifiers perform very well, resulting in near perfect performance, while some do even worse than random. As you are selecting your classifiers, you suddenly find that at a certain iteration $k$, the new classifier being selected and added in takes on a negative weight $\alpha_k$ in the final additive model. Explain why the negative weight appears, and justify your answer.
\ifsolution
\ \\ \ \\
\large
\textbf{Solution}
\normalsize
\\
The negative weights appear because of the classifiers that perform worse than random. Their $\beta_k$ value is greater than 1, causing the $\alpha_k$ value to be negative. An intuitive explanation for this is that we can invert the decision by a classifier that performs worse than chance to get a classifier better than chance. \\
\else
\pagebreak
\fi

\item \textbf{(5 points)} As shown in figure \ref{fig:cameras}, a point $Q$ is observed in a known (i.e. intrinsic parameters are calibrated) affine camera with image plane $\Pi_1$. Then you translate the camera parallel to the image plane with a known translation to a new image plane $\Pi_2$ and observe it again.
\begin{enumerate}[(a)]
\item (2 points) Draw the image points $Q_1'$ and $Q_2'$ on $\Pi_1$ and $\Pi_2$ on the left figure of Fig. \ref{fig:cameras}. Is it possible to find the depth of the 3D point $Q$ in this scenario? Briefly explain why.
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.45\linewidth]{cameras.png}
\includegraphics[width=0.45\linewidth]{cameras.png}
\caption{3D point reconstruction}
\label{fig:cameras}
\end{center}
\end{figure}
\ifsolution
\ \\ \ \\
\large
\textbf{Solution}
\normalsize \\
The solution of both parts is in figure \ref{fig:cameras_sol}.\\

No. We cannot determine point $Q$ because it can be any 3D point on the line.
\begin{figure}[h]
\begin{center}
\includegraphics[width=0.45\linewidth]{cameras_affine.png}
\includegraphics[width=0.45\linewidth]{cameras_perspective.png}
\caption{3D point reconstruction}
\label{fig:cameras_sol}
\end{center}
\end{figure}
\else
\vspace{50mm}
\fi
\item (3 points) What if this is a perspective camera? Draw $Q_1'$ and $Q_2'$ on the right figure of Fig. \ref{fig:cameras}. Is it possible to find the depth of the 3D point $Q$ in this scenario? Briefly explain why.
\ifsolution
\ \\ \ \\
\large
\textbf{Solution}
\normalsize \\
Yes, because we can do triangulation in this case.
\else
\pagebreak
\fi
\end{enumerate}

\item \textbf{(6 points)} \textbf{Fundamental matrix estimation}
\begin{enumerate}[(a)]
 \item (2 points) What is the rank of the fundamental matrix?
\ifsolution
\ \\ \ \\
\large
\textbf{Solution}
\normalsize \\
The rank is 2.\\
\else
\vspace{50mm}
\fi
 \item (4 points) In the 8-point algorithm, what math technique is used to enforce the estimated fundamental matrix to have the proper rank? Explain how this math technique is used to enforce the proper matrix rank.\\
\ifsolution
\ \\ \ \\
\large
\textbf{Solution} \\
In the 8-point algorithm, SVD can be used to enforce the estimated $F$ has rank 2. Specifically, we compute the SVD
decomposition $F=U\Sigma V$, and we then zero out diagnals of $\Sigma$ except for the two largest singular values to
obtain $\tilde{\Sigma}$. We can reconstruct $F=U\tilde{\Sigma}V$.\\
\else
\pagebreak
\fi
\end{enumerate}


\textbf{Note}: All of the following questions require you to specify whether the given statement is true or false and provide an explanation. No credit will be awarded without a valid explanation. Please limit your explanation to \textbf{1 -- 2 lines}.

\begin{figure}[h!]
\centering
\subfloat{\includegraphics[width=2in]{cat1.jpg}}
\subfloat{\includegraphics[width=2in]{cat2.jpg}}
\subfloat{\includegraphics[width=2in]{cat3.jpg}}
\caption{Example of input images}
\label{fig:cats}
\end{figure}

\item \textbf{(3 points)} True / False : Given a set of 3 images as shown in Fig.~\ref{fig:cats}, finding and labeling the image in the center as "containing cat" is considered a {\em detection} task in recognition. Why or why not?
\ifsolution
\\
\\
\large \textbf{Solution} \normalsize \\
False. We are not localizing the cat in the image, so this is considered classification.
\else
\vspace{50mm}
\fi

\item \textbf{(3 points)} True / False : When doing face recognition, we are given a vector of features (usually pixel values) as the representation for each of the images in our training set. In order to compute the eigenfaces, we concatenate each of these vectors together into a matrix, and then find the eigenvectors of this matrix. Why or why not?
\ifsolution
\\
\\
\large \textbf{Solution} \normalsize \\
False. We compute the eigenfaces by finding the eigenvectors of the covariance matrix.
\else
\pagebreak
\fi


\item \textbf{(3 points)} True / False : Both Eigenfaces and Fisherfaces are unsupervised methods. That is, they are able to operate on data without having to provide labels for the instances. Why or why not?
\ifsolution
\\
\\
\large \textbf{Solution} \normalsize \\
False. Eigenfaces are indeed an unsupervised method, but Fisherfaces utilize class labels in the formulation.
\else
\vspace{80mm}
\fi

\item \textbf{(3 points)} True / False : If we initialize the k-means clustering algorithm with the same number of clusters but different starting positions for the centers, the algorithm will always converge to the same solution. Why or why not?
\ifsolution
\\
\\
\large \textbf{Solution} \normalsize \\
False. Different initializations will result in different clusters because they are local minima.
\else
\pagebreak
\fi
\end{enumerate}

\end{document}
