From 005d951e9909b35163c1f9247bdaf034b4ccbb63 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Wed, 7 May 2014 12:32:31 +0200 Subject: [PATCH] Some more on the parametric push-relabel --- flow.tex | 142 +++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 122 insertions(+), 20 deletions(-) diff --git a/flow.tex b/flow.tex index 5c8ab20..ea2c1d1 100644 --- a/flow.tex +++ b/flow.tex @@ -367,32 +367,29 @@ maximum flow by sending excess flow from inside the network back to the source. We can skip this part of the algorithm, as we are only interested in finding a minimum cut, and not the maximum flow. -The following theorem allows us to find a minimum cut after the firt +The following theorem allows us to find a minimum cut after the first phase of the algorithm is finished. \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 an $x \in \mathbb{N} \cap \left(0, - N \right)$ such that there is no vertex with label $x$, and the - vertex sets $S = \{ u : d(u) > x\}$ and $T = V - S$ define a minimum + remain. Then there exists an $k \in \mathbb{N} \cap \left(0, + N \right)$ such that there is no vertex with label $k$, and the + vertex sets $S = \{ u : d(u) > k\}$ and $T = V - S$ define a minimum cut $C = (S, T)$ in $G$. + \label{thm:cut_identification} \end{theorem} \begin{proof} - \fixme{Sketch of proof, could be nicer, shorter (split up?) and more - rigorous maybe.} - There are $N$ nodes, the source has label $N$ and the sink has label $0$, so the $N - 2$ remaining vertices can not occupy all the $N-1$ - other labels, and there must exist an $x$ as described. + other labels, and there must exist an $k$ as described. - As no vertex has label $x$, the set $T$ contains all (and only) - vertices with labels less than $x$. + As no vertex has label $k$, the set $T$ contains all (and only) + vertices with labels less than $k$. Assume there was an edge non-saturated edge $(u, v) \in E_f$ such that $u \in S$ and $v \in T$. From the construction of $S$ and $T$, - we have $d(v) \leq d(u) + 2$, which contradicts the valid labeling - constraint stating that $d(u) \leq d(v) + 1$ for every residual - edge. Therefore, no such non-saturated edge from $S$ to $T$ can + we 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 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 @@ -400,27 +397,56 @@ phase of the algorithm is finished. 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 + 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} +\fixme{Sketch of proof, could be nicer, shorter (split up?) and more +rigorous maybe.} + \subsubsection{Complexity} Bleep bloop. +\fixme{Edge list problematikk.} + +\subsubsection{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.} + \subsubsection{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 graphs. The most used -heuristics are the gap- and global relabeling heuristics, both +heuristics are the gap- and global relabeling heuristics, both aiming to +reduce the total number of relabelings needed. + +The gap relabeling heuristic aims to find a label $k$ as in Theorem +\ref{thm:cut_identification} such that no vertex has that label. +Realizing that no more flow can ever be sent from the nodes $u$ such +that $d(u) > k$ we can relabel them with label $N$ and never consider +them 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}{$u$} - \State $k \gets h(u)$ - \ForAll{$v$ with height $\geq k$} - \State $h(v) \gets N$ + \Function{Gap}{$k$} + \ForAll{$u$ such that $d(u) \geq k$} + \State $d(u) \gets N$ \EndFor \EndFunction \end{algorithmic} @@ -428,9 +454,85 @@ heuristics are the gap- and global relabeling heuristics, both \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$. Then 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 flow is conserved + and only the labels are changed, so the preflow and capacity + constraint remain fulfilled 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. +\end{proof} + +\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 \fixme{ref}. For +every level $\lambda \in ??$ 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$. + +Solving \fixme{??} 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. + +Going back to Equation \fixme{??} and the sub-network representations in +Figure \fixme{??} and Figure \fixme{??} we know that only edges from +sub-networks representing the fidelity term depend on our level +parameter $\lambda$. From Figure \fixme{move closer??} 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 +\fixme{??} 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 \fixme{ref} 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 \fixme{ref} the capacity of these edges will + decrease monotonically with decreasing $\lambda$ parameter. +\end{description} + +\subsubsection{Bleep bloop} + 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 +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). -- 2.47.3