From faa8c92e9bd537a23b5b705fd50fe0578632ce86 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Mon, 8 Dec 2014 15:31:01 +0100 Subject: [PATCH] Nomenclature and stuff --- Makefile | 1 + fig/area_proof.tex | 6 ++--- introduction.tex | 59 +++++++++++++++++++++++++++++----------------- main.tex | 7 ++++++ theory.tex | 54 ++++++++++++++++++++++++++++-------------- 5 files changed, 85 insertions(+), 42 deletions(-) diff --git a/Makefile b/Makefile index 5e8b3e4..bf77339 100644 --- a/Makefile +++ b/Makefile @@ -2,5 +2,6 @@ all: xelatex -shell-escape main bibtex main xelatex -shell-escape -no-pdf main + makeindex main.nlo -s nomencl.ist -o main.nls xelatex -shell-escape main cp main.pdf ~/Dropbox/master/ diff --git a/fig/area_proof.tex b/fig/area_proof.tex index a819764..9822aef 100644 --- a/fig/area_proof.tex +++ b/fig/area_proof.tex @@ -60,8 +60,8 @@ \end{tikzpicture} \caption{ - A visual argument that $\delta^2 = \Delta \rho \norm{e}$. If extended - to the whole plane, there will be the same amount of blue squares as - red squares, so their area must be equal. + A visual argument showing that $\delta^2 = \Delta \rho \norm{e}$. If + extended to the whole plane, there will be the same amount of blue + squares as red rectangles, so their areas must be equal. } \label{fig:area_proof} diff --git a/introduction.tex b/introduction.tex index 696d40f..4642b62 100644 --- a/introduction.tex +++ b/introduction.tex @@ -5,6 +5,9 @@ found in the introduction of the project. Maybe we also say something about the different noise models, and common assumptions concerning the noise. +\fixme{introduce u and f as images} +\fixme{introduce Omega} + \section{Diffusion filtering} Diffusion filtering is a broad group of filtering or restoration methods @@ -18,6 +21,7 @@ the Gaussian function y^2}{2\sigma^2} \right). \label{eq:gaussian_function} \end{equation} +\nomenclature{$K_\sigma(x,y)$}{The Gaussian kernel.}% In the discrete setting where the image consists of a grid of pixels, the Gaussian blur amounts to calculating each pixel in the output image as a weighted average of its neighboring pixels in the input image. @@ -43,21 +47,22 @@ vary for different parts of the image. \subsection{Non-linear diffusion} In the theory of the heat equation one can introduce a \emph{thermal -diffusivity} -$\alpha$ such that +diffusivity} $\alpha$ such that \begin{equation} \begin{cases} \partial_t u &= \diver \big( \alpha(u) \nabla u\big) \\ u |_{t=0} &= f \end{cases} \end{equation} -The thermal diffusivity $\alpha$ is material dependant, and can also vary throughout -the object. It specifies how well heat travels through the specific -point in the object. We can make use of this in the image restoration context by -controlling the diffusivity in different parts of the image, where our -goal is to reduce noise without loosing image detail. Optimally, -we would like there to be a lot of diffusion in smooth parts of the -image, and not so much in areas with a lot of details. +\nomenclature{$\alpha(u)$}{Thermal diffusivity scalar.}% +The thermal diffusivity $\alpha$ is material dependent, and can also +vary throughout the object. It specifies how well heat travels through +the specific point in the object. We can make use of this in the image +restoration context by controlling the diffusivity in different parts of +the image, where our goal is to reduce noise without loosing image +detail. Optimally, we would like there to be a lot of diffusion in +smooth parts of the image, and not so much in areas with a lot of +details. One much-studied non-linear diffusion equation is the Perona--Malik equation @@ -72,7 +77,7 @@ norm of the gradient $\abs{\nabla u}$ grows. Although noise will also contribute to an increase in the size of $\abs{\nabla u}$, the general assumption is that this is a good measure of where the details are in the image. This particular form of the thermal diffusivity has been -shown to be related to how brightness is percepted by the human visual +shown to be related to how brightness is perceived by the human visual system. The model has some theoretical problems related to well-posedness, for more information see \cite{weickert1998anisotropic}. @@ -81,7 +86,7 @@ distinction between non-linear and anisotropic methods. The Perona--Malik method, and other methods with varying scalar diffusivities, are often called anisotropic, but we will call them non-linear, and spare the anisotropic term for methods where the -diffusivity is a tensor, and thus both location and direction dependant. +diffusivity is a tensor, and thus both location and direction dependent. A different kind of non-linear diffusion model is the total variation flow which can be formulated as @@ -91,13 +96,14 @@ flow which can be formulated as where the diffusivity has a similar effect of reducing the diffusion in areas of high variation. As the name suggests this model can be related to the variational total variation formulation presented later. One -discrete time-step in the solution of this PDE corresponds to the -Euler--Lagrange equation of the variational formulation. +discrete time-step in the solution of this partial differential equation +corresponds to the Euler--Lagrange equation of the variational +formulation. Common for all of these are that we control the amount of diffusion done in each point of the image, based somehow on the image itself. But we -can go further by not only making the diffusivity location dependant, -but also direction dependant. This allows us to have have more +can go further by not only making the diffusivity location dependent, +but also direction dependent. This allows us to have have more diffusion in directions with little variation. As mentioned, we will use the term anisotropic diffusion, meaning ``not uniform in all directions.'' @@ -105,7 +111,7 @@ directions.'' \subsection{Anisotropic diffusion} \label{sec:anisotropic_diffusion} -The diffusivity is made directionally dependant by introducing a diffusion +The diffusivity is made directionally dependent by introducing a diffusion \emph{tensor} $A(u)$ such that the initial boundary value problem becomes \begin{equation} @@ -119,6 +125,8 @@ becomes \end{cases} \label{eq:aniso_diff} \end{equation} +\nomenclature{$A(u)$}{Thermal diffusivity tensor, or anisotropy +tensor.}% \fixme{triple column alignment?} where $\nu$ is the outer normal of $\Omega$. The tensor $A(u)$ would normally be constructed such as to diminish the effect of $\nabla @@ -126,9 +134,12 @@ u$ across what we believe to be edges in the image. This way, there will also be less diffusion through these edges. Weickert suggests in \cite{weickert1998anisotropic} constructing $A(u)$ based on the edge estimator $\nabla u_\sigma$ where +\nomenclature{$\nabla u_\sigma$}{Edge estimator.}% \begin{equation} u_\sigma := K_\sigma * \tilde{u} \end{equation} +\nomenclature{$u_\sigma$}{Image $u$ smoothed with a Gaussian of +parameter $\sigma$.}% and $\tilde{u}$ is an extension of $u$ from $\Omega$ to $\mathbb{R}^2$ made by for example symmetrically extending $u$ across the edges. Assuming we are at an edge in the image, the @@ -141,8 +152,9 @@ scale, we introduce the \emph{structure tensor} \begin{equation} S_\rho(x) := K_\rho * (\nabla u_\sigma \otimes \nabla u_\sigma), \end{equation} +\nomenclature{$S_\rho(x)$}{Structure tensor.} where the convolution with the Gaussian function $K_\rho$ is done -componentwise. The anisotropy tensor $A(u)$ can then be constructed +component-wise. The anisotropy tensor $A(u)$ can then be constructed based on the eigenvectors and eigenvalues of $S_\rho(x)$. The structure tensor and its properties will be discussed further when @@ -222,6 +234,7 @@ variation using the distributional derivative. $\Omega$. \label{def:tv} \end{definition} +\nomenclature{$\TV(u)$}{Total variation of image $u$.}% Note that since $\Omega$ is open and bounded, the test functions $\varphi$ vanish on the boundary of $\Omega$. This means we assume @@ -241,6 +254,8 @@ to introduce the space of functions of bounded variation. \right\}. \end{equation} \end{definition} +\nomenclature{$\BV(\Omega)$}{Functions of bounded variation in +$\Omega$.}% Our optimization problem has thus become \begin{equation} \min_{u \in \BV(\Omega)} \int_\Omega \abs{u - v}^p \, dx + \beta \, @@ -251,9 +266,9 @@ and there are many different numerical methods to find or approximate a solution. As with anisotropic diffusion, the total variation method also has its -strengths and weaknesses. Its main strenght is its ability to recover +strengths and weaknesses. Its main strength is its ability to recover edges in the input image. The total variation of a section only takes -the absolute change into account, and does not favour gradual changes +the absolute change into account, and does not favor gradual changes over sharp discontinuities like the diffusion methods. This comes at a cost though, and in some cases the method may introduce new edges that were not in the original image, since flat sections of zero variation @@ -314,7 +329,9 @@ defined as \begin{equation} u^\lambda = \idfun_{u > \lambda}. \end{equation} +\nomenclature{$u^\lambda$}{Thresholded image at level $\lambda$.}% Here, $\idfun_E$ signifies the characteristic function of the set $E$, +\nomenclature{$\idfun_E$}{Characteristic function of the set $E$.}% the function which is equal to one in every point in $E$, and zero elsewhere. The graph cut we find later will for each level $\lambda$ give us the thresholded image $u^\lambda$ which can then be combined to @@ -332,9 +349,9 @@ perimeter of the level sets \end{equation} Our input images will be digital images given as pixels on a grid, and -we will represent them as functions $u : \mathcal{G} \to \mathcal{L}$, +we will represent them as functions $u : \mathcal{G} \to \mathcal{P}$, where $\mathcal{G}$ is our regular discrete pixel grid, and -$\mathcal{L} = \{0, \hdots, L-1\}$ is the set of discrete level values. +$\mathcal{P} = \{0, \hdots, L-1\}$ is the set of discrete level values. Through careful manipulation of the functional in \eqref{eq:second_min_presentation} we obtain a discrete energy functional decomposed as a sum over all the level values diff --git a/main.tex b/main.tex index e2e5549..d1b4c96 100644 --- a/main.tex +++ b/main.tex @@ -59,6 +59,7 @@ \usepackage{subcaption} \usepackage{xfrac} \usepackage{listings} +\usepackage[intoc]{nomencl} \lstset{ % FIXME: Courier 9pt anbefales @@ -85,6 +86,8 @@ \input{commands} +\makenomenclature + % Selve dokumentet begynner: \begin{document} @@ -115,6 +118,10 @@ % Pass på at neste side ikke begynner på baksida av en annen side. \cleardoublepage +\printnomenclature[2.5cm] + +\cleardoublepage + % Arabisk (vanlige tall) sidenummerering. Starter på side 1 igjen. \pagenumbering{arabic} diff --git a/theory.tex b/theory.tex index b6e408d..4c18060 100644 --- a/theory.tex +++ b/theory.tex @@ -64,6 +64,8 @@ If we let $\norm{\xi}_A = \sqrt{\xi^T A \xi}$ and $\norm{\eta}_A^* = \end{equation} \label{def:extended_tv} \end{definition} +\nomenclature{$\TVA(u)$}{Anisotropic total variation of image $u$, with +anisotropy tensor $A(u)$.}% With this extended definition, we have arrived at a minimization problem where we seek to find a minimizer of the functional @@ -143,7 +145,7 @@ structure tensor is a good edge detector. We are also interested in identifying and being sensitive to features in a neighborhood around the point, such as corners or curved edges and \fixme{coherent structures}. This is why we introduce the convolution -with $K_\rho$, which is done componentwise. The parameter $\rho$, called +with $K_\rho$, which is done component-wise. The parameter $\rho$, called the \emph{integration scale} thus controls the size of the neighborhood which affects the structure tensor. It controls the size of the structures we want our anisotropy tensor to be sensitive to. @@ -565,6 +567,8 @@ the following definition of the anisotropic set perimeter. A measurable set $U \subset \Omega$ is of finite anisotropic perimeter in $\Omega$ if $\idfun_U \in \BV(\Omega)$. \fixme{nope?} \end{definition} +\nomenclature{$\PerA(u;\Omega)$}{Anisotropic perimeter of set $U$ using +anisotropy tensor $A$.}% The anisotropic set perimeter is not like the regular set perimeter and does not measure the length of the boundary of the set, but it can be calculated in the following way @@ -635,6 +639,12 @@ Cauchy--Crofton formula, which gives us a way to calculate the length of a curve by looking at the measure of the set of lines that intersect the curve. Note that the measure $d\mathcal{L}$ is invariant under rigid motions, meaning combinations of translations and rotations. +\nomenclature{$\mathcal{L}$}{The set of all straight lines in the +plane.}% +\nomenclature{$\ell_{\phi, \rho}$}{A line given by the angle of the +normal $\phi$ and the distance to origin $\rho$.}% +\nomenclature{$\ell_{\nu, \rho}$}{A line given by a tangent vector $\nu$ +and the distance to origin $\rho$.}% \begin{theorem}[The Euclidean Cauchy--Crofton formula] Given a differentiable curve $C$ in $\mathbb{R}^2$, the length of this curve $\abs{C}$ is related to the set of lines $\mathcal{L}$ as @@ -656,6 +666,10 @@ If our space is equipped with a metric tensor $M(x)$ such that the inner product of two vectors $a$ and $b$ in a point $x$ is calculated as $\langle a, b\rangle_M = \langle a, M(x) b \rangle$, then the length of a curve $\gamma$ parametrized by some parameter $t$ becomes +\nomenclature{$M(x)$}{A metric tensor.}% +\nomenclature{$\abs{C}$}{The length of the curve $C$.}% +\nomenclature{$\abs{C}_M$}{The length of the curve $C$ calculated using +the metric tensor $M$.}% \begin{equation} \abs{\gamma}_M = \int_\gamma \sqrt{\langle \dot{\gamma}, M\big(\gamma(t)\big) \, \dot{\gamma} \rangle} \, dt. @@ -711,6 +725,8 @@ integration theory see for example \cite{bartle1995elements}. where $J_M(\ell_{\phi, \rho})$ is the Jacobian of our coordinate transformation $F : \mathcal{L} \to \mathcal{L}$, which maps $\ell_{\phi, \rho} \mapsto \Mhalf \ell_{\phi, \rho}$. + \nomenclature{$J_M(\ell_{\phi, \rho})$}{Jacobian of the coordinate + transformation induced by the metric tensor $M$.} We will now compute the Jacobian $J_M(\ell_{\phi, \rho})$. As $M\in \mathbb{R}^{2\times2}$ is symmetric, so is $M^{\sfrac{1}{2}}$, and @@ -1060,11 +1076,11 @@ tested later). Then the stencil shape can be adjusted as well. We assume that our discrete images are given on a grid $\mathcal{G}$, where each discrete point is called a pixel and we further assume that -each \emph{pixel} takes a value in the set of levels $\mathcal{L} = \{0, +each \emph{pixel} takes a value in the set of levels $\mathcal{P} = \{0, \hdots, L-1\}$. This is a reasonable assumption for grayscale images. (\fixme{repeated}). We now want to discretize the energy function in \eqref{eq:continuous_energy}. In addition, we want to decompose the -energyfunction as a sum over all the levels $\mathcal{L}$. +energyfunction as a sum over all the levels $\mathcal{P}$. \subsection{Fidelity term} @@ -1072,7 +1088,7 @@ Since it is not affected by our introduction of the anisotropy tensor, the fidelity term can be discretized as in my project work \cite{project}. For some pixel position $x \in \mathcal{G}$ and some level value $k \in -\mathcal{L}$, we define the following function +\mathcal{P}$, we define the following function \begin{equation} N_x(k) = \abs{k - v_x}^p \end{equation} @@ -1086,7 +1102,7 @@ of $k$. This allows us write \end{equation} The reason we introduce the function $N_x(k)$ is that we want to apply the following decomposition formula, which holds for any function $F(k)$ -taking values $k \in \mathcal{L}$: +taking values $k \in \mathcal{P}$: \begin{equation} \begin{aligned} F(k) &= \sum_{\lambda = 0}^{k-1} \big( F(\lambda + 1) - @@ -1106,7 +1122,7 @@ rewrite \eqref{eq:fidelity_approx_1} and obtain \end{equation} As our domain is discretized uniformly, we drop the constant $\Delta x$, and absorb it into our parameter $\beta$. Note that since -our image takes values in $\mathcal{L} = \{0, \hdots, L-1\}$, the +our image takes values in $\mathcal{P} = \{0, \hdots, L-1\}$, the thresholded image $u^{L-1}$ is equal to zero everywhere. \subsection{Regularization term} @@ -1166,7 +1182,7 @@ Figure \ref{fig:line_neigh} In the discrete setting our domain $\Omega$ is discretized as a regular grid $\mathcal{G}$. Our image is then reduced to a function $u : -\mathcal{G} \to \mathcal{L}$. \fixme{mathcal L is now two things.} +\mathcal{G} \to \mathcal{P}$. Moreover, the level sets $\{ u > \lambda\}$ will be functions taking the value of 0 or 1 on this grid, as shown in Figure \fixme{ref}. @@ -1227,8 +1243,10 @@ structure tensor in \eqref{eq:s_def} corresponding to the \emph{integration scale} $\rho$, and thus we expect the tensors $M(a)$ and $M(b)$ to be similar for edges $e$ of reasonably short length. -\fixme{really? componentwise? will that not mess up the -eigenvalues? sure, a bit, but it won't change consistency..} +We also remark that using the min-max theorem, it is easy to conclude +that the eigenvalues of the tensor approximation $M(e_{ab})$ is bounded +below and above by the smallest and largest eigenvalues of $M(a)$ and +$M(b)$. \fixme{Reference to min-max/Rayleigh} \begin{figure} \input{fig/area_proof} @@ -1246,15 +1264,15 @@ will be provided by the following lemma. \label{lem:delta_rho} \end{lemma} \begin{proof} - Consider a line $\ell$ intersecting the point $(p, q)$ in the grid. - The distance $\Delta \rho$ from this line $\ell$ to the next line - can then be calculated as a minimum over the distance to all other - lines. - - The given family of lines consists of edges in the grid, which we - write $e = (\delta s, \delta t)^T$ where $s$ and $t$ are coprime - such that $e$ does not intersect any other points than its two - endpoints. + Consider a line $\ell$ intersecting the point $(p, q) \in + \mathbb{Z}^2$ in the grid. + The distance $\Delta \rho$ from this line $\ell$ to the neighboring + lines can then be calculated as a minimum over the distance to all + other lines. + + The lines are split into edges $e = (\delta s, \delta t)^T$ where + $s, t \in \mathbb{Z}$ are coprime such that $e$ does not intersect + any other points than its two endpoints. Let $(p\prime, q\prime)$ be an arbitrary point not on the line $\ell$. We can then calculate -- 2.47.3