\documentclass[12pt,a4paper]{article}

\usepackage{amstext}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{listings}
\usepackage{pstricks}
\usepackage{pst-plot}
\usepackage{wasysym}
\usepackage{rotating}
\usepackage{pifont}

\title{}
\author{}
\date{}

\pagestyle{fancy}

\lhead{Assignment 6}
\chead{}
\rhead{}
\lfoot{COPCV}
\cfoot{Page \thepage}
\rfoot{SS 2009}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\exercise}[1]{\subsection{#1}}
\renewcommand{\theenumi}{\textbf{\alph{enumi}}}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[2]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[#1]{#2}\\[0.2cm]
	\end{figure}
	}

\newcommand{\m}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\+}{\phantom{-}}
\newcommand{\f}{\frac}

\newcommand{\XMARK}{\ding{56}}
\newcommand{\CMARK}{\ding{52}}

%\maketitle

%\thispagestyle{empty}

%\newpage
\setcounter{page}{1}
\setcounter{section}{6}

\exercise{Warping and SOR}
\begin{enumerate}
	\item If we rearrange the two equations, we get
		\begin{eqnarray*}
			\alpha \Delta u^k - J_{13}^k & = & J_{11}^k du^k + J_{12}^k dv^k - \alpha \Delta du^k \\
			\alpha \Delta v^k - J_{23}^k & = & J_{12}^k du^k + J_{22}^k dv^k - \alpha \Delta dv^k
		\end{eqnarray*}
		\begin{eqnarray*}
			0 & = & [J_{11}^k]_{i,j} du_{i,j}^k + [J_{12}^k]_{i,j} dv_{i,j}^k + [J_{13}^k]_{i,j} - \alpha \sum \sum \frac{du_{\tilde{i},\tilde{j}}^k - du_{i,j}^k}{h_l^2} \\
			&& - \alpha \sum \sum \frac{u_{\tilde{i},\tilde{j}}^k - u_{i,j}^k}{h_l^2} \\
			0 & = & [J_{12}^k]_{i,j} du_{i,j}^k + [J_{22}^k]_{i,j} dv_{i,j}^k + [J_{23}^k]_{i,j} - \alpha \sum \sum \frac{dv_{\tilde{i},\tilde{j}}^k - dv_{i,j}^k}{h_l^2} \\
			&& - \alpha \sum \sum \frac{v_{\tilde{i},\tilde{j}}^k - v_{i,j}^k}{h_l^2}
		\end{eqnarray*}
		where the double-summation has the following arguments (they are omitted due to limited space):
		$$\sum_{l \in x,y} \sum_{(\tilde{i}, \tilde{j}) \in \mathcal{N}_l (i,j)}.$$
		From this we have to go to an equation system of the form $A\textbf{x} = \textbf{b}$. Let's define the following:
		\begin{eqnarray*}
			\textbf{x} & := & \left(\begin{array}{c}du^k \\ du^k \\ du^k \\ dv^k \\ dv^k \\ dv^k\end{array}\right) \\
			\textbf{b} & := & \left(\begin{array}{c}J_{13}^k \\ J_{13}^k \\ J_{13}^k \\ J_{23}^k \\ J_{23}^k \\ J_{23}^k\end{array}\right) - \alpha D \left(\begin{array}{c}u^k \\ u^k \\ u^k \\ v^k \\ v^k \\ v^k\end{array}\right)
		\end{eqnarray*}
		
		\begin{eqnarray*}
			A & := & \left(\begin{array}{cccccc}J_{11}^k & & & J_{12}^k \\ & J_{11}^k & & & J_{12}^k \\  & & J_{11}^k & & & J_{12}^k \\ J_{12}^k & & & J_{22}^k \\ & J_{12}^k & & & J_{22}^k \\ & & J_{12}^k & & & J_{22}^k\end{array}\right) \\
			&& + \alpha \underbrace{\left(\begin{array}{rrrrrr}1 & -1 \\ -1 & 2 & -1 \\ & -1 & 1 \\ & & & 1 & -1 \\ & & & -1 & 2 & -1 \\ & & & & -1 & 1\end{array}\right)}_{=:D}
		\end{eqnarray*}
	\item The structure of the double-summation is slightly changed here, since one sometimes needs $\mathcal{N}_l^-$ (newly computed) and $\mathcal{N}_l^+$ (old ones). First, we compute the Gau\ss-Seidel method. After that, the step to SOR is very easy.
		{\scriptsize
		\begin{eqnarray*}
			\tilde{du}_{i,j}^{m+1,k} & = & \frac{\alpha \sum \sum \frac{u_{\tilde{i},\tilde{j}}^k - u_{i,j}^k}{h_l^2} - [J_{13}^k]_{i,j} - \left([J_{12}^k]_{i,j} dv_{i,j}^{m,k} - \alpha \sum \sum_{\mathcal{N}_l^-} \frac{du_{\tilde{i},\tilde{j}}^{m+1,k}}{h_l^2} - \alpha \sum \sum_{\mathcal{N}_l^+} \frac{du_{\tilde{i},\tilde{j}}^{m,k}}{h_l^2}\right)}{[J_{11}]_{i,j} + \alpha \sum \sum \frac{1}{h_l^2}} \\
			\tilde{dv}_{i,j}^{m+1,k} & = & \frac{\alpha \sum \sum \frac{v_{\tilde{i},\tilde{j}}^k - v_{i,j}^k}{h_l^2} - [J_{23}^k]_{i,j} - \left([J_{12}^k]_{i,j} {\color{red}{du_{i,j}^{m+1,k}}} - \alpha \sum \sum_{\mathcal{N}_l^-} \frac{dv_{\tilde{i},\tilde{j}}^{m+1,k}}{h_l^2} - \alpha \sum \sum_{\mathcal{N}_l^+} \frac{dv_{\tilde{i},\tilde{j}}^{m,k}}{h_l^2}\right)}{[J_{22}]_{i,j} + \alpha \sum \sum \frac{1}{h_l^2}}
		\end{eqnarray*}
		}
		where $m$ is the iteration step and $k$ the warping level. \\
		Remark: In the formula for $\tilde{dv}_{i,j}^{m+1,k}$ appears $du_{i,j}$ with $m+1,k$. This is due to the fact that $du$ is already computed, assuming the ordering $du \rightarrow dv$ for the computation. \\
		Let's state the SOR step:
		\begin{eqnarray*}
			du_{i,j}^{m+1,k} & = & (1 - \omega) du_{i,j}^{m,k} + \omega \tilde{du}_{i,j}^{m+1,k} \\
			dv_{i,j}^{m+1,k} & = & (1 - \omega) dv_{i,j}^{m,k} + \omega \tilde{dv}_{i,j}^{m+1,k}
		\end{eqnarray*}
\end{enumerate}

\exercise{Photometric Invariants and Robustification}
\begin{enumerate}
	\item Let's first give an overview over the different properties where the following assumptions are considered:
	\begin{itemize}
		\item[\ding{172}] global multiplicative illumination changes
		\item[\ding{173}] shadow and shading (local multiplicative changes)
		\item[\ding{174}] highlights and specular reflections (local additive / local multiplicative changes)
	\end{itemize}
	\begin{center}
		\begin{tabular}{cccc}
		& \ding{172} & \ding{173} & \ding{174} \\ \hline
		$p_1$ & \XMARK & \XMARK & \XMARK \\ \hline
		$p_2$ & \XMARK & \XMARK & \XMARK \\ \hline
		$p_3$ & \CMARK & \CMARK & \XMARK \\ \hline
		$p_4$ & \CMARK & \CMARK & \CMARK \\ \hline
		$p_5$ & \CMARK & \XMARK & \XMARK \\ \hline
		$p_6$ & \CMARK & \XMARK & \XMARK
		\end{tabular}
	\end{center}
	For the decision, what classes do apply, we consider Lecture 5, slide 21.
	\begin{enumerate}[1.]
		\item
			\begin{eqnarray*}
				p_1 & = & R - 3B + G \\
				& = & e\left(m_i(\textbf{x}) w_i + m_b(\textbf{x}) \hat{R_b}(\textbf{x})\right) - 3e\left(m_i(\textbf{x}) w_i + m_b(\textbf{x}) \hat{B_b}(\textbf{x})\right) \\
				&& + e\left(m_i(\textbf{x})w_i + m_b(\textbf{x}) \hat{G_b} (\textbf{x}\right) \\
				& = & e\left(-m_i(\textbf{x}) w_i + m_b(\textbf{x})(\hat{R_b}(\textbf{x}) - 3 \hat{B_b}(\textbf{x}) + \hat{G_b}(\textbf{x}))\right)
			\end{eqnarray*}
		\item Here we have an invariance under local additive changes only.
			\begin{eqnarray*}
				p_2 & = & R^2 + B^2 - 2BR = (R-B)^2 \\
				& = & \left[e\left(m_i(\textbf{x})w_i + m_b(\textbf{x}) \hat{R_b}(\textbf{x}) - m_i(\textbf{x})w_i - m_b(\textbf{x}) \hat{B_b}(\textbf{x})\right)\right]^2 \\
				& = & \left[e m_b(\textbf{x}) (\hat{R_b}(\textbf{x}) - \hat{B_b}(\textbf{x}))\right]^2 \\
				& = & e^2 m_b(\textbf{x})^2 (\hat{R_b}(\textbf{x}) - \hat{B_b}(\textbf{x}))^2
			\end{eqnarray*}
		\item
			\begin{eqnarray*}
				p_3 & = & \frac{R-B}{R+G} \\
				& = & \frac{e\left(m_i(\textbf{x})w_i + m_b(\textbf{x}) \hat{R_b}(\textbf{x}) - m_i(\textbf{x})w_i - m_b(\textbf{x}) \hat{B_b}(\textbf{x})\right)}{e\left(m_i(\textbf{x})w_i + m_b(\textbf{x}) \hat{R_b}(\textbf{x}) + m_i(\textbf{x})w_i + m_b(\textbf{x}) \hat{G_b}(\textbf{x})\right)} \\
				& = & \frac{m_b(\textbf{x}) \left(\hat{R_b}(\textbf{x}) - \hat{B_b}(\textbf{x})\right)}{2 m_i(\textbf{x})w_i + m_b(\textbf{x}) \left(\hat{R_b}(\textbf{x}) + \hat{B_b}(\textbf{x})\right)} \\
				& = & \frac{\hat{R_b}(\textbf{x}) - \hat{B_b}(\textbf{x})}{\hat{R_b}(\textbf{x}) + \hat{B_b}(\textbf{x})} \quad \text{ if } m_i(\textbf{x}) = 0.
			\end{eqnarray*}
		\item
			\begin{eqnarray*}
				p_4 & = & 2 \frac{BG+RG}{B^2 - R^2} - \frac{B+R}{B-R} \\
				& = & 2 \frac{G(B+R)}{(B-R)(B+R)} - \frac{B+R}{B-R} = \frac{2G - B - R}{B-R} \\
				& = & \frac{m_b(\textbf{x}) \left(2 \hat{G_b}(\textbf{x}) - \hat{B_b}(\textbf{x}) - \hat{R_b}(\textbf{x})\right)}{m_b(\textbf{x}) \left(\hat{B_b}(\textbf{x}) - \hat{R_b}(\textbf{x})\right)} \\
				& = & \frac{2 \hat{G_b}(\textbf{x}) - \hat{B_b}(\textbf{x}) - \hat{R_b}(\textbf{x})}{\hat{B_b}(\textbf{x}) - \hat{R_b}(\textbf{x})}
			\end{eqnarray*}
		\item Let's consider the following fact
			$$\ln(\underbrace{c}_{\text{factor}} B)_x = (\underbrace{\ln c}_{\text{constant}} + \ln B)_x = (\ln B)_x$$
			\begin{eqnarray*}
				p_5 & = & (\ln B)_x + (\ln R)_x \\
				& = & \frac{1}{\left[e(m_i(\textbf{x})w_i + m_b(\textbf{x}) \hat{B_b}(\textbf{x}))\right]_x} + \frac{1}{\left[e(m_i(\textbf{x})w_i + m_b(\textbf{x}) \hat{R_b}(\textbf{x}))\right]_x}
			\end{eqnarray*}
		\item Invariant under global additive only.
			\begin{eqnarray*}
				p_6 & = & \ln B_x + \ln R_x = \ln (B_x \cdot R_x) \\
				& = & \ln \left[\left(e(m_i(\textbf{x})w_i + m_b(\textbf{x}) \hat{B_b}(\textbf{x}))\right)_x \cdot \left(e(m_i(\textbf{x})w_i + m_b(\textbf{x}) \hat{R_b}(\textbf{x}))\right)_x\right]
			\end{eqnarray*}
	\end{enumerate}
	\item We consider here
		$$\Psi(s^2) = \sqrt{s^2 + \varepsilon^2} \quad \text{ with } \varepsilon = 10^{-3}.$$
		Let's give the joint robustification
		\begin{eqnarray*}
			E_{joint}(u,v) & = & \int_\Omega \Psi \left(\sum_{i=1}^6 \left(p_i(x+u, y + v, t+1) - p_i(x,y,t)\right)^2\right) \\
			&& \quad + \alpha \left(|\nabla u|^2 + |\nabla v|^2\right) \; \mathrm dx \mathrm dy
		\end{eqnarray*}
	\item Joint robustification was given in part \textbf{b.}. Separate robustification is given by
		\begin{eqnarray*}
			E_{sep}(u,v) & = & \int_\Omega \sum_{i=1}^6 \Psi\Big(\big(p_i(x+u, y + v, t+1) - p_i(x,y,t)\big)^2\Big) \\
			&& \quad + \alpha \left(|\nabla u|^2 + |\nabla v|^2\right) \; \mathrm dx \mathrm dy
		\end{eqnarray*}
		The Euler-Lagrange equations that have to be satisfied are
		\begin{eqnarray*}
			0 & = & F_u - \frac{\partial}{\partial x} F_{u_x} - \frac{\partial}{\partial y} F_{u_y} \\
			0 & = & F_v - \frac{\partial}{\partial x} F_{v_x} - \frac{\partial}{\partial y} F_{v_y}
		\end{eqnarray*}
		\begin{itemize}
			\item joint robustification:
				\begin{eqnarray*}
					F & = & \Psi \left(\sum_{i=1}^6 \left(p_i(x+u, y + v, t+1) - p_i(x,y,t)\right)^2\right) \\
					&& \quad + \alpha \left(|\nabla u|^2 + |\nabla v|^2\right) \\
					F_u & = & 2 \cdot \Psi'(...) \\
					&& \cdot \sum_{i=1}^6 (p_i(x+u,y+v,t+1) - p_i(x,y,t)) \\
					&& \quad \quad \cdot p_{i_x} (x+u,y+v,t+1) \\
					F_v & = & 2 \cdot \Psi'(...) \\
					&& \cdot \sum_{i=1}^6 (p_i(x+u,y+v,t+1) - p_i(x,y,t)) \\
					&& \quad \quad \cdot p_{i_y} (x+u,y+v,t+1) \\
					F_{u_x} & = & 2 \alpha u_x \\
					F_{u_y} & = & 2 \alpha u_y \\
					F_{v_x} & = & 2 \alpha v_x \\
					F_{v_y} & = & 2 \alpha v_y
				\end{eqnarray*}
				The Euler-Lagrange equations now read as (divided by 2):
				{\scriptsize
				\begin{eqnarray*}
					0 & = & \Psi'(...) \Big(\sum_{i=1}^6 (p_i(x+u,y+v,t+1) - p_i(x,y,t)) p_{i_x} (x+u, y+v, t+1)\Big) - \alpha \Delta u \\
					0 & = & \Psi'(...) \Big(\sum_{i=1}^6 (p_i(x+u,y+v,t+1) - p_i(x,y,t)) p_{i_y} (x+u, y+v, t+1)\Big) - \alpha \Delta v
				\end{eqnarray*}
				}
			\item separate robustification:
				\begin{eqnarray*}
					F & = & \sum_{i=1}^6 \Psi_\Big(\big(p_i(x+u, y + v, t+1) - p_i(x,y,t)\big)^2\Big) \\
					&& \quad + \alpha \left(|\nabla u|^2 + |\nabla v|^2\right) \\
					F_u & = & 2 \cdot \sum_{i=1}^6 \Psi'(...) \cdot (p_i(x+u,y+v,t+1) - p_i(x,y,t)) \\
					&& \quad \quad \quad \cdot p_{i_x} (x+u,y+v,t+1) \\
					F_v & = & 2 \cdot \sum_{i=1}^6 \Psi'(...) \cdot (p_i(x+u,y+v,t+1) - p_i(x,y,t)) \\
					&& \quad \quad \quad \cdot p_{i_y} (x+u,y+v,t+1) \\
					F_{u_x} & = & 2 \alpha u_x \\
					F_{u_y} & = & 2 \alpha u_y \\
					F_{v_x} & = & 2 \alpha v_x \\
					F_{v_y} & = & 2 \alpha v_y
				\end{eqnarray*}
				The Euler-Lagrange equations read as (again divided by 2):
				{\scriptsize
				\begin{eqnarray*}
					0 & = & \sum_{i=1}^6 \Big(\Psi'(...) (p_i(x+u,y+v,t+1) - p_i(x,y,t)) \cdot p_{i_x} (x+u,y+v,t+1)\Big) - \alpha \Delta u \\
					0 & = & \sum_{i=1}^6 \Big(\Psi'(...) (p_i(x+u,y+v,t+1) - p_i(x,y,t)) \cdot p_{i_y} (x+u,y+v,t+1)\Big) - \alpha \Delta v
				\end{eqnarray*}
				}
		\end{itemize}
\end{enumerate}

\end{document}
