From 7be67131a55a15525de342e438634d77bc772acd Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Wed, 10 Sep 2014 16:32:49 +0200 Subject: [PATCH] Some more structure --- .gitignore | 1 + commands.tex | 2 +- introduction.tex | 119 ++++++++++++++++++++++++++++++++++++++++++++++- main.tex | 1 - theory.tex | 21 +++++++-- 5 files changed, 137 insertions(+), 7 deletions(-) diff --git a/.gitignore b/.gitignore index dba8159..080e206 100644 --- a/.gitignore +++ b/.gitignore @@ -5,3 +5,4 @@ *.out *.pdf *.toc +*.swp diff --git a/commands.tex b/commands.tex index 4b6a8a8..ce9b613 100644 --- a/commands.tex +++ b/commands.tex @@ -2,7 +2,7 @@ \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\TV}{\mathit{TV}} \newcommand{\BV}{\mathit{BV}} -\newcommand{\idfun}{\mathbbm{1}} +\newcommand{\idfun}{\chi} \definecolor{fixme-color}{rgb}{0.7,0.2,0} \newcommand{\fixme}[1]{\textcolor{fixme-color}{FIXME: #1}} \def\cpp{C{}\texttt{++}} diff --git a/introduction.tex b/introduction.tex index 56bfd85..661677f 100644 --- a/introduction.tex +++ b/introduction.tex @@ -20,17 +20,35 @@ $\alpha$. Here I guess Perona-Malik is the most noteworthy. We write something about the motivation, its well-posedness (or lack thereof) and other alternatives. But we can control the diffusion even more! +Perona--Malik +\begin{equation} + \partial_t u = \mathrm{div} \left( \frac{\nabla u}{1 + + \frac{\abs{\nabla u}^2}{\lambda^2}} \right). + \label{eq:perona_malik} +\end{equation} +Total variation flow +\begin{equation} + \partial_t u = \mathrm{div} \frac{\nabla u}{\abs{\nabla u}}. +\end{equation} + \subsection{Anisotropic diffusion} Section for methods introducing a diffusion \emph{tensor} $A$ that varies around the image. This means we can control diffusion strength in different directions. More specifically we can make the diffusion strong -along edges, and weak across edges. +along edges, and weak across edges. We should give a real theoretical +background here, so we have something to base the next chapter on. We must also say something about what this method does well, and where it fails. Anisotropic filtering might introduce structures that do not exist in the original image. Some example images are possible here. +\begin{equation} + \partial_t u = \mathrm{div} \big(A(u) \cdot \nabla u\big). +\end{equation} + +Main source here is Weickert. + \section{Total variation filtering} Describe briefly the functional we minimize in this method, and @@ -39,6 +57,10 @@ about how we find our minimizer? We have to at least mention that there are different ways to do it, and that one of them involves finding a minimum cut for each level. +We could introduce the normal coarea and perimeter theory here so that +we can refer to it when we introduce the anisotropic versions in the +next chapter? + We also write something about the limitations of the method. It is good at preserving sharp edges, but suffers from the so-called stair-casing effect. Thin objects and corners might gradually lose contrast depending @@ -48,3 +70,98 @@ Then finish the chapter in some way saying that we will try to combine these two methods, retaining their strenghts but eliminating their weaknesses. +\fixme{This is taken from the project.} + +First we introduce this. +\begin{equation} + \min_u \int_\Omega \abs{u - v}^p + \beta \int_\Omega \abs{\nabla u}. + \label{eq:first_min_presentation} +\end{equation} +Then we say something about difficulties calculating the gradient and +introduce the total variation. +\begin{definition}[Total variation] + Given a function $u \in L^1(\Omega)$, the total variation of $u$, + often written $\int_\Omega \abs{Du}$, where the $D$ is the gradient + taken in the distributional sense, is + \begin{equation} + \TV(u) + = \int_\Omega \abs{Du} + = \sup \left\{ \int_\Omega u \cdot \mathrm{div} \, \varphi : + \varphi \in C^\infty_c\left(\Omega, \mathbb{R}^2\right), + \norm{\varphi}_{L^\infty(\Omega)} \leq 1 + \right\}. + \end{equation} + The test functions $\varphi$ are taken from + $C^\infty_c\left(\Omega, \mathbb{R}^2\right)$, the space of smooth + functions from $\Omega$ to $\mathbb{R}^2$ with compact support in + $\Omega$. +\end{definition} + +Note that since $\Omega$ is open and bounded, the test functions +$\varphi$ vanish on the boundary of $\Omega$ \fixme{which means we +assume some boundary condition}. Next we introduce the space of +functions with bounded variation. +\begin{definition}[Functions of bounded variation] + The space of functions of bounded variation $\BV(\Omega)$ is the + space of functions $u \in L^1(\Omega)$ for which the total variation + is finite, i.e., + \begin{equation} + \BV(\Omega) = \left\{ u \in L^1(\Omega) : \TV(u) < \infty + \right\}. + \end{equation} +\end{definition} + +Before introducing the coarea formula, we need the formal definition of +a set perimeter. Here, $\idfun_E$ signifies the characteristic function +of the set $E$, the function which is equal to one in every point in +$E$, and zero elsewhere. +\begin{definition}[Set perimeter] + The perimeter of a set $E$ is defined as + \begin{equation} + P(E,\Omega) = \int_\Omega \abs{D \idfun_E}. + \end{equation} + A measurable set $E \subset \Omega$ is of finite perimeter in + $\Omega$ if $\idfun_E \in \BV(\Omega)$. +\end{definition} +\fixme{Something about reduced boundary and Hausdorff measures here?} +The set perimeter behaves mostly as one might expect for ``nice'' sets, +just note that if the boundary of $E$ overlaps with the boundary of +$\Omega$, then $P(E,\Omega)$ will not include the overlapping parts of +the boundary. + +For an image $u$ and a level $\lambda$ we denote the \emph{level set} by +$\{u \leq \lambda\}$ defined as the set $\{ x \in \Omega : u_x \leq +\lambda\}$. The thresholded images are defined as +\begin{equation} + u^\lambda = \idfun_{u \leq \lambda}. + \label{eq:level_set} +\end{equation} +With all these definitions in place, we are ready to introduce the +coarea formula, which will let us write the total variation as an +integral over the range of the image levels $\lambda$. +\begin{theorem}[The coarea formula] + Let $u \in BV(\Omega)$. Then for almost every $\lambda$ the set + $\{u \leq \lambda\}$ is of finite perimeter, and one has the coarea + formula + \begin{equation} + \TV(u) + = \int_\Omega \abs{D u} + = \int_\mathbb{R} P(\{u \leq \lambda\},\Omega) \, d\lambda + \label{eq:coarea_formula} + \end{equation} +\end{theorem} +Note that the equality in \eqref{eq:coarea_formula} holds for all $u \in +L^1(\Omega)$, not only when the total variation is finite. We can now +rewrite \eqref{eq:first_min_presentation} as +\begin{equation} + E_v(u) = + \int_\Omega \abs{u - v}^p + + \beta \int_\mathbb{R} P(\{u \leq \lambda\},\Omega) \, d\lambda. + \label{eq:energy_perimeter} +\end{equation} +\fixme{Should this be a minimization problem or an energy function.} + +\fixme{Shorten this section (or maybe it's short enough, only two pages, +but we need to fill in some text at least), and add some general +references.} + diff --git a/main.tex b/main.tex index 7b75885..8972998 100644 --- a/main.tex +++ b/main.tex @@ -23,7 +23,6 @@ \usetikzlibrary{calc} \usepackage{color} -\usepackage{bbm} % Indicator function \mathbbm{1} %\usepackage[margin=0.8cm]{caption} \usepackage{caption} %\usepackage[subrefformat=parens,labelformat=parens]{subcaption} diff --git a/theory.tex b/theory.tex index 1457eea..e335090 100644 --- a/theory.tex +++ b/theory.tex @@ -44,10 +44,23 @@ choose the same stencil in every point, and only let the weights depend on the anisotropy. This can work, but size has to be discussed (and tested later). Then the stencil shape can be adjusted as well. -\section{Graph theory} +\section{Graph cut formulation} -\subsection{Intro} -\subsection{Graphification} +\subsection{Networks} -\section{Flow} +\fixme{Maybe just call them graphs this time?} + +\subsection{Network representable energy functions} + +\subsection{Network construction} + +\section{Maximum flow approach} + +\subsection{Flow networks} + +\subsection{Augmenting flow algorithms} + +\subsection{Push--relabel algorithm} + +\subsection{Boykov--Kolmogorov algorithm} -- 2.47.3