From 739bd3abbdeb45aa8285fd647c23dfe97899c33e Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Mon, 2 Jun 2014 16:05:57 +0200 Subject: [PATCH] Write an introduction and fix stuff --- Makefile | 1 + bib.bib | 42 ++++++++++++++++++++++++++++++++++++++ cut.tex | 2 +- flow.tex | 2 -- introduction.tex | 53 ++++++++++++++++++++++++++++++++++++++++-------- main.tex | 3 ++- methods.tex | 4 ++-- pushrelabel.tex | 6 ++---- results.tex | 48 +++++++++++++++++++++++++++++++++++-------- total.tex | 5 +---- 10 files changed, 135 insertions(+), 31 deletions(-) diff --git a/Makefile b/Makefile index 8501ffe..ce7713e 100644 --- a/Makefile +++ b/Makefile @@ -3,3 +3,4 @@ all: bibtex main xelatex main xelatex main + cp main.pdf ~/Dropbox diff --git a/bib.bib b/bib.bib index 7c182e6..6d3cf18 100644 --- a/bib.bib +++ b/bib.bib @@ -364,4 +364,46 @@ incollection{dinitz2006dinitz, publisher={SIAM} } +@misc{darbonsigellebinary, + title={{J}{\'e}r{\^o}me {D}arbon, {T}otal {V}ariation {M}inimization}, + howpublished = {\url{http://jerome.berbiqui.org/total-variation-code/}}, + note={Accessed: 2014-02-10} +} + +@article {hochbaum2001efficient, + AUTHOR = {Hochbaum, Dorit S.}, + TITLE = {An efficient algorithm for image segmentation, {M}arkov random + fields and related problems}, + JOURNAL = {J. ACM}, + FJOURNAL = {Journal of the ACM}, + VOLUME = {48}, + YEAR = {2001}, + NUMBER = {4}, + PAGES = {686--701 (electronic)}, + ISSN = {0004-5411}, + MRCLASS = {68U10 (62M40 68Q25)}, + MRNUMBER = {2144926 (2005m:68226)}, + DOI = {10.1145/502090.502093}, + URL = {http://dx.doi.org/10.1145/502090.502093}, +} + +@article {gallo1989fast, + AUTHOR = {Gallo, Giorgio and Grigoriadis, Michael D. and Tarjan, Robert + E.}, + TITLE = {A fast parametric maximum flow algorithm and applications}, + JOURNAL = {SIAM J. Comput.}, + FJOURNAL = {SIAM Journal on Computing}, + VOLUME = {18}, + YEAR = {1989}, + NUMBER = {1}, + PAGES = {30--55}, + ISSN = {0097-5397}, + CODEN = {SMJCAT}, + MRCLASS = {68Q25 (05C35 68R10 90B10)}, + MRNUMBER = {978165 (90b:68038)}, + MRREVIEWER = {Andreas Brandst{\"a}dt}, + DOI = {10.1137/0218003}, + URL = {http://dx.doi.org/10.1137/0218003}, +} + diff --git a/cut.tex b/cut.tex index a699403..147851d 100644 --- a/cut.tex +++ b/cut.tex @@ -216,7 +216,7 @@ we have and by Theorem \ref{thm:network_rep_id} our energy function is graph representable. In \cite{kolmogorov2002energy}, Kolmogorov and Zabih presents a way to construct a graph for any graph representable function -on the form shown in theorem \ref{thm:network_rep_id}. Since the +on the form shown in Theorem \ref{thm:network_rep_id}. Since the energies in \eqref{eq:neigh_energies} are especially simple, the construction and presentation is simplified. diff --git a/flow.tex b/flow.tex index f1dd45d..fffc835 100644 --- a/flow.tex +++ b/flow.tex @@ -87,8 +87,6 @@ then be a minimum cut. %finding this minimum cut, we make use of an important duality theorem in %network flow theory, stating that the capacity of a minimum $s$-$t$-cut %in a network, is equal to the maximum flow from the source to the sink. -\fixme{No anti-parallel edges. Or save that for the residual network -section.} But how does this help us? We know that if we know the maximum flow value, and we have an $s$-$t$-cut with capacity equal to the maximum diff --git a/introduction.tex b/introduction.tex index cd74da6..275cb84 100644 --- a/introduction.tex +++ b/introduction.tex @@ -1,13 +1,48 @@ -% Dette eksempelet er laget for article-dokumentklassen. Hvis -% skriver i 'book'-dokumentklassen vil du kanskje bytte ut -% \section med \chapter, \subsection med \section, osv... - \section{Introduction} -\fixme{An appendix is also normal.} +Ever since the invention of the camera people have been improving +the way we record images for future use, and with the advent of +computers, the use of images is no longer restricted to capturing a +moment. Tasks previously reserved for the human brain, like recognizing +textures, detecting edges and inferring shapes and motion, can now be +performed algorithmically. The background of these methods span several +fields, including statistics and analysis for the mathematical +foundation, and computer science for the implementation and performance +analysis. + +Imagining the things we can do to an image, it is possible to roughly +spread it out along a line spanning from the raw capturing of light +coming into the camera, a purely physical and engineering problem, to +the computer vision methods in the other end, semantically interpreting +the scene, recognizing objects, and their position and movement. In +between we have algorithms working on the captured image, without +implying too much about what the image contains. This includes but is +not limited to image restoration, segmentation, filtering and edge +detection. + +In the process of capturing the image with our engineered apparatus, +there is always some noise included. Some might come from the physical +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 +image. These methods often takes 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 captured image. + +In the next section we will see a small overview of some of the most +popular methods in image restoration, but in the rest of the paper we +will focus of the method of total variation. One of the strong points of +this method is its ability to preserve edges, instead of smoothing over +them. The problem is formulated as a minimization of an energy function. +We will discretize this energy function, and find a global minimum by +formulating it as a series of minimum cut problems from graph theory. + +The problem formulation and algorithmical solution is the main focus of +this project, but we will also see some image restoration results in the +end, showing how the method performs for different kinds of noise, and +different input parameters. -Introduce the field field of early vision (?), image restoration, image -restoration. What methods exists, and what are they good at, what are -their applications. What kinds of noise exists. Also, write something -about what was done in this project, and what was achieved. +\newpage diff --git a/main.tex b/main.tex index 1ab8bb4..ba9cbdb 100644 --- a/main.tex +++ b/main.tex @@ -128,8 +128,9 @@ % Bibliografi/referanseliste skal komme før appendiks \bibliography{bib} -\bibliographystyle{plain} +\bibliographystyle{unsrt} +\newpage % En latex-kommando for å si fra at kapitlene/seksjonene fra nå % av skal nummereres med store bokstaver: \appendix diff --git a/methods.tex b/methods.tex index b7b726b..5d959e4 100644 --- a/methods.tex +++ b/methods.tex @@ -25,8 +25,8 @@ be taken on the boundary, and one possibility is to symmetrically extend the image in all directions. By basic Fourier analysis it is possible to show that the Gaussian -filter is a low-pass filter which attenuates high frequencies. -\fixme{Cite Weickert for example?} +filter is a low-pass filter which attenuates high frequencies. See for +example \cite{weickert1998anisotropic} for more information. \subsection{Anisotropic diffusion} Since the Gaussian filter will blur out both noise and details of the diff --git a/pushrelabel.tex b/pushrelabel.tex index 1cb287b..537b4cd 100644 --- a/pushrelabel.tex +++ b/pushrelabel.tex @@ -106,8 +106,6 @@ and $d$ remains a valid labeling, even if the edge $(v, u)$ appears. \end{algorithmic} \caption{ \sf The push procedure of the Push-Relabel algorithm. - \fixme{Here we have a problem with anti-parallel edges again, in the - if statement.} } \label{alg:push} \end{algorithm} @@ -498,8 +496,8 @@ The idea is now that we have halved the possible $\lambda$ interval for separately, and applying the algorithm recursively, at each time halving the $\lambda$ interval until we have the value of every pixel. -See \cite{goldfarb2009parametric} and \fixme{hochbaum} and \fixme{one -more} for more information. +See \cite{gallo1989fast}, \cite{hochbaum2001efficient} and +\cite{goldfarb2009parametric} for more information. \subsection{Implementation} A \cpp\ implementation can be found in appendix diff --git a/results.tex b/results.tex index 6fd2d78..af86901 100644 --- a/results.tex +++ b/results.tex @@ -155,18 +155,18 @@ exit the interval. \end{figure} Figure \ref{fig:gaussian_restored} and \ref{fig:laplace_restored} shows -the noisy images from figure \ref{fig:noisy_lena} restored for different +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$. +feather hanging from her hat has lost details, especially for higher +values of $\beta$. -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. +We see in the method noise, especially in Figure +\ref{fig:laplace_restored_1}, that the feather in Lena's hat 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. As mentioned earlier, one of the theoretically nice properties of the total variation method is that it preserves edges. Looking at the @@ -174,3 +174,35 @@ 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. +\subsection{Algorithm performance} + +\begin{table} + \centering + \caption{ + Performance comparison of the implemented algorithms, and the + algorithm of Darbon and Sigelle \cite{darbon2006image} using + sections of the Lena test image of increasing size. The + Push-Relabel algorithm is run both using the highest level + selection rule (HL) and the first-in first-out selection rule + (FIFO). All numbers are in seconds. + } + \begin{tabular}{lrrrr} + Method & $64\times 64$ & $128\times 128$ & $256\times 256$ & $512\times + 512$ \\ + \hline + Dinitz & 0.55 & 5.75 & 36.7 & 279 \\ + Push-Relabel HL & 0.070 & 0.380 & 2.46 & 19.3 \\ + Push-Relabel FIFO & 0.059 & 0.335 & 1.83 & 8.51 \\ + Darbon and Sigelle & 0.013 & 0.043 & 0.162 & 0.627 + \end{tabular} + \label{tab:perf} +\end{table} + +Table \ref{tab:perf} shows the how the implemented algorithms perform on +test images of different sizes. The binary provided by Darbon and +Sigelle at \cite{darbonsigellebinary}, implemented following the +description in \cite{darbon2006image}, has also been timed for +comparison. They use the specialized algorithm of Boykov and Kolmogorov +\cite{boykov2004experimental}, and additionally a divide and conquer +approach which could explain the superior performance. + diff --git a/total.tex b/total.tex index 78c29db..75c8f94 100644 --- a/total.tex +++ b/total.tex @@ -20,8 +20,6 @@ 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!} Image processing is pushing forward in many fields at once, analysis, spatial statistics and discrete optimization to name a few. Methods can @@ -197,8 +195,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{Bad! The level sets are not sets! But the perimeter -function want sets!} +\fixme{Meh. Level sets.} For an image $u$ we denote by $u \leq \lambda$ the set $\{ x \in \Omega : u_x \leq \lambda\}$ and the thresholded images -- 2.47.3