\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{Image Processing and Computer Vision \\ \large Assignment T4}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \\[0.5cm] Group T1: Tue, 14-16 (Sebastian Zimmer)}% \and \shortstack[c]{name\\ \scriptsize matr}}
\date{}

\pagestyle{fancy}

\lhead{Assignment T4}
\chead{}
\rhead{Dithmar (2031259)}
\lfoot{IPCV}
\cfoot{Page \thepage}
\rfoot{WS 2007/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}

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

\exercise{Continuous Nonquadratic Variational Methods}
\begin{enumerate}
	\item To state the Euler-Lagrange equations I have to compute the partial derivatives first, where I only look at the integrand
		$$F(x,u,u_x) = \left(\frac{1}{2} (u-f)^2 + \alpha \cdot \lambda^2 \cdot \sqrt{1 + \frac{u_x^2}{\lambda^2}}\right) dx$$
		
		\begin{eqnarray*}
			F_u & = & u - f \\
			F_{u_x} & = & \alpha \cdot \lambda^2 \cdot \frac{1}{2} \frac{1}{\sqrt{1 + \frac{u_x^2}{\lambda^2}}} \cdot \frac{2}{\lambda^2} \cdot u_x \\
			& = & \alpha \cdot \frac{1}{\sqrt{1 + \frac{u_x^2}{\lambda^2}}} \cdot u_x
		\end{eqnarray*}
		Now I can state the Euler-Lagrange equation:
		
		\begin{eqnarray*}
			0 & = & F_u - \frac{d}{dx} F_{u_x} = (u - f) - \frac{d}{dx} \frac{\alpha}{\sqrt{1 + \frac{u_x^2}{\lambda^2}}} \cdot u_x \\
			& = & (u - f) - \alpha \frac{d}{dx} \frac{1}{\sqrt{1 + \frac{u_x^2}{\lambda^2}}} \cdot u_x \\
			& = & u - f - \alpha \cdot \left(\frac{1}{\sqrt{1 + \frac{u_x^2}{\lambda^2}}} \cdot u_{xx} + \frac{d}{dx} \cdot \left(\frac{1}{\sqrt{1 + \frac{u_x^2}{\lambda^2}}}\right) \cdot u_x\right) \\
			& = & u - f - \alpha \cdot \left(\frac{1}{\sqrt{1 + \frac{u_x^2}{\lambda^2}}} \cdot u_{xx} + u_x \cdot \left(-\frac{1}{2}\right) \cdot 2 \cdot \frac{u_x \cdot u_{xx}}{\lambda^2 \cdot (1 + \frac{u_x^2}{\lambda^2})^{\frac{3}{2}}}\right) \\
			& = & u - f - \alpha \cdot \left(\frac{1}{\sqrt{1 + \frac{u_x^2}{\lambda^2}}} \cdot u_{xx} - u_x^2 \cdot u_{xx} \cdot \frac{1}{\lambda^2 \cdot (1 + \frac{u_x^2}{\lambda^2})^{\frac{3}{2}}}\right) \\
		\end{eqnarray*}
		
		\begin{eqnarray*}
			\phantom{0} & = & u - f - \alpha \cdot u_{xx} \cdot \left(\frac{1}{\sqrt{1 + \frac{u_x^2}{\lambda^2}}} - u_x^2 \cdot \frac{1}{\lambda^2 \cdot (1 + \frac{u_x^2}{\lambda^2})^{\frac{3}{2}}}\right) \\
			& = & u - f - \alpha \cdot u_{xx} \cdot \left(\frac{\lambda^2 \cdot (1 + \frac{u_x^2}{\lambda^2})}{\lambda^2 \cdot (1 + \frac{u_x^2}{\lambda^2})^{\frac{3}{2}}} - u_x^2 \cdot \frac{1}{\lambda^2 \cdot (1 + \frac{u_x^2}{\lambda^2})^\frac{3}{2}}\right) \\
			& = & u - f - \alpha \cdot u_{xx} \cdot \left(\frac{\lambda^2 + u_x^2 - u_x^2}{\lambda^2 \cdot (1 + \frac{u_x^2}{\lambda^2})^\frac{3}{2}}\right) \\
			& = & u - f - \alpha \cdot u_{xx} \cdot \frac{1}{(1 + \frac{u_x^2}{\lambda^2})^\frac{3}{2}}
		\end{eqnarray*}
		with boundary conditions
		$$F_{u_x} = 0$$
		in $x=a$ and $x=b$.
	\item $\lambda$ is some kind of contrast parameter. The idea is that if $|\nabla u|$ is greater than a certain "threshold" $\lambda$, you have locations where you have edges. This means that you can use this fact for edge preserving.
	\item First, one has to show that $E(u)$ is strictly convex. From the lecture (Lecture 15, slide 7) we know that it is helpful to use the fact that $g(s) = s^2$ is strictly convex. Furthermore, one has to show that
		$$E(\beta u + (1-\beta)v) < \beta E(u) + (1-\beta) E(v)$$
		which I will do first:
		\begin{eqnarray*}
			E(\beta u + (1-\beta) v) & = & \int_a^b \left(\frac{1}{2} ((\beta u + (1-\beta) v) - f)^2\right. \\
			& & \quad \quad \left. + \alpha \lambda^2 \sqrt{1 + \frac{(\beta u_x + (1-\beta) v_x)^2}{\lambda^2}}\right) dx \\[0.3cm]
			& = & \frac{1}{2} \cdot \int_a^b (\beta u + (1-\beta) v - f)^2 dx \\
			& & + \alpha \lambda^2 \int_a^b \sqrt{1 + \frac{(\beta u_x + (1-\beta) v_x)^2}{\lambda^2}} dx
		\end{eqnarray*}
		\begin{eqnarray*}
			\phantom{E(\beta u + (1-\beta) v)} & = & \frac{1}{2} \int_a^b (\beta (u-f) + (1-\beta) (v-f))^2 dx \\
			& & + \alpha \lambda^2 \int_a^b \sqrt{1 + \frac{(\beta u_x + (1-\beta) v_x)^2}{\lambda^2}} dx \\[0.3cm]
			& \stackrel{(*)}{<} & \frac{1}{2} \beta \int_a^b (u-f)^2 dx \\
			& & + \frac{1}{2} (1-\beta) \int_a^b (v-f)^2 dx \\
			& & \quad + \alpha \lambda^2 \int_a^b \sqrt{1 + \frac{(\beta u_x + (1-\beta) v_x)^2}{\lambda^2}} dx \\[0.3cm]
			& \stackrel{(**)}{<} & \frac{1}{2} \beta \int_a^b (u-f)^2 dx + \frac{1}{2} (1-\beta) \int_a^b (v-f)^2 dx \\
			& & + \alpha \lambda^2 \beta \int_a^b \sqrt{1 + \frac{u_x^2}{\lambda^2}} dx \\
			& & \quad + \alpha \lambda^2 (1-\beta) \int_a^b \sqrt{1 + \frac{v_x^2}{\lambda^2}} dx \\[0.3cm]
			& = & \beta \int_a^b \left(\frac{1}{2} (u-f)^2 + \alpha \lambda^2 \sqrt{1 + \frac{u_x^2}{\lambda^2}}\right) dx \\
			& & + (1-\beta) \int_a^b \left(\frac{1}{2}(v-f)^2 + \alpha \lambda^2 \sqrt{1 + \frac{v_x^2}{\lambda^2}}\right) dx \\[0.3cm]
			& = & \beta \cdot E(u) + (1-\beta) \cdot E(v)
		\end{eqnarray*}
		where
		\begin{itemize}
			\item $(*)$: $g(s) = s^2$ is strictly convex.
			\item $(**)$: $g(y) = \sqrt{1+y^2}$ is strictly convex. \\
				Proof:
				\begin{eqnarray*}
					f(x) & = & \sqrt{1 + \frac{x^2}{\lambda^2}} = \sqrt{1 + \left(\frac{x}{\lambda}\right)^2} \\
					\mbox{Substitution: } y & = & \frac{x}{\lambda} \\
					\Rightarrow g(y) & = & \sqrt{1 + y^2} \\[0.5cm]
					g_y & = & \frac{y}{\sqrt{1+y^2}} \\
					g_{yy} & = & \frac{1}{(1+y^2)^\frac{3}{2}}
				\end{eqnarray*}
				The second derivative is positive everywhere, so $g(y) = \sqrt{1+y^2}$ is strictly convex.
		\end{itemize}
		Result: This energy functional is strictly convex. From the lecture we know that the solution is unique and the single extremum of $E(u)$ is then a minimum.
\end{enumerate}

\exercise{Discrete Variational Methods}
\begin{enumerate}
	\item $$E_f(u) = \frac{1}{2} \cdot \sum_{k=1}^N (u_k - f_k)^2 + \alpha \cdot \lambda^2 \cdot \sum_{k=1}^{N-1} \sqrt{1 + \frac{(u_{k+1} - u_k)^2}{\lambda^2 \cdot h^2}}$$
		where the signal is given by $[u_1, \dots, u_N]$ and $h$ is the step-size.
	\item We know from the lecture (Lecture 15, slide 5) that the first partial derivatives w.r.t. $u_1, ..., u_N$ must vanish:
	
		\begin{eqnarray*}
			0 & = & \frac{\partial E_f}{\partial u_1} = u_1 - f_1 + \frac{\alpha}{h^2} \cdot \frac{u_2 - u_1}{\sqrt{1 + \frac{(u_2 - u_1)^2}{h^2 \cdot \lambda^2}}} \\[0.3cm]
			0 & = & \frac{\partial E_f}{\partial u_i} = u_i - f_i + \frac{\alpha}{h^2} \cdot \left(\frac{u_i - u_{i-1}}{\sqrt{1 + \frac{(u_i - u_{i-1})^2}{h^2 \cdot \lambda^2}}} - \frac{u_{i+1} - u_i}{\sqrt{1 + \frac{(u_{i+1} - u_i)^2}{h^2 \cdot \lambda^2}}}\right) \\[0.3cm]
			& & \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad  , i = 2, ..., N-1 \\[0.3cm]
			0 & = & \frac{\partial E_f}{\partial u_N} = u_N - f_N + \frac{\alpha}{h^2} \cdot \frac{u_N - u_{N-1}}{\sqrt{1 + \frac{(u_N - u_{N-1})^2}{h^2 \cdot \lambda^2}}}
		\end{eqnarray*}
\end{enumerate}

\exercise{Wavelet Shrinkage}
\begin{enumerate}
	\item $$f=(3,4,1,-2,0,4,-2,-4)^\top$$
		We have
		\begin{eqnarray*}
			c_{j,k} & = & \frac{1}{\sqrt{2}} \cdot (c_{j-1,2k} + c_{j-1,2k+1}) \\
			d_{j,k} & = & \frac{1}{\sqrt{2}} \cdot (c_{j-1,2k} - c_{j-1,2k+1})
		\end{eqnarray*}
		and we start from $c_{0,k} = f_k$ for $k=0,...,N-1$ where $N=8$. \\
		Since $f$ has 8 components, we have the scale $j=1,2,3$:
		\begin{eqnarray*}
			c_{1,0} & = & \frac{1}{\sqrt{2}} \cdot (3 + 4) = \frac{1}{\sqrt{2}} \cdot 7 \\
			c_{1,1} & = & \frac{1}{\sqrt{2}} \cdot (1 + (-2)) = -\frac{1}{\sqrt{2}} \\
			c_{1,2} & = & \frac{1}{\sqrt{2}} \cdot (0 + 4) = 2\sqrt{2} \\
			c_{1,3} & = & \frac{1}{\sqrt{2}} \cdot (-2 + (-4)) = -3\sqrt{2} \\
			c_{2,0} & = & \frac{1}{\sqrt{2}} \cdot \left(\frac{1}{\sqrt{2}} \cdot 7 + \left(- \frac{1}{\sqrt{2}}\right)\right) = 3 \\
			c_{2,1} & = & \frac{1}{\sqrt{2}} \cdot (2\sqrt{2} + (-3\sqrt{2})) = -1 \\
			c_{3,0} & = & \frac{1}{\sqrt{2}} \cdot (3 + (-1)) = \sqrt{2}
		\end{eqnarray*}
		\begin{eqnarray*}
			d_{1,0} & = & \frac{1}{\sqrt{2}} \cdot (3 - 4) = -\frac{1}{\sqrt{2}} \\
			d_{1,1} & = & \frac{1}{\sqrt{2}} \cdot (1 - (-2)) = 3 \cdot \frac{1}{\sqrt{2}} \\
			d_{1,2} & = & \frac{1}{\sqrt{2}} \cdot (0 - 4) = -2\sqrt{2} \\
			d_{1,3} & = & \frac{1}{\sqrt{2}} \cdot (-2 - (-4)) = \sqrt{2} \\
			d_{2,0} & = & \frac{1}{\sqrt{2}} \cdot \left(\frac{1}{\sqrt{2}} \cdot 7 - \left(- \frac{1}{\sqrt{2}}\right)\right) = 4 \\
			d_{2,1} & = & \frac{1}{\sqrt{2}} \cdot (2\sqrt{2} - (-3\sqrt{2})) = 5 \\
			d_{3,0} & = & \frac{1}{\sqrt{2}} \cdot (3 - (-1)) = -\frac{1}{\sqrt{2}}
		\end{eqnarray*}
		From that, I can state the transformed signal:
		$$\Rightarrow \hat{f} = \left(\sqrt{2}, -\frac{1}{\sqrt{2}}, 4, 5, -\frac{1}{\sqrt{2}}, 3 \cdot \frac{1}{\sqrt{2}}, -2\sqrt{2}, \sqrt{2}\right)^\top$$
	\item The transformed signal $\hat{f}$ is approximately:
		$$\hat{f} = (1.4, -0.7, 4, 5, -0.7, 2.1, 2.8, 1.4)^\top$$
		Since we want to remove three coefficients, the threshold parameter $T$ has to be chosen s.t.
		$$3 \cdot \frac{1}{\sqrt{2}} \leq T$$
		Now I can state the signal after the hard wavelet shrinkage (without touching the scaling coefficient):
		$$\hat{f}' = (\sqrt{2}, 0, 4, 5, 0, 0, -2\sqrt{2}, 0)^\top$$
	\item Computing the backtransform of the signal $\hat{f}'$ looks like this: \\
		We have
		\begin{eqnarray*}
			c_{j,2k} & = & \frac{1}{\sqrt{2}} (c_{j+1,k} + d_{j+1,k}) \\
			c_{j,2k+1} & = & \frac{1}{\sqrt{2}} (c_{j+1,k} - d_{j+1,k})
		\end{eqnarray*}
		and use the scale $j=2,1,0$:
		\begin{eqnarray*}
			c_{2,0} & = & \frac{1}{\sqrt{2}} \left(\sqrt{2} + \left(-\frac{1}{\sqrt{2}}\right)\right) = \frac{1}{2} \\
			c_{2,1} & = & \frac{1}{\sqrt{2}} \left(\sqrt{2} - \left(-\frac{1}{\sqrt{2}}\right)\right) = \frac{3}{2} \\[0.5cm]
			c_{1,0} & = & \frac{1}{\sqrt{2}} (3 + 4) = 7 \cdot \frac{1}{\sqrt{2}} \\
			c_{1,1} & = & \frac{1}{\sqrt{2}} (3 - 4) = -\frac{1}{\sqrt{2}} \\
			c_{1,2} & = & \frac{1}{\sqrt{2}} (-1 + 5) = 2 \cdot \sqrt{2} \\
			c_{1,3} & = & \frac{1}{\sqrt{2}} (-1 - 5) = -3 \cdot \sqrt{2} \\[0.5cm]
			c_{0,0} & = & \frac{1}{\sqrt{2}} \left(7 \cdot \frac{1}{\sqrt{2}} + 0\right) = \frac{7}{2} \\
			c_{0,1} & = & \frac{1}{\sqrt{2}} \left(7 \cdot \frac{1}{\sqrt{2}} - 0\right) = \frac{7}{2} \\
			c_{0,2} & = & \frac{1}{\sqrt{2}} \left(-\frac{1}{\sqrt{2}} + 0\right) = -\frac{1}{2} \\
			c_{0,3} & = & \frac{1}{\sqrt{2}} \left(-\frac{1}{\sqrt{2}} - 0\right) = -\frac{1}{2} \\
			c_{0,4} & = & \frac{1}{\sqrt{2}} (2 \cdot \sqrt{2} + (-2 \cdot \sqrt{2})) = 0 \\
			c_{0,5} & = & \frac{1}{\sqrt{2}} (2 \cdot \sqrt{2} - (-2 \cdot \sqrt{2})) = 4 \\
			c_{0,6} & = & \frac{1}{\sqrt{2}} (-3 \cdot \sqrt{2} + 0) = -3 \\
			c_{0,7} & = & \frac{1}{\sqrt{2}} (-3 \cdot \sqrt{2} - 0) = -3
		\end{eqnarray*}
		Since $f_k' = c_{0,k}$, the signal is the following:
		$$f' = \left(\frac{7}{2}, \frac{7}{2}, -\frac{1}{2}, -\frac{1}{2}, 0, 4, -3, -3\right)^\top$$
\end{enumerate}

\end{document}
