\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{gastex}
%\usepackage{ngerman}
\usepackage{wasysym}
\usepackage{rotating}

\title{\textsc{Differential Equations in Image Processing and Computer Vision \\ \large Assignment T4}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \\ Group 2: Thu, 12-14 (Markus Mainberger)}% \and \shortstack[c]{name\\ \scriptsize matr}}
\date{}

\pagestyle{fancy}

\lhead{Assignment T4}
\chead{}
\rhead{Dithmar (2031259)}
\lfoot{DIC}
\cfoot{Page \thepage}
\rfoot{SS 2008}

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

\maketitle

\thispagestyle{empty}

\begin{center}
	\begin{tabular}{p{1.5cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}||p{1.5cm}c}
		\centering 1 & \centering 2 & \centering 3 & \centering 4 & \centering$\sum$ & \\ \hline
		\phantom{x} & \phantom{x} & \phantom{x} & \phantom{x} & \phantom{x}
	\end{tabular}
\end{center}

\newpage
\setcounter{page}{1}
\setcounter{section}{4}

\exercise{Continuous Variational Regularisation}
We have
$$E_f(u) = \int_\Omega \left( \Psi_1 \left((u-f)^2\right) + \alpha \Psi_2\left(|\nabla u|^2\right) \right) d\textbf{x}$$
with
\begin{eqnarray*}
	\Psi_1(s^2) & = & \sqrt{s^2 + \varepsilon^2} \\
	\Psi_2(s^2) & = & \lambda^2 \log\left(1 + s^2/\lambda^2\right)
\end{eqnarray*}
and $\alpha, \varepsilon, \lambda > 0$. \\
It follows:
$$E_f(u) = \int_\Omega \left(\sqrt{(u-f)^2 + \varepsilon^2} + \alpha \lambda^2 \log\left(1 + |\nabla u|^2 / \lambda^2\right)\right) d\textbf{x}$$
We have
$$E_f(u) = \int_\Omega F(x_1, x_2, u, u_{x_1}, u_{x_2}) d\textbf{x}$$
which has to satisfy the Euler-Lagrange equation
$$F_u - \partial_{x_1} F_{u_{x_1}} - \partial_{x_2} F_{u_{x_2}} = 0$$
with the boundary condition
$$\textbf{n}^\top \left(\begin{array}{c} F_{u_{x_1}} \\ F_{u_{x_2}}\end{array}\right) = 0.$$
\begin{eqnarray*}
	F & = & \sqrt{(u-f)^2 + \varepsilon^2}+ \alpha \lambda^2 \log\left( 1 + |\nabla u|^2 / \lambda^2\right) \\
	F_u & = & \frac{1}{2} \cdot \left((u-f)^2 + \varepsilon^2\right)^{-\frac{1}{2}} \cdot 2(u-f) \\
	& = & \frac{u-f}{\sqrt{(u-f)^2 + \varepsilon^2}} \\
	F_{u_{x_1}} & = & \alpha \lambda^2 \frac{1}{1 + |\nabla u|^2 / \lambda^2} 2 u_{x_1} / \lambda^2 \\
	& = & 2 \alpha \frac{u_{x_1}}{1 + |\nabla u|^2 / \lambda^2} \\
	F_{u_{x_2}} & = & \alpha \lambda^2 \frac{1}{1 + |\nabla u|^2 / \lambda^2} 2 u_{x_2} / \lambda^2 \\
	& = & 2 \alpha \frac{u_{x_2}}{1 + |\nabla u|^2 / \lambda^2}
\end{eqnarray*}
Just plugging in the results into the Euler-Lagrange equation yields
\begin{eqnarray*}
	\frac{u-f}{\sqrt{(u-f)^2 + \varepsilon^2}} - \partial_{x_1} 2 \alpha \frac{u_{x_1}}{1 + |\nabla u|^2 / \lambda^2} - \partial_{x_2} 2 \alpha \frac{u_{x_2}}{1 + |\nabla u|^2 / \lambda^2} & = & 0 \\
	\frac{u-f}{\sqrt{(u-f)^2 + \varepsilon^2}} - 2 \alpha \partial_{x_1} \frac{u_{x_1}}{1 + |\nabla u|^2 / \lambda^2} - 2 \alpha \partial_{x_2} \frac{u_{x_2}}{1 + |\nabla u|^2 / \lambda^2} & = & 0 \\
	\frac{u-f}{\sqrt{(u-f)^2 + \varepsilon^2}} - 2 \alpha \mbox{ div} \left(\frac{\nabla u}{1 + |\nabla u|^2 / \lambda^2}\right) & = & 0
\end{eqnarray*}
with the boundary condition
$$\textbf{n}^\top \left(\begin{array}{c}F_{u_{x_1}} \\ F_{u_{x_2}}\end{array}\right) = 0.$$
This knowledge allows to formulate the gradient descent:
\begin{eqnarray*}
	\partial_t u & = & - \gamma \nabla_u E \\
	& = & - \gamma \cdot \left(\frac{u-f}{\sqrt{(u-f)^2 + \varepsilon^2}} - 2 \alpha \mbox{ div} \left(\frac{\nabla u}{1 + |\nabla u|^2 / \lambda^2}\right)\right)
\end{eqnarray*}

\exercise{Rotation Invariance of Energy Functionals}
In both cases it should hold the following:
$$\Psi (u_x, u_y) = \Psi (u_\xi, u_\eta)$$
\begin{enumerate}
	\item $\Psi (u_x, u_y) = |u_x| + |u_y|$. \\
		It follows that $\Psi(u_\xi, u_\eta) = |u_\xi| + |u_\eta|$. From the hint we can get the following for $u_\xi$ and $u_\eta$:
		\begin{eqnarray*}
			u_\xi & = & u_x \cdot \cos \vartheta + u_y \cdot \sin \vartheta \\
			u_\eta & = & - u_x \cdot \sin \vartheta + u_y \cdot \cos \vartheta
		\end{eqnarray*}
		$$\Rightarrow \Psi (u_\xi, u_\eta) = |u_x \cdot \cos \vartheta + u_y \cdot \sin \vartheta| + |-u_x \cdot \sin \vartheta + u_y \cdot \cos \vartheta|$$
		Let's have a look at the case that $\vartheta = \frac{\pi}{4}$. Then we get
		$$\Psi (u_\xi, u_\eta) = \frac{\sqrt{2}}{2} (|u_x + u_y| + |u_y - u_x|) \neq |u_x| + |u_y| = \Psi(u_x, u_y)$$
		Thus $\Psi(u_x, u_y) = |u_x| + |u_y|$ is not rotaionally invariant.
	\item $\Psi(u_x, u_y) = u_x^2 + u_y^2$. \\
		It follows $\Psi(u_\xi, u_\eta) = u_\xi^2 + u_\eta^2$. Using again the hint, we get for $u_\xi$ and $u_\eta$ the same as above.
		\begin{eqnarray*}
			\Rightarrow \Psi(u_\xi, u_\eta) & = & (u_x \cdot \cos \vartheta + u_y \cdot \sin \vartheta)^2 + (u_y \cdot \cos \vartheta - u_x \sin \vartheta)^2 \\
			& = & u_x^2 \cos^2 \vartheta + 2 u_x u_y \cos \vartheta \sin \vartheta + u_y^2 \sin^2 \vartheta \\
			& & + u_y^2 \cos^2 \vartheta - 2 u_x u_y \cos \vartheta \sin \vartheta + u_x^2 \sin^2 \vartheta \\
			& = & u_x^2 (\underbrace{\cos^2 \vartheta + \sin^2 \vartheta}_{=1}) + u_y^2 (\underbrace{\cos^2 \vartheta + \sin^2 \vartheta}_{=1}) \\
			& = & u_x^2 + u_y^2 = \Psi (u_x, u_y)
		\end{eqnarray*}
		Thus $\Psi (u_x, u_y) = u_x^2 + u_y^2$ is rotationally invariant.
\end{enumerate}

\exercise{Discrete Energy Minimisation}
$$E_f(u_1, ..., u_N) = \sum_{k=1}^N (u_k - f_k)^2 + \alpha \sum_{k=1}^{N-1} (u_{k+1} - u_k)^2 + \beta \sum_{k=2}^{N-1} (u_{k+1} - 2u_k + u_{k-1})^2$$
\begin{enumerate}
	\item Setting $\frac{\partial E}{\partial u_i} = 0$ for $i=1,...,N$ gives
		\begin{eqnarray*}
			0 & = & 2(u_1 - f_1) - 2 \alpha (u_2 - u_1) + 2 \beta (u_3 - 2u_2 + u_1) \\
			& = & u_1 - f_1 - \alpha (u_2 - u_1) + \beta (u_3 - 2u_2 + u_1) \\[0.3cm]
			0 & = & 2 (u_2 - f_2) - 2 \alpha (u_3 - u_2) + 2 \alpha (u_2 - u_1) + 2 \beta (u_4 - 2u_3 + u_2) \\
			& & - 4 \beta (u_3 - 2u_2 + u_1) \\
			& = & u_2 - f_2 - \alpha (u_3 - u_2) + \alpha (u_2 - u_1) + \beta (u_4 - 2u_3 + u_2) \\
			& & - 2 \beta (u_3 - 2u_2 + u_1) \\
			0 & = & 2 (u_i - f_i) - 2 \alpha (u_{i+1} - u_i) + 2 \alpha (u_i - u_{i-1}) \\
			& & + 2 \beta (u_{i+2} - 2u_{i+1} + u_i) - 4 \beta (u_{i+1} - 2 u_i + u_{i-1}) \\
			& & + 2 \beta (u_i - 2u_{i-1} + u_{i-2}) \quad \quad \quad (i = 3,...,N-2) \\
			& = & (u_i - f_i) - \alpha (u_{i+1} - u_i) + \alpha (u_i - u_{i-1}) \\
			& & + \beta (u_{i+2} - 2u_{i+1} + u_i) - 2 \beta (u_{i+1} - 2 u_i + u_{i-1}) \\
			& & + \beta (u_i - 2u_{i-1} + u_{i-2}) \quad \quad \quad (i = 3,...,N-2)
		\end{eqnarray*}
		\begin{eqnarray*}
			0 & = & 2(u_{N-1} - f_{N-1}) - 2 \alpha (u_N - u_{N-1}) + 2 \alpha (u_{N-1} - u_{N-2})  \\
			& & - 4 \beta (u_N - 2u_{N-1} + u_{N-2}) + 2 \beta (u_{N-1} - 2 u_{N-2} + u_{N-3}) \\
			& = & u_{N-1} - f_{N-1} - \alpha (u_N - u_{N-1}) + \alpha (u_{N-1} - u_{N-2}) \\
			& & - 2 \beta (u_N - 2u_{N-1} + u_{N-2}) + \beta (u_{N-1} - 2u_{N-2} + u_{N-3}) \\[0.3cm]
			0 & = & 2 (u_N - f_N) +  2 \alpha (u_N - u_{N-1}) - 2 \beta (u_N - 2u_{N-1} + u_{N-2}) \\
			& = & u_N - f_N + \alpha (u_N - u_{N-1}) - \beta (u_N - 2u_{N-1} + u_{N-2})
		\end{eqnarray*}
	\item I would say that the terms where a $\beta$ stands in front of are the discretisations of the fourth order derivatives. If you combine these terms to one term you get a structure where $u_{i+2}, u_{i+1}, u_i, u_{i-1}, u_{i-2}$ are involved, so this is not a second order but a fourth order derivative.
\end{enumerate}

\exercise{Half-Quadratic Regularisation}
$$E_f(u) = \int_\Omega \left( (u-f)^2 + \alpha 2 \lambda^2 \left(1 - \exp\left(- \frac{|\nabla u|^2}{2\lambda^2}\right)\right)\right) d \textbf{x}$$
I can rewrite this into
$$E_f(u) = \int_\Omega \left((u-f)^2 + \alpha \Psi\left(|\nabla u|^2\right)\right) d\textbf{x}$$
with
$$\Psi(|\nabla u|^2) = 2 \lambda^2 \left(1 - \exp\left(- \frac{|\nabla u|^2}{2\lambda^2}\right)\right)$$
\begin{eqnarray*}
	F & = & (u-f)^2 + \alpha \Psi\left(|\nabla u|^2\right) \\
	F_u & = & 2 (u-f) \\
	F_{u_{x_1}} & = & 2 \alpha \lambda^2 \left( -\exp\left(- \frac{|\nabla u|^2}{2\lambda^2}\right)\right) \cdot \left(-2 u_{x_1} / 2\lambda^2\right) \\
	& = & 2 \alpha u_{x_1} \exp\left(- \frac{|\nabla u|^2}{2\lambda^2}\right) \\
	F_{u_{x_2}} & = & 2 \alpha \lambda^2 \left( -\exp\left(- \frac{|\nabla u|^2}{2\lambda^2}\right)\right) \cdot \left(-2 u_{x_2} / 2\lambda^2\right) \\
	& = & 2 \alpha u_{x_2} \exp\left(- \frac{|\nabla u|^2}{2\lambda^2}\right)
\end{eqnarray*}
Its Euler-Lagrange equation is given by (divided by 2)
$$0 = (u-f) - \alpha \cdot \mbox{ div} \left(\underbrace{\exp\left(- \frac{|\nabla u|^2}{2\lambda^2}\right)}_{\Psi'(|\nabla u|^2)} \nabla u\right)$$
Let's formulate the energy functional for the Half-Quadratic case:
$$E_{HQ}(u,v) := \int_\Omega \left((u-f)^2 + \alpha (v \cdot |\nabla u|^2 + \eta(v))\right) d\textbf{x}$$
$E_{HQ}(u,v)$ has the two Euler-Lagrange equations:
\begin{eqnarray*}
	0 & = & (u-f) - \alpha \mbox{ div} (v \nabla u) \\
	0 & = & |\nabla u|^2 + \eta'(v)
\end{eqnarray*}
We know that
$$v := \Psi'(|\nabla u|^2) = \exp \left(- \frac{|\nabla u|^2}{2 \lambda^2}\right)$$
To obtain $|\nabla u|^2$, let's solve $v$ for $|\nabla u|^2$:
\begin{eqnarray*}
	v & = & \exp \left(- \frac{|\nabla u|^2}{2 \lambda^2}\right) \\
	\log(v) & = & - \frac{|\nabla u|^2}{2 \lambda^2} \\
	|\nabla u|^2 & = & - \log(v) \cdot 2 \lambda^2 \\
	& = & -2\lambda^2 \cdot \log(v)
\end{eqnarray*}
Then we can rewrite the Euler-Lagrange equations
\begin{eqnarray*}
	0 & = & (u-f) - \alpha \mbox{ div} (v \nabla u) \\
	0 & = & |\nabla u|^2  \underbrace{-2 \lambda^2 \log(v)}_{= \eta'(v)}
\end{eqnarray*}
We know that $\eta'(v) = -2 \lambda^2 \log(v)$ and thus
$$\eta(v) = -2 \lambda^2 v(\log(v) - 1)$$
This gives
$$E_{HQ}(u,v) := \int_\Omega \left( (u-f)^2 + \alpha (v |\nabla u|^2 - 2 \lambda^2 v (\log(v) - 1))\right) d\textbf{x}$$

\end{document}
