\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}
\usepackage{mathdefs}

\def\bx{{\bf x}}
\def\by{{\bf y}}
\def\bp{{\bf p}}
\def\dbp{\Delta\bp}
\def\bW{{\bf W}}
\def\bz{{\bf z}}
\def\bb{{\bf b}}
\def\bzero{{\bf 0}}
\def\A{{\bf A}}
\def\V{{\bf V}}
\def\vl{{\bf l}}
\def\vm{{\bf m}}
\def\mS{{\bf S}}
\def\mT{{\bf T}}
\def\bH{{\bf H}}
\def\mA{{\bf A}}
\def\mM{{\bf M}}
\def\mP{{\bf P}}
\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{\Ev}{\mathbf{E}}
\newcommand{\Fv}{\mathbf{F}}

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

\begin{document}

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

\bigskip

\section*{Question 1}

In this quiz, you will derive the Lucas-Kanade (or forward-additive) image alignment algorithm. Consider first a \emph{warp function} $\bW\paren{\bx; \bp}$ that maps coordinate vectors $\bx\in\R^2$ to other coordinate vectors in $\R^2$, with the mapping depending on a set of parameters $\bp \in \R^N$. Given an image $I(\bx)$ and a template $T(\bx)$, we want to find the parameters $\bp$ such that the warp $\bW\paren{\bx; \bp}$ best aligns the image with the template in terms of sum-of-squared-differences (SSD) error. That is, we want to find the parameters $\bp$ that minimize the loss function:
\begin{equation}\label{eq:lk:nonlinear}
\min_\bp \sum_\bx \bracket{I\paren{\bW\paren{\bx;\bp}}-T\paren{\bx}}^2.
\end{equation}

The Lucas-Kanade alignment algorithm minimizes Equation~\eqref{eq:lk:nonlinear} using the Gauss-Newton algorithm. To this end, given some initial set of parameters $\bp^0$, they are updated iteratively as:
\begin{equation}\label{eq:lk:update}
\bp^{t+1} = \bp^{t} + \dbp^{t},
\end{equation}
for $t = 0,\dots,T$, where the number of iterations $T$ can be selected based on any of the common convergence criteria. Then, the Gauss-Newton algorithm corresponds to selecting a specific form for the update vector $\dbp^{t}$, which you will derive below step-by-step.

\begin{enumerate}

\item Use the first-order Taylor expansion to linearize the composite function $I\paren{\bW\paren{\bx;\bp}}$ with respect to $\bp$ around the value $\bp^{t}$. Write out the expression for this Taylor expansion.

\item Combine the Taylor expansion expression with Equation~\eqref{eq:lk:update}, to obtain an approximation for $I\paren{\bW\paren{\bx;\bp^t + \dbp^{t}}}$.

\item Show that, using this approximation, the optimization problem of Equation~\eqref{eq:lk:nonlinear} can be rewritten in the form:
\begin{equation}\label{eq:lk:linear}
\min_{\dbp^t} \norm{\A \dbp^t - \bb}^2,
\end{equation}
for some matrix $\A$ and vector $\bb$. 

\item Show how to solve the optimization problem of Equation~\eqref{eq:lk:linear} for the parameter update $\dbp^t$, and write out an expression for this solution.

\item Finally, explain how this expression for $\dbp^t$ can be evaluated, using image convolutions, warps, element-wise operations, and matrix-vector operations. You can either explain this in words or provide pseudocode, but make sure to explain each step clearly.

\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}
