From ec5115bc26dbb4e85a173f445de9e9497a2e0988 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Tue, 20 Jan 2015 19:35:03 +0100 Subject: [PATCH] BOOP --- fig/norm_evolution.tex | 6 +- fig/norm_subgraph.tex | 10 +- introduction.tex | 18 ++-- results.tex | 206 +++++++++++++++++++++++------------------ theory.tex | 97 ++++++++++--------- 5 files changed, 182 insertions(+), 155 deletions(-) diff --git a/fig/norm_evolution.tex b/fig/norm_evolution.tex index ca85d77..8373460 100644 --- a/fig/norm_evolution.tex +++ b/fig/norm_evolution.tex @@ -3,7 +3,7 @@ \centering \begin{tikzpicture} \draw[->] (0,0) -- (4,0) node[right] {$\lambda$}; - \draw[->] (0,-2) -- (0,2) node[above] {$E_\lambda^x(0)$}; + \draw[->] (0,-2) -- (0,2) node[above] {$E_\lambda^x(1)$}; \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}); @@ -29,7 +29,7 @@ \centering \begin{tikzpicture} \draw[->] (0,0) -- (4,0) node[right] {$\lambda$}; - \draw[->] (0,-2) -- (0,2) node[above] {$E_\lambda^x(0)$}; + \draw[->] (0,-2) -- (0,2) node[above] {$E_\lambda^x(1)$}; \draw[line,domain=0:4] plot ({\x},{.8*\x - 1.6}); \draw (2.5,2pt) -- (2.5,-2pt) node[ @@ -48,7 +48,7 @@ \caption{$L^2$ fidelity term.} \label{fig:l2_norm_evolution} \end{subfigure} -\caption{Two figures showing how the fidelity energy term $E_\lambda^x(0)$ +\caption{Two figures showing how the fidelity energy term $E_\lambda^x(1)$ 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 index 24b5083..7162104 100644 --- a/fig/norm_subgraph.tex +++ b/fig/norm_subgraph.tex @@ -6,10 +6,10 @@ \node[vertex] (u) at (0, -1) {$u^\lambda_x$}; \node[vertex] (t) at (0, -2) {t}; - \path[edge] (u) -- node[weight noslope] {$E_\lambda^x(0)$} (t); + \path[edge] (s) -- node[weight noslope] {$E_\lambda^x(1)$} (u); \end{tikzpicture} \caption{% - The graph when $E_\lambda^x(0) > 0$, with constant equal to 0. + The graph when $E_\lambda^x(1) > 0$, with constant equal to 0. } \label{fig:norm_subgraph_pos} \end{subfigure} @@ -21,10 +21,10 @@ \node[vertex] (u) at (0, -1) {$u^\lambda_x$}; \node[vertex] (t) at (0, -2) {t}; - \path[edge] (s) -- node[weight noslope] {$-E_\lambda^x(0)$} (u); + \path[edge] (u) -- node[weight noslope] {$-E_\lambda^x(1)$} (t); \end{tikzpicture} - \caption{Graph when $E_\lambda^x(0) < 0$, with constant equal to - $-E_\lambda^x(0)$. + \caption{Graph when $E_\lambda^x(1) < 0$, with constant equal to + $-E_\lambda^x(1)$. } \label{fig:norm_subgraph_neg} \end{subfigure} diff --git a/introduction.tex b/introduction.tex index ba6abd5..9e51f9d 100644 --- a/introduction.tex +++ b/introduction.tex @@ -27,7 +27,7 @@ nature of how light travels from the scene to the objective, while some might result from inaccuracies in the construction of the capturing apparatus. These noise-inducing processes can be studied, and modeled mathematically, and the process of image restoration looks at how one -can remove some -- or optimally all -- of the noise in the captured +can remove some---or optimally all---of the noise in the captured image. These methods often take into account how we would expect a ``normal'' image to look in the capturing conditions, and also what kinds of noise we expect to be a part of the image. @@ -419,18 +419,14 @@ regularized image. \label{fig:tv_example} \end{figure} -\subsection{Chambolle's dual approach} +\subsection{Numerical methods} -\fixme{Maybe give a list of references, instead of seemingly favoring -Chambolle's method.} +See \cite{chan2011numerical} for an overview of some of the numerical +methods relating to total variation image restoration. Amongst others it +describes some dual and primal-dual methods, as well as the graph cut +approach we take in this thesis. -A popular approach for solving the minimization problem, is the dual -algorithm of Chambolle described in \cite{chambolle2004algorithm}. It -has been improved on by others, and also extended to primal-dual -methods. An overview of the different methods and further references can -be found in \cite{caselles2011total}. - -\subsection{Graph cut approach} +\subsubsection{Graph cut approach} \fixme{Could probably be shortened a lot, but I thought it could be useful to at least give an idea how it is done.} diff --git a/results.tex b/results.tex index 71c08d5..545cdd7 100644 --- a/results.tex +++ b/results.tex @@ -4,7 +4,9 @@ In the previous chapters we have carefully constructed a method always trying to argue how the choices we make can have a positive impact on the image restoration results. The anisotropic total variation is the main advance from my project work \cite{project}, and we would like to -see what its effects are. +see how it affects the performance of the restoration algorithm. + +\section{Tensor parameters} \begin{figure} \centering @@ -45,7 +47,7 @@ tensor construction described earlier, we will look at how a simple predescribed tensor affects the regularization. Imagine a tensor which is a diagonal matrix $A = \operatorname{diag}(1, \epsilon)$, where $\epsilon \ll 1$ is small. This would result in us down-weighting the -size of $\nabla f_\sigma$ in the $y$-direction, and thus regularizing +size of $\nabla f_\sigma$ in the $y$-direction, and thus regularization mostly in the $x$-direction. The results of this experiment can be seen in @@ -122,20 +124,20 @@ the $y$-direction. It is useful to look at intermediate results to better understand what happens and how the parameters affect our end result. In -Figure~\ref{fig:lena_process} we show the stages of our image +Figure~\ref{fig:lena_process} we show the different stages of our image restoration algorithm. We start out with a section of the much-used Lena test image in Figure~\ref{fig:lena_process_orig}. The first step in the construction of the structure tensor is to blur the image with parameter $\sigma$, and the result is shown in Figure~\ref{fig:lena_process_blur}. The blurring is done so that the edge detector $\nabla f_\sigma$, which -is shown squared in Figure~\ref{fig:lena_process_edge}, is not too +is shown squared and normalized in Figure~\ref{fig:lena_process_edge}, is not too sensitive to noise in the image. The structure tensor is then constructed using $\nabla f_\sigma$, and further transformed into the anisotropy tensor, which is visualized in Figure~\ref{fig:lena_process_tensor}. In a selection of points, the tensor has been drawn as its two eigenvectors, with the corresponding -eigenvalues as their length, and we clearly see that the eigenvalues are -reduced across edges. Another way of visualizing the tensor, which makes +eigenvalue as its length, and we clearly see that the eigenvalues are +smaller across edges. Another way of visualizing the tensor, which makes it possible to see it in every point, is using the color wheel in Figure~\ref{fig:color_wheel}. The color is decided by the tensor angle, while the brightness, or the radius in the wheel, is set to $1 / @@ -155,12 +157,6 @@ black. Finally, Figure~\ref{fig:lena_process_restored} shows the restored image, and we see that it has been heavily regularized. -In the construction of the tensor in -Section~\ref{sec:anisotropy_tensor}, we have several parameters. The -\emph{noise scale} $\sigma$ controls the smoothing done before $\nabla -f_\sigma$ is calculated, and thus controls how sensitive the edge -detector is to noise in the input image $f$. All details of scale less -than $\sigma$ will be considered to be noise. \begin{figure} \centering \begin{subfigure}[t]{0.30\textwidth} @@ -200,7 +196,7 @@ than $\sigma$ will be considered to be noise. \centering \includegraphics[width=\textwidth]{fig/factory/lines/r_p2_n8_b5000_g100_r15_s0.2_color.png} \caption{% - Restored with low noise scale (0.2), but large integration + Restored with low noise scale $\sigma = 0.2$, but large integration scale $\rho = 15$. } \label{fig:scale_comp_int} @@ -211,22 +207,24 @@ than $\sigma$ will be considered to be noise. \label{fig:scale_comp} \end{figure} -Figure~\ref{fig:scale_comp} shows a constructed zebra pattern of -increasing width. The anisotropy introduced should in theory help reduce contrast +To look further into the effects of the parameters in our tensor +construction we have a constructed a zebra pattern of increasing width +as shown in Figure~\ref{fig:scale_comp}. +The anisotropy introduced should in theory help reduce contrast loss in this situation, by reducing the regularization done in the $x$-direction, but there is the question of how the different scales affect the regularization. In Figure~\ref{fig:scale_comp_high} the noise scale is increased such -that the edge detector, and thus the anisotropy tensor, considers these -fine lines to be noise rather than details. Thus this part is +that the edge detector, and thus the anisotropy tensor, considers the +finest lines to be noise rather than details. Thus this left-most part is regularized to a smooth gray area. -The \emph{integration scale} $\rho$ of \eqref{eq:s_def} represents the +The integration scale $\rho$ of \eqref{eq:s_def} controls the size of the structures we want to detect with our anisotropy tensor. In Figure~\ref{fig:scale_comp_int} a high value for $\rho$ means that the structure found in the inner square is almost completely ignored in -favour of the larger, more coherent structure around. +favour of the larger, more coherent structure around it. \begin{figure} \centering @@ -254,7 +252,8 @@ favour of the larger, more coherent structure around. } \end{subfigure} \caption{% - Not so funny caption. Include some parameters. + A noisy fingerprint with the anisotropy tensor visualized for + different integration scales $\rho$. } \label{fig:finger_tensor} \end{figure} @@ -263,12 +262,8 @@ Another visualization of the anisotropy tensor can be seen for a fingerprint image in Figure~\ref{fig:finger_tensor}. We see that the gradual changes in the direction of the edges are captured by the tensor. Even the singularities in the fingerprint can be identified by -finding the dark spots, as the changes in these areas do not tend to one -single direction. - -\fixme{We show how the different neighborhoods work. Here we might make some -nice, very contrived examples, maybe. To show that both too small and -too big is bad.} +finding the dark spots, as the gradient of the image in these areas do +not point in one single direction. \begin{figure} \centering @@ -278,6 +273,7 @@ too big is bad.} \caption{% Circle. } + \label{fig:n_circle} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} @@ -286,6 +282,7 @@ too big is bad.} \caption{% $\abs{\mathcal{N}} = 8$. } + \label{fig:n_circle_8} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} @@ -294,6 +291,7 @@ too big is bad.} \caption{% $\abs{\mathcal{N}} = 72$. } + \label{fig:n_circle_72} \end{subfigure} \begin{subfigure}[t]{0.30\textwidth} @@ -302,6 +300,7 @@ too big is bad.} \caption{% Octagon. } + \label{fig:n_octagon} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} @@ -310,6 +309,7 @@ too big is bad.} \caption{% $\abs{\mathcal{N}} = 8$. } + \label{fig:n_octagon_8} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} @@ -318,6 +318,7 @@ too big is bad.} \caption{% $\abs{\mathcal{N}} = 72$. } + \label{fig:n_octagon_72} \end{subfigure} \begin{subfigure}[t]{0.30\textwidth} @@ -326,6 +327,7 @@ too big is bad.} \caption{% Tilted square. } + \label{fig:n_square} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} @@ -334,6 +336,7 @@ too big is bad.} \caption{% $\abs{\mathcal{N}} = 4$. } + \label{fig:n_square_4} \end{subfigure} ~ \begin{subfigure}[t]{0.30\textwidth} @@ -342,13 +345,19 @@ too big is bad.} \caption{% $\abs{\mathcal{N}} = 72$. } + \label{fig:n_square_72} \end{subfigure} \caption{% - Not so funny caption. Include some parameters. + Different test images restored without anisotropy, different + neighborhoods and a large restoration parameter $\beta$. We see + how different neighborhood stencils introduce different + artifacts. } - \label{fig:circle_arti} + \label{fig:neigh_shapes} \end{figure} +\section{Neighborhood stencils} + The neighborhoods were introduced as a way to describe the discrete set of lines $\mathcal{L}_D$ in the discretization of the regularization term in Section~\ref{sec:disc_regularization}. And as discussed, we want @@ -356,12 +365,23 @@ the stencil to have many short edges, such that the angular differences $\Delta \phi$, the inter-line distances $\Delta \rho$ and the edge lengths $e$ are ``small.'' -Figure~\ref{fig:circle_arti} shows a circle that has been strongly -regularized using a 8-point stencil. The circle has clearly been -deformed to look more like an octagon. This is due to the fact that the -8-point stencil measures horizontal, vertical and 45\textdegree{} lines -exactly in the Cauhcy--Crofton formula, while the length of other lines -overestimated as the sum of their three components. +Figure~\ref{fig:neigh_shapes} shows three images of different shapes +that are heavily regularized using different neighborhood stencils. In +these results we see some of the artifacts that may occur because of +this discretization method. It is clear that the size-8 stencil prefers +horizontal, vertical and 45\textdegree{} lines, such that the circle in +Figure~\ref{fig:n_circle} is shaped like an octagon when regularized in +Figure~\ref{fig:n_circle_8}. The neighborhood of size 72 manages to +keep the circular shape however. + +Next, in Figure~\ref{fig:n_octagon}, we see that the size-8 stencil +actually favors octagon-like shapes, as the restored shape is the same +octagon, just with some contrast loss. + +The tilted square in Figure~\ref{fig:n_square}, hints that a size-4 +neighborhood favors horizontal and vertical edges only. While the larger +size-72 neighborhood retains the square shape but smoothes the corners +some. \begin{figure} \centering @@ -381,7 +401,8 @@ overestimated as the sum of their three components. } \end{subfigure} \caption{% - Noisy Lena restored using different neighborhood stencils. + Noisy Lena restored using different neighborhood stencils. Note + how the large neighborhood introduces some pixel size artifacts. } \label{fig:lena_neigh} \end{figure} @@ -421,7 +442,7 @@ has been restored using two differently sized neighborhood stencils, and there are obvious differences. For the stencil of size 72, the restored image still contains some salt- and pepper-like noise, seemingly very different from their neighboring pixels. An explanation can be found in -Figure~\ref{boop}, where we see that the length of a one-pixel curve is +Figure~\ref{fig:pixel_perimeter}, where we see that the length of a one-pixel curve is very underestimated because so many edges cross over it, and thus ignore it completely. @@ -453,7 +474,8 @@ it completely. \label{fig:finger_contrast_atv} \end{subfigure} \caption{% - Funny caption. Parameters. + The different stages in the restoration of a part of the Lena + test image. } \label{fig:finger_contrast} \end{figure} @@ -491,61 +513,61 @@ noise, we want to remove that kind of noise. An indication of problems can in that case be if the method noise contains a lot of the details of the image. -Figure~\ref{fig:lena_method_noise} shows the results after restoring the -noisy Lena picture in Figure \fixme{noisylena}, with different -parameters, and their method noise. We note that the method noise of the -regular total variation method shows and outline of Lena, which -indicates some detail loss. Further, we see that the method noise of the -anisotropically restored image, has less details. - -\begin{figure} - \centering - \begin{subfigure}[t]{0.30\textwidth} - \centering - \includegraphics[width=\textwidth]{fig/lena_tv.png} - \end{subfigure} - ~ - \begin{subfigure}[t]{0.30\textwidth} - \centering - \includegraphics[width=\textwidth]{fig/lena_atv.png} - \end{subfigure} - ~ - \begin{subfigure}[t]{0.30\textwidth} - \centering - \includegraphics[width=\textwidth]{fig/lena_atv72.png} - \end{subfigure} - - \centering - \begin{subfigure}[t]{0.30\textwidth} - \centering - \includegraphics[width=\textwidth]{fig/lena_method_tv.png} - \caption{% - Regular total variation. - } - \end{subfigure} - ~ - \begin{subfigure}[t]{0.30\textwidth} - \centering - \includegraphics[width=\textwidth]{fig/lena_method_atv.png} - \caption{% - Anisotropic total variation. - } - \end{subfigure} - ~ - \begin{subfigure}[t]{0.30\textwidth} - \centering - \includegraphics[width=\textwidth]{fig/lena_method_atv72.png} - \caption{% - Size 72 neighborhood. - } - \end{subfigure} - \caption{% - Funny caption. Parameters. - } - \label{fig:lena_method_noise} -\end{figure} - -\section{Conclusion} +%Figure~\ref{fig:lena_method_noise} shows the results after restoring the +%noisy Lena picture in Figure \fixme{noisylena}, with different +%parameters, and their method noise. We note that the method noise of the +%regular total variation method shows and outline of Lena, which +%indicates some detail loss. Further, we see that the method noise of the +%anisotropically restored image, has less details. + +%\begin{figure} +% \centering +% \begin{subfigure}[t]{0.30\textwidth} +% \centering +% \includegraphics[width=\textwidth]{fig/lena_tv.png} +% \end{subfigure} +% ~ +% \begin{subfigure}[t]{0.30\textwidth} +% \centering +% \includegraphics[width=\textwidth]{fig/lena_atv.png} +% \end{subfigure} +% ~ +% \begin{subfigure}[t]{0.30\textwidth} +% \centering +% \includegraphics[width=\textwidth]{fig/lena_atv72.png} +% \end{subfigure} +% +% \centering +% \begin{subfigure}[t]{0.30\textwidth} +% \centering +% \includegraphics[width=\textwidth]{fig/lena_method_tv.png} +% \caption{% +% Regular total variation. +% } +% \end{subfigure} +% ~ +% \begin{subfigure}[t]{0.30\textwidth} +% \centering +% \includegraphics[width=\textwidth]{fig/lena_method_atv.png} +% \caption{% +% Anisotropic total variation. +% } +% \end{subfigure} +% ~ +% \begin{subfigure}[t]{0.30\textwidth} +% \centering +% \includegraphics[width=\textwidth]{fig/lena_method_atv72.png} +% \caption{% +% Size 72 neighborhood. +% } +% \end{subfigure} +% \caption{% +% Funny caption. Parameters. +% } +% \label{fig:lena_method_noise} +%\end{figure} + +\chapter{Conclusion} Bleep bloop. Bad sides, good sides? diff --git a/theory.tex b/theory.tex index bf6fc68..177996b 100644 --- a/theory.tex +++ b/theory.tex @@ -1774,7 +1774,7 @@ depend on. \input{fig/norm_subgraph} \end{figure} -We will construct a graph in such a way that if a variable +We will construct a graph in such a way that if a vertex $u^\lambda_x$ ends up on the source side of the cut we set $u^\lambda_x = 0$, and if it ends up on the sink side we set $u^\lambda_x = 1$, as in Definition~\ref{def:graph_representable}. This is an arbitrary choice, @@ -1799,12 +1799,11 @@ term coming from our aim to minimize the total variation. \begin{tabular}{ccccc} \hline $u^\lambda_x$ & $E_\lambda^x(u^\lambda_x)$ & Min.\ cut $(S, T)$ - & graph \subref{fig:norm_subgraph_pos} cut cap. & Graph + & Graph \subref{fig:norm_subgraph_pos} cut cap. & Graph \subref{fig:norm_subgraph_neg} cut cap. \\ \hline - $0$ & $E_\lambda^x(0)$ & $(\{s, u^\lambda_x\}, \{t\})$ & - $E_\lambda^x(0)$ & $0$ \\ - $1$ & $0$ & $(\{s\}, \{u^\lambda_x, t\})$ & $0$ & $-E_\lambda^x(0)$ + $0$ & $0$ & $(\{s, u^\lambda_x\}, \{t\})$ & $0$ & $-E_\lambda^x(1)$ \\ + $1$ & $E_\lambda^x(1)$ & $(\{s\}, \{u^\lambda_x, t\})$ & $E_\lambda^x(1)$ & $0$ \end{tabular} \label{tab:fid_energy} \end{table} @@ -1818,19 +1817,19 @@ term coming from our aim to minimize the total variation. The fidelity term of our energy function in \eqref{eq:total_energy} simplifies to \begin{align} - E_\lambda^x(0) &= + E_\lambda^x(0) &= 0 + \label{eq:fidelity_energy0} \\ + E_\lambda^x(1) &= N_x(\lambda + 1) - N_x(\lambda) - \label{eq:fidelity_energy0} \\ - E_\lambda^x(1) &= 0 \label{eq:fidelity_energy1} \end{align} -where $E_\lambda^x(0)$ might be positive or negative depending on +where $E_\lambda^x(1)$ might be positive or negative depending on $\lambda$ and the pixel value $v_x$. Figure~\ref{fig:norm_subgraph} shows how graphs can be constructed to represent this part of the total energy. The construction differs -depending on whether $E_\lambda^x(0)$ is positive or negative. +depending on whether $E_\lambda^x(1)$ is positive or negative. Table~\ref{tab:fid_energy} shows how the cuts correspond to the values of $u^\lambda_x$ and we can easily verify that the constructed graph actually represents the fidelity term in the energy function. @@ -2102,6 +2101,7 @@ for a description of the breadth-first search, and a formal proof of the running time of the Edmonds-Karp algorithm. \section{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. @@ -2119,17 +2119,10 @@ to $t$ following edges in $E_f'$. After the blocking flow $f'$ has been found and added to $f$, the distance labels are recalculated, and the label of the sink will be increased by at least one. - -\fixme{it's own section now} 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 to Boykov and Kolmogorov, -it outperforms the other algorithms in experimental comparisons for this -specific application. +occuring in graphical applications. It will be presented in +Section~\ref{sec:bk} \section{Push--relabel algorithm} @@ -2535,7 +2528,7 @@ know that only the capacity of edges from sub-graphs 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_\lambda^x(0)$ increases monotonically with increasing $\lambda$ +$E_\lambda^x(1)$ 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 @@ -2665,26 +2658,8 @@ push-relabel algorithm. See \cite{gallo1989fast}, \cite{hochbaum2001efficient} and \cite{goldfarb2009parametric} for more information. -\subsection{Implementation} - -A \cpp\ implementation can be found in -Appendix~\ref{app:c++implementation}. It uses the open computer vision -library OpenCV \cite{opencv_library} to load and save image files. - -Note that when implementing maximum flow algorithms it is not a good -idea, memory- and performance-wise, to actually construct the residual -graph $G_f$. Instead, every time we update the flow $f(u,v)$ we set -the flow in the opposite direction to its negative value $f(v,u) = --f(u,v)$. Then we can at any time, consider the value $c(u,v) - f(u,v)$ -in the place of the residual capacity $c_f(u,v)$. - -For the gap relabeling heuristic, we need to have a easy way of finding -when a gap occurs. This is done by keeping track of how many vertices -exist with each label. - -\fixme{move this since we also implemented boykov--kolmogorov} - \section{Boykov--Kolmogorov algorithm} +\label{sec:bk} \begin{algorithm} \begin{algorithmic} @@ -2894,10 +2869,6 @@ When no more active vertices remain, there are no more possible augmenting paths, and the algorithms terminates with a maximum flow. A proof of correctness can be found in \fixme{kolmogorov-phd}. -\subsection{Performance improvements} - -Adopt to vertex closest to root. And FIFO. Do two-edge pushes initially. - \subsection{Graph reuse} As in the push-relabel algorithm described earlier, it is not necessary @@ -2916,7 +2887,7 @@ break the flow conservation constraint. However, the graph construction in \fixme{ref} did allow for the addition of an arbitrary constant to all the edges of the sub-graph. Thus the construction in Figure~\ref{bk_norm_subgraph} is also valid. We have added the -non-negative constant $\max\{E_{L-1}^x(0), 0\}$ to all the edges of the +non-negative constant $\max\{E_{L-1}^x(1), 0\}$ to all the edges of the graph in \fixme{ref}. As $\lambda$ goes from $L-1$ to $0$ both edges stay non-negative. The edge from $u_\lambda^x$ to $t$ is non-decreasing with decreasing $\lambda$ parameter. @@ -2933,6 +2904,44 @@ paths, the capacity will only change for edges after $u$, as we only change the capacity of edges $(v, t)$. Thus these saturated edges will stay saturated, and $u$ will stay in $T$. +\subsection{Performance improvements} + +There are several open choices in the implementation of the algorithm, +for example the order in which active vertices are processed. As +recommended in \cite{boykov2004experimental}, we have implemented a +«First-In-First-Out» queue. This ensures that at least the first +augmenting path found is a shortest path, although later the distance +information is lost in the adoption stage. + +In the adoption stage it is possible, and perhaps preferrable to seek +possible parent that is closest to the root of the tree, and adopt that +vertex as parent, instead of the first possible. + +Because of the particular graph construction, all vertices except $s$ +and $t$ are connected to $s$ and $t$. Thus there are as many two-edged +paths from $s$ to $t$ as there are pixels in the image. When increasing +the capacity of edges $(v, t)$, a quick sweep over these two-edged paths +to send any possible flow may speed up the algorithm. + +\section{Implementation} + +A \cpp{} implementation can be found in +Appendix~\ref{app:c++implementation}. It uses the open computer vision +library OpenCV \cite{opencv_library} to load and save image files. + +Note that when implementing maximum flow algorithms it is not a good +idea, memory- and performance-wise, to actually construct the residual +graph $G_f$. Instead, every time we update the flow $f(u,v)$ we set +the flow in the opposite direction to its negative value $f(v,u) = +-f(u,v)$. Then we can at any time, consider the value $c(u,v) - f(u,v)$ +in the place of the residual capacity $c_f(u,v)$. + +For the gap relabeling heuristic, we need to have a easy way of finding +when a gap occurs. This is done by keeping track of how many vertices +exist with each label. + +\fixme{something on bk?} + \section{Performance comparison} Maybe. -- 2.47.3