From 2b3ff8bb39461a82f1a7488347424fcb73aa934d Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Mon, 14 Apr 2014 16:28:49 +0200 Subject: [PATCH] fig folder, and some fixes --- cut.tex | 718 ++++++++++++----------------------------- fig/neigh_subgraph.tex | 44 +++ fig/norm_evolution.tex | 54 ++++ fig/norm_subgraph.tex | 36 +++ flow.tex | 265 +++++++++++++++ main.tex | 6 +- total.tex | 35 +- 7 files changed, 631 insertions(+), 527 deletions(-) create mode 100644 fig/neigh_subgraph.tex create mode 100644 fig/norm_evolution.tex create mode 100644 fig/norm_subgraph.tex create mode 100644 flow.tex diff --git a/cut.tex b/cut.tex index 31f1fd6..4693c1e 100644 --- a/cut.tex +++ b/cut.tex @@ -1,242 +1,184 @@ \section{Graph cut formulation} -\fixme{Short intro here maybe? Something about what this section is all +\fixme{Short intro here. Something about what this section is all about.} -\subsection{Flow networks} +\subsection{Networks} Using the notation of \cite{cormen2009introduction} we will denote a directed graph as $G = (V, E)$ where $V$ is a finite set of vertices, and $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$. When dealing with flow in a -graph we introduce the non-negative capacity function $c : V \times V -\to [0, \infty)$. A positive capacity $c(u, v) = q > 0$ means -that it is possible to send between 0 and $q$ flow from $u$ to $v$. +an edge from $u$ to $v$ in the graph $G$. -There are two special nodes in the network, the source $s$ and the sink -$t$. In the context of maximal flow, the source can produce and the sink -can receive, an unlimited amount of flow. - -For convenience we will let $c(u, v) = 0$ for any edge $(u, v) \not\in -E$, and we do not allow self-loops in our graph. Contrary to Cormen et. -al. in \cite{cormen2009introduction} we allow antiparallel edges in our -graph \fixme{and it is ok.} - -A flow in the network $G$ is a real-valued function $f : V \times V \to -\mathbb{R}$, such that $f(u, v)$ indicates how much flow is sent over -the edge $(u, v)$. The flow must satisfy these two constraints -\begin{description} - \item[Capacity constraint:] For all $u, v \in V, f(u, v) \leq c(u, - v)$, i.e., for every edge, the flow is less than or equal to the - capacity. - \item[Flow conservation:] For all $u \in V - \{s, t\}$ - \begin{equation} - \sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v), - \end{equation} - i.e., for any node except the source and the sink, the - flow into the node must be equal to the flow out of the node. -\end{description} -For the capacity constraint, we purposedly allow the flow to be -negative, and we will see why later. Finding the maximal flow that is -possible to send from the source to the sink in a network is a much -studied problem, which has numerous applications, and also good -algorithms. +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 +\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 +with capacity function $c$, we call it a network, and write $G = (V, E, +c)$. -When further discussing the max-flow problem we will need the notion of -a residual network $G_f$, which is derived from the original network $G$ -and contains the edges along which it is possible to send additional -flow. This means that $G_f$ contains the edges $(u, v)$ from $G$ where -$f(u,v) < c(u,v)$. A very important realisation is that it is also -possible to push flow \emph{back} along an edge where the flow is -already positive, meaning that if an edge $(u, v)$ has a positive flow -$f(u, v) > 0$, the residual graph $G_f$ should contain an edge $(v, u)$ -with capacity $f(u, v)$. - -Instead of constructing $G_f$ explicitly, we employ a common trick when -modifying the flow of an edge. For every edge $(u, v)$ in the graph, we -will also include an edge $(v, u)$, initially with a capacity of zero, -unless otherwise specified. If the flow along $(u, v)$ is increased -with an amount $q$, we will at the same time subtract $q$ from the flow -of $(v, u)$. This means that $f(v, u) + q \leq c(v, u)$, so it will be -possible to at some later stage push at least $q$ flow back from $v$ to -$u$. The edge $(v, u)$ will be included in the residual graph $G_f$ -since it includes all edges where the flow is less than the capacity. - -\fixme{NOT VERY CLEAR} +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. -\fixme{$\abs{f}$ needs to be defined somewhere?} +\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 graph, is a the minimal $s$-$t$-cut, a -«minimal» line through the graph that cuts a set of edges and separates -the source from the sink. +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. \begin{definition}[$s$-$t$-cut] - Given a network $G = (E, V, c)$, a cut $(S, T)$ of a network $G = - (V, E, c)$ is a partition of $V$ into $S$ and $T = V - S$ such that + 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 \begin{equation} - c(S, T) = \sum_{u \in S} \sum_{v \in S} c(u, v), + c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u, v), \end{equation} - and the minimum $s$-$t$-cut is the cut whose capacity is minimum - over all possible $s$-$t$-cuts in the network. + and a minimum $s$-$t$-cut is a cut whose capacity is minimum over + all possible $s$-$t$-cuts in the network. \end{definition} -When finding this minimum cut, we make use of an important duality -theorem in network flow theory, stating that the capacity of the minimum -$s$-$t$-cut in a network, is equal to the maximum flow from $s$ to $t$. -\begin{theorem}[Max-flow min-cut theorem] - If $f$ is a flow in a network $G = (V, E, c)$ with source $s$ and - sink $t$, then the following is equivalent: - \begin{enumerate} - \item $f$ is a maximum flow in $G$. - \item The residual network $G_f$ contains no augmenting paths. - \item $\abs{f} = c(S, T)$ for some cut $(S, T)$ of $G$. - \end{enumerate} -\end{theorem} -See \cite{cormen2009introduction} for a proof. Note that for any -$s$-$t$-cut $C = \{S, T\}$ in a graph $G$ with flow $\abs{f}$ from source to sink, -the \emph{flow} across the cut is always equal to $\abs{f}$, while the -\emph{capacity} of the cut will depend on the cut, and will only be -equal to $\abs{f}$ for one of the minimal $s$-$t$-cuts in $G$. - -\fixme{But how do we find THE minimum cut? Which one do we want? The -maximum one? The minimum one? EEEEK} - -\fixme{Maximum vs maximal.} - -\subsection{Augmenting flow algorithms} -The family of augmenting flow algorithms represent a popular approach to -the max flow problem. The idea is simply to look for paths from the -source to the sink in the graph, along which is is possible to send more -flow, and then send the maximum amount of flow along this path. When no -such path exists anymore, no more flow can be sent through the graph, -and maximum flow has been reached. -\begin{figure} - \centering -\begin{tikzpicture}[scale=1.5] - \node[vertex] (s) at (0, 0) {s}; - \node[vertex] (u) at (2, 1) {u}; - \node[vertex] (v) at (2, -1) {v}; - \node[vertex] (t) at (4, 0) {t}; - - \path[edge] (s) -- node[weight] {5/5} (u); - \path[selected edge] (s) -- node[weight] {} (v); - \path[edge] (s) -- node[weight] {0/5} (v); - \path[selected edge] (u) -- node[weight] {} (v); - \path[edge] (u) -- node[weight] {5/5} (v); - \path[selected edge] (u) -- node[weight] {} (t); - \path[edge] (u) -- node[weight] {0/5} (t); - \path[edge] (v) -- node[weight] {5/5} (t); -\end{tikzpicture} -\caption{A network with the flow and capacity shown as flow/capacity. -The marked path is a valid augmenting path from $s$ to $t$, and by -increasing the flow along it, we will push flow back from $v$ to -$u$. \fixme{refer to this figure somewhere?}} -\label{fig:aug_flow} -\end{figure} - -\subsubsection{Ford-Foulkerson} -The Ford-Foulkerson algorithm is the most basic augmenting flow -algorithm, which can be extended to more advanced algorithms. -\begin{algorithm} -\begin{algorithmic} - \Function{Ford-Foulkerson}{$G$, $s$, $t$} - \While{there exists a path $p$ from $s$ to $t$ in the residual - network $G_f$} - \State $\alpha \gets \min\{c_f(u, v) : (u, v) \in p \}$ - \ForAll{$(u, v) \in p$} - \State $f(u, v) \mathrel{+}= \alpha$ - \State $f(v, u) \mathrel{-}= \alpha$ - \EndFor - \EndWhile - \EndFunction -\end{algorithmic} -\caption{\sf The Ford-Foulkerson max-flow algorithm} -\end{algorithm} -Of course, a choice has to be made on how to search for a path in the -residual network. A common choice is to do a breadth-first search from -the source node until the sink node is found, as this will yield the -shortest possible augmenting path. This version of the algorithm is -called Edmonds-Karp and has a running time of $O(VE^2)$. The reasoning -being that on each iteration, at least one edge disappears from the -residual network, and each edge can only disappear and reappear in the -residual network $O(V)$ times. This means that the number of loop -iterations is in $O(VE)$. Going through the edges in the augmenting path -takes $O(E)$ time, giving a total running time of $O(VE^2)$. A formal -proof can be found in \cite{cormen2009introduction}. -\fixme{Unneccesary hand-waving?} - -\fixme{HAVE TO REFER TO THE ALGORITHMS, THEY ARE FLOATING} -\fixme{Use res or $c_f$?} - -\subsubsection{Dinitz'} -\fixme{I did implement this, but it is maybe not very central to the -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 -minimize the energy in (\fixme{should make an equation in the last -section I can reference}) using minimal graph cuts. We will do this by -constructing simple graphs representing the separate summands of the -energy function. For these small graphs it will be easy to verify that -the minimal cut also minimizes the energy function. These small graphs -can be added together giving a graph representing the complete energy -function of (\fixme{?}). +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.} + +\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 +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}. 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 -\begin{definition}[Graph representable functions] - Let $E(x_1, \hdots, x_n)$ be a function of $n$ binary variables. - $E$ is graph-representable - if there exists a graph $G = (V, E, c)$ with terminals $s$ and $t$, +\begin{definition}[Network representable functions] + A function $\mathcal{E}(x_1, \hdots, x_n)$ of $n$ binary + variables is network-representable if + there exists a network $G = (V, E, c)$ with terminals $s$ and $t$, and a subset of vertices $V_0 = \{v_1, \hdots, v_n\} \subseteq V - \{s, t\}$ such that, for any configuration $(x_1, \hdots, x_n) \in - \{0, 1\}^n$, the value of the energy $E(x_1, \hdots, x_n)$ is equal - to a constant plus the cost of the minimum $s$-$t$-cut among all - cuts $C = \{S, T\}$ where $x_i = 0 \Leftrightarrow v_i \in S$ and - $x_i = 1 \Leftrightarrow v_i \in T$, $\forall\, 1 \leq i \leq n$. + \{0, 1\}^n$, the value of the energy $\mathcal{E}(x_1, \hdots, x_n)$ + is equal to a constant plus the cost of the minimum $s$-$t$-cut + among all cuts $C = \{S, T\}$ where $x_i = 0 \Leftrightarrow v_i \in + S$ and $x_i = 1 \Leftrightarrow v_i \in T$, $\forall\, 1 \leq i \leq + n$. + \label{def:network_representable} \end{definition} -From this definition we see that if we have a graph-representable -function $E$ it is possible to find the exact global minimum of $E$ by -finding the minimal $s$-$t$-cut in the corresponding graph. - -Further they present an important result concerning what kinds of -functions are graph-representable -\fixme{Bad title} -\begin{theorem}[Identification of graph representable functions] - Given an energy function $E$ of $n$ binary variables on the form +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. + +Furthermore Kolmogorov and Zabih present an important result concerning +what kinds of functions are network-representable. +\begin{theorem}[Identification of network representable functions] + Given an energy function $\mathcal{E}$ of $n$ binary variables on + the form \begin{equation} - E(x_1, \hdots, x_n) = \sum_i E^i(x_i) - + \sum_{i 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{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} + \input{fig/norm_evolution} \end{figure} \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 + \begin{tikzpicture}[scale=1.3] + \begin{scope}[ + yshift=-100,every node/.append style={ + yscale=.3,yslant=.4,xslant=-0.6},yscale=.3,yslant=.4,xslant=-0.6 ] - {$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 -versus the $S$-side.} - -\fixme{Graph is usually called network when we are talking about flow.} - -\begin{figure} - \centering -\begin{tikzpicture}[scale=1.3] - \begin{scope}[ - yshift=-100,every node/.append style={ - yscale=.3,yslant=.4,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) {}; + \foreach \x in {0,...,3} { + \foreach \y in {0,...,3} { + \node[vertex] (\x\y) at (\x, \y) {}; + } } - } - \foreach \x in {0,...,3} { - \foreach \y [count=\yi] in {0,...,2} { - \path[double edge] (\x\y)--(\x\yi); - \path[double edge] (\y\x)--(\yi\x); + \foreach \x in {0,...,3} { + \foreach \y [count=\yi] in {0,...,2} { + \path[double edge] (\x\y)--(\x\yi); + \path[double edge] (\y\x)--(\yi\x); + } } - } - \end{scope} + \end{scope} - \node[vertex] (s) at (1, 0) {s}; - \node[vertex] (t) at (1, -5) {t}; + \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); - \path[edge] (\x\y) to (t); - } - } - \end{pgfonlayer} -\end{tikzpicture} -\caption{HELLO} -\label{fig:image_flow} + \begin{pgfonlayer}{background} + \foreach \x in {0,...,3} { + \foreach \y in {0,...,3} { + \path[edge] (s) to (\x\y); + \path[edge] (\x\y) to (t); + } + } + \end{pgfonlayer} + \end{tikzpicture} + \caption{HELLO} + \label{fig:image_flow} \end{figure} -\fixme{DISREGARD THIS $\downarrow$} - -\subsubsection{Dinic's algorithm} -The «best» of the augmenting-path algorithms (citation needed). Makes a -level graph with BFS, and finds a blocking flow through this graph which -only goes from nodes with one label to nodes with greater labels. When -this blocking flow is found we restart at the BFS. - -\subsubsection{The push-relabel algorithm} -The nodes are allowed to have a positive excess but we still follow the -capacity constraints. The nodes also have a labeling, which has to be -valid. Push flow from active nodes, and relabel, preferrably in a -specific order, until it is not possible anymore. The minimal cut is -actually found before the flow becomes valid (has to be explained). - -Because of the way the graph evolves, we can reuse the graph between the -different labels. - -Initially proposed in \cite{goldberg1988new} where one can also find -proof that the algorithm maintains a valid labeling and that it -terminates at at maximal flow. Also has the lemma that if you have a -preflow, then there is no path from $s$ to $t$ in the residual graph. -But what is a preflow? Also, the distance label never decreases. Also -propose the global relabeling heuristic. - -Shiloach and Vishkin originally proposed the FIFO way of doing things -(according to Golberg and Tarjan)? - -Cherkassky and Goldberg present some good implementation tips in -\cite{cherkassky1997implementing}, for example the global and gap -relabeling heuristics. Also has OK presentations of the different ways -of choosing the order of discharge operations. In the results I should -include some results with and without the heuristics. - -\cite{ahuja1997computational} has some good performance analysis. - -\cite{boykov2006graph} is a good source on how graph cuts are used in -image analysis. It considers both one level graphs, and multilevel -graphs. Which is nice. It has just a small section on the different -algorithms that exist and that the special Boykov Kolmogorov algorithm -is the best. - -\cite{derigs1989implementing} is also a good source for the different -heuristics. And also on the neighbor list that should not be reset after -each discharge (should try to implement this again, and reset at every -relabel!). Also has some semi-usable notes on how the minimal cut is -found after phase 1 of the algorithm is finished. Note that in this -article the gap relabeling heuristic is also called RELABEL-GLOBAL. - -\begin{algorithm} -\begin{algorithmic} - \Function{Push}{$u$} - \ForAll{$v$ neighbour of $u$} - \If{$res(u, v) > 0$} - \State $f \gets \min(res(u, v), excess[u])$ - \State $flow(u, v) \mathrel{+}= f$ - \State $flow(v, u) \mathrel{-}= f$ - \State $excess[u] \mathrel{-}= f$ - \State $excess[v] \mathrel{+}= f$ - \EndIf - \EndFor - \EndFunction -\end{algorithmic} -\caption{\sf The push procedure of the Push-Relabel algorithm} -\end{algorithm} - -\begin{algorithm} -\begin{algorithmic} - \Function{Relabel}{$u$} - \If{$u$ is only node at its height} - \Call{Gap}{$u$} - \Else - \State $height[u] \gets min(height[v] \, \forall v \in - neighbors[u] : res(u, v) > 0) + 1$ - \EndIf - \EndFunction -\end{algorithmic} -\caption{\sf The relabel procedure of the Push-Relabel algorithm} -\end{algorithm} - -\begin{algorithm} -\begin{algorithmic} - \Function{Gap}{$u$} - \State $k \gets height[u]$ - \ForAll{$v$ with height $\geq k$} - \State $height[v] \gets N$ - \EndFor - \EndFunction -\end{algorithmic} -\caption{\sf The gap procedure of the Push-Relabel algorithm} -\end{algorithm} - -\subsubsection{Other algorithms} -Special made augmenting flow algorithm for this type of graphs. Used in -software1, software2, etc. Is fast. - diff --git a/fig/neigh_subgraph.tex b/fig/neigh_subgraph.tex new file mode 100644 index 0000000..bc6ab03 --- /dev/null +++ b/fig/neigh_subgraph.tex @@ -0,0 +1,44 @@ +\centering +\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)$. See Table + \ref{tab:neigh_energy} for an overview of the different possible + configurations of $(u^\lambda_x, u^\lambda_y)$ and the corresponding + cuts. +} +\label{fig:neigh_subgraph} diff --git a/fig/norm_evolution.tex b/fig/norm_evolution.tex new file mode 100644 index 0000000..21f65a6 --- /dev/null +++ b/fig/norm_evolution.tex @@ -0,0 +1,54 @@ +\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 \eqref{eq:total_energy} increases monotonically with $\lambda$. +} +\label{fig:norm_evolution} diff --git a/fig/norm_subgraph.tex b/fig/norm_subgraph.tex new file mode 100644 index 0000000..43f44d7 --- /dev/null +++ b/fig/norm_subgraph.tex @@ -0,0 +1,36 @@ +\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{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{ + The network construction for the fidelity term $E^x(u^\lambda_x)$. + See Table \ref{tab:fid_energy} for an overview of the different + possible cuts, and on why this construction works. +} +\label{fig:norm_subgraph} diff --git a/flow.tex b/flow.tex new file mode 100644 index 0000000..ce7c9b5 --- /dev/null +++ b/flow.tex @@ -0,0 +1,265 @@ +\section{Maximum flow approach} +\fixme{Capacities introduced in the last chapter. Introduce flow here, +and shortly what is to come} + +\subsection{Flow networks} +We have already introduced capacities, and briefly mentioned the notion +of flow as something the capacity limits. In other words, flow is +something we can send through our network, but the capacity limits how +much we can send along each edge. It is useful to imagine for example a +water supply network with pipes of different sizes. The source and sink +introduced earlier would then be represented by a water reservoir, and a +drain out to sea, respectively. + +Formally, we introduce the \emph{flow} as the function $f : V \times V +\to [0, \infty)$. This function keeps count of how much flow we are +sending through each edge of our network and must satisfy the following +two constraints +\begin{description} + \item[Capacity constraint:] For all $u, v \in V, 0 \leq f(u, v) \leq c(u, + v)$, i.e., for every edge, the flow is less than or equal to the + capacity. + \item[Flow conservation:] For all $u \in V - \{s, t\}$ + \begin{equation} + \sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v), + \end{equation} + i.e., for any node except the source and the sink, the + flow into the node must be equal to the flow out of the node. +\end{description} +Note that we have defined $f$ with all pairs of vertices as its domain, +even though it is only non-zero on edges $(u, v) \in E$. This makes it +easier to write sums like in the flow conservation constraint. + +\fixme{No anti-parallel edges.} + +\subsubsection{Residual network} +When further discussing the max-flow problem we will need the notion of +a residual network $G_f = (V_f, E_f, c_f)$, which is derived from the +original network $G$ and contains the edges along which it is possible +to send additional flow. This means that $E_f$ contains the edges $(u, +v)$ from $E$ where $f(u,v) < c(u,v)$. But that is not all, an important +realisation is that it is also possible to push flow \emph{back} along +an edge where the flow is already positive. In other words, sending flow +from $v$ to $u$ by cancelling some or all of the flow that is already +going from $u$ to $v$. + +Thus the capacity function $c_f$ of our residual network becomes +\begin{equation} + c_f(u, v) = + \begin{cases} + c(u, v) - f(u, v) & \text{if } (u, v) \in E, \\ + f(v, u) & \text{if } (v, u) \in E, \\ + 0 & \text{otherwise.} + \end{cases} +\end{equation} +The vertices $V_f$ of $G_f$ are the same as the original network $G$, +while the edges $E_f$ are taken to be all pairs of vertices $(u, v)$ +with $c_f(u, v) > 0$. Since we can in $E_f$ at most have all the +original edges, and their reversals, we have $\abs{E_f} \leq \abs{E}$. + +\fixme{$\abs{f}$ needs to be defined somewhere?} + +What we seek in our graph, is a the minimal $s$-$t$-cut, a +«minimal» line through the graph that cuts a set of edges and separates +the source from the sink. +\begin{definition}[$s$-$t$-cut] + Given a network $G = (E, V, c)$, a cut $(S, T)$ of a network $G = + (V, E, c)$ 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 S} c(u, v), + \end{equation} + and the minimum $s$-$t$-cut is the cut whose capacity is minimum + over all possible $s$-$t$-cuts in the network. +\end{definition} + +\fixme{COROLLARY 26.5 in Cormen.} +\fixme{Define $\abs{f}$.} + +When finding this minimum cut, we make use of an important duality +theorem in network flow theory, stating that the capacity of the minimum +$s$-$t$-cut in a network, is equal to the maximum flow from $s$ to $t$. +\begin{theorem}[Max-flow min-cut theorem] + If $f$ is a flow in a network $G = (V, E, c)$ with source $s$ and + sink $t$, then the following is equivalent: + \begin{enumerate} + \item $f$ is a maximum flow in $G$. + \item The residual network $G_f$ contains no augmenting paths. + \item $\abs{f} = c(S, T)$ for some cut $(S, T)$ of $G$. + \end{enumerate} +\end{theorem} +See \cite{cormen2009introduction} for a proof. Note that for any +$s$-$t$-cut $C = (S, T)$ in a graph $G$ with flow $\abs{f}$ from source +to sink, the \emph{flow} across the cut is always equal to $\abs{f}$, +while the \emph{capacity} of the cut will depend on the cut, and will +only be equal to $\abs{f}$ for one of the minimal $s$-$t$-cuts in $G$. + +\fixme{But how do we find THE minimum cut? Which one do we want? The +maximum one? The minimum one? EEEEK} + +\subsection{Augmenting flow algorithms} +The family of augmenting flow algorithms represent a popular approach to +the max flow problem. The idea is simply to look for paths from the +source to the sink in the graph, along which is is possible to send more +flow, and then send the maximum amount of flow along this path. When no +such path exists anymore, no more flow can be sent through the graph, +and maximum flow has been reached. +\begin{figure} + \centering + \begin{tikzpicture}[scale=1.5] + \node[vertex] (s) at (0, 0) {s}; + \node[vertex] (u) at (2, 1) {u}; + \node[vertex] (v) at (2, -1) {v}; + \node[vertex] (t) at (4, 0) {t}; + + \path[edge] (s) -- node[weight] {5/5} (u); + \path[selected edge] (s) -- node[weight] {} (v); + \path[edge] (s) -- node[weight] {0/5} (v); + \path[selected edge] (u) -- node[weight] {} (v); + \path[edge] (u) -- node[weight] {5/5} (v); + \path[selected edge] (u) -- node[weight] {} (t); + \path[edge] (u) -- node[weight] {0/5} (t); + \path[edge] (v) -- node[weight] {5/5} (t); + \end{tikzpicture} + \caption{A network with the flow and capacity shown as flow/capacity. + The marked path is a valid augmenting path from $s$ to $t$, and by + increasing the flow along it, we will push flow back from $v$ to + $u$. \fixme{refer to this figure somewhere?}} + \label{fig:aug_flow} +\end{figure} + +\subsubsection{Ford-Fulkerson} +The Ford-Fulkerson algorithm is the most basic augmenting flow +algorithm, which can be extended to more advanced algorithms. +\begin{algorithm} +\begin{algorithmic} + \Function{Ford-Fulkerson}{$G$, $s$, $t$} + \While{there exists a path $p$ from $s$ to $t$ in the residual + network $G_f$} + \State $\alpha \gets \min\{c_f(u, v) : (u, v) \in p \}$ + \ForAll{$(u, v) \in p$} + \State $f(u, v) \mathrel{+}= \alpha$ + \State $f(v, u) \mathrel{-}= \alpha$ + \EndFor + \EndWhile + \EndFunction +\end{algorithmic} +\caption{\sf The Ford-Fulkerson max-flow algorithm} +\end{algorithm} +Of course, a choice has to be made on how to search for a path in the +residual network. A common choice is to do a breadth-first search from +the source node until the sink node is found, as this will yield the +shortest possible augmenting path. This version of the algorithm is +called Edmonds-Karp and has a running time of $O(\abs{V}\abs{E}^2)$. The +reasoning being that on each iteration, at least one edge disappears +from the residual network, and each edge can only disappear and reappear +in the residual network $O(\abs{V})$ times. This means that the number +of loop iterations is in $O(\abs{V}\abs{E})$. Going through the edges in +the augmenting path takes $O(\abs{E})$ time, giving a total running time +of $O(\abs{V}\abs{E}^2)$. A formal proof can be found in +\cite{cormen2009introduction}. +\fixme{Unneccesary hand-waving?} + +\fixme{HAVE TO REFER TO THE ALGORITHMS, THEY ARE FLOATING} + +\subsubsection{Dinitz'} +\fixme{I did implement this, but it is maybe not very central to the +project/report, since I use an other algorithm in the final +implementation. Maybe a comparison would be nice though.} + +\fixme{DISREGARD THIS $\downarrow$} + +\subsubsection{Dinic's algorithm} +The «best» of the augmenting-path algorithms (citation needed). Makes a +level graph with BFS, and finds a blocking flow through this graph which +only goes from nodes with one label to nodes with greater labels. When +this blocking flow is found we restart at the BFS. + +\subsubsection{The push-relabel algorithm} +The nodes are allowed to have a positive excess but we still follow the +capacity constraints. The nodes also have a labeling, which has to be +valid. Push flow from active nodes, and relabel, preferrably in a +specific order, until it is not possible anymore. The minimal cut is +actually found before the flow becomes valid (has to be explained). + +Because of the way the graph evolves, we can reuse the graph between the +different labels. + +Initially proposed in \cite{goldberg1988new} where one can also find +proof that the algorithm maintains a valid labeling and that it +terminates at at maximal flow. Also has the lemma that if you have a +preflow, then there is no path from $s$ to $t$ in the residual graph. +But what is a preflow? Also, the distance label never decreases. Also +propose the global relabeling heuristic. + +Shiloach and Vishkin originally proposed the FIFO way of doing things +(according to Golberg and Tarjan)? + +Cherkassky and Goldberg present some good implementation tips in +\cite{cherkassky1997implementing}, for example the global and gap +relabeling heuristics. Also has OK presentations of the different ways +of choosing the order of discharge operations. In the results I should +include some results with and without the heuristics. + +\cite{ahuja1997computational} has some good performance analysis. + +\cite{boykov2006graph} is a good source on how graph cuts are used in +image analysis. It considers both one level graphs, and multilevel +graphs. Which is nice. It has just a small section on the different +algorithms that exist and that the special Boykov Kolmogorov algorithm +is the best. + +\cite{derigs1989implementing} is also a good source for the different +heuristics. And also on the neighbor list that should not be reset after +each discharge (should try to implement this again, and reset at every +relabel!). Also has some semi-usable notes on how the minimal cut is +found after phase 1 of the algorithm is finished. Note that in this +article the gap relabeling heuristic is also called RELABEL-GLOBAL. + +\begin{algorithm} +\begin{algorithmic} + \Function{Push}{$u$} + \ForAll{$v$ neighbour of $u$} + \If{$res(u, v) > 0$} + \State $f \gets \min(res(u, v), excess[u])$ + \State $flow(u, v) \mathrel{+}= f$ + \State $flow(v, u) \mathrel{-}= f$ + \State $excess[u] \mathrel{-}= f$ + \State $excess[v] \mathrel{+}= f$ + \EndIf + \EndFor + \EndFunction +\end{algorithmic} +\caption{\sf The push procedure of the Push-Relabel algorithm} +\end{algorithm} + +\begin{algorithm} +\begin{algorithmic} + \Function{Relabel}{$u$} + \If{$u$ is only node at its height} + \Call{Gap}{$u$} + \Else + \State $height[u] \gets min(height[v] \, \forall v \in + neighbors[u] : res(u, v) > 0) + 1$ + \EndIf + \EndFunction +\end{algorithmic} +\caption{\sf The relabel procedure of the Push-Relabel algorithm} +\end{algorithm} + +\begin{algorithm} +\begin{algorithmic} + \Function{Gap}{$u$} + \State $k \gets height[u]$ + \ForAll{$v$ with height $\geq k$} + \State $height[v] \gets N$ + \EndFor + \EndFunction +\end{algorithmic} +\caption{\sf The gap procedure of the Push-Relabel algorithm} +\end{algorithm} + +\subsubsection{Other algorithms} +Special made augmenting flow algorithm for this type of graphs. Used in +software1, software2, etc. Is fast. + diff --git a/main.tex b/main.tex index 7a81b16..c20cdc7 100644 --- a/main.tex +++ b/main.tex @@ -28,8 +28,8 @@ \usepackage{color} \usepackage{bbm} % Indicator function \mathbbm{1} -\usepackage{caption} -\usepackage{subcaption} +\usepackage[margin=0.8cm]{caption} +\usepackage[subrefformat=parens,labelformat=parens]{subcaption} \usepackage{xfrac} \usepackage{algorithm} @@ -103,7 +103,7 @@ \input{methods} \input{total} \input{cut} -\input{noise} +\input{flow} \input{results} % Bibliografi/referanseliste skal komme før appendiks diff --git a/total.tex b/total.tex index e6deea5..74a2dd9 100644 --- a/total.tex +++ b/total.tex @@ -415,10 +415,9 @@ Boykov and Kolmogorov prove we have convergence when all of $h$, $\Delta \subsubsection{Fidelity term} Now that the total variation is discretized, we need to take care of the -fidelity term. -We define the following function for some pixel value $k$ and some pixel -position $x$ in the original image $v$, which is the value of the energy -if we were to color pixel $u$ with label $k$ +fidelity term. We define the following function for some pixel value +$k$ and some pixel position $x$ in the original image $v$, which is the +value of the energy if we were to color pixel $x$ with label $k$ \begin{equation} N_x(k) = \abs{k - v_x}^p. \end{equation} @@ -454,6 +453,8 @@ Since $\mathbbm{1}_{\lambda < u_x} = (1 - u^\lambda_x)$ we rewrite (1 - u^\lambda_x) + N_x(0) \end{equation} +\fixme{$E_\lambda^x$} + \subsubsection{Total energy} We have now discretized the energy function and decomposed it into a sum over all the levels $\lambda$. Ignoring the constant term $N_x(0)$ we @@ -463,6 +464,8 @@ are left with \sum_{\lambda=0}^{L-2} \sum_x E^x(u^\lambda_x) + \beta \sum_{\lambda = 0}^{L-2} \sum_{x < y} E^{x,y}(u^\lambda_x, u^\lambda_y) + = \sum_{\lambda=0}^{L-2} F_\lambda(u^\lambda) + \label{eq:total_energy} \end{equation} where \begin{align} @@ -480,29 +483,31 @@ where \right). \label{eq:neigh_energy} \end{align} -In the sum of the energy between neighboring pixels, we consider only +\fixme{In the sum of the energy between neighboring pixels, we consider only relations where $x < y$ since the term \eqref{eq:neigh_energy} is symmetric. The factor of $2$ which appears when combining the terms is -absorbed into the $\beta$ parameter. +absorbed into the $\beta$ parameter.} If we minimize each level separately it is obvious that we also minimize -the total energy. The question is if the 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 level values, i.e.\ +the total energy. In other words if we for every $\lambda$ find a level +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 +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?} \fixme{Some like to call one term the fidelity term, and the other the regularization term?} -\fixme{ - Why is it OK to optimize each - level separately? Why does it work? -} - -- 2.47.3