From 83f4017b1adf5c37c4fa137d0c3867d11665db48 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Sat, 10 May 2014 16:01:19 +0200 Subject: [PATCH] Fixes --- cut.tex | 126 +++++++++++++++++++++++++++++++++--------------------- total.tex | 11 ++--- 2 files changed, 81 insertions(+), 56 deletions(-) diff --git a/cut.tex b/cut.tex index 4c98e81..1eeda5a 100644 --- a/cut.tex +++ b/cut.tex @@ -1,7 +1,17 @@ \section{Graph cut formulation} +We have successfully discretized our original continuous total variation +optimization problem, and decomposed it into one smaller problem for +each level of the image. These smaller problems are binary in the sense +that for each pixel, we want to know if its value should be above the +current level $\lambda$ or not. The only thing tying these problems +together is the fact that we should be able to stack the thresholded +images in the end. -\fixme{Short intro here. Something about what this section is all -about.} +We will in this section present a graph cut approach to the level +subproblem. A graph is constructed containing all the pixels as +vertices, with carefully chosen edge weights such that a minimum cut of +the graph will also minimize the energy function of +\eqref{eq:total_energy}. \subsection{Networks} Using the notation of \cite{cormen2009introduction} we will denote a @@ -10,8 +20,8 @@ $E$ is a binary relation on $V$. We say that if $(u, v) \in E$ there is an edge from $u$ to $v$ in the graph $G$. We introduce the non-negative capacity function $c : V \times V \to -\left[0, \infty \right)$. A positive capacity $c(u, v) = q > 0$ is only -possible if $(u, v) \in E$ and means that it is possible to send a +\left[0, \infty \right)$. Only edges $(u, v) \in E$ can have a positive +capacity $c(u, v) = q > 0$ and it means that it is possible to send a \emph{flow} of maximum $q$ units from $u$ to $v$. For convenience we will let $c(u, v) = 0$ for any pair $(u, v) \not\in E$, and we do not allow self-loops in our graph. When a directed graph $G$ is equipped @@ -21,45 +31,50 @@ c)$. There are two special nodes in the network, the source $s$ and the sink $t$. Contrary to other nodes, which can neither produce nor receive excess flow, the source can produce and the sink can receive, an -unlimited amount of flow. +unlimited amount of flow. The most common problem in flow network theory +is the question of how much flow it is possible to send through the +network from the source to the sink. \fixme{Contrary to Cormen et.\ al.\ in \cite{cormen2009introduction} we allow antiparallel edges in our graph, for now? This is only a problem later when discussing flow.} -What we seek in our final network, is a minimum $s$-$t$-cut, a +What we seek in our final network is a minimum $s$-$t$-cut, a ``minimal'' line through the network that cuts a set of edges and -separates the source from the sink. +divides the vertex set in two, separating the source from the sink. \begin{definition}[$s$-$t$-cut] - Given a network $G = (V, E, c)$, a cut $(S, T)$ of $G$ is a - partition of $V$ into $S$ and $T = V - S$ such that - $s \in S$ and $t \in T$. The capacity of the cut is + Given a network $G = (V, E, c)$, an $s$-$t$-cut $(S, T)$ of $G$ is a + partition of $V$ into $S$ and $T = V - S$ such that $s \in S$ and $t + \in T$. The capacity of the cut is \begin{equation} c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u, v), \end{equation} and a minimum $s$-$t$-cut is a cut whose capacity is minimum over - all possible $s$-$t$-cuts in the network. + all $s$-$t$-cuts. \label{def:s_t_cut} \end{definition} -Note that there might exist many different minimum $s$-$t$-cuts in a -network, resulting in different partitions of $V$. This is why we need -to be careful later that \fixme{WHAT? The sets fit nicely on top of -eachother etc.} +We will see later that if a vertex is in the set $S$ or $T$ is what +indicates whether we should set the binary variable $u^\lambda_x$ to 0 +or 1. + +Note that there might exist several minimum $s$-$t$-cuts in a network, +resulting in different partitions of $V$. This is why we need to be +careful later that we are sure the cuts we obtain will result in +stackable thresholded images. \subsection{Network representable energy functions} The next step is to find a way to construct a network such that we can minimize the energy in \eqref{eq:total_energy} by finding a minimum -$s$-$t$-cut in the network. We will do this by creating simple networks +$s$-$t$-cut. We will do this by creating small and simple networks representing the separate summands of the energy function. For these small networks it will be easy to verify that the minimal cut also -minimizes the energy function. These small networks can be added -together giving a network representing the complete energy function of -\eqref{eq:total_energy}. +minimizes the corresponding part of the energy function. These small +networks can then be merged giving a network representing the complete +energy function \eqref{eq:total_energy}. -First we need to establish the definition and result allowing us to -construct and add these special networks together. Kolmogorov and Zabih -define in \cite{kolmogorov2002energy} the class of graph representable -functions as follows +First we need to establish the definition of a network representable +function, presented by Kolmogorov and Zabih in +\cite{kolmogorov2002energy}. \begin{definition}[Network representable functions] A function $\mathcal{E}(x_1, \hdots, x_n)$ of $n$ binary variables is network-representable if @@ -75,8 +90,8 @@ functions as follows \end{definition} From this definition we see that if we have a network-representable function $\mathcal{E}$ it is possible to find an exact global minimum -of $\mathcal{E}$ by finding a minimal $s$-$t$-cut in the corresponding -network. +of $\mathcal{E}$ by finding a minimal $s$-$t$-cut in a network +representing $\mathcal{E}$. Furthermore Kolmogorov and Zabih present an important result concerning what kinds of functions are network-representable. @@ -107,28 +122,39 @@ Finally, the following theorem, proved by Kolmogorov and Zabih in \hdots, x_n), \end{equation} each represented by a network $G^k = (V^k, E^k, c^k)$, is - network-representable by $G = (E, V, c)$ where $V = \cup_k V^k$ and + network-representable by $G = (V, E, c)$ where $V = \cup_k V^k$, $E = \cup_k E^k$ and $c(u,v) = \sum_k c^k(u,v)$. \end{theorem} -It allows us to construct simple networks representing the different -summands of our energy function in \eqref{eq:total_energy}, before -adding them together to create a final network representing the total -energy. +It allows us to construct small networks representing the different +summands of our energy function \eqref{eq:total_energy}, before adding +them together to create a final network representing the total energy. Note that when we apply this theorem later, we will assume that all the summands of \eqref{eq:total_energy} have the whole picture as their domain. It is unproblematic to extend $E^x(u^\lambda_x)$ and -$E^{x,y}(u^\lambda_x, u^\lambda_y)$ such that they take the whole image -$u$ as their argument and ignore all pixels except the ones they -actually depend on. +$E^{x,y}(u^\lambda_x, u^\lambda_y)$ such that they take all the pixels +their argument and then ignore all pixels except the ones they actually +depend on. \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$ as in +$u^\lambda_x$ ends up on the source side of the cut, we set $u^\lambda_x += 0$, and if it ends up on the sink side, we set $u^\lambda_x = 1$ as in Definition \ref{def:network_representable}. This is an arbitrary choice, -but something we have to keep in mind through the rest of the section -nonetheless. +but still something we have to keep in mind through the rest of the +section. + +We will now consider the two kinds of summands in the energy function in +\eqref{eq:total_energy}. The fidelity term comes from our aim to keep +the output image close to the original image, and in the decomposition, +the edge capacities resulting from this term will depend on the level +value. + +The regularization term of \eqref{eq:total_energy} comes from our aim to +minimize to total variation, and the edge capacities coming from this +term will not depend on the level value. + +\fixme{MEH} \subsubsection{Fidelity term} The fidelity term of our energy function in \eqref{eq:total_energy} @@ -141,8 +167,8 @@ simplifies to 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$. +where $E^x(0)$ might be positive or negative depending on $\lambda$ and +the pixel value $v_x$. \begin{figure} \input{fig/norm_subgraph} @@ -244,13 +270,17 @@ energy function. \begin{figure} \centering \begin{tikzpicture}[scale=1.3] + + \node[vertex] (s) at (1, 0) {s}; + \node[vertex] (t) at (1, -5) {t}; + \begin{scope}[ yshift=-100,every node/.append style={ - yscale=.3,yslant=.4,xslant=-0.6},yscale=.3,yslant=.4,xslant=-0.6 + yscale=.3,yslant=.3,xslant=-0.6},yscale=.3,yslant=.4,xslant=-0.6 ] \foreach \x in {0,...,3} { \foreach \y in {0,...,3} { - \node[vertex] (\x\y) at (\x, \y) {}; + \node[fill=white,vertex,draw=black] (\x\y) at (\x, \y) {}; } } \foreach \x in {0,...,3} { @@ -261,17 +291,15 @@ energy function. } \end{scope} - \node[vertex] (s) at (1, 0) {s}; - \node[vertex] (t) at (1, -5) {t}; - \begin{pgfonlayer}{background} - \foreach \x in {0,...,3} { - \foreach \y in {0,...,3} { - \path[edge] (s) to (\x\y); + \foreach \x in {0,...,3} { + \foreach \y in {0,...,3} { + \path[edge] (s) to (\x\y); + \begin{pgfonlayer}{background} \path[edge] (\x\y) to (t); - } + \end{pgfonlayer} } - \end{pgfonlayer} + } \end{tikzpicture} \caption{HELLO} \label{fig:image_flow} diff --git a/total.tex b/total.tex index 42be4f5..bb00258 100644 --- a/total.tex +++ b/total.tex @@ -473,19 +473,16 @@ set $u^\lambda$ that minimizes $F_\lambda(u^\lambda)$, the sum in \eqref{eq:total_energy} will be minimized. But the question remains if these obtained level sets $u^\lambda$ can be combined to make an output image. The level sets were defined as $u^\lambda = \mathbbm{1}_{u \leq -\lambda}$, so we need them to be monotonely increasing in increasing +\lambda}$, so we need them to be monotonically increasing in increasing level values, i.e.\ \begin{equation} u^\lambda_x \leq u^\mu_x \quad \forall \lambda \leq \mu, \quad \forall x \in S. \end{equation} -We will later see that our graph cut algorithm finds level sets which -minimizes each level, \emph{and} guarantees that our level sets meet -this requirement. - -\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?} +In the following sections we will present a graph cut algorithm that +finds thresholded images minimizing each level, \emph{while} +guaranteeing that they meet this requirement. \fixme{Some like to call one term the fidelity term, and the other the regularization term?} -- 2.47.3