From 9636e6d6034125e4d22a65425b8c5e8b0fa52deb Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Wed, 26 Feb 2014 15:53:10 +0100 Subject: [PATCH] Initial commit --- .gitignore | 9 +++ Makefile | 5 ++ appendix.tex | 8 +++ bib.bib | 93 +++++++++++++++++++++++++ introduction.tex | 10 +++ main.tex | 85 +++++++++++++++++++++++ notes | 5 ++ results.tex | 18 +++++ theory.tex | 173 +++++++++++++++++++++++++++++++++++++++++++++++ titlepage.tex | 12 ++++ 10 files changed, 418 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 appendix.tex create mode 100644 bib.bib create mode 100644 introduction.tex create mode 100644 main.tex create mode 100644 notes create mode 100644 results.tex create mode 100644 theory.tex create mode 100644 titlepage.tex diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..07370bf --- /dev/null +++ b/.gitignore @@ -0,0 +1,9 @@ +*.aux +*.bbl +*.blg +*.dvi +*.log +*.out +*.pdf +*.toc + diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..f242a84 --- /dev/null +++ b/Makefile @@ -0,0 +1,5 @@ +all: + pdflatex main + bibtex main + pdflatex main + pdflatex main diff --git a/appendix.tex b/appendix.tex new file mode 100644 index 0000000..a267dc8 --- /dev/null +++ b/appendix.tex @@ -0,0 +1,8 @@ +% 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{C++ implementation} + +int main() + diff --git a/bib.bib b/bib.bib new file mode 100644 index 0000000..a22d23b --- /dev/null +++ b/bib.bib @@ -0,0 +1,93 @@ + + +@article{goldberg1988new, + title={A new approach to the maximum-flow problem}, + author={Goldberg, Andrew V and Tarjan, Robert E}, + journal={Journal of the ACM (JACM)}, + volume={35}, + number={4}, + pages={921--940}, + year={1988}, + publisher={ACM} +} + +@article{Mazzoni1991257, + title = "The maximum flow problem: A max-preflow approach ", + journal = "European Journal of Operational Research ", + volume = "53", + number = "3", + pages = "257 - 278", + year = "1991", + note = "", + issn = "0377-2217", + doi = "http://dx.doi.org/10.1016/0377-2217(91)90060-9", + url = "http://www.sciencedirect.com/science/article/pii/0377221791900609", + author = "Giuseppe Mazzoni and Stefano Pallottino and Maria Grazia Scutellà", + keywords = "Maximum flow", + keywords = "maximum preflow", + keywords = "distance function", + keywords = "algorithm", + keywords = "experimentation " +} + +@article{cherkassky1997implementing, + title={On implementing the push—relabel method for the maximum flow problem}, + author={Cherkassky, Boris V and Goldberg, Andrew V}, + journal={Algorithmica}, + volume={19}, + number={4}, + pages={390--410}, + year={1997}, + publisher={Springer} +} + +@article{ahuja1997computational, + title={Computational investigations of maximum flow algorithms}, + author={Ahuja, Ravindra K and Kodialam, Murali and Mishra, Ajay K and Orlin, James B}, + journal={European Journal of operational research}, + volume={97}, + number={3}, + pages={509--542}, + year={1997}, + publisher={Elsevier} +} + +@incollection{boykov2006graph, + title={Graph cuts in vision and graphics: Theories and applications}, + author={Boykov, Yuri and Veksler, Olga}, + booktitle={Handbook of mathematical models in computer vision}, + pages={79--96}, + year={2006}, + publisher={Springer} +} + +@article{derigs1989implementing, + title={Implementing Goldberg's max-flow-algorithm—A computational investigation}, + author={Derigs, Ulrich and Meier, Wolfgang}, + journal={Zeitschrift f{\"u}r Operations Research}, + volume={33}, + number={6}, + pages={383--403}, + year={1989}, + publisher={Springer} +} + +@incollection{caselles2011total, + title={Total variation in imaging}, + author={Caselles, Vicent and Chambolle, Antonin and Novaga, Matteo}, + journal={Handbook of Mathematical Methods in Imaging}, + pages={1016--1057}, + year={2011}, + publisher={Springer} +} + +@incollection{chan2011numerical, + title={Numerical methods and applications in total variation image restoration}, + author={Chan, Raymond and Chan, Tony and Yip, Andy}, + booktitle={Handbook of Mathematical Methods in Imaging}, + pages={1059--1094}, + year={2011}, + publisher={Springer} +} + + diff --git a/introduction.tex b/introduction.tex new file mode 100644 index 0000000..f955d41 --- /dev/null +++ b/introduction.tex @@ -0,0 +1,10 @@ +% 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} + +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. + diff --git a/main.tex b/main.tex new file mode 100644 index 0000000..dc75594 --- /dev/null +++ b/main.tex @@ -0,0 +1,85 @@ +% Først spesifiserer vi hvilken dokumentklasse vi vil ha og noen +% globale opsjoner. Bytt ut 'article' med 'book' hvis du vil ha +% med kapitler. +\documentclass[a4paper, twoside, titlepage, 11pt]{article} + +% Så sier vi fra om hvilke tilleggspakker vi trenger +% til dokumentet vårt. De som du ikke trenger (se kommentaren) +% kan det være en fordel å kommentere ut (sett prosenttegn foran), +% da vil kompilering gå raskere. + +\usepackage[T1]{fontenc} % norsk tegnsett (æøå) +\usepackage[utf8]{inputenc} % norsk tegnsett +\usepackage{geometry} % anbefalt pakke for å styre marger. + +\usepackage{amsmath,amsfonts,amssymb} % matematikksymboler +\usepackage{amsthm} % for å lage teoremer og lignende. +\usepackage{graphicx} % inkludering av grafikk + +\usepackage{hyperref} % Lager hyperlinker i evt. pdf-dokument + % men har noen bugs, så den er kommentert + % bort her. +\usepackage{algorithm} +\usepackage{algpseudocode} + +% Indeksgenerering er kommentert ut her. Ta bort prosenttegnene +% hvis du vil ha en indeks: +%\usepackage{makeidx} +%\makeindex + +% Selve dokumentet begynner: + +\begin{document} + +% På forsida skal vi ikke ha noen sidenummerering: + +\pagestyle{empty} +\pagenumbering{roman} + +% Inkluder forsida: +\input{titlepage} + +% Romerske tall på alt før selve rapporten starter er pent. +\pagenumbering{roman} + +% For å ikke begynne innholdslista på baksida av forsida: +\cleardoublepage +% (kun aktuelt når man har twoside som global opsjon) + +% Nå vi vil ha noe i topp- og bunnteksten +\pagestyle{headings} + +% Si til LaTeX at vi vil ha ei innholdsliste generert akkurat her: +\tableofcontents + +% Pass på at neste side ikke begynner på baksida av en annen side. +\cleardoublepage + +% Arabisk (vanlige tall) sidenummerering. Starter på side 1 igjen. +\pagenumbering{arabic} + +% Inkluder alle de andre kildefilene: + +% NB: Vi trenger ikke ta med filendelsen .tex her. Den vet +% LaTeX om selv! + +\input{introduction} +\input{theory} +\input{results} + +% Bibliografi/referanseliste skal komme før appendiks +\bibliography{bib} +\bibliographystyle{plain} + +% En latex-kommando for å si fra at kapitlene/seksjonene fra nå +% av skal nummereres med store bokstaver: +\appendix + +\input{appendix} + +% Indeks for rapporten. Ta bort prosenttegn hvis du vil ha det med. +%\printindex + +% Avslutter dokumentet vårt: +\end{document} + diff --git a/notes b/notes new file mode 100644 index 0000000..adedf87 --- /dev/null +++ b/notes @@ -0,0 +1,5 @@ +o Relabeling + - Goldberg and Tarjan introduced global relabeling (every 2n discharge) + - Derigs and Meier introduced gap relabeling + - Setubal proves that global is better + - Goldberg recommends using both diff --git a/results.tex b/results.tex new file mode 100644 index 0000000..ed0d873 --- /dev/null +++ b/results.tex @@ -0,0 +1,18 @@ +% 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{Results} +Method noise is the original image subtracted from the output image. It +should not containt too many features. + +\subsection{Image segmentation} +Some figures maybe. Showing the segmentation for different parameters. + +\subsection{Image restoration} +Different kinds of noise, different parameters. Compare it with other +methods maybe. + +\subsubsection{Impulse noise} +\subsubsection{Gaussian noise} + diff --git a/theory.tex b/theory.tex new file mode 100644 index 0000000..57516e0 --- /dev/null +++ b/theory.tex @@ -0,0 +1,173 @@ +% 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{Theory} + +\subsection{Methods} + +\subsubsection{Anistrophic diffusion} +Some partial differential equation magic. + +\subsubsection{Gaussian filtering} +Convolve the image with Gaussian function. Adds blur. + +\subsubsection{Non-local means} +Somehow averaging over all the pixels in the image. Has a very good +method noise. + +\subsubsection{Non-linear filters} +Median filter for example. + +\subsubsection{Total variation} +Our method. WHAT IS SPLIT BREGMAN? + +\subsection{Continuous formulation} +Formulate the energy function, describe the different terms. Total +variation. \cite{caselles2011total} has a nice introduction to total +variation. It describes the foundations, the spaces, and some methods, +but mostly continuous. + +\subsection{Discrete problem} +How do we get to the discrete formulation. Why is it OK to do what we do +with the gradient. How do we decompose the energy function into +different levels and why is it OK to optimize each level separately. How +do we choose the different neighbourhoods, and what could this mean for +the result. Darbon and Sigelle. \cite{chan2011numerical} describes +different methods for using total variation, and especially how one can +use it in the discrete setting. It also goes into the min-cut method. +Yay. Good book. + +\subsection{Graph cut formulation} +Short introduction to graphs. Notation. What is a cut, what is a minimal +s-t-cut. How do we get from the discrete energy to the graph and why +does finding the graph cut result in minimizing the energy of the +current label. Boykov and Kolmogorov. + +\subsubsection{Min-cut max-flow theorem} +Want to find the minimal s-t-cut, so we introduce flow here maybe? Or +earlier? Finding the max flow results in also finding the minimal cut, +and there are «good» algorithms for finding the maximal flow. + +\subsection{Maximum flow algorithms} +Two different ideas. One is to always maintain a valid flow in the +network, Ford Foulkerson, always looking for new paths from s to t along +which we can send additional flow. This leads to Edmonds-Karp, and +Dinic/Dinitz. Second idea is push-relabel, allowing positive excess in +the nodes. We lift the source, and let as much flow as possible flow +towards the sink. + +\subsubsection{Dinic's algorithm} +The «best» of the augmenting-path algorithms (citation needed). Makes a +level graph with BFS, and finds a blocking flow through this graph which +only goes from nodes with one label to nodes with greater labels. When +this blocking flow is found we restart at the BFS. + +\subsubsection{The push-relabel algorithm} +The nodes are allowed to have a positive excess but we still follow the +capacity constraints. The nodes also have a labeling, which has to be +valid. Push flow from active nodes, and relabel, preferrably in a +specific order, until it is not possible anymore. The minimal cut is +actually found before the flow becomes valid (has to be explained). + +Because of the way the graph evolves, we can reuse the graph between the +different labels. + +Initially proposed in \cite{goldberg1988new} where one can also find +proof that the algorithm maintains a valid labeling and that it +terminates at at maximal flow. Also has the lemma that if you have a +preflow, then there is no path from $s$ to $t$ in the residual graph. +But what is a preflow? Also, the distance label never decreases. Also +propose the global relabeling heuristic. + +Shiloach and Vishkin originally proposed the FIFO way of doing things +(according to Golberg and Tarjan)? + +Cherkassky and Goldberg present some good implementation tips in +\cite{cherkassky1997implementing}, for example the global and gap +relabeling heuristics. Also has OK presentations of the different ways +of choosing the order of discharge operations. In the results I should +include some results with and without the heuristics. + +\cite{ahuja1997computational} has some good performance analysis. + +\cite{boykov2006graph} is a good source on how graph cuts are used in +image analysis. It considers both one level graphs, and multilevel +graphs. Which is nice. It has just a small section on the different +algorithms that exist and that the special Boykov Kolmogorov algorithm +is the best. + +\cite{derigs1989implementing} is also a good source for the different +heuristics. And also on the neighbor list that should not be reset after +each discharge (should try to implement this again, and reset at every +relabel!). Also has some semi-usable notes on how the minimal cut is +found after phase 1 of the algorithm is finished. Note that in this +article the gap relabeling heuristic is also called RELABEL-GLOBAL. + +\begin{algorithm} +\begin{algorithmic} + \Function{Push}{$u$} + \ForAll{$v$ neighbour of $u$} + \If{$res(u, v) > 0$} + \State $f \gets min(res(u, v), excess[u])$ + \State $flow(u, v) \mathrel{+}= f$ + \State $flow(v, u) \mathrel{-}= f$ + \State $excess[u] \mathrel{-}= f$ + \State $excess[v] \mathrel{+}= f$ + \EndIf + \EndFor + \EndFunction +\end{algorithmic} +\caption{\sf The push procedure of the Push-Relabel algorithm} +\end{algorithm} + +\begin{algorithm} +\begin{algorithmic} + \Function{Relabel}{$u$} + \If{$u$ is only node at its height} + \Call{Gap}{$u$} + \Else + \State $height[u] \gets min(height[v] \, \forall v \in + neighbors[u] : res(u, v) > 0) + 1$ + \EndIf + \EndFunction +\end{algorithmic} +\caption{\sf The relabel procedure of the Push-Relabel algorithm} +\end{algorithm} + +\begin{algorithm} +\begin{algorithmic} + \Function{Gap}{$u$} + \State $k \gets height[u]$ + \ForAll{$v$ with height $\geq k$} + \State $height[v] \gets N$ + \EndFor + \EndFunction +\end{algorithmic} +\caption{\sf The gap procedure of the Push-Relabel algorithm} +\end{algorithm} + +\subsubsection{Other algorithms} +Special made augmenting flow algorithm for this type of graphs. Used in +software1, software2, etc. Is fast. + +\subsection{Noise theory} +What kinds of noise occur in what kinds of settings. Which methods +should be good for which + +\subsubsection{Gaussian noise} +Common. Thermal noise? Central limit theorem. Read in Jähne. + +\subsubsection{Poisson noise} + +\subsubsection{Salt and pepper noise} + +\subsubsection{Shot noise} +Same as Poisson noise? Quantum effects in the way light is emitted at +the source. For regular photographs it will only be a determining factor +in low light conditions. + +Dark current, or reverse bias leakage current, which is due to the +random generation of electrons in the sensor, can also be modelled by a +Poisson distribution. + diff --git a/titlepage.tex b/titlepage.tex new file mode 100644 index 0000000..82d2256 --- /dev/null +++ b/titlepage.tex @@ -0,0 +1,12 @@ +% Enkel forside som bruker latex sin \titlepage kommando: +% NB: Bruken av \and mellom navn! + +\titlepage +\title{Image restoration using graph cuts} +\author{Bjørn Rustad} +\date{\today} +\maketitle + +% Local Variables: +% TeX-master: "master" +% End: -- 2.47.3