From d5ab81e2c65f309b66d862807b1905142f4d78cd Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Wed, 26 Mar 2014 09:12:57 +0100 Subject: [PATCH] Runde 2 --- cut.tex | 225 ++++++++++++++++++++++++++++++++++++++++++++++-------- main.tex | 2 + total.tex | 40 +++------- 3 files changed, 203 insertions(+), 64 deletions(-) diff --git a/cut.tex b/cut.tex index 33eebcb..31f1fd6 100644 --- a/cut.tex +++ b/cut.tex @@ -1,8 +1,7 @@ \section{Graph cut formulation} -\fixme{Short introduction to graphs. Notation. What is a cut, what is a - minimal s-t-cut. How do we get from the discrete energy to the graph - and why does finding the graph cut result in minimizing the energy - of the current label. Boykov and Kolmogorov.} + +\fixme{Short intro here maybe? Something about what this section is all +about.} \subsection{Flow networks} Using the notation of \cite{cormen2009introduction} we will denote a @@ -169,7 +168,8 @@ proof can be found in \cite{cormen2009introduction}. \subsubsection{Dinitz'} \fixme{I did implement this, but it is maybe not very central to the -project/report.} +project/report, since I use an other algorithm in the final +implementation. Maybe a comparison would be nice though.} \subsection{Graph representable energy functions} The next step is to find a way to create special graph such that we can @@ -216,7 +216,7 @@ functions are graph-representable \end{equation} \end{theorem} -The following theorem proved by Kolmogorov and Zabih in +The following theorem is proved by Kolmogorov and Zabih in \cite{kolmogorov2002energy} and will be crucial in our graph construction. \begin{theorem}[Additivity] @@ -229,7 +229,13 @@ It allows us to construct simple graphs representing the different summands of \fixme{(?????)} and add them together to create our final graph. -\subsection{Graph construction} +\subsection{Network construction} +We will construct a network in such a way that if a variable +$u^\lambda_x$ ends up on the $s$-side of the cut, we set $u^\lambda_x = +0$, and if it ends up on the $t$-side, we set $u^\lambda_x = 1$. This is +of course an arbitrary choice, but something we have to keep in mind +through the rest of the section nonetheless. + For our neighboring relation in (\fixme{ref}) on the form \begin{equation} E^{x,y}(u^\lambda_x, u^\lambda_y) = @@ -241,10 +247,10 @@ For our neighboring relation in (\fixme{ref}) on the form we have \begin{equation} \begin{aligned} - E^{x,y}(0, 0) &= w_{x,y} \cdot 0, \\ - E^{x,y}(0, 1) &= w_{x,y} \cdot 1, \\ - E^{x,y}(1, 0) &= w_{x,y} \cdot 1, \\ - E^{x,y}(1, 1) &= w_{x,y} \cdot 0, + E^{x,y}(0, 0) &= w_{xy} \cdot 0, \\ + E^{x,y}(0, 1) &= w_{xy} \cdot 1, \\ + E^{x,y}(1, 0) &= w_{xy} \cdot 1, \\ + E^{x,y}(1, 1) &= w_{xy} \cdot 0, \end{aligned} \label{eq:neigh_energies} \end{equation} @@ -253,35 +259,188 @@ Kolmogorov and Zabih presents a way to construct a graph for any graph representable function in \cite{kolmogorov2002energy}. Since our energies in \eqref{eq:neigh_energies} are especially simple, the construction and presentation is simplified. -\begin{figure} + +The fidelity term of our energy function in (\fixme{REF}) simplifies to +\begin{align} + E^x(0) &= + N_x(\lambda + 1) - + N_x(\lambda) + \label{eq:fidelity_energy0} \\ + E^x(1) &= 0 + \label{eq:fidelity_energy1} +\end{align} +where $E^x(0)$ might end up being positive or negative depending on +$\lambda$ and the pixel value $v_x$. Figure \ref{fig:norm_subgraph} +shows how a network can be constructed to represent the \fixme{fidelity} +term of \eqref{eq:fidelity_energy0}. + +Figure \ref{fig:neigh_subgraph} shows how a network can be constructed +to represent the term $E^x(u^\lambda_x, u^\lambda_y)$ of (\fixme{ref}). +Table \ref{tab:neigh_energy} shows the energies, and also the cut +capacities of the different possible variable value combinations, making +it easy to verify that these two network constructions actually +represent our energy function. +\begin{table} \centering -\begin{tikzpicture}[scale=1.5] - \node[vertex] (s) at (0, 0) {s}; - \node[vertex] (u) at (-1,-2) {u}; - \node[vertex] (v) at (1, -2) {v}; - \node[vertex] (t) at (0, -4) {t}; + \caption{The possible configurations of the variables in the term + $E^{x,y}(u^\lambda_x, u^\lambda_y)$, the corresponding energy, and + the cut capacity for the two alternative network constructions shown in + Figure \ref{fig:neigh_subgraph}. + } + \begin{tabular}{cccc} + \hline + Configuration & $E^{x,y}(u^\lambda_x, u^\lambda_y)$ + & Alt. 1 cut cap. & Alt. 2 cut cap. \\ + \hline + $(0, 0)$ & $0$ & $w_{xy}$ & $0$ \\ + $(0, 1)$ & $w_{xy}$ & $2w_{xy}$ & $w_{xy}$ \\ + $(1, 0)$ & $w_{xy}$ & $2w_{xy}$ & $w_{xy}$ \\ + $(1, 1)$ & $0$ & $w_{xy}$ & $0$ + \end{tabular} + \label{tab:neigh_energy} +\end{table} - \path[edge] (s) -- node[weight] {$w_{x,y}$} (u); - \path[edge] (u) -- node[weight] {$2w_{x,y}$} (v); - \path[edge] (v) -- node[weight] {$w_{w,y}$} (t); -\end{tikzpicture} -\caption{\fixme{Why can't we subtract $w_{x,y}$ from the whole graph -here? AND CHOOSE u v or x y....} -\label{fig:neigh_subgraph} +\begin{figure} + \centering + \begin{subfigure}[t]{0.45\textwidth} + \centering + \begin{tikzpicture}[scale=2.0] + \node[vertex] (s) at (0, 0) {s}; + \node[vertex] (u) at (0, -1) {$u^\lambda_x$}; + \node[vertex] (t) at (0, -2) {t}; + + \path[edge] (u) -- node[weight noslope] {$E^x(0)$} (t); + \end{tikzpicture} + %\caption{Network when $E^x(0) \geq 0$.} + \caption{The network when $E^x(0) > 0$, with constant equal to + 0. + } + \label{fig:norm_subgraph_pos} + \end{subfigure} + ~ + \begin{subfigure}[t]{0.45\textwidth} + \centering + \begin{tikzpicture}[scale=2.0] + \node[vertex] (s) at (0, 0) {s}; + \node[vertex] (u) at (0, -1) {$u^\lambda_x$}; + \node[vertex] (t) at (0, -2) {t}; + + \path[edge] (s) -- node[weight noslope] {$-E^x(0)$} (u); + \end{tikzpicture} + \caption{Network when $E^x(0) < 0$, with constant equal to + $-E^x(0)$. + } + \label{fig:norm_subgraph_neg} + \end{subfigure} + \caption{For the two possible configurations $u^\lambda_x \in \{0, + 1\}$, the energies in our energy function (\fixme{ref}) are + $\{E^x(0), 0\}$. The minimal $s$-$t$-cuts obtaining these + configurations are $(S, T) = (\{s, u^\lambda_x\}, \{t\})$ and + $(S, T) = (\{s\}, \{u^\lambda_x, t\})$. They have capacity equal + to the corresponding energy \emph{plus} the constant (as + permitted in \fixme{theorem}). + } +\label{fig:norm_subgraph} \end{figure} \begin{figure} \centering -\begin{tikzpicture}[scale=2.0] - \node[vertex] (s) at (0, 0) {s}; - \node[vertex] (u) at (0, -1) {u}; - \node[vertex] (t) at (0, -2) {t}; + \begin{subfigure}[t]{0.4\textwidth} + \centering + \begin{tikzpicture}[scale=1.5] + \node[vertex] (s) at (0, 0) {s}; + \node[vertex] (u) at (-1,-2) {$u^\lambda_x$}; + \node[vertex] (v) at (1, -2) {$u^\lambda_y$}; + \node[vertex] (t) at (0, -4) {t}; + + \path[edge] (s) -- node[weight] {$w_{xy}$} (u); + \path[edge] (u) -- node[weight] {$2w_{xy}$} (v); + \path[edge] (v) -- node[weight] {$w_{xy}$} (t); + \end{tikzpicture} + \caption{Representing $E^{x,y}(u^\lambda_x, u^\lambda_y)$ with a + constant term of $w_{xy}$.} + \label{fig:neigh_subgraph_alt1} + \end{subfigure} + ~ + \begin{subfigure}[t]{0.4\textwidth} + \centering + \begin{tikzpicture}[scale=1.5] + \node[vertex] (s) at (0, 0) {s}; + \node[vertex] (u) at (-1,-2) {$u^\lambda_x$}; + \node[vertex] (v) at (1, -2) {$u^\lambda_y$}; + \node[vertex] (t) at (0, -4) {t}; + + \path[edge] ([yshift=1.5pt]u.east) -- node[weight around] + {$w_{xy}$} + ([yshift=1.5pt]v.west); + \path[edge] ([yshift=-1.5pt]v.west) -- node[weight around] + {$w_{xy}$} + ([yshift=-1.5pt]u.east); + \end{tikzpicture} + \caption{Representing $E^{x,y}(u^\lambda_x, u^\lambda_y)$ with a + constant term of 0.} + \label{fig:neigh_subgraph_alt2} + \end{subfigure} + \caption{Two alternative ways of constructing a network representing + the energy term $E^{x,y}(u^\lambda_x, u^\lambda_y)$. + } + \label{fig:neigh_subgraph} +\end{figure} - \path[edge] (s) -- node[weight noslope] {$E^u(0)$} (u); -\end{tikzpicture} -\caption{Something something $E^u(0)$ is always positive and $E^u(1)$ is -always zero.} -\label{fig:norm_subgraph} +\begin{figure} + \centering + \begin{subfigure}[t]{0.4\textwidth} + \centering + \begin{tikzpicture} + \draw[->] (0,0) -- (4,0) node[right] {$\lambda$}; + \draw[->] (0,-2) -- (0,2) node[above] {$E^x(0)$}; + \draw[line,domain=0:1] plot ({\x},{-1}); + \draw[line,domain=1:2,dashed] plot ({\x},{2*\x-3}); + \draw[line,domain=2:4] plot ({\x},{1}); + + \draw (1,2pt) -- (1,-2pt) node[ + font=\small, + anchor=south + ] + {$v_x-1$}; + + \draw (2,2pt) -- (2,-2pt) node[ + font=\small, + anchor=north + ] + {$v_x$}; + + \end{tikzpicture} + \caption{$L^1$ fidelity term.} + \label{fig:l1_norm_evolution} + \end{subfigure} + ~ + \begin{subfigure}[t]{0.4\textwidth} + \centering + \begin{tikzpicture} + \draw[->] (0,0) -- (4,0) node[right] {$\lambda$}; + \draw[->] (0,-2) -- (0,2) node[above] {$E^x(0)$}; + \draw[line,domain=0:4] plot ({\x},{.8*\x - 1.6}); + + \draw (2.5,2pt) -- (2.5,-2pt) node[ + font=\small, + anchor=north + ] + {$v_x$}; + + \draw (1.5,2pt) -- (1.5,-2pt) node[ + font=\small, + anchor=south + ] + {$v_x-1$}; + + \end{tikzpicture} + \caption{$L^2$ fidelity term.} + \label{fig:l2_norm_evolution} + \end{subfigure} + \caption{Two figures showing how the fidelity energy term $E^x(0)$ + in (\fixme{REF}) increases monotonically with $\lambda$.} + \label{fig:norm_evolution} \end{figure} \fixme{Make it clear what happens when a node lands on the $T$-side diff --git a/main.tex b/main.tex index 9fae3a8..f517b0f 100644 --- a/main.tex +++ b/main.tex @@ -42,8 +42,10 @@ \tikzstyle{double edge} = [draw,thick,<->] \tikzstyle{weight} = [font=\small,sloped,fill=white] \tikzstyle{weight noslope} = [font=\small,fill=white] +\tikzstyle{weight around} = [font=\small,sloped,auto] \tikzstyle{selected edge} = [draw,line width=5pt,-,red!50] \tikzstyle{ignored edge} = [draw,line width=5pt,-,black!20] +\tikzstyle{line} = [ultra thick,scale=1,smooth,variable=\x,blue] \pgfdeclarelayer{background} \pgfdeclarelayer{foreground} \pgfsetlayers{background,main,foreground} diff --git a/total.tex b/total.tex index 505c645..89a901c 100644 --- a/total.tex +++ b/total.tex @@ -156,13 +156,6 @@ with different numerical methods for solving it. Results on how the set of jumps in the resulting image $u$ is contained in the set of jumps in the original image $v$ are also presented. -\fixme{\cite{caselles2011total} has a nice introduction to total - variation. It describes the foundations, the spaces, and some - methods, but mostly continuous. Could include some more theory here, - like the coarea stuff, and the number of discontinuities?} - -\fixme{Write something about the different methods that exist?} - \subsection{Discrete problem} Since digital images are given on a discrete grid, with values taken from a discrete and finite set of levels, we want to discretize @@ -317,8 +310,6 @@ Boykov and Kolmogorov prove we have convergence when all of $h$, $\Delta \phi_{xy}$, and $d_{xy}$ go to zero. In other words, if the grid size decreases and we at the same time increase the density of the neighborhood. -\fixme{Maybe move (and expand) this somewhere else? Where the grids are -discussed for example? Also, the section is a bit messy.} \fixme{BAD TRANSITION} @@ -355,14 +346,13 @@ function $N(k)$ taking values $k \in \mathcal{L}$ \big) + N(0) \\ &= \sum_{\lambda=0}^{L-2} \big( N(\lambda + 1) - N(\lambda) - \big) \mathbbm{1}_{\lambda < k} + N(0) \\ - &= \sum_{\lambda=0}^{L-2} \big( - N(\lambda + 1) - N(\lambda) - \big) (1 - u^\lambda) + N(0). + \big) \mathbbm{1}_{\lambda < k} + N(0) \end{aligned} \end{equation} -Using this we rewrite \eqref{eq:norm_discrete_int} and obtain +Since $\mathbbm{1}_{\lambda < u_x} = (1 - u^\lambda_x)$ we rewrite +\eqref{eq:norm_discrete_int} and obtain \begin{equation} + \sum_x N_x(u_x) = \sum_{\lambda=0}^{L-2} \sum_x \big( N_x(\lambda + 1) - @@ -410,26 +400,14 @@ monotonely increasing in increasing level values, i.e.\ \quad \forall x \in S. \end{equation} -\fixme{Want to use $u$ and $v$ as pixels/nodes, what to use as image? -Since $s$ and $t$ normally is the source and sink.} +\fixme{So, $u$ and $v$ are images, but also nodes in the flow-section? +$x$ and $y$ are pixels. $s$ is the source, and $t$ is the sink?} \fixme{Some like to call one term the fidelity term, and the other the regularization term?} -\fixme{\cite{boykov2003computing} motivates the discrete estimation of - the perimeter of a set, and it makes sense. The size of the - perimeter should be proportional to the number of edges it crosses, - which is why we sum up $\abs{u^\lambda_s - u^\lambda_t}$ (which is - only different from zero at the cut). -} - -\fixme{How do we get to the discrete formulation. Why is it OK to do - what we do with the gradient. How do we decompose the energy - function into different levels and why is it OK to optimize each - level separately. How do we choose the different neighbourhoods, and - what could this mean for the result. Darbon and Sigelle. - \cite{chan2011numerical} describes different methods for using total - variation, and especially how one can use it in the discrete - setting. It also goes into the min-cut method. Yay. Good book. +\fixme{ + Why is it OK to optimize each + level separately? Why does it work? } -- 2.47.3