% Template for MIA electronic tresentation, 2002, Pavel Mrazek
\documentclass[miaitalkstyle]{cmptalk-mia262}

\hypersetup{bookmarks=false,pdfstartpage=1}%,pdfpagemode=FullScreen}
%\hypersetup{pdftitle=,pdfauthor=,pdfsubject=,pdfkeywords=}

\usepackage{bigfig} % to make images full-screen on click
\usepackage{color}
\usepackage{graphicx}
\usepackage{texpower}

\definecolor{titleblue}{rgb}{0.05,0.2,0.75}
\newcommand{\important}[1]{{\textsl{\color{miared}{#1}}}}
\newcommand{\comments}[1]{}
\newcommand{\stitle}[1]{{\Large \bfseries \color{miablue}{#1}}}

\author{Jan Hendrik Dithmar \\ \texttt{jadi5003@stud.uni-saarland.de}}
\title{\color{miablue}{On Robust Estimation and Smoothing \\ with Spatial and Tonal Kernels}}

\begin{document}
\maketitle
\slidetitle{\normalsize\bfseries%
    Mathematical Image Analysis Group, Saarland University\\
    Seminar "Modern Methods in Image Analysis"
%    \href{http://www.mia.uni-saarland.de}{http://www.mia.uni-saarland.de}
}

\begin{center}
{\small Based on \\ "On Robust Estimation and Smoothing with Spatial and Tonal Kernels" \\ by P. Mr\'{a}zek, J. Weickert and A. Bruhn.}
\end{center}

%\subhead{Outline:}
%\begin{enumerate} 
%\end{enumerate}

% -----------------------------------------------------------------------
\foilhead{Motivation}

\stitle{Motivation}
\newline
\begin{itemize}
	\item Image denoising or simplification are well established nowadays. There exist several methods.
	\item Examples of different methods:
		\begin{itemize}
			\item Statistical estimation
			\item Histogram operations
			\item Local M-smoothers
%			\item Bayesian and regularisation frameworks
%			\item Diffusion filtering
			\item Bilateral filtering
			\item ...
		\end{itemize}
	\item Advantages of the various approaches and the relations between the different methods are only partially understood. \\
	\item What can be done to understand the different approaches in a better way?
\end{itemize}


% -----------------------------------------------------------------------
\foilhead{Methods}

\stitle{Statistical estimation}
\newline
\begin{itemize}
	\item Assume, $u$ being an \textsl{unknown (constant)} signal.% that is observed $N$-times.
	\item We have noisy samples $f_j$
		$$f_j = u + n_j \quad \quad (j = 1, ..., N)$$
		where $n$ stands for the noise.
%	\item Complications arise if $n$ is not normally distributed ($\rightarrow$ it might have heavier tails, i.e., more (distant) outliers in the data).
	\item Goal: Estimate $u$ ($\rightarrow$ M-Estimate).
	\item M-Estimate can be found by minimising the energy
		$$E(u) = \sum_{j=1}^N \Psi \left(|u - f_j|^2\right)$$
		where $\Psi$ is some increasing function (also called error norm or penaliser).
\end{itemize}

\newpage

{\color{miablue}{\textbf{Examples of error norms for M-estimators}}}

\begin{itemize}
	\item $\Psi(s^2) = s^2$
		\begin{itemize}
			\item minimises the $L^2$-distance $E(u) = \sum_{j=1}^N |u - f_j|^2$
			\item gives the arithmetic mean (good for removing Gaussian noise)
		\end{itemize}
		\begin{center}
			\includegraphics[height=0.2\textheight]{Pic/mean-visualisation-crop.pdf} \quad \quad
		\end{center}
	\item $\Psi(s^2) = |s|$
		\begin{itemize}
			\item minimises the $L^1$-distance $E(u) = \sum_{j=1}^N |u - f_j|$
			\item gives the median (good for removing impulse noise)
		\end{itemize}
		\begin{center}
			\includegraphics[height=0.2\textheight]{Pic/median-visualisation-crop.pdf}
		\end{center}
\end{itemize}

\newpage

\begin{itemize}
	\item $\Psi(s^2) = 1 - e^{-s^2 / \lambda^2}$
		\begin{itemize}
			\item mode approximation (influence of outliers is very much reduced)
		\end{itemize}
		\begin{center}
			\includegraphics[height=0.2\textheight]{Pic/modeapprox-visualisation-crop.pdf}
		\end{center}
\end{itemize}

What is the problem of this approach? \pause \textbf{We only get one estimate!}


% -----------------------------------------------------------------------
\foilhead{Methods}

\stitle{Histogram operations}
\newline
\begin{itemize}
	\item In image analysis, the data $f_j$ is measured at positions $x_j$.
	\item Usually, we want a solution $\textbf{u} = (u_i)_{i=1,...,N}$ where each output value $u_i$ belongs to the position $x_i$.
	\item Construction of M-estimates $u_i$ by minimising
		$$E(\textbf{u}) = \sum_{i=1}^N \sum_{j=1}^N \Psi \left(|u_i - f_j|^2\right)$$
\end{itemize}
%\pause
{\color{miablue}{\textbf{Minimising $E(\textbf{u})$}}}

\begin{itemize}
	\item $E(\textbf{u})$ can be minimised by gradient descent.
%	\item Reminder: Gradient descent (in the discrete case)
%		\begin{itemize}
%			\item We know that a minimiser of the energy functional $E(\textbf{u})$ with $\textbf{u} \in \mathbb{R}^n$ satisfies
%				$$\nabla_\textbf{u} E = 0$$
%			\item $\nabla_\textbf{u} E$ points in the direction of the steepest ascent.
%			\item Idea: Find a minimiser as the steady state of an evolution equation that slides downhill:
%				$$\partial_t \textbf{u} = - \gamma \nabla_\textbf{u} E$$
%				with an arbitrary speed factor $\gamma > 0$. The steady state is reached when $t \to \infty$.
%		\end{itemize}
%\end{itemize}

%\newpage

%\begin{itemize}
%	\item The gradient descent becomes in this case:
%	\item The ingredients
%		$$\tau := \frac{1}{2 \sum_{j=1}^N \Psi' \left(|u_i^k - f_j|^2\right)} \quad , \quad u_i^{k+1} = u_i^k - \tau \frac{\partial E}{\partial u_i} \quad , \quad g(s^2) := \Psi'(s^2)$$
%		become
	\item One can obtain the following iterative formula:
			$$u_i^0 = f_i \quad , \quad \quad u_i^{k+1} = \frac{\sum_{j=1}^N g\left(|u_i^k - f_j|^2\right) f_j}{\sum_{j=1}^N g\left(|u_i^k - f_j|^2\right)}$$
%			u_i^{k+1} & = & u_i^k - \tau \frac{\partial E}{\partial u_i} \\
%			& = & \left(1 - 2 \tau \sum_{i=1}^N \Psi' \left(|u_i^k - f_j|^2\right)\right) u_i^k \\
%			& & + 2 \tau \sum_{j=1}^N \Psi' \left(|u_i^k - f_j|^2\right) f_j
%		\end{eqnarray*}
%	\item $\tau$ is the step size. It can be chosen adaptively to the data.
%	\item Setting
%		$$\tau := \frac{1}{2 \sum_{j=1}^N \Psi' \left(|u_i^k - f_j|^2\right)}, \quad g(s^2) := \Psi'(s^2)$$
%		results in the iterative formula
%		$$u_i^{k+1} = \frac{\sum_{j=1}^N g\left(|u_i^k - f_j|^2\right) f_j}{\sum_{j=1}^N g\left(|u_i^k - f_j|^2\right)}$$
\end{itemize}


% -----------------------------------------------------------------------
\foilhead{Methods}

\stitle{Local M-smoothers}
\newline
\begin{itemize}
	\item Estimates the grey value of a pixel from a \textsl{local} neighbourhood only.
	\item Modification: introduction of a weighting term.% \\
%		It depends on the spatial distance between the position of $u_i$ and $f_i$, where $u_i$ is the restored pixel and $f_i$ the input sample.
		$$E_D(\textbf{u}) = \sum_{i=1}^N \sum_{j\in\mathcal{B}(i)} \Psi_D \left(|u_i - f_j|^2\right)  w_D \left(|x_i - x_j|^2\right)$$
		$\mathcal{B}(i)$ is introduced to make the index $j$ run through the neighbourhood of $x_i$.
%\pause
	\item Examples for weighting functions:
		\begin{itemize}
			\item hard disk-shaped window
				$$w(s^2) = \left\{\begin{array}{cl}1 & s^2 < \theta \\ 0 & \mbox{otherwise}\end{array}\right. \quad \quad \includegraphics[height=0.1\textheight]{Pic/hard_window-visualisation-crop.pdf}$$
			\item soft window
				$$w(s^2) = e^{-s^2/\theta^2} \quad \quad \quad \quad \quad \quad \includegraphics[height=0.1\textheight]{Pic/soft_window-visualisation-crop.pdf}$$
		\end{itemize}
\end{itemize}

\newpage

{\color{miablue}{\textbf{Minimising $E_D(\textbf{u})$}}}

\begin{itemize}
	\item Similarly to the minimisation of $E(\textbf{u})$ in the part about histogram operations, one can state an iterative formula:
		\begin{eqnarray*}
			u_i^0 & = & f_i \\
			u_i^{k+1} & = & \frac{\sum_{j \in \mathcal{B}(i)} {\color{blue}{g}}\left(|u_i^k - f_j|^2\right) {\color{red}{w}}\left(|x_i - x_j|^2\right) f_j}{\sum_{j \in \mathcal{B}(i)} {\color{blue}{g}}\left(|u_i^k - f_j|^2\right) {\color{red}{w}}\left(|x_i - x_j|^2\right)}
		\end{eqnarray*}
		where {\color{blue}{$g$}} is called the {\color{blue}{\textsl{tonal weight}}} and {\color{red}{$w$}} the {\color{red}{\textsl{spatial weight}}}.
	\item This procedure is called the \important{W-estimator}. It is one possibility to obtain a solution to the local M-estimation problem.
	\item Note: \\
		One is only interested here in the \important{steady state} for $k \to \infty$, not in the evolution towards the minimiser.
\end{itemize}

% -----------------------------------------------------------------------
%\foilhead{Methods}

%\stitle{Bayesian and regularisation frameworks}
%\newline
%\begin{itemize}
%	\item Taking the windowed M-estimator
%		$$E(\textbf{u}) = \sum_{i=1}^N \sum_{j\in\mathcal{B}(i)} \Psi \left(|u_i - f_j|^2\right)  w \left(|x_i - x_j|^2\right)$$
%		and decreasing the spatial window size $\theta$ leads to the weighting
%		$$w\left(|x_i - x_j|^2\right) = \left\{\begin{array}{cl}1 & \mbox{if } x_i = x_j \\ 0 & \mbox{otherwise}\end{array}\right.$$
%	\item We get the functional
%		$$E_D(\textbf{u}) = \sum_{i=1}^N \Psi \left(|u_i - f_i|^2\right)$$
%\end{itemize}


% -----------------------------------------------------------------------
%\foilhead{Methods}

%\stitle{Diffusion filtering}


% -----------------------------------------------------------------------
\foilhead{Methods}

\stitle{Bilateral filtering}
\newline
\begin{itemize}
	\item Estimate the image gradient magnitude as a sum of squared differences from a pixel to its neighbours. The discrete smoothness penaliser reads
		$$E_S(\textbf{u}) = \sum_{i=1}^N \Psi_S \left(\sum_{j \in \mathcal{N}(i)} |u_i - u_j|^2\right)$$
		where $\mathcal{N}(i)$ is the set of 4-neighbours of a pixel $i$.
	\item Interesting fact: Exchanging the order of summation and penalisation gives an \important{anisotropic} smoothness measure
		$$E_S(\textbf{u}) = \sum_{i=1}^N \sum_{{\color{miared}{j \in \mathcal{N}(i)}}} \Psi_S \left(|u_i - u_j|^2\right)$$
	\item Increasing the neighbourhood, the smoothness term becomes
		$$E_S(\textbf{u}) = \sum_{i=1}^N \sum_{{\color{miared}{j \in \mathcal{B}(i)}}} \Psi_S \left(|u_i - u_j|^2\right) w_S\left(|x_i - x_j|^2\right)$$
\end{itemize}

\newpage

{\color{miablue}{\textbf{Minimising $E_S(\textbf{u})$}}}

\begin{itemize}
	\item The smoothness term can be minimised by an iterative procedure
%		$$\tau := \frac{1}{2 \sum_{j \in \mathcal{B}(i)} \Psi_S' \left(|u_i^k - u_j^k|^2\right)} \quad , \quad u_i^{k+1} = u_i^k - \tau \frac{\partial E}{\partial u_i}$$
%	\item Setting $g(s^2) := \Psi_S' (s^2)$ leads to the weighted averaging scheme
		\begin{eqnarray*}
			u_i^0 & = & f_i \\
			u_i^{k+1} & = & \frac{\sum_{j \in \mathcal{B}(i)} g\left(|u_i^k - u_j^k|^2\right) w\left(|x_i - x_j|^2\right) u_j^k}{\sum_{j \in \mathcal{B}(i)} g\left(|u_i^k - u_j^k|^2\right) w\left(|x_i - x_j|^2\right)}
		\end{eqnarray*}
		This is called \important{iterative bilateral filter}. This stands in contrast to the original proposal as a heuristic algorithm.
	\item Note: \\
		Bilateral filtering uses the \important{evolving image}. For $k \to \infty$, one would obtain a flat image!
\end{itemize}


% -----------------------------------------------------------------------
\foilhead{Methods}

\stitle{Overview of the iterative formulas}
\newline
\begin{itemize}
	\item Histogram operations
		$$u_i^{k+1} = \frac{\sum_{j=1}^N g\left(|u_i^k - f_j|^2\right) f_j}{\sum_{j=1}^N g\left(|u_i^k - f_j|^2\right)}$$
	\item Local M-smoothers
		$$u_i^{k+1} = \frac{\sum_{j \in \mathcal{B}(i)} g\left(|u_i^k - {\color{red}{f_j}}|^2\right) w\left(|x_i - x_j|^2\right) {\color{red}{f_j}}}{\sum_{j \in \mathcal{B}(i)} g\left(|u_i^k - {\color{red}{f_j}}|^2\right) w\left(|x_i - x_j|^2\right)}$$
	\item Iterative Bilateral filtering
		$$u_i^{k+1} = \frac{\sum_{j \in \mathcal{B}(i)} g\left(|u_i^k - {\color{blue}{u_j^k}}|^2\right) w\left(|x_i - x_j|^2\right) {\color{blue}{u_j^k}}}{\sum_{j \in \mathcal{B}(i)} g\left(|u_i^k - {\color{blue}{u_j^k}}|^2\right) w\left(|x_i - x_j|^2\right)}$$
\end{itemize}


% -----------------------------------------------------------------------
\foilhead{A Unifying Framework}

\stitle{A Unifying Framework}
\newline
		\begin{eqnarray*}
%			{\color{red}{E_D(\textbf{u})}} & = & \sum_{i,j \in J} \Psi_D \left(|u_i - {\color{red}{f_j}}|^2\right) w_D \left(|x_i - x_j|^2\right) \\
%			{\color{blue}{E_S(\textbf{u})}} & = & \sum_{i,j \in J} \Psi_S \left(|u_i - {\color{blue}{u_j}}|^2\right) w_S \left(|x_i - x_j|^2\right)
			{\color{red}{E_D(\textbf{u})}} & = & \sum_{i=1}^N \sum_{j=1}^N \Psi_D \left(|u_i - {\color{red}{f_j}}|^2\right) w_D \left(|x_i - x_j|^2\right) \\
			{\color{blue}{E_S(\textbf{u})}} & = & \sum_{i=1}^N \sum_{j=1}^N \Psi_S \left(|u_i - {\color{blue}{u_j}}|^2\right) w_S \left(|x_i - x_j|^2\right)
		\end{eqnarray*}
\begin{itemize}
%	\item Model
	\item The unifying energy looks as follows (convex combination):
		$$E(\textbf{u}) = \sigma {\color{red}{E_D(\textbf{u})}} + (1 - \sigma) {\color{blue}{E_S(\textbf{u})}} \quad 0 \leq \sigma \leq 1$$
	\item Advantages: Freedom in selecting
		\begin{itemize}
			\item the penaliser type $\Psi_D$ and $\Psi_S$ as well as its parameters and
			\item the balance between smoothness and data terms.
		\end{itemize}
\end{itemize}

%\newpage

%\begin{itemize}
%	\item Note: We already know the minimisers of the two terms in the model.
%	\item W-estimators minimise the windowed data term
%		$${\color{red}{E_D(\textbf{u})}} = \sum_{i,j \in J} \Psi_D \left(|u_i - {\color{red}{f_j}}|^2\right) w_D \left(|x_i - x_j|^2\right)$$
%	\item Iterative bilateral filtering minimises the windowed smoothness term
%		$${\color{blue}{E_S(\textbf{u})}} = \sum_{i,j \in J} \Psi_S \left(|u_i - {\color{blue}{u_j}}|^2\right) w_S \left(|x_i - x_j|^2\right)$$
%	\item This gives minimal energy for constant $u$. This is the reason why we are not interested in the evolution, but in the steady state (as already mentioned in the context of local M-smoothers).
%\end{itemize}


% -----------------------------------------------------------------------
\foilhead{Experiments}

\stitle{Experiments}
\newline
\begin{center}
	\includegraphics[height=0.45\textheight]{Pic/Figure4.pdf}
\end{center}
{\small Input images for the filtering examples. \textbf{Left:} Noise-free version. \textbf{Right:} Noisy version. \textbf{Authors:} P. Mr\'{a}zek, J. Weickert, A. Bruhn.}

\newpage

\begin{center}
	\includegraphics[height=0.75\textheight]{Pic/Figure5.pdf}
\end{center}
{\small Filtering using the penaliser $\Psi(s^2) = 1 - e^{-s^2 / \lambda^2}$ with soft window of varied size of the spatial neighbourhood ($\theta =1, \theta = 3, \theta = 10$). \textbf{Top:} local M-smoothers (data term, steady state after iteration). \textbf{Bottom:} bilateral filtering (smoothness term, 200 iterations). \textbf{Authors:} P. Mr\'{a}zek, J. Weickert, A. Bruhn.}

\newpage

\begin{center}
	\includegraphics[height=0.75\textheight]{Pic/Figure6.pdf}
\end{center}
{\small Effect of the penaliser type on the filtering result, starting with the noise-free image (with soft spatial weighting $w(s^2) = e^{-s^2 / \theta^2}$, $\theta = 3$). \textbf{Authors:} P. Mr\'{a}zek, J. Weickert, A. Bruhn.}

\newpage

\begin{center}
	\includegraphics[height=0.75\textheight]{Pic/Figure7.pdf}
\end{center}
{\small Effect of the penaliser type on the filtering result, starting from the noisy image (filtering in a soft window $w(s^2) = e^{-s^2 / \theta^2}$, $\theta = 3$). \textbf{Authors:} P. Mr\'{a}zek, J. Weickert, A. Bruhn.}


% -----------------------------------------------------------------------
\foilhead{Summary}

\stitle{Summary}
\newline
\begin{itemize}
	\item Local M-smoothers minimise an energy with a windowed \important{data} term. \\ Performing a fixed-point iteration results in \important{W-estimators}.
	\item Iterative bilateral filtering minimises an energy with a windowed \important{smoothness} term.
	\item The unifying framework minimises functionals, combining nonlocal data term and nonlocal smoothness term.% This is now called \important{NDS}.
	\item It helps for a better understanding of the different methods and allows to combine the advantages of known filters to make way for new techniques.
	\item Filters are for example %By combining the two energies, one can express different filters by a unifying framework. Filters are:
		\begin{itemize}
%			\item M-estimators,
			\item Local M-smoothers,
			\item Bilateral filters,
			\item and more.
		\end{itemize}
%	\item This should have given a glimpse on how to obtain the unifying framework. (Nevertheless, there are more details involved.)

\end{itemize}


% -----------------------------------------------------------------------
\foilhead{References}

\stitle{References}
\newline
{\small
\begin{itemize}
%	\item P. Mr\'{a}zek, J. Weickert, A. Bruhn. \textsl{On Robust Estimation and Smoothing with Spatial and Tonal Kernels}. Preprint No. 51, DFG Priority Program 1114, University of Bremen, Germany, June 2004. \\
	\item R. Klette, R. Kozera, L. Naakes, J. Weickert (Eds.): Geometric Properties for Incomplete Data, 335 -- 352. Springer Dordrecht, 2006. \\
	{\color{miared}{\textsl{(unified denoising model)}}}
	\item Lecture "Differential Equations in Image Processing and Computer Vision". SS 2008. \url{http://www.mia.uni-saarland.de/Teaching/dic08.shtml}. \\
	{\color{miared}{\textsl{(Lecture 25 gives insights in the unifying framework)}}}
	\item C. K. Chu, I. Glad, F. Godtliebsen, J. S. Marron: Edge-preserving smoothers for image processing. \textsl{Journal of the American Statistical Association}, Vol. 93, No. 442, 526--556, 1998. \\
	{\color{miared}{\textsl{(local M-smoothers)}}}
	\item G. Winkler, V. Aurich, K. Hahn, A. Martin: Noise reduction in images: some recent edge-preserving methods. \textsl{Pattern Recognition and Image Analysis}, Vol. 9, No. 4, 749--766, 1999. \\
	{\color{miared}{\textsl{(W-estimators)}}}
	\item C. Tomasi, R. Manduchi: Bilateral filtering for gray and color images. \textsl{Proc. Sixth International Conference on Computer Vision} (Bombay, India, Jan.\ 1998), 839--846, Narosa, 1998. \\
	{\color{miared}{\textsl{(bilateral filter)}}}
\end{itemize}
}


% -----------------------------------------------------------------------
\foilhead{Thank you}

\ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \\ \ \\
\begin{center}
{\Huge \color{miablue}{Thank you for your attention!}}
\end{center}
%
%
% -----------------------------------------------------------------------
%\foilhead{...}
%
%\stitle{...}

\end{document}
