From e99013a3f98d1fc8426e030f4204e39fe9c6a612 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Mon, 19 May 2014 18:25:45 +0200 Subject: [PATCH] Refactor and more results --- bib.bib | 20 ++ flow.tex | 531 +++--------------------------------------------- main.tex | 1 + pushrelabel.tex | 499 +++++++++++++++++++++++++++++++++++++++++++++ results.tex | 119 ++++++----- total.tex | 25 +-- 6 files changed, 628 insertions(+), 567 deletions(-) create mode 100644 pushrelabel.tex diff --git a/bib.bib b/bib.bib index 456c02d..7b01474 100644 --- a/bib.bib +++ b/bib.bib @@ -176,4 +176,24 @@ year = {2000} } +@incollection{dinitz2006dinitz, + title={Dinitz' algorithm: The original version and Even's version}, + author={Dinitz, Yefim}, + booktitle={Theoretical Computer Science}, + pages={218--240}, + year={2006}, + publisher={Springer} +} + +@article{boykov2004experimental, + title={An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision}, + author={Boykov, Yuri and Kolmogorov, Vladimir}, + journal={Pattern Analysis and Machine Intelligence, IEEE Transactions on}, + volume={26}, + number={9}, + pages={1124--1137}, + year={2004}, + publisher={IEEE} +} + diff --git a/flow.tex b/flow.tex index eef7b59..40027d1 100644 --- a/flow.tex +++ b/flow.tex @@ -181,509 +181,30 @@ See for example \cite{cormen2009introduction} for a description of the breadth-first search, and a formal proof of the running time of the algorithm. -\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.} - -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. - -\section{The push-relabel algorithm} -\fixme{Maybe this could be a section? Since it is a bit different than -regular max-flow-min-cut} - -The push-relabel algorithm is a different approach to the maximum flow -problem, presented by Goldberg and Tarjan in \cite{goldberg1988new}. -Unlike the augmenting flow algorithms, it does not maintain a valid flow -$f$ in the network at all times, but still obtains a valid maximum flow -when the algorithm is finished. - -\subsection{Preflow} -Instead of maintaining a valid flow, we introduce the concept of a -\emph{preflow} as we relax the flow conservation constraint from -earlier. For a preflow $f$, the capacity constraint still holds so the -flow must always be less than the capacity, but we allow positive excess -in the vertices. The flow conservation constraint from before then -becomes -\begin{description} - \item[Preflow conservation:] For all $u \in V - \{s, t\}$ - \begin{equation} - \sum_{v \in V} f(v, u) \geq \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 greater or equal to the flow out of the - node. -\end{description} - -\fixme{Vertex vs.\ node.} -\fixme{Describe saturated in the $G_f$ section. And $N$.} - -For all vertices $u \in V$ we define the excess -\begin{equation} - e(u) = \sum_{v \in V} f(v, u) - \sum_{v \in V} f(u, v), -\end{equation} -which represents the amount of flow which \emph{disappears} in node $u$. -Equivalent to the preflow conservation constraint is stating that $e(u) -\geq 0$ for all vertices $u \in V - \{s,t\}$. - -The idea of the algorithm is to maintain a height map of the -vertices of the network where connected nodes can not have a large -height difference. Then we ``lift'' the source vertex to let as -many units as possible flow through the edges of the network towards the -sink. When a maximum preflow is reached, there will normally be excess -flow in some of the vertices, which has to be pushed back towards the -source in order to obtain a valid flow. - -The height map $d : V \to \mathbb{N}$ is also often called a distance -labeling and it satisfies $d(t) = 0$, and for every edge $(u, v)$ in the -residual network, i.e.\ every edge with $c_f(u, v) > 0$, we require that -$d(u) \leq d(v) + 1$. For every vertex $u$ for which there is a path -through the residual network to the sink, $d(u)$ will be a lower bound -on the length of such a path. - -A vertex $u$ is \emph{active} if $u \in V - \{s,t\}$, it has positive -excess ($e(u) > 0$) and $d(u) < N$. These are the nodes we want to -operate on to increase the preflow. - -\subsection{Basic operations} - -The algorithm performs two basic operations, the \emph{push} and -\emph{relabel} operations, while always maintaining a valid preflow $f$ -and a valid distance labeling $d$. - -\subsubsection{The push procedure} - -The push procedure moves excess flow from an active vertex along an edge -$(u, v) \in E_f$ such that $d(u) = d(v) + 1$, i.e.\ to a vertex with a -smaller distance label. We call such edges \emph{admissible}. See -Algorithm \ref{alg:push} for a pseudocode implementation of the push -operation. - -Assuming that $f$ is a valid preflow, it is easy to verify that $f$ -remains a valid preflow after running the push procedure on some -admissible edge $(u, v)$. The capacity constraint is fulfilled since we -at most increase the flow along $(u, v)$ with the residual capacity -$c_f(u,v)$. The preflow constraint is fulfilled since the excess $e$ -increases for $v$, remains non-negative for $u$ and remains the same for -all other vertices. - -The distance labels are not changed during the push procedure, however, -the residual network can change. The edge $(u, v)$ might disappear, and -an edge $(v, u)$ will surely appear if it does not already exist. Assume -that $d$ is a valid labeling. When starting the push procedure we have -$d(u) = d(v) + 1$, so we also have the following -\begin{align} - d(u) &\leq d(v) + 1 \\ - d(v) &\leq d(u) + 1, -\end{align} -and $d$ remains a valid labeling, even if the edge $(v, u)$ appears. - -\fixme{Change height $h$ to distance $d$.} - -\fixme{Operation < procedure.} - -\begin{algorithm} -\begin{algorithmic} - \Function{Push}{$u$, $v$} - \State $f_\text{aug} \gets \min(c_f(u, v), e(u))$ - \State $f(u, v) \mathrel{+}= f_\text{aug}$ - \State $e(u) \mathrel{-}= f_\text{aug}$ - \State $e(v) \mathrel{+}= f_\text{aug}$ - \EndFunction -\end{algorithmic} -\caption{\sf The push procedure of the Push-Relabel algorithm} -\label{alg:push} -\end{algorithm} - -\subsubsection{The relabel procedure} -The relabel procedure is our tool for changing the distance labels of -our vertices. It changes the label of a vertex to the greatest possible -value, which is one more than the lowest label among its neighbors in -the residual graph. See Algorithm \ref{alg:relabel} for a rather -mathematical pseudocode implementation. -\begin{algorithm} -\begin{algorithmic} - \Function{Relabel}{$u$} -% \If{$u$ is only node at its height} -% \Call{Gap}{$u$} -% \Else - \If{there is a $v \in V$ such that $(u, v) \in E_f$} - \State $d(u) \gets \min\{d(v), \; \forall v \in V : (u,v) \in E_f\} + 1$ - \Else - \State $d(u) \gets N$ - \EndIf -% \EndIf - \EndFunction -\end{algorithmic} -\caption{\sf The relabel procedure of the Push-Relabel algorithm} -\label{alg:relabel} -\end{algorithm} - -If $d$ was a valid labeling before running the relabel procedure, then -we still have $d(u) \leq d(v) + 1$ for all neighbors $v$ of $u$ in the -residual graph, and $d$ remains a valid labeling. The capacity -constraint and preflow constraint remain satisfied assuming they were -satisfied before the procedure was started. - -\subsection{Putting it all together} - -\fixme{Should be clearer what is really happening, and especially when - we are finished/what our goal is. That we are finished as soon as - there are no more active vertices. And that how we get there does - not matter as long as we follow our constraints. -} - -In the first phase of the algorithm we initialize a valid preflow and -distance labeling by saturating all edges out of the source $s$, and -then setting its distance label $d(s) = N$. We then run the push and -relabel procedures when applicable until there are no more active nodes -and a maximum preflow is obtained. - -\fixme{What is saturated?} - -A vertex $u$ can only be successfully relabeled to obtain a new label if -the outgoing edges of $u$ in the residual network have changed since the -previous relabeling. This is why the push and relabel procedures often -are combined into a \emph{discharge} procedure as shown in Algorithm -\ref{alg:discharge}. When it is run on an active vertex $u$, we push as -much as possible of the excess flow to other vertices before the vertex -is relabeled. -\begin{algorithm} -\begin{algorithmic} - \Function{Discharge}{$u$} - \ForAll{$v \in V$ such that $(u, v) \in E_f$} - \If{$c_f(u, v) > 0$ and $d(u) = d(v) + 1$} - \Call{Push}{$u$, $v$} - \EndIf - \EndFor - - \If{$e(u) > 0$} - \Call{Relabel}{$u$} - \EndIf - \EndFunction -\end{algorithmic} -\caption{\sf The discharge procedure of the Push-Relabel algorithm} -\label{alg:discharge} -\end{algorithm} - -In the second phase of the algorithm this preflow is turned into a -maximum flow by sending excess flow which did not reach the sink, from -inside the network back to the source. We can skip this part of the -algorithm, as it is possible to identify a minimum cut as soon as the -first phase is finished, and the following theorem allows us to do that. -\begin{theorem}[Cut identification] - Given a network $G = (V, E, c)$, assume that the first phase of - the push-relabel algorithm has terminated and no more active nodes - remain. Then there exists a $k \in \mathbb{N} \cap \left(0, N - \right)$ such that there is no vertex with label $k$, and the vertex - sets $S = \{ u \in V : d(u) > k\}$ and $T = V - S$ define a minimum - cut $C = (S, T)$ in $G$. - \label{thm:cut_identification} -\end{theorem} -\begin{proof} - There are $N$ nodes, the source has label $N$ and the sink has label - $0$, and the $N - 2$ remaining vertices can not occupy all the $N-1$ - labels in $\{1, \ldots, N-1\}$, so there must exist an $k$ as - described. - - As no vertex has label $k$, we can write $T = \{ u \in V : d(u) > - k\}$. - - Assume there was an edge $(u, v) \in E_f$ such that $u \in S$ and $v - \in T$. From the construction of $S$ and $T$, we would have $d(v) - \leq d(u) + 2$, which contradicts the labeling constraint, so no - such non-saturated edge from $S$ to $T$ can exist. - - From the construction of $E_f$ we now know that all edges in $E$ - from $S$ to $T$ are saturated, and all edges from $T$ to $S$ have no - flow. This means that the capacity of the cut is equal to the flow - through the cut, i.e.\ $c(S, T) = f(S, T)$. - - Since the first phase of the algorithm has terminated, there can be - no active vertices, and therefore no excess in $T$, except for the - sink. If all flow excess in vertices in $S$ is returned to the - source, we can apply the max-flow min-cut theorem to conclude that - $C = (S, T)$ is a minimum $s$-$t$-cut, since the cut capacity is - equal to the flow from $s$ to $t$. -\end{proof} - -We will see later that with the gap relabeling heuristic, there will -always be a gap at label $k = N - 1$ such that we can construct our cut -by taking $S = \{ u \in V : d(u) \geq N \}$. - -\fixme{Sketch of proof, could be nicer, shorter (split up?) and more -rigorous maybe.} - -\subsection{Complexity} -Bleep bloop. -\fixme{Edge list problematikk.} -\fixme{We have proved that when the first phase has terminated, we can - find the minimum cut, but should we maybe prove that the first phase - will terminate? Using the fact that the distance labels can only - increase? And the fact that we only push to lower vertices? - Computing the complexity is kind of like proving termination since - we find an upper bound on the number of operations. -} - -\subsection{Vertex selection rules} -\fixme{Also mention this over complexity.} -Until now we have just stated that the discharge procedure is run on -active nodes until there are no more active nodes left. The choice of -the order in which to discharge these active nodes remain, and multiple -possibilities exist. - -The FIFO approach is to always maintain a queue of active vertices. When -the vertex from the beginning of the queue is discharged, other vertices -might become active, and these are added at the end of the queue. -\fixme{Running time and reference.} - -The highest level selection rule always discharges the vertex with the -largest distance label. -\fixme{Running time and reference.} - -\subsection{Heuristics} -Different heuristics exists that can speed up the algorithm -considerably. Being heuristics, they are not guaranteed to work, and -might perform differently on different kinds of networks. The most used -heuristics are the gap and global relabeling heuristics, both aiming to -reduce the total number of relabeling steps. - -The gap relabeling heuristic aims to find a label $k$ as in Theorem -\ref{thm:cut_identification} such that no vertex has that label. -From vertices $u$ with $d(u) > k$, there are no unsaturated edges going -to vertices with smaller distance labels so no more flow can ever find -its way from these vertices to the sink. These vertices are therefore -given the label $N$ and never considered again as they will never become -active. Algorithm \ref{alg:gap} shows a pseudocode representation of -what is done once a gap $k$ is found. - -\begin{algorithm} -\begin{algorithmic} - \Function{Gap}{$k$} - \ForAll{$u \in V$ such that $d(u) > k$} - \State $d(u) \gets N$ - \EndFor - \EndFunction -\end{algorithmic} -\caption{\sf The gap procedure of the Push-Relabel algorithm} -\label{alg:gap} -\end{algorithm} - -\fixme{This could be a lemma with a proof maybe? Refer to Derigs and -Meyer.} - -But why does this work? The only thing we need to verify is that given a -network with a valid preflow and a valid labeling, the gap relabeling -procedure will not change the validity of these two things. - -\begin{lemma}[Gap relabeling validity] - Given a network $G = (V, E, c)$, a distance labeling $d$ and a - preflow $f$, assume there exists a gap $k$ such that no vertex has - label $k$. Running the gap relabeling procedure on label $k$ will - yield a valid distance labeling and an unchanged and valid preflow - $f$. -\end{lemma} -\begin{proof} - No new edges are created, no edges disappear, the preflow is - unchanged, so the preflow and capacity constraint remain satisfied - after the gap relabeling. - - Define the vertex sets $S = \{ u \in V : d(u) > k\}$ and $T = V - - S$. Initially, we have $d(u) \leq d(v) + 1$ for every edge $(u,v) - \in E_f$. These inequalities have to hold after the gap procedure is - finished, when all vertices $u \in S$ have label $d(u) = N$. - - For $(u, v) \in E_f$ we have four possibilities - \begin{description} - \item[$u, v \in T$] - The labels $d(u)$ and $d(v)$ remain unchanged and the - inequality still holds. - \item[$u, v \in S$] - After the gap procedure we have $d(u) = d(v)$ so the - inequality still holds. - \item[$u \in S, v \in T$] - This is not possible as it would imply $d(u) \geq d(v) + 2$ - and we have assumed an initial valid labeling. - \item[$u \in T, v \in S$] - After relabeling we have $d(u) < k < N < d(v) + 1$. - \end{description} - - Hence, both the preflow $f$ and distance labeling $d$ are valid. - - \fixme{A bit long, could be more compact since it is not really a - very interesting proof? (And it's not really a lemma either?)} -\end{proof} - -When running the push-relabel algorithm with the gap heuristic, we can -be sure that there will never be a node $u$ with label $d(u) = N-1$ at -the end of the algorithm, i.e.\ we know that there will always be a gap -at label $N-1$. Using the same reasoning as in Theorem -\ref{thm:cut_identification}, if there was a vertex with label $N-1$, -there would only be $N-3$ possibly having labels in $[1, N-2]$, so a gap -must exist somewhere in that interval. When using the gap relabeling -heuristic, such a gap can not exist, so we can conclude that there is no -vertex with label $N-1$. - -Using Theorem \ref{thm:cut_identification} we can then conclude that the -sets $S = \{ u \in V : d(u) \geq N\}$ and $T = V - S$ form a minimum cut -of the network. - -\fixme{Ugh, what a mess. Lemma maybe?} - -\subsection{Parametric push-relabel algorithm} -Now we have an algorithm for finding a minimum $s$-$t$-cut in a network, -so let's return to the network constructed in Section -\ref{sec:network_construction}. For every level $\lambda \in \{0, -\ldots, L\}$ we want to find a minimum $s$-$t$-cut which gives us the -thresholded image $u^\lambda$. These can then hopefully be stacked -together to form the final image $u$. - -\subsubsection{Network reuse} -Solving $L$ separate minimum cut problems seems like a lot of work, but -when using the push-relabel algorithm we will, if we do things in the -right order, be able to reuse the network when going from one label to -the next. - -\begin{figure} - \input{fig/norm_evolution} -\end{figure} - -Going back to the network representations in Figure -\ref{fig:norm_subgraph} and Figure \ref{fig:neigh_subgraph} we know that -only the capacity of edges from sub-networks representing the fidelity -term depend on our level parameter $\lambda$. From the expression in -\eqref{eq:fidelity_energy0}, visualized in Figure -\ref{fig:norm_evolution}, we see that the energy term $E^x(0)$ increases -monotonically with increasing $\lambda$ parameter. Let $u, v \in V - -\{s, t\}$. Since the edges in Figure \ref{fig:norm_subgraph} now are the -only ones depending on $\lambda$, the following is true for -\emph{decreasing} values of $\lambda$ -\begin{description} - \item[Edges from $s$ to $u$] - As seen in Figure \ref{fig:norm_subgraph_neg} the capacity of - these edges will increase monotonically with decreasing - $\lambda$ parameter. - \item[Edges from $u$ to $v$] - These edges have no $\lambda$-dependence and will remain - unchanged. - \item[Edges from $v$ to $t$] - As seen in Figure \ref{fig:norm_subgraph_pos} the capacity of - these edges will decrease monotonically with decreasing - $\lambda$ parameter. -\end{description} - -After running the push-relabel algorithm for $\lambda = k$, we are left -with a network $G = (V, E, c)$, a preflow $f$ and a labeling $d$. To -obtain the network for $\lambda = k-1$ we have to change the capacity of -two different kinds of edges, and this is done in the following way to -keep the capacity and preflow constraints satisfied. -\begin{description} - \item[Edges from $s$ to $u$] - The capacity $c(s, u)$ is increased, and the flow is set to be - equal to the capacity $f(s, u) = c(s, u)$. The vertex $u$ might - have an increased excess $e(u)$, which might in turn make it - active. - \item[Edges from $v$ to $t$] - The capacity $c(v, t)$ is decreased. If it is decreased to a - value below the current flow value, we set $f(v, t) = c(v, t)$ - which will decrease the excess of the sink $t$, and increase the - excess of $v$. -\end{description} - -None of these actions will create new edges in the residual network, and -we do not change the labeling $d$, so the labeling constraints are also -satisfied in the new network. - -Through this procedure we have easily created the network for $\lambda = -k-1$, and the distance labels remain the same. As these labels always -increase monotonically, we have a head start compared to if we had reset -the flow and labels. - -\subsubsection{Output image construction} - -We mentioned already in section \ref{sec:total_energy} that in order to -be able to construct our output image $u$, the thresholded images -$u^\lambda$ would have to stack one on top of the other as shown in -Figure \ref{fig:img_decomp}. We will now show that through reuse of the -distance labels from the last iteration of the push-relabel algorithm, -we can guarantee that it is possible to stack the thresholded images. - -\fixme{More precise statement than ``stack on top of each other''} - -Consider two subsequent runs of the push-relabel algorithm, for labels -$\lambda = k$ and $\lambda = k-1$ ending with distance labels $d^k$ and -$d^{k-1}$ respectively. We already know that the distance labels $d$ are -monotonically increasing. This means that the set $\{ u \in V : d(u) -\geq N \}$ is increasing in size, more precisely, we have the inclusion -\begin{equation} - \{ u \in V : d^k(u) \geq N \} \subseteq \{ u \in V : d^{k-1}(u) \geq - N \} -\end{equation} - -We then construct our output image $u$ by giving each pixel the value -\begin{equation} - u_x = \min \{ \lambda \in \{0, \ldots, L-1\} : u^\lambda_x = 1 \}. -\end{equation} -This marks the end of the description of the implemented algorithm, but -we will further discuss some possible improvements, and also look at -results when using the method on different kinds of pictures, with -different kinds of noise. - -\subsection{Divide and conquer} -\fixme{Write something here.} - -\subsection{Implementation} -\cite{opencv_library} - -\subsection{Bleep bloop} - -Maybe we should delete the $u$-$t$ edge when the vertex reaches a level -> 1? - -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, preferably 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. - -\subsubsection{Other algorithms} -Special made augmenting flow algorithm for this type of graphs. Used in -software1, software2, etc. Is fast. +\subsection{Other algorithms} +There are many different maximum flow algorithms that fall into the +augmenting path category, although we will see a different approach in +the next section. + +The algorithm of Dinitz, originally published in 1970, later improved +on, and described by the original author in \cite{dinitz2006dinitz}, is +a variant of the augmenting path algorithm. It maintains a distance +labeling $d(u)$ of the vertices $u \in V$ in the network, where $d(u)$ +is the shortest path from the $s$ to $u$ in the residual network. This +can be computed with a simple breadth-first search. The next step is to +construct a blocking flow $f'$, using only edges in $E_f' = \{ (u,v) \in +E_f : d(u) + 1 = d(v) \}$. The blocking flow is such that if we augment +the flow $f$ by $f'$, there is no longer any paths from $s$ to $t$ +following edges in $E_f'$. After the blocking flow has been found, the +distance labels are recalculated, and the label of the sink will be +increased by at least one. + +Boykov and Kolmogorov present a variant of the augmenting path algorithm +in \cite{boykov2004experimental}, specialized for the kinds of graphs +occuring in graphical applications. It keeps two non-overlapping trees +of non-saturated edges, one with the source and the other with the sink +as its root. These trees are ``grown'' towards eachother and augmenting +paths are found when their leaf nodes touch. In theory, the complexity +of this algorithm is not great, but according the Boykov and Kolmogorov, +it outperforms the other algorithms in experimental comparisons. diff --git a/main.tex b/main.tex index 20cd4f0..c48645c 100644 --- a/main.tex +++ b/main.tex @@ -122,6 +122,7 @@ \input{total} \input{cut} \input{flow} +\input{pushrelabel} \input{results} % Bibliografi/referanseliste skal komme før appendiks diff --git a/pushrelabel.tex b/pushrelabel.tex new file mode 100644 index 0000000..e20b918 --- /dev/null +++ b/pushrelabel.tex @@ -0,0 +1,499 @@ +\section{The push-relabel algorithm} + +The push-relabel algorithm is a different approach to the maximum flow +problem, presented by Goldberg and Tarjan in \cite{goldberg1988new}. +Unlike the augmenting flow algorithms, it does not maintain a valid flow +$f$ in the network at all times, but still obtains a valid maximum flow +when the algorithm is finished. + +\subsection{Preflow} +Instead of maintaining a valid flow, we introduce the concept of a +\emph{preflow} as we relax the flow conservation constraint from +earlier. For a preflow $f$, the capacity constraint still holds so the +flow must always be less than the capacity, but we allow positive excess +in the vertices. The flow conservation constraint from before then +becomes +\begin{description} + \item[Preflow conservation:] For all $u \in V - \{s, t\}$ + \begin{equation} + \sum_{v \in V} f(v, u) \geq \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 greater or equal to the flow out of the + node. +\end{description} + +\fixme{Vertex vs.\ node.} +\fixme{Describe saturated in the $G_f$ section. And $N$.} + +For all vertices $u \in V$ we define the excess +\begin{equation} + e(u) = \sum_{v \in V} f(v, u) - \sum_{v \in V} f(u, v), +\end{equation} +which represents the amount of flow which \emph{disappears} in node $u$. +Equivalent to the preflow conservation constraint is stating that $e(u) +\geq 0$ for all vertices $u \in V - \{s,t\}$. + +The idea of the algorithm is to maintain a height map of the +vertices of the network where connected nodes can not have a large +height difference. Then we ``lift'' the source vertex to let as +many units as possible flow through the edges of the network towards the +sink. When a maximum preflow is reached, there will normally be excess +flow in some of the vertices, which has to be pushed back towards the +source in order to obtain a valid flow. + +The height map $d : V \to \mathbb{N}$ is also often called a distance +labeling and it satisfies $d(t) = 0$, and for every edge $(u, v)$ in the +residual network, i.e.\ every edge with $c_f(u, v) > 0$, we require that +$d(u) \leq d(v) + 1$. For every vertex $u$ for which there is a path +through the residual network to the sink, $d(u)$ will be a lower bound +on the length of such a path. + +A vertex $u$ is \emph{active} if $u \in V - \{s,t\}$, it has positive +excess ($e(u) > 0$) and $d(u) < N$. These are the nodes we want to +operate on to increase the preflow. + +\subsection{Basic operations} + +The algorithm performs two basic operations, the \emph{push} and +\emph{relabel} operations, while always maintaining a valid preflow $f$ +and a valid distance labeling $d$. + +\subsubsection{The push procedure} + +The push procedure moves excess flow from an active vertex along an edge +$(u, v) \in E_f$ such that $d(u) = d(v) + 1$, i.e.\ to a vertex with a +smaller distance label. We call such edges \emph{admissible}. See +Algorithm \ref{alg:push} for a pseudocode implementation of the push +operation. + +Assuming that $f$ is a valid preflow, it is easy to verify that $f$ +remains a valid preflow after running the push procedure on some +admissible edge $(u, v)$. The capacity constraint is fulfilled since we +at most increase the flow along $(u, v)$ with the residual capacity +$c_f(u,v)$. The preflow constraint is fulfilled since the excess $e$ +increases for $v$, remains non-negative for $u$ and remains the same for +all other vertices. + +The distance labels are not changed during the push procedure, however, +the residual network can change. The edge $(u, v)$ might disappear, and +an edge $(v, u)$ will surely appear if it does not already exist. Assume +that $d$ is a valid labeling. When starting the push procedure we have +$d(u) = d(v) + 1$, so we also have the following +\begin{align} + d(u) &\leq d(v) + 1 \\ + d(v) &\leq d(u) + 1, +\end{align} +and $d$ remains a valid labeling, even if the edge $(v, u)$ appears. + +\fixme{Change height $h$ to distance $d$.} + +\fixme{Operation < procedure.} + +\begin{algorithm} +\begin{algorithmic} + \Function{Push}{$u$, $v$} + \State $f_\text{aug} \gets \min(c_f(u, v), e(u))$ + \State $f(u, v) \mathrel{+}= f_\text{aug}$ + \State $e(u) \mathrel{-}= f_\text{aug}$ + \State $e(v) \mathrel{+}= f_\text{aug}$ + \EndFunction +\end{algorithmic} +\caption{\sf The push procedure of the Push-Relabel algorithm} +\label{alg:push} +\end{algorithm} + +\subsubsection{The relabel procedure} +The relabel procedure is our tool for changing the distance labels of +our vertices. It changes the label of a vertex to the greatest possible +value, which is one more than the lowest label among its neighbors in +the residual graph. See Algorithm \ref{alg:relabel} for a rather +mathematical pseudocode implementation. +\begin{algorithm} +\begin{algorithmic} + \Function{Relabel}{$u$} +% \If{$u$ is only node at its height} +% \Call{Gap}{$u$} +% \Else + \If{there is a $v \in V$ such that $(u, v) \in E_f$} + \State $d(u) \gets \min\{d(v), \; \forall v \in V : (u,v) \in E_f\} + 1$ + \Else + \State $d(u) \gets N$ + \EndIf +% \EndIf + \EndFunction +\end{algorithmic} +\caption{\sf The relabel procedure of the Push-Relabel algorithm} +\label{alg:relabel} +\end{algorithm} + +If $d$ was a valid labeling before running the relabel procedure, then +we still have $d(u) \leq d(v) + 1$ for all neighbors $v$ of $u$ in the +residual graph, and $d$ remains a valid labeling. The capacity +constraint and preflow constraint remain satisfied assuming they were +satisfied before the procedure was started. + +\subsection{Putting it all together} + +\fixme{Should be clearer what is really happening, and especially when + we are finished/what our goal is. That we are finished as soon as + there are no more active vertices. And that how we get there does + not matter as long as we follow our constraints. +} + +In the first phase of the algorithm we initialize a valid preflow and +distance labeling by saturating all edges out of the source $s$, and +then setting its distance label $d(s) = N$. We then run the push and +relabel procedures when applicable until there are no more active nodes +and a maximum preflow is obtained. + +\fixme{What is saturated?} + +A vertex $u$ can only be successfully relabeled to obtain a new label if +the outgoing edges of $u$ in the residual network have changed since the +previous relabeling. This is why the push and relabel procedures often +are combined into a \emph{discharge} procedure as shown in Algorithm +\ref{alg:discharge}. When it is run on an active vertex $u$, we push as +much as possible of the excess flow to other vertices before the vertex +is relabeled. +\begin{algorithm} +\begin{algorithmic} + \Function{Discharge}{$u$} + \ForAll{$v \in V$ such that $(u, v) \in E_f$} + \If{$c_f(u, v) > 0$ and $d(u) = d(v) + 1$} + \Call{Push}{$u$, $v$} + \EndIf + \EndFor + + \If{$e(u) > 0$} + \Call{Relabel}{$u$} + \EndIf + \EndFunction +\end{algorithmic} +\caption{\sf The discharge procedure of the Push-Relabel algorithm} +\label{alg:discharge} +\end{algorithm} + +In the second phase of the algorithm this preflow is turned into a +maximum flow by sending excess flow which did not reach the sink, from +inside the network back to the source. We can skip this part of the +algorithm, as it is possible to identify a minimum cut as soon as the +first phase is finished, and the following theorem allows us to do that. +\begin{theorem}[Cut identification] + Given a network $G = (V, E, c)$, assume that the first phase of + the push-relabel algorithm has terminated and no more active nodes + remain. Then there exists a $k \in \mathbb{N} \cap \left(0, N + \right)$ such that there is no vertex with label $k$, and the vertex + sets $S = \{ u \in V : d(u) > k\}$ and $T = V - S$ define a minimum + cut $C = (S, T)$ in $G$. + \label{thm:cut_identification} +\end{theorem} +\begin{proof} + There are $N$ nodes, the source has label $N$ and the sink has label + $0$, and the $N - 2$ remaining vertices can not occupy all the $N-1$ + labels in $\{1, \ldots, N-1\}$, so there must exist an $k$ as + described. + + As no vertex has label $k$, we can write $T = \{ u \in V : d(u) > + k\}$. + + Assume there was an edge $(u, v) \in E_f$ such that $u \in S$ and $v + \in T$. From the construction of $S$ and $T$, we would have $d(v) + \leq d(u) + 2$, which contradicts the labeling constraint, so no + such non-saturated edge from $S$ to $T$ can exist. + + From the construction of $E_f$ we now know that all edges in $E$ + from $S$ to $T$ are saturated, and all edges from $T$ to $S$ have no + flow. This means that the capacity of the cut is equal to the flow + through the cut, i.e.\ $c(S, T) = f(S, T)$. + + Since the first phase of the algorithm has terminated, there can be + no active vertices, and therefore no excess in $T$, except for the + sink. If all flow excess in vertices in $S$ is returned to the + source, we can apply the max-flow min-cut theorem to conclude that + $C = (S, T)$ is a minimum $s$-$t$-cut, since the cut capacity is + equal to the flow from $s$ to $t$. +\end{proof} + +We will see later that with the gap relabeling heuristic, there will +always be a gap at label $k = N - 1$ such that we can construct our cut +by taking $S = \{ u \in V : d(u) \geq N \}$. + +\fixme{Sketch of proof, could be nicer, shorter (split up?) and more +rigorous maybe.} + +\subsection{Complexity} +Bleep bloop. +\fixme{Edge list problematikk.} +\fixme{We have proved that when the first phase has terminated, we can + find the minimum cut, but should we maybe prove that the first phase + will terminate? Using the fact that the distance labels can only + increase? And the fact that we only push to lower vertices? + Computing the complexity is kind of like proving termination since + we find an upper bound on the number of operations. +} + +\subsection{Vertex selection rules} +\fixme{Also mention this over complexity.} +Until now we have just stated that the discharge procedure is run on +active nodes until there are no more active nodes left. The choice of +the order in which to discharge these active nodes remain, and multiple +possibilities exist. + +The FIFO approach is to always maintain a queue of active vertices. When +the vertex from the beginning of the queue is discharged, other vertices +might become active, and these are added at the end of the queue. +\fixme{Running time and reference.} + +The highest level selection rule always discharges the vertex with the +largest distance label. +\fixme{Running time and reference.} + +\subsection{Heuristics} +Different heuristics exists that can speed up the algorithm +considerably. Being heuristics, they are not guaranteed to work, and +might perform differently on different kinds of networks. The most used +heuristics are the gap and global relabeling heuristics, both aiming to +reduce the total number of relabeling steps. + +The gap relabeling heuristic aims to find a label $k$ as in Theorem +\ref{thm:cut_identification} such that no vertex has that label. +From vertices $u$ with $d(u) > k$, there are no unsaturated edges going +to vertices with smaller distance labels so no more flow can ever find +its way from these vertices to the sink. These vertices are therefore +given the label $N$ and never considered again as they will never become +active. Algorithm \ref{alg:gap} shows a pseudocode representation of +what is done once a gap $k$ is found. + +\begin{algorithm} +\begin{algorithmic} + \Function{Gap}{$k$} + \ForAll{$u \in V$ such that $d(u) > k$} + \State $d(u) \gets N$ + \EndFor + \EndFunction +\end{algorithmic} +\caption{\sf The gap procedure of the Push-Relabel algorithm} +\label{alg:gap} +\end{algorithm} + +\fixme{This could be a lemma with a proof maybe? Refer to Derigs and +Meyer.} + +But why does this work? The only thing we need to verify is that given a +network with a valid preflow and a valid labeling, the gap relabeling +procedure will not change the validity of these two things. + +\begin{lemma}[Gap relabeling validity] + Given a network $G = (V, E, c)$, a distance labeling $d$ and a + preflow $f$, assume there exists a gap $k$ such that no vertex has + label $k$. Running the gap relabeling procedure on label $k$ will + yield a valid distance labeling and an unchanged and valid preflow + $f$. +\end{lemma} +\begin{proof} + No new edges are created, no edges disappear, the preflow is + unchanged, so the preflow and capacity constraint remain satisfied + after the gap relabeling. + + Define the vertex sets $S = \{ u \in V : d(u) > k\}$ and $T = V - + S$. Initially, we have $d(u) \leq d(v) + 1$ for every edge $(u,v) + \in E_f$. These inequalities have to hold after the gap procedure is + finished, when all vertices $u \in S$ have label $d(u) = N$. + + For $(u, v) \in E_f$ we have four possibilities + \begin{description} + \item[$u, v \in T$] + The labels $d(u)$ and $d(v)$ remain unchanged and the + inequality still holds. + \item[$u, v \in S$] + After the gap procedure we have $d(u) = d(v)$ so the + inequality still holds. + \item[$u \in S, v \in T$] + This is not possible as it would imply $d(u) \geq d(v) + 2$ + and we have assumed an initial valid labeling. + \item[$u \in T, v \in S$] + After relabeling we have $d(u) < k < N < d(v) + 1$. + \end{description} + + Hence, both the preflow $f$ and distance labeling $d$ are valid. + + \fixme{A bit long, could be more compact since it is not really a + very interesting proof? (And it's not really a lemma either?)} +\end{proof} + +When running the push-relabel algorithm with the gap heuristic, we can +be sure that there will never be a node $u$ with label $d(u) = N-1$ at +the end of the algorithm, i.e.\ we know that there will always be a gap +at label $N-1$. Using the same reasoning as in Theorem +\ref{thm:cut_identification}, if there was a vertex with label $N-1$, +there would only be $N-3$ possibly having labels in $[1, N-2]$, so a gap +must exist somewhere in that interval. When using the gap relabeling +heuristic, such a gap can not exist, so we can conclude that there is no +vertex with label $N-1$. + +Using Theorem \ref{thm:cut_identification} we can then conclude that the +sets $S = \{ u \in V : d(u) \geq N\}$ and $T = V - S$ form a minimum cut +of the network. + +\fixme{Ugh, what a mess. Lemma maybe?} + +\subsection{Parametric push-relabel algorithm} +Now we have an algorithm for finding a minimum $s$-$t$-cut in a network, +so let's return to the network constructed in Section +\ref{sec:network_construction}. For every level $\lambda \in \{0, +\ldots, L\}$ we want to find a minimum $s$-$t$-cut which gives us the +thresholded image $u^\lambda$. These can then hopefully be stacked +together to form the final image $u$. + +\subsubsection{Network reuse} +Solving $L$ separate minimum cut problems seems like a lot of work, but +when using the push-relabel algorithm we will, if we do things in the +right order, be able to reuse the network when going from one label to +the next. + +\begin{figure} + \input{fig/norm_evolution} +\end{figure} + +Going back to the network representations in Figure +\ref{fig:norm_subgraph} and Figure \ref{fig:neigh_subgraph} we know that +only the capacity of edges from sub-networks representing the fidelity +term depend on our level parameter $\lambda$. From the expression in +\eqref{eq:fidelity_energy0}, visualized in Figure +\ref{fig:norm_evolution}, we see that the energy term $E^x(0)$ increases +monotonically with increasing $\lambda$ parameter. Let $u, v \in V - +\{s, t\}$. Since the edges in Figure \ref{fig:norm_subgraph} now are the +only ones depending on $\lambda$, the following is true for +\emph{decreasing} values of $\lambda$ +\begin{description} + \item[Edges from $s$ to $u$] + As seen in Figure \ref{fig:norm_subgraph_neg} the capacity of + these edges will increase monotonically with decreasing + $\lambda$ parameter. + \item[Edges from $u$ to $v$] + These edges have no $\lambda$-dependence and will remain + unchanged. + \item[Edges from $v$ to $t$] + As seen in Figure \ref{fig:norm_subgraph_pos} the capacity of + these edges will decrease monotonically with decreasing + $\lambda$ parameter. +\end{description} + +After running the push-relabel algorithm for $\lambda = k$, we are left +with a network $G = (V, E, c)$, a preflow $f$ and a labeling $d$. To +obtain the network for $\lambda = k-1$ we have to change the capacity of +two different kinds of edges, and this is done in the following way to +keep the capacity and preflow constraints satisfied. +\begin{description} + \item[Edges from $s$ to $u$] + The capacity $c(s, u)$ is increased, and the flow is set to be + equal to the capacity $f(s, u) = c(s, u)$. The vertex $u$ might + have an increased excess $e(u)$, which might in turn make it + active. + \item[Edges from $v$ to $t$] + The capacity $c(v, t)$ is decreased. If it is decreased to a + value below the current flow value, we set $f(v, t) = c(v, t)$ + which will decrease the excess of the sink $t$, and increase the + excess of $v$. +\end{description} + +None of these actions will create new edges in the residual network, and +we do not change the labeling $d$, so the labeling constraints are also +satisfied in the new network. + +Through this procedure we have easily created the network for $\lambda = +k-1$, and the distance labels remain the same. As these labels always +increase monotonically, we have a head start compared to if we had reset +the flow and labels. + +\subsubsection{Output image construction} + +We mentioned already in section \ref{sec:total_energy} that in order to +be able to construct our output image $u$, the thresholded images +$u^\lambda$ would have to stack one on top of the other as shown in +Figure \ref{fig:img_decomp}. We will now show that through reuse of the +distance labels from the last iteration of the push-relabel algorithm, +we can guarantee that it is possible to stack the thresholded images. + +\fixme{More precise statement than ``stack on top of each other''} + +Consider two subsequent runs of the push-relabel algorithm, for labels +$\lambda = k$ and $\lambda = k-1$ ending with distance labels $d^k$ and +$d^{k-1}$ respectively. We already know that the distance labels $d$ are +monotonically increasing. This means that the set $\{ u \in V : d(u) +\geq N \}$ is increasing in size, more precisely, we have the inclusion +\begin{equation} + \{ u \in V : d^k(u) \geq N \} \subseteq \{ u \in V : d^{k-1}(u) \geq + N \} +\end{equation} + +We then construct our output image $u$ by giving each pixel the value +\begin{equation} + u_x = \min \{ \lambda \in \{0, \ldots, L-1\} : u^\lambda_x = 1 \}. +\end{equation} +This marks the end of the description of the implemented algorithm, but +we will further discuss some possible improvements, and also look at +results when using the method on different kinds of pictures, with +different kinds of noise. + +\subsection{Divide and conquer} +The possibility of re-using the network between separate level +is a very nice property of the push-relabel algorithm, but there are +further room for improvements. Consider one pixel $x$ with value $u_x$, +and imagine we only wanted to find the value of this pixel. One could go +through all pixel values $\lambda \in (L-1, \ldots, 0)$, and see when +$u^\lambda_x$ changes from $1$ to $0$, just as we do for all the pixels +in the algorithm above. Ignoring network re-use this would have us solve +$O(L)$ maximum flow problems. + +Improving on this we could employ the idea of binary search to find the +value of $u_x$ in only $O(\log_2 L)$ time. After finding one cut, we +know whether $u_x$ is above or below the current $\lambda$ value, and by +choosing $\lambda$ as the midpoint of the current possible range of +$u_x$, we can cut the search space in half for each iteration of the +algorithm. + +We can extend this idea to the problem of finding all pixel values. +Instead of running the algorithm for successively decreasing values of +$\lambda$, we choose some $\lambda$ in the middle of the range $\{0, +\ldots, L-1\}$. The cut we obtain consists of two sets $S = \{ u \in V : +d(u) \geq N\}$ and $T = V - S$. We know that no more flow can be sent +from $S$ to $T$, even if we decrease the value of $\lambda$ and adjust +the capacities accordingly. + +The idea is now that we have halved the possible $\lambda$ interval for +\emph{all} pixels. We continue by considering the two sets $S$ and $T$ +separately, and applying the algorithm recursively, at each time halving +the $\lambda$ interval until we have the value of every pixel. + +\subsection{Implementation} +\cite{opencv_library} + +\subsection{Bleep bloop} + +Maybe we should delete the $u$-$t$ edge when the vertex reaches a level +> 1? + +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. + +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 could +include some results with and without the heuristics. + +\cite{ahuja1997computational} has some good performance analysis. + +\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. + diff --git a/results.tex b/results.tex index 89275da..9a8b5a1 100644 --- a/results.tex +++ b/results.tex @@ -1,28 +1,4 @@ \section{Image restoration results} -Although the theory behind the graph cut image restoration algorithm has -been the main focus of this project, we will look at some results when -applying the algorithm to different noisy input images. - -The two main parameters available to the user of the algorithm are the -$\beta$ parameter and the neighborhood specification. With $\beta$ being -the weight of the total variation in the energy function, larger values -will give more smoothing in the output image. By changing the pixel -neighborhoods we can change the reach of the smoothing, and maybe try to -reduce some visual effects introduced by the discretization. - -Measuring the performance of the method is hard, especially as different -applications have different measures for what is a ``good'' output -image. We will in this section consider an original image with -artificially added noise, and try to remove the noise to obtain an -output image as close to the original as possible. - -The most obvious approach is to just look at the two images and see how -much alike they are, something that makes sense especially if the output -is made for the eye to see. One can also consider the \emph{method -noise} which is the difference between the noisy image and the de-noised -version. If noise is independent of the original image, one would also -hope that the method noise would not contain too many features from the -original image, since it is only the noise we want to remove. \begin{figure} \centering @@ -47,10 +23,40 @@ original image, since it is only the noise we want to remove. The classical Lena Söderberg portrait, with two different types of additive noise. } - \label{fig:lena_and_gaussian} + \label{fig:noisy_lena} \end{figure} -Figure \ref{fig:lena_and_gaussian} shows the Lena Söderberg portrait +Although the theory behind the graph cut image restoration algorithm has +been the main focus of this project, we will look at some results when +applying the algorithm to different noisy input images. + +The two main parameters available to the user of the algorithm are the +$\beta$ parameter and the neighborhood specification. With $\beta$ being +the weight of the total variation in the energy function, larger values +will give more smoothing in the output image. By changing the pixel +neighborhoods we can change the reach of the smoothing, and maybe try to +reduce some visual effects introduced by the discretization. + +Measuring the performance of the method is hard, especially as different +applications have different measures for what is a ``good'' output +image. We will in this section consider an original image with +artificially added noise, and try to remove the noise to obtain an +output image as close to the original as possible. + +The most obvious approach is to just look at the two images and see how +much alike they are, something that makes sense especially if the output +is made for the eye to see. One can also consider the \emph{method +noise} which is the difference between the noisy image and the de-noised +version. If noise is independent of the original image, one would also +hope that the method noise would not contain too many features from the +original image, since it is only the noise we want to remove. + +Since our digitized representation of the images we are restricted to +pixel values in $\{0, \ldots, 255\}$, we show the method noise as an +image with pixel values $127 + \alpha (v - u)$. The scaling $\alpha$ can +be tuned depending on the magnitude of difference $v - u$. + +Figure \ref{fig:noisy_lena} shows the Lena Söderberg portrait which has been used as a test image in digital imaging countless times. Gaussian and Laplace noise has been added. Since the pixel values in these gray scale images are limited to the range $\{0, \ldots, 255\}$, @@ -93,61 +99,78 @@ exit the interval. \includegraphics[width=\textwidth]{../image-restoration/figures/normal/method_50.png} \end{subfigure} \caption{ - \fixme{GAUSSIAN} - The first row shows restored images for different $\beta$ - parameter using a size four neighborhood. In the second row the - method noise is shown around a gray value of $127$ without any - scaling. + The first row shows the image with additional Gaussian noise + restored for different values of $\beta$, using a size four + neighborhood and $p = 2$ as the exponent in the fidelity term. + In the second row the method noise is shown around a gray value + of $127$ without any scaling. } + \label{fig:gaussian_restored} \end{figure} \begin{figure} \centering \begin{subfigure}[t]{0.30\textwidth} \centering - \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/restored_10.png} - \caption{$\beta = 10$} + \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/restored_0.3.png} + \caption{$\beta = 0.3$} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} \centering - \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/restored_30.png} - \caption{$\beta = 30$} + \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/restored_0.7.png} + \caption{$\beta = 0.7$} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} \centering - \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/restored_50.png} - \caption{$\beta = 50$} + \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/restored_1.png} + \caption{$\beta = 1$} + \label{fig:laplace_restored_1} \end{subfigure} \centering \begin{subfigure}[t]{0.30\textwidth} \centering - \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/method_10.png} + \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/method_0.3.png} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} \centering - \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/method_30.png} + \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/method_0.7.png} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} \centering - \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/method_50.png} + \includegraphics[width=\textwidth]{../image-restoration/figures/laplace/method_1.png} \end{subfigure} \caption{ - \fixme{LAPLACE, should run with different norm.} + The first row shows the image with additional Laplace noise + restored for different values of $\beta$, using a size four + neighborhood and $p = 1$ as the exponent in the fidelity term. + In the second row the method noise is shown around a gray value + of $127$ without any scaling. } + \label{fig:laplace_restored} \end{figure} -\subsection{Image segmentation} -Some figures maybe. Showing the segmentation for different parameters. +Figure \ref{fig:gaussian_restored} and \ref{fig:laplace_restored} shows +the noisy images from figure \ref{fig:noisy_lena} restored for different +parameters of $\beta$ and the exponent $p$ in the fidelity term. First +we note that the method works quite well on smooth surfaces, like Lena's +shoulder and the background of the image, while her hair, and the +\fixme{what} hanging from her hat has lost details, especially for +higher values of $\beta$. -\subsection{Image restoration} -Different kinds of noise, different parameters. Compare it with other -methods maybe. +We see in the method noise, especially in figure +\ref{fig:laplace_restored_1}, that the \fixme{what} has lost details. +Being especially bright, the method noise here tells us that the +algorithm has corrected this area more than the rest, all the while the +noise was spread evenly over the whole image. -\subsubsection{Impulse noise} -\subsubsection{Gaussian noise} +As mentioned earlier, one of the theoretically nice properties of the +total variation method is that it preserves edges. Looking at the +restored images, we see that the edges in the original image are sharp +even for high values of $\beta$, taking Lena's shoulder as an example +again. diff --git a/total.tex b/total.tex index e7891ba..dcf38c2 100644 --- a/total.tex +++ b/total.tex @@ -15,10 +15,11 @@ regularize the image. How we can integrate the gradient of an image which can contain discontinuities will be clarified later, but first we will look at how -this model can be grounded in spatial statistics; \fixme{an important -field in image analysis.} +this model can be grounded in spatial statistics; a field which forms +an important part of image analysis. \subsection{Probabilistic background} +\label{sec:prob} \fixme{The actual expression for the total variation has not been introduced yet!} @@ -193,7 +194,7 @@ The set perimeter behaves mostly as one might expect, just note that if the boundary of $E$ overlaps with the boundary of $\Omega$, then $P(E,\Omega)$ will not include the overlapping part of the boundary. -\fixme{WOW, this is bad! The level sets are not sets! But the perimeter +\fixme{Bad! The level sets are not sets! But the perimeter function want sets!} For an image $u$ we introduce the level sets of $u$ as @@ -354,10 +355,11 @@ level values \abs{u_x^\lambda - u_y^\lambda}. \label{eq:tv_discrete_int} \end{equation} -The sum over $(x,y)$ signifies a sum over all pixels $x$ and $y$ that -are in a neighborhood relation, and $w_{xy}$ is a weight parameter. The -sum over $\lambda$ ends at $L-2$ since $u^{L-1}$ is equal to 1 in every -pixel of the image. +The sum over $(x,y)$ signifies a sum over all pixels cliques of size +two, i.e.\ all pairs $(x, y)$ such that $x$ and $y$ are in a +neighborhood relation. The $w_{xy}$ is a weight parameter. The sum over +$\lambda$ ends at $L-2$ since $u^{L-1}$ is equal to 1 in every pixel of +the image. Intuitively, the perimeter of the level set $u^\lambda$ is proportional to the number of pixels at the boundary of the set. This is again @@ -442,7 +444,7 @@ are left with \begin{equation} E_v(u) = \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, + + \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} @@ -463,10 +465,6 @@ where \right). \label{eq:neigh_energy} \end{align} -\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.} If we minimize each level separately it is obvious that we also minimize the total energy. In other words if we for every $\lambda$ find a level @@ -485,6 +483,5 @@ 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?} +\fixme{Consistently call them the fidelity and regularization terms.} -- 2.47.3