From d0527982925bc629ad08c0e8256afc79395e75c4 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Wed, 10 Sep 2014 12:07:33 +0200 Subject: [PATCH] Setting up the structure --- .gitignore | 7 ++ Makefile | 6 + appendix.tex | 4 + bib.bib | 294 +++++++++++++++++++++++++++++++++++++++++++++++ commands.tex | 8 ++ introduction.tex | 50 ++++++++ main.tex | 112 ++++++++++++++++++ results.tex | 4 + theory.tex | 53 +++++++++ titlepage.tex | 8 ++ 10 files changed, 546 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 appendix.tex create mode 100644 bib.bib create mode 100644 commands.tex create mode 100644 introduction.tex create mode 100644 main.tex 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..dba8159 --- /dev/null +++ b/.gitignore @@ -0,0 +1,7 @@ +*.aux +*.bbl +*.blg +*.log +*.out +*.pdf +*.toc diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..c2023ad --- /dev/null +++ b/Makefile @@ -0,0 +1,6 @@ +all: + xelatex main + bibtex main + xelatex main + xelatex main + cp main.pdf ~/Dropbox/master/ diff --git a/appendix.tex b/appendix.tex new file mode 100644 index 0000000..87c013b --- /dev/null +++ b/appendix.tex @@ -0,0 +1,4 @@ +\chapter{\cpp\ implementation} + +Some code. + diff --git a/bib.bib b/bib.bib new file mode 100644 index 0000000..6d7589b --- /dev/null +++ b/bib.bib @@ -0,0 +1,294 @@ + + +@article{goldberg1988new, + AUTHOR = {Goldberg, Andrew V. and Tarjan, Robert E.}, + TITLE = {A new approach to the maximum-flow problem}, + JOURNAL = {J. Assoc. Comput. Mach.}, + FJOURNAL = {Journal of the Association for Computing Machinery}, + VOLUME = {35}, + YEAR = {1988}, + NUMBER = {4}, + PAGES = {921--940}, + ISSN = {0004-5411}, + CODEN = {JACOAH}, + MRCLASS = {90B10 (68Q25)}, + MRNUMBER = {1072405 (92c:90050)}, + MRREVIEWER = {Robert E. Beck}, + DOI = {10.1145/48014.61051}, + URL = {http://dx.doi.org/10.1145/48014.61051}, +} + +@article{cherkassky1997implementing, + AUTHOR = {Cherkassky, B. V. and Goldberg, A. V.}, + TITLE = {On implementing the push-relabel method for the maximum flow problem}, + JOURNAL = {Algorithmica}, + FJOURNAL = {Algorithmica. An International Journal in Computer Science}, + VOLUME = {19}, + YEAR = {1997}, + NUMBER = {4}, + PAGES = {390--410}, + ISSN = {0178-4617}, + CODEN = {ALGOEJ}, + MRCLASS = {68Q25 (68R05)}, + MRNUMBER = {1470042}, + DOI = {10.1007/PL00009180}, + URL = {http://dx.doi.org/10.1007/PL00009180}, +} + +@incollection{boykov2006graph, + AUTHOR = {Boykov, Y. and Veksler, O.}, + TITLE = {Graph cuts in vision and graphics: theories and applications}, + BOOKTITLE = {Handbook of mathematical models in computer vision}, + PAGES = {79--96}, + PUBLISHER = {Springer, New York}, + YEAR = {2006}, + MRCLASS = {68U05 (94A08)}, + MRNUMBER = {2232525}, + DOI = {10.1007/0-387-28831-7_5}, + URL = {http://dx.doi.org/10.1007/0-387-28831-7_5}, +} + +@article{derigs1989implementing, + AUTHOR = {Derigs, U. and Meier, W.}, + TITLE = {Implementing {G}oldberg's max-flow-algorithm---a computational + investigation}, + JOURNAL = {Z. Oper. Res.}, + FJOURNAL = {Zeitschrift f\"ur Operations Research. Mathematical Methods of + Operations Research}, + VOLUME = {33}, + YEAR = {1989}, + NUMBER = {6}, + PAGES = {383--403}, + ISSN = {0340-9422}, + MRCLASS = {90C35 (90B10)}, + MRNUMBER = {1030791 (90k:90163)}, + DOI = {10.1007/BF01415937}, + URL = {http://dx.doi.org/10.1007/BF01415937}, +} + +@incollection{caselles2011total, + year={2011}, + isbn={978-0-387-92919-4}, + booktitle={Handbook of Mathematical Methods in Imaging}, + editor={Scherzer, Otmar}, + doi={10.1007/978-0-387-92920-0_23}, + title={Total Variation in Imaging}, + url={http://dx.doi.org/10.1007/978-0-387-92920-0_23}, + publisher={Springer New York}, + author={Caselles, V. and Chambolle, A. and Novaga, M.}, + pages={1016-1057} +} + +@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} +} + +@article{rudin1992nonlinear, + title={Nonlinear total variation based noise removal algorithms}, + author={Rudin, Leonid I and Osher, Stanley and Fatemi, Emad}, + journal={Physica D: Nonlinear Phenomena}, + volume={60}, + number={1--4}, + pages={259--268}, + year={1992}, + publisher={Elsevier} +} + +@article{darbon2006image, + AUTHOR = {Darbon, J{\'e}r{\^o}me and Sigelle, Marc}, + TITLE = {Image restoration with discrete constrained total variation. + {P}art {I}: {F}ast and exact optimization}, + JOURNAL = {J. Math. Imaging Vision}, + FJOURNAL = {Journal of Mathematical Imaging and Vision}, + VOLUME = {26}, + YEAR = {2006}, + NUMBER = {3}, + PAGES = {261--276}, + ISSN = {0924-9907}, + CODEN = {JMIVEK}, + MRCLASS = {68U10 (94A08)}, + MRNUMBER = {2286448 (2008b:68117)}, + MRREVIEWER = {Vassileios Drakopoulos}, + DOI = {10.1007/s10851-006-8803-0}, + URL = {http://dx.doi.org/10.1007/s10851-006-8803-0}, +} + +@inproceedings{boykov2003computing, + title={Computing geodesics and minimal surfaces via graph cuts}, + author={Boykov, Yuri and Kolmogorov, Vladimir}, + booktitle={Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on}, + pages={26--33}, + year={2003}, + organization={IEEE} +} + +@book{weickert1998anisotropic, + AUTHOR = {Weickert, Joachim}, + TITLE = {Anisotropic diffusion in image processing}, + SERIES = {European Consortium for Mathematics in Industry}, + PUBLISHER = {B. G. Teubner, Stuttgart}, + YEAR = {1998}, + ISBN = {3-519-02606-6}, + MRCLASS = {94A08 (65M30 68U10)}, + MRNUMBER = {1666943 (2000a:94003)}, + MRREVIEWER = {Gilbert Crombez}, +} + +@article{chambolle2004algorithm, + AUTHOR = {Chambolle, Antonin}, + TITLE = {An algorithm for total variation minimization and + applications}, + NOTE = {Special issue on mathematics and image analysis}, + JOURNAL = {J. Math. Imaging Vision}, + FJOURNAL = {Journal of Mathematical Imaging and Vision}, + VOLUME = {20}, + YEAR = {2004}, + NUMBER = {1-2}, + PAGES = {89--97}, + ISSN = {0924-9907}, + CODEN = {JMIVEK}, + MRCLASS = {49M30 (65R32 68T45 68U10 90C30)}, + MRNUMBER = {2049783 (2005m:49058)}, + DOI = {10.1023/B:JMIV.0000011320.81911.38}, + URL = {http://dx.doi.org/10.1023/B:JMIV.0000011320.81911.38}, +} + +@incollection{kolmogorov2002energy, + title={What energy functions can be minimized via graph cuts?}, + author={Kolmogorov, Vladimir and Zabih, Ramin}, + booktitle={Computer Vision—ECCV 2002}, + pages={65--81}, + year={2002}, + publisher={Springer} +} + +@book{cormen2009introduction, + title={Introduction to algorithms}, + author={Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford}, + edition={Third}, + year={2009}, + publisher={MIT press} +} + +@book{scherzer2008variational, + AUTHOR = {Scherzer, Otmar and Grasmair, Markus and Grossauer, Harald and + Haltmeier, Markus and Lenzen, Frank}, + TITLE = {Variational methods in imaging}, + SERIES = {Applied Mathematical Sciences}, + VOLUME = {167}, + PUBLISHER = {Springer, New York}, + YEAR = {2009}, + ISBN = {978-0-387-30931-6}, + MRCLASS = {49-02 (49J10 68U10 94A08)}, + MRNUMBER = {2455620 (2009j:49001)}, + MRREVIEWER = {Bogdan G. Nita}, +} + +@article{opencv_library, + author = {Bradski, G.}, + citeulike-article-id = {2236121}, + journal = {Dr. Dobb's Journal of Software Tools}, + keywords = {bibtex-import}, + posted-at = {2008-01-15 19:21:54}, + priority = {4}, + title = {OpenCV Library}, + year = {2000} +} + +@incollection{dinitz2006dinitz, + AUTHOR = {Dinitz, Yefim}, + TITLE = {Dinitz' algorithm: the original version and {E}ven's version}, + BOOKTITLE = {Theoretical computer science}, + SERIES = {Lecture Notes in Comput. Sci.}, + VOLUME = {3895}, + PAGES = {218--240}, + PUBLISHER = {Springer, Berlin}, + YEAR = {2006}, + MRCLASS = {90C35 (01A60 05C85 90-03)}, + MRNUMBER = {2248665 (2007f:90123)}, + MRREVIEWER = {Mechthild Opperud}, + DOI = {10.1007/11685654_10}, + URL = {http://dx.doi.org/10.1007/11685654_10}, +} + +@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} +} + +@article{cheriyan1989analysis, + title={Analysis of preflow push algorithms for maximum network flow}, + author={Cheriyan, Joseph and Maheshwari, S. N.}, + journal={SIAM Journal on Computing}, + volume={18}, + number={6}, + pages={1057--1086}, + year={1989}, + publisher={SIAM} +} + +@article{goldfarb2009parametric, + title={Parametric maximum flow algorithms for fast total variation minimization}, + author={Goldfarb, Donald and Yin, Wotao}, + journal={SIAM Journal on Scientific Computing}, + volume={31}, + number={5}, + pages={3712--3743}, + year={2009}, + 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/commands.tex b/commands.tex new file mode 100644 index 0000000..4b6a8a8 --- /dev/null +++ b/commands.tex @@ -0,0 +1,8 @@ +\newcommand{\abs}[1]{\lvert #1 \rvert} +\newcommand{\norm}[1]{\lVert #1 \rVert} +\newcommand{\TV}{\mathit{TV}} +\newcommand{\BV}{\mathit{BV}} +\newcommand{\idfun}{\mathbbm{1}} +\definecolor{fixme-color}{rgb}{0.7,0.2,0} +\newcommand{\fixme}[1]{\textcolor{fixme-color}{FIXME: #1}} +\def\cpp{C{}\texttt{++}} diff --git a/introduction.tex b/introduction.tex new file mode 100644 index 0000000..56bfd85 --- /dev/null +++ b/introduction.tex @@ -0,0 +1,50 @@ +\chapter{Introduction} + +So here maybe we introduce the field of image restoration. Ideas can be +found in the introduction of the project. Maybe we also say something +about the different noise models, and common assumptions concerning the +noise. + +\section{Diffusion filtering} + +First we say something about normal Gaussian filtering, how it is +related to solving the heat equation etc. Weickert +\cite{weickert1998anisotropic} is a good reference here, and in many of +the other sections. End with the motivation of controlling the diffusion +coefficient. + +\subsection{Non-linear diffusion} + +This section is for methods that control the diffusion coefficient +$\alpha$. Here I guess Perona-Malik is the most noteworthy. We write +something about the motivation, its well-posedness (or lack thereof) and +other alternatives. But we can control the diffusion even more! + +\subsection{Anisotropic diffusion} + +Section for methods introducing a diffusion \emph{tensor} $A$ that +varies around the image. This means we can control diffusion strength in +different directions. More specifically we can make the diffusion strong +along edges, and weak across edges. + +We must also say something about what this method does well, and where +it fails. Anisotropic filtering might introduce structures that do not +exist in the original image. Some example images are possible here. + +\section{Total variation filtering} + +Describe briefly the functional we minimize in this method, and +intuitively how this leads to a filtered image. But how much do we write +about how we find our minimizer? We have to at least mention that there +are different ways to do it, and that one of them involves finding a +minimum cut for each level. + +We also write something about the limitations of the method. It is good +at preserving sharp edges, but suffers from the so-called stair-casing +effect. Thin objects and corners might gradually lose contrast depending +on the strength of the regularization. Example images here as well. + +Then finish the chapter in some way saying that we will try to combine +these two methods, retaining their strenghts but eliminating their +weaknesses. + diff --git a/main.tex b/main.tex new file mode 100644 index 0000000..7b75885 --- /dev/null +++ b/main.tex @@ -0,0 +1,112 @@ +\documentclass[a4paper, titlepage, twoside, 12pt]{report} + +\usepackage{geometry} + +\usepackage{amsmath} +\usepackage{unicode-math} +\usepackage{fontspec} +\usepackage{amsthm} +\usepackage{graphicx} +\usepackage{mathtools} + +\usepackage{polyglossia} +\setmainlanguage[variant=american]{english} + +\usepackage[hidelinks]{hyperref} + +\usepackage[binary-units=true]{siunitx} + +\usepackage{tikz} +\usetikzlibrary{matrix} +\usetikzlibrary{arrows} +\usetikzlibrary{positioning} +\usetikzlibrary{calc} + +\usepackage{color} +\usepackage{bbm} % Indicator function \mathbbm{1} +%\usepackage[margin=0.8cm]{caption} +\usepackage{caption} +%\usepackage[subrefformat=parens,labelformat=parens]{subcaption} +\usepackage{subcaption} +\usepackage{xfrac} +\usepackage{listings} + +\lstset{ + % FIXME: Courier 9pt anbefales + basicstyle=\footnotesize\ttfamily, + keepspaces=true, + tabsize=4, + %inputencoding=utf8/latin1, + extendedchars=true, + breakatwhitespace=false, + breaklines=true, +} + +\usepackage{algorithm} +\usepackage{algpseudocode} + +\newtheorem{theorem}{Theorem} +\newtheorem{lemma}{Lemma} +\newtheorem{definition}{Definition} + +% Indeksgenerering er kommentert ut her. Ta bort prosenttegnene +% hvis du vil ha en indeks: +%\usepackage{makeidx} +%\makeindex + +\input{commands} + +% Selve dokumentet begynner: + +\begin{document} + +% På forsida skal vi ikke ha noen sidenummerering: + +\pagestyle{empty} +\pagenumbering{roman} + +% Inkluder forsida: +\input{titlepage} + +\cleardoublepage + +% 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 +\input{introduction} +\input{theory} +\input{results} + +% Bibliografi/referanseliste skal komme før appendiks +\bibliography{bib} +\bibliographystyle{unsrt} + +\newpage +% 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/results.tex b/results.tex new file mode 100644 index 0000000..3a9bc06 --- /dev/null +++ b/results.tex @@ -0,0 +1,4 @@ +\chapter{Results} + +\section{Comparison} + diff --git a/theory.tex b/theory.tex new file mode 100644 index 0000000..1457eea --- /dev/null +++ b/theory.tex @@ -0,0 +1,53 @@ +\chapter{Theory} + +This is the chapter containing all the theory of the presented +restoration method. The order in which everything is presented is not +fixed. For example how much should we discuss the details of the +anisotropy matrix $M$ before introducing the coarea and perimiter +theory? Because the coarea formula \emph{can} be presented in a very +general form. We will figure that out as we go. + +\section{Anisotropic total variation} + +Here we start out with the normal total variation (?), give some +motivation and introduce the anisotropy. We probably need the definition +of total variation, and the space of functions of bounded variation. The +order is not clear to me, yet! + +\section{Anisotropy tensor} + +We discuss what kind of properties we want from the anisotropy tensor, +and also introduce the structure tensor (?) described by Weickert. This +tensor can be visualized, and can be used for edge detection. There is +probably a bit to be said about the smoothing we do. We also discuss +whether to use the noisy image (yes, probably), or the smoothed image +(implicitly, complicated, possible iteratively) in the structure tensor. +We then describe how the structure tensor is decomposed and transformed +into our anisotropy tensor. Then there are some problems related to +stability which we can discuss here, or maybe we should leave it for a +later, more implementation-focused chapter. + +\section{Continuous formulation} + +In spirit of my project I have included a section with this title. It +will be a theory heavy chapter, probably including the anisotropic +coarea formula and the perimeters and all that. Should probably include +some proofs and derivations as it is not easy to find this in the +literature. This is one of the most important parts of the theory +chapter, I guess. + +\section{Discretization} + +This is where we discretize! It will also be an important chapter, as +the choices and possibilities are endless. The easiest way out is to +choose the same stencil in every point, and only let the weights depend +on the anisotropy. This can work, but size has to be discussed (and +tested later). Then the stencil shape can be adjusted as well. + +\section{Graph theory} + +\subsection{Intro} +\subsection{Graphification} + +\section{Flow} + diff --git a/titlepage.tex b/titlepage.tex new file mode 100644 index 0000000..678469b --- /dev/null +++ b/titlepage.tex @@ -0,0 +1,8 @@ +\title{Anisotropic total variation based image restoration using graph +cuts} + +\date{\today} + +\author{Bjørn Rustad} + +\maketitle -- 2.47.3