\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amsopn}
\usepackage{graphicx}
\usepackage{color}
\usepackage{verbatim}
\usepackage{setspace}
\usepackage{gensymb}
\usepackage{float}
\usepackage[normalem]{ulem}
%\usepackage[dvips,bookmarks=false,colorlinks,urlcolor=blue,pdftitle={
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}

\def\vO{{\bf O}}
\def\vP{{\bf P}}
\def\vp{{\bf p}}
\def\vx{{\bf x}}
\def\vl{{\bf l}}
\def\mS{{\bf S}}
\def\mT{{\bf T}}
\def\mH{{\bf H}}
\def\mA{{\bf A}}
\def\tx{{\tilde{\bf x}}}
\def\ta{{\tilde{\bf a}}}
\def\tb{{\tilde{\bf b}}}
\def\tc{{\tilde{\bf c}}}
\def\hn{{\bf \hat{n}}}
\def\hv{{\bf \hat{v}}}
\def\hh{{\bf \hat{h}}}
\def\vh{{\bf h}}
\def\vs{{\bf s}}
\def\hs{{\bf \hat{s}}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\ud}{\,\mathrm{d}}

\usepackage[bookmarks=false,colorlinks,urlcolor=blue,pdftitle={Take-home Quiz 3},pdfauthor={Matthew O'Toole}]{hyperref}

\begin{document}

\begin{centering}
	{\large 16-385 Computer Vision, Fall 2020\\}
	\vspace{2ex}
	{\LARGE Take-home Quiz 3\\}
	\vspace{2ex}
	{\large Due Date: Monday October 5, 2020 23:59\\}
\end{centering}

\bigskip

\section*{Question 1 \emph{\small(5 points)}}

Given a set of $N$ points $\vp_i=(x_i,y_i), \, i=1,\dots,N,$ in the image plane, we wish to find the best line passing through those points. 
\begin{enumerate}
\item One way to solve this problem is to find $(a,b)$ that most closely satisfy the
equations $y_i=ax_i+b$, in a least-squares sense. Write these equations in the form of a \emph{heterogeneous} least-squares problem ${\bf A}\vx={\bf b}$, where
$\vx=(a,\ b)^\mathsf{T}$, and give an expression for the least-squares estimate
of $\vx$. Also, give a geometrical interpretation of the error being minimized, and use a simple graph to visualize the error.

\item Another way to solve the problem is to find $\boldsymbol\ell=(a,\ b,\ c)$
(defined up to scale) that most closely satisfies the equations $ax_i+by_i+c=0$, in a
least-squares sense. Write these equations in the form of a \emph{homogeneous} least-squares problem ${\bf A}\boldsymbol\ell = {\bf
0}$ where $\boldsymbol\ell=(a,\ b,\ c)^\mathsf{T}$ and $\boldsymbol\ell\ne{\bf 0}$.
This problem has a trivial solution (zero vector $\boldsymbol{0}$), which is not of
much use. Describe some ways to avoid this trivial solution, and corresponding algorithms for
solving the resulting optimization problem.
\end{enumerate}

\section*{Question 2 \emph{\small(5 points)}}

The equation for a conic in the plane using inhomogeneous coordinates
$(x,y)$ is
\begin{equation}\label{eq:conic}
ax^2+bxy+cy^2+dx+ey+f=0.
\end{equation}

\begin{enumerate}

\item Suppose you are given a set of inhomogeneous points $\tilde{\bf
x}_i=(x_i,y_i)$, $i=1,\ldots,N$. Derive an expression for the least squares
estimate of the conic ${\bf c}=(a,b,c,d,e,f)$ passing through those points.
(Your expression may take the form of a null vector or eigenvector of a matrix; if so, you must provide expressions for the matrix elements.)

\item In general, what is the minimum value of $N$ that allows a unique solution for ${\bf
c}$?

\item ``Homogenize'' Eq.~\ref{eq:conic} by making the substitutions
$x\rightarrow x_1/x_3$, $y\rightarrow x_2/x_3$, and show that in terms of
homogeneous coordinates (${\bf x}=(x_1,x_2,x_3)$) the conic can be expressed in
matrix form,
\begin{displaymath}
{\bf x}^\top{\bf C}{\bf x}=0,
\end{displaymath}
with a symmetric matrix ${\bf C}$.

\item Suppose we apply a projective transformation to our points: ${\bf
x}_i'={\bf H}{\bf x}_i$. The transformed points ${\bf x}_i'$ will lie on a
transformed conic represented by a new symmetric matrix ${\bf C}'$. Write an equation that specifies the relationship between  ${\bf C}'$ and ${\bf C}$, in terms of the homography ${\bf H}$.

\end{enumerate}

\section*{Instructions}

\begin{enumerate}
    \item \textbf{Integrity and collaboration:} Students are encouraged to work
    in groups but each student must submit their own work. If you work as a
    group, include the names of your collaborators in your write up. Plagiarism
    is strongly prohibited and may lead to failure of this course.

    \item \textbf{Questions:} If you have any questions, please look at Piazza
    first. Other students may have encountered the same problem, and it may be solved
    already. If not, post your question on the discussion board. Teaching staff will
    respond as soon as possible.

    \item \textbf{Write-up:} Your write-up should be typeset in \LaTeX and should consist of your answers to the theory questions. Please note that we
    \textbf{\color{red}do not} accept handwritten scans for your write-up in quizzes.

    \item \textbf{Submission:} Your submission for this take-home quiz should be a
    PDF file, \texttt{<andrew-id.pdf>}, with your write-up. \textbf{\color{red}Please do not submit ZIP files.}
\end{enumerate}

\end{document}
