\documentclass[a4paper, 12pt, titlepage, twoside]{report}

\year=2008
\month=10
\day=01

% TODO check \ref's!!


%% Package includes
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[normalem]{ulem}
\usepackage{times}

\usepackage{fancyhdr}

\addtolength{\footskip}{+1cm}
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{+1cm}
\addtolength{\headheight}{+0.6cm}
\addtolength{\evensidemargin}{-2cm}
\addtolength{\textwidth}{+2cm}

%\usepackage{pifont}

\usepackage{makeidx}

\usepackage{graphicx}
\usepackage{bold-extra}
\usepackage{color}
\usepackage{pstricks}
\usepackage{pst-plot}
\usepackage{pstricks-add}

\usepackage{multirow}

\usepackage{listings}

\usepackage{booktabs}

\usepackage[pdfpagelabels]{hyperref}
\usepackage[hyphenbreaks]{breakurl}

\usepackage{appendix}

%% Look&Feel
\newcommand{\cmd}[1]{{\ttfamily\bfseries\selectfont #1}}
\newcommand{\cmdmeta}[1]{{\normalfont\ttfamily\selectfont #1}}
\newenvironment{cmdblock}{\vspace{0.5em}\newline\begin{tabular}{p{0.95\textwidth}}\ttfamily\bfseries\selectfont}{\end{tabular}\vspace{0.5em}\newline}
\newcommand{\fname}[1]{{\small\sffamily\selectfont #1}}
\newcommand{\config}[1]{{\itshape\slshape\ttfamily con\-fi\-gu\-ra\-tion#1}}

%% Useful stuff
\newcommand{\ttbs}{\symbol{92}}  %tt backslash
\newcommand{\cursor}{\ding{122}} %cursor
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}

%% Colors
\definecolor{grey}{rgb}{0.6,0.6,0.6}
\definecolor{lightgrey}{rgb}{0.9,0.9,0.9}
\definecolor{lightblue}{rgb}{0.625,0.68,0.89}
\definecolor{lightgreen}{rgb}{0.61,0.875,0.648}
\definecolor{lightorange}{rgb}{1.0,0.8,0.6}
\definecolor{niceblue}{rgb}{0.0,0.0,0.8}
\definecolor{nicegreen}{rgb}{0.0,0.7,0.1}

%% Re-hyphenation
%\hyphenation{FFMPEG}

\makeindex
\pagenumbering{roman}

\lstset{language=[ANSI]C,basicstyle=\ttfamily,basewidth=0.5em,breaklines=true}
\newcommand{\code}[1]{\lstinline{#1}}
\newcommand{\asm}[1]{\texttt{#1}}
\newcommand{\mbti}[1]{\mbox{\footnotesize{}#1}}

\usepackage[margin=10pt,bf]{caption}

\newcommand{\topcaption}{%
\setlength{\abovecaptionskip}{0pt}%
\setlength{\belowcaptionskip}{10pt}%
\caption}

\fancyhf{}
\fancyhead[LE]{\leftmark} 
\fancyhead[RO]{\rightmark}
\fancyfoot[LE]{\thepage}
\fancyfoot[RO]{\thepage}

\begin{document}

\vfuzz=10cm\relax
\vbadness=10000

%titlepage
\begin{titlepage}
\pagestyle{plain}
\centering
\vspace*{-3cm}
Saarland University\\
Faculty of Natural Sciences and Technology I\\
Department of Computer Science\\
Bachelor's Program in Computer Science\\
\vspace{\fill}
\LARGE
\sout{\hspace*{\fill}}\textbf{ Bachelor's Thesis }\sout{\hspace*{\fill}}\\
\Huge
\vspace{0.5\baselineskip}
\textbf{Audio Denoising with \\ Non-Local Algorithms from \\ Image Processing}\\
{\LARGE \hrulefill\\}
\vspace{0.5\baselineskip}
\LARGE
\textbf{ Jan Hendrik Dithmar }\\
\Large
\number\year-\number\month-\number\day\\
\vspace{\fill}
\hfuzz=10cm\relax
   \normalsize
\begin{center}
\begin{tabular}{lcr}
\begin{minipage}{2.1cm}
\hspace{-1.5cm}\includegraphics[height=1.8cm]{figures/mia-logo.eps}
\end{minipage}
&
\makebox[2cm]{}
&
\begin{minipage}{8cm}
\hspace{1.5cm}
   \begin{tabular}{rl}
     \vspace{.5\baselineskip}
     Supervisor             & Prof.\ Dr.\ Joachim Weickert\\
     \vspace{.5\baselineskip}
     Advisor                & Dr.\ Martin Welk\\
     \vspace{1.5\baselineskip}
     Reviewers              & Prof.\ Dr.\ Joachim Weickert\\
                            & PD Dr.\ Meinard M{\"u}ller
   \end{tabular}
\end{minipage}
\end{tabular}
\end{center}

\vspace*{-3cm}
\end{titlepage}
\fancypagestyle{plain}{%
\fancyfoot[LE]{\thepage}%
\fancyfoot[RO]{\thepage}}

\pagestyle{plain}

\fancyhf{}
\fancyhead[LE]{\leftmark} 
\fancyhead[RO]{\rightmark}
\fancyfoot[LE]{\thepage}
\fancyfoot[RO]{\thepage}

%\maketitle

%% Affidavit
\hfuzz=0cm\relax
\cleardoublepage
\pagestyle{plain}
\vspace*{\fill}
\section*{Affidavit}
I hereby declare that this bachelor's thesis has been written only by the undersigned and without any assistance from third parties.\\
Furthermore I confirm that no sources have been used in the preparation of this thesis other than those indicated in the thesis itself.
\vspace{2cm}\\
Saarbr\"ucken, \number\year-\number\month-\number\day

\section*{Declaration of Consent}
Herewith I agree that this thesis will be made available through the library of the Computer Science Department. This consent explicitly includes both the printed, as well as the electronic form attached to this thesis.\\
I confirm that the electronic and the printed version are of identical content.\\
\vspace{2cm}\\
Saarbr\"ucken, \number\year-\number\month-\number\day

%% Abstract
\cleardoublepage
\pagestyle{plain}
%\vspace*{\fill}
\section*{Abstract}
Noisy structures can appear in different variations in images. They might appear as noise that is present in the whole image, like Gaussian white noise, salt-and-pepper noise or speckle noise. Speckle noise, for example, is caused by the measurement of an ultrasound image. But noise can also appear locally in an image, e.g.\ as a black spot in the middle of a color image. These concepts are also present in audio signals. On the one hand side one can have Gaussian noise that degrades a whole signal or on the other hand side a structure that appears locally, for example a cough. Of course, noise in images and audio signals is different if one looks at them in detail, but the basic ideas of noise are present in both fields. This thesis investigates noise that appears locally as an isolated and intense event in the audio signal.

In the last few years, research interest was focussed on non-local algorithms in image processing by many groups. Since these algorithms worked well and were very easy to understand in most cases, the investigation of those is still going on. An algorithm that is very popular in that respect is the NL-means approach by Buades, Coll and Morel \cite{buades05}. Furthermore, non-local algorithms in image processing are based on the same assumptions that could also be formulated for audio processing. An assumption is to find similar patches in an image or audio signal by doing a Fourier transform and analyze the spectrum afterwards by an appropriate similarity measurement. Having found similar patches, one can try to repair using a non-local approach.
%Image denoising has become a well established field in computer science nowadays. There exist a lot of good and fast algorithms to denoise structures. Since filters like low pass filters can appear in everyday work of image processing people, but also studio engineers, the question how far one can dive into the audio sector with the methods known from image processing is pretty natural.

This thesis gives an overview of the modifications in terms of the Fourier transform and the NL-means approach that are necessary to adapt these methods known from image processing to audio signals. Also, the usage of non-local inpainting -- i.e.\ copying data already present in the audio signal -- and an averaging on a sample basis are introduced. At the end, all the presented methods are evaluated by experiments.

%% Thanks
\cleardoublepage
\pagestyle{plain}
%\vspace*{\fill}
\section*{Acknowledgements}
\hbadness=10000
I would like to express my sincere thanks to my advisor Dr.\ Martin Welk and my supervisor Prof.\ Dr.\ Joachim Weickert for their excellent mentoring and support during the development of this thesis. Their encouragement and the friendly atmosphere in the Mathematical Image Analysis Group greatly assisted me in my work. I also like to thank PD Dr.\ Meinard M{\"u}ller for consenting to review my thesis.
\\\\
Special thanks also go to my family who enabled me to perform my studies and to pursue my musical career as I did and who therefore also significantly contributed to the success I have enjoyed so far.

%\newpage\vspace*{\fill}\newpage
\cleardoublepage
\hbadness=1000

\tableofcontents

\cleardoublepage
\listoffigures
\listoftables

%\newpage\vspace*{\fill}\newpage
\cleardoublepage
\pagenumbering{arabic}
\setcounter{page}{1}

%%%%%%%%%%%%%%%%%% INTRODUCTION %%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\cleardoublepage\chapter{Introduction\index{introduction}}
%%%%%%%%%%%%%%%%%% INTRODUCTION: MOTIVATION %%%%%%%%%%%%%%%%%%
\section{Motivation}\label{introduction.motivation}
Post-editing and post-production of music becomes more and more important in music industry. When recording a live performance it can happen that a certain part is degraded that cannot be re-recorded again, for example caused by a cough.

Another possible scenario could be a noisy playback, say by a record player playing an old vinyl. Here, the noise is due to the playback technique itself.

Naturally, one is interested in correcting noisy parts of a recording. To achieve this, one tries to exploit the high redundancy in music. Typically, one would proceed manually as follows: people would have to go through the whole piece of music and acoustically judge whether a certain part is similar to the noisy one. After having found a possible candidate it had to be (manually) copied at the location of the noisy data. Recently, this work is supported by spectrograms which represent the audio signal in a three-dimensional way, giving the time on the x-axis, the frequency on the y-axis and the intensity of the frequencies in a color representation. But also other representations exist. An example is shown in figure \ref{introduction.figures.spectrogram}.

\begin{figure}[ht]
\centering
\includegraphics[height=0.4\textheight]{figures/spectrogram-example.eps}
\caption[Spectrogram representing a part of a song.]{Spectrogram representing a part of \fname{cyftlt-mono.wav}. \textit{x-axis:} Time. \textit{y-axis:} Frequencies. \textit{Colors:} Intensity. The blue color stands for a high intensity going over red and yellow to white which stands for a low intensity. \textbf{Visualization:} using RavenLite 1.0 \cite{ravenlite}.}
\label{introduction.figures.spectrogram}
\end{figure}

During this thesis, a preprint by A. Szlam \cite{nlmeansaudio} appeared which also studies the application of the NL-means algorithm as proposed by \cite{buades05} for audio denoising. While Szlam investigates speech as audio data where the whole signal is degraded by Gaussian white noise, this thesis covers music data -- to be more precise: piano music -- where the noisy events appear only locally. Another difference is that the work by Szlam uses noise that is quite moderate while the noise investigated in this thesis is very intense. Nevertheless, the averaging approach which is the key of the NL-means algorithm is similar in both approaches, the one by Szlam and the one here.

Both, image processing and audio processing use the Fourier transform \cite{fourierfull} to analyze the corresponding data which gives some evidence that it is also possible to adapt other image processing methods to do audio processing. The concept of noise is also present in both settings. Noise in an image can be something that degrades the image as a whole -- Gaussian white noise or salt-and-pepper noise would be examples for this -- or can appear locally. A local appearance of noise could be e.g.\ a black spot in the middle of someone's face in a color image. Methods to repair a defect like the non-local inpainting (see \cite{efros99}) and the NL-means algorithm \cite{buades05} are well understood in image processing.

In audio files, these types of noise can also appear. One might have to deal with Gaussian white noise as well as with degradations that appear locally like a cough. An in-depth introduction to audio processing is given by M. M\"uller in \cite{mueller}. Degradations like Gaussian white noise are investigated by A. Szlam \cite{nlmeansaudio} and shortly touched here. In this thesis, the main focus lies on isolated noisy events.

%At first glance, images and audio data seem to have less in common. But assisted by the Fourier transform\index{fourier transform}, it's possible to check whether similar patches can be found by the use of an appropriate similarity measurement. Furthermore the results can be judged by putting the patches categorized as similar at the position where a noisy patch is located (inpainting).

%%%%%%%%%%%%%%%%%% INTRODUCTION: GOALS %%%%%%%%%%%%%%%%%%
\section{Goals\index{goals}}
Since it is relatively new to transfer ideas from image processing to audio data, a good foundation should be established and evaluated whether different approaches from image processing work for audio data and how well they perform on standard problems where the runtime is not in the main focus of this thesis.

The thesis deals with noise that can be represented as an isolated but intense event, e.g.\ a cough. Note that this is a restriction to a certain group of noise.

%The noise is represented as an isolated but intense event, e.g. a cough. Noisy playbacks like produced by a record player are not investigated.

For this purpose, a theoretical background shall be established and a software shall be written to find similar patches in a piece of music. Using this framework as a basis, different methods like non-local inpainting, averaging the $n$ best results on a sample basis or non-local means shall be evaluated.

The software is realized by a C program that is built from scratch except for the code used for the fast Fourier transform (FFT)\index{fast fourier transform}\index{FFT|see{fast fourier transform}} \cite{fft} which was provided.

As a first step in the analysis, the program should get synthetically generated data as a test input where the result of the denoising can be easily verified. After having the knowledge that the program runs correctly on these signals, real-world examples can be investigated.


%%%%%%%%%%%%%%%%%% INTRODUCTION: CONTENTS %%%%%%%%%%%%%%%%%%
\section{Contents\index{structure}\index{contents}}
The structure of this thesis is as follows. In Chapter \ref{sim}, a short overview of the similarity measurement is given. The modification that is needed to use the Fourier transform\index{fourier transform} on audio signals is mentioned (section \ref{sim.prerequisites}) as well as how possible similarity measurements are computed (section \ref{sim.similaritymeasurement}).

Chapter \ref{nlalgosip} discusses shortly non-local algorithms in image processing. This builds the basis for chapter \ref{nlalgosap}, where the introduced methods are modified to fit the needs of audio processing.

Chapter \ref{experiments} investigates different experiments. By first explaining two parameter settings (section \ref{experiments.stepsizewindowwidth}), a few words are said about the memory requirements of the algorithm (\ref{experiments.stepsizewindowwidth.memrequirements}) and the runtime (\ref{experiments.stepsizewindowwidth.runtime}) under the different parameter settings. Furthermore,  different methods to repair noisy data are investigated, starting in section \ref{experiments.nlinpainting}.

Chapter \ref{final} concludes the thesis and gives ideas for possible future work.

The WAV file format -- which is the file format used in this thesis -- is described in Appendix \ref{appendix.wavfiles} where the file structure is given in \ref{appendix.wavfiles.wavefileformat} and a short overview of the meaning of this data is given in section \ref{appendix.wavfiles.meaning}. Appendix \ref{appendix.contents} gives an overview of all the files used in this thesis including their denoised versions.


%%%%%%%%%%%%%%%%%% SIMILARITY MEASUREMENT %%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\cleardoublepage\chapter{Similarity Measurement\index{similarity measurement}}\label{sim}
%%%%%%%%%%%%%%%%%% SIMILARITY MEASUREMENT: PREREQUISITES %%%%%%%%%%%%%%%%%%
\section{Prerequisites}\label{sim.prerequisites}
Before the similarity measurement can be described, some prerequisites have to be introduced. These prerequisites are easy to understand since the ideas from image processing are only slightly modified. Here it becomes evident that some parallels exist between image processing and audio processing.

\subsection{Short-Time Fourier Transform\index{short-time fourier transform}\index{STFT|see{short-time fourier transform}}}\label{sim.stft}
The short-time Fourier transform\index{short-time fourier transform} is a Fourier-related transform that deals with a problem of the Fourier transform\index{fourier transform}, namely that the latter makes no statement about the spatial  appearance -- in the case of this thesis "temporal appearance", respectively -- of the frequencies. Since a temporal analysis is needed for a piece of music, the short-time Fourier transform\index{short-time fourier transform} is used to compensate this disadvantage of the Fourier transform\index{fourier transform}.

A signal can be subdivided into different frames which usually overlap each other (see also section \ref{sim.stepsizewindowwidth}). The short-time Fourier transform\index{short-time fourier transform} takes one of these frames, multiplies it with a window function $w$ and repeats this step with the next frame until the end of the signal. This means that a window of a certain width is moved over the whole signal where each window corresponds to one frame. The "classical" Fourier transform\index{fourier transform} is used to calculate the Fourier coefficients\index{fourier coefficient} for each window.

Often used in music analysis, it can assist studio engineers by depicting the frequencies of a song with a spectrogram which has already been touched in section \ref{introduction.motivation}.

One drawback of the short-time Fourier transform\index{short-time fourier transform} is that it either has a good frequency resolution or a good time resolution, but not both. A wide window gives better frequency resolution while a narrow window gives good time resolution.

A lot of possibilities exist for the window function. One could use a box function \cite{windowfunctions} which would result in a too hard windowing at the boundaries, since the amplitude would change abruptly resulting in a broad spectrum in the frequency domain. Using a smooth window function avoids this problem.% This can be also easily understood from another viewpoint: a box function would weight the most important point at the center as much as a point far away which would not make sense, because a point far away from a point to investigate cannot be of the same importance as the investigation point itself.

\subsection{Hamming Window\index{hamming window}}\label{sim.hammingwindow}
Since a windowed Fourier transform is used for the interpretation of the data, a window function is needed that is suitable for the analysis meaning that it is smooth and that every sample in a certain time period should approximately make the same contribution. A Gaussian would fulfill this property where here the problem arises that it has to be cut at the window boundaries -- due to its infinite extend -- which would result in some kind of approximation being dependent on the point where the cutting is performed.

So one has to come up with another window which deals a bit more clever with that boundary problem. An example for such a window is the Hamming window (cf. figure \ref{sim.figure.hammingwindow}) which can be seen as a modified cosine window and is defined as follows:
$$w(n) = 0.53836 - 0.46164\cos\left(\frac{2 \pi n}{N-1}\right)$$
where $N$ is the width of  a discrete-time window function in samples (typically a power of 2) and $n$ an integer value with $0 \leq n \leq N-1$.
\begin{figure}[ht]
\centering
\includegraphics[height=0.28\textheight]{figures/hamming.eps} \\
\caption[Hamming window]{Hamming window. \textbf{Left:} Window function in the sample domain. \textbf{Right:} Frequency response. \textbf{Source:} Wikipedia \cite{windowfunctions}.}
\label{sim.figure.hammingwindow}
\end{figure}

\begin{figure}[ht]
\centering
\includegraphics[height=0.28\textheight]{figures/hann.eps} \\
\caption[Hann window]{Hann window. \textbf{Left:} Window function in the sample domain. \textbf{Right:} Frequency response. \textbf{Source:} Wikipedia \cite{windowfunctions}.}
\label{sim.figure.hannwindow}
\end{figure}

The frequency response depicts how a window deals with a sharp frequency. A narrow peak in the middle and nothing else is optimal since it would mean that only the concrete frequency one is interested in and nothing else is considered. In the case of the Hamming window the actual frequency is represented quite well. It only smears to the neighbor frequencies in a quite moderate way.

Another possibility is the Hann window (cf. figure \ref{sim.figure.hannwindow}). As one can see in the frequency response, it doesn't deal that nicely with the frequency one is interested in: the peak in the middle is a bit broader. So it seems that the Hamming window is a good choice, because it has a relatively narrow peak in the middle while not smearing the neighbor frequencies too much, meaning the neighbor frequencies do not contribute that much to the sharp one like it happens with the Hann window.
% This can be easily seen when comparing the different peaks in the frequency domain of the different windows as depicted in \cite{windowfunctions}.

\subsection{Step Size and Window Width\index{step size}\index{window width}}\label{sim.stepsizewindowwidth}
As already known, the short-time Fourier transform\index{short-time fourier transform} is the key to analyze pieces of music. Since it doesn't deal with the signal as a whole but processes only small pieces, a step size has to be specified which determines how big the steps are that are taken to go to the next input frame for the short-time Fourier transform\index{short-time fourier transform}.

But also another parameter is of importance: the window width. Since a Hamming window is applied to the data which is used for the Fourier transform\index{fourier transform}, it needs to know how much data actually to consider. The window width should be a power of 2 since this is a requirement of the fast Fourier transform\index{fast fourier transform} (FFT).

Imagine to use the values 256 for the step size and 1024 for the window width. This would mean that every 256 samples a data window of width 1024 is considered. Note that an overlap of 75\% of the signal is present for this example. An overlap is in general a good idea since it means that a lot of different frames contribute to find results that are similar to the reference frame. This becomes evident when requiring that every acoustic event is sufficiently represented in at least one window to guarantee that the event will appear in its frequency decomposition in the short-time Fourier transform.

For a WAV file at 44100 Hz, a step size of 256 would mean to go through the recording in steps of 5.8 ms where a step size of 2048 would mean to process the data in steps of 46.4 ms. The latter should be fine enough for most applications.

\subsection{Frame -- Time Conversion\index{frame -- time conversion}}\label{sim.frametimeconversion}
The conversion from a frame number to the corresponding time and vice versa is also an important need for the whole analysis since the program uses frames (cf. figure \ref{appendix.figure.samplesframespic}) to access the locations in the audio data. The conversion from a frame number to the corresponding time can be calculated using the following formula
$$\mbox{time[s]} = \frac{\mbox{frame} \times \mbox{step size}}{\mbox{sample rate [Hz]}}$$
or vice versa via the formula
$$\mbox{frame} = \frac{\mbox{time [s]} \times \mbox{sample rate [Hz]}}{\mbox{step size}}.$$

Calculating a frame number with the given formula can result in a non-integer value. Since the program only processes integer values for the frame numbers, one has to round. Rounding should be done in the following way: if an area of frames has to be specified, always a bigger area should be covered to be on the safe side. This means, considering for example frames 82.9 until 85.1, the area should be specified by the user with frames 82 until 86. If only a frame should be specified -- say to specify the reference frame --, one can round in the standard mathematical sense.

%%%%%%%%%%%%%%%%%% SIMILARITY MEASUREMENT: SIMILARITY MEASUREMENT %%%%%%%%%%%%%%%%%%
\section{Similarity Measurement\index{similarity measurement}}\label{sim.similaritymeasurement}
To find a frame that is similar to a given reference frame, several possibilities for a similarity measurement exist, e.g.\ the Euclidean distance of the power spectra of these two frames can be minimized or the scalar product of the power spectra of these two frames can be maximized. The latter is a good solution for the similarity measurement as proposed by \cite{musicsum}. The power spectrum is explained in a bit more detailed fashion in section \ref{nlalgosap.similaritymeasurement}.

Minimizing the Euclidean distance would mean to compute
$$\left\{i \; \left| \; \underset{i}{\mbox{min}} \; \left\||\hat{f}_i|^2 - |\hat{f}_{ref}|^2\right\|\right.\right\}$$
where $|\hat{f}_{ref}|^2$ denotes the power spectrum of the reference frame and $|\hat{f}_i|^2$ the power spectrum of the frame currently compared to the reference frame. %The result is an index $i$ for which the distance above is minimal.

The power spectrum can also be understood as a one-dimensional vector which carries all the coefficients of the power spectrum. This makes it possible to maximize the scalar product, i.e.\ computing
$$\left\{i \; \left| \; \underset{i}{\mbox{max}} \; \frac{\left\langle |\hat{f}_i|^2, |\hat{f}_{ref}|^2 \right\rangle}{\left\||\hat{f}_i|^2\right\| \cdot \left\||\hat{f}_{ref}|^2\right\|}\right.\right\}$$
where the scalar product is normalized by the standard vector norm of the two vectors $|\hat{f}_i|^2$ and $|\hat{f}_{ref}|^2$. This is used in the context of this thesis. %The result is an index $i$ for which the scalar product above is maximal which is used in the context of this thesis.

In both cases, the result is the index $i$ for which the result is minimal or maximal, respectively.

%%%%%%%%%%%%%%%%%% SIMILARITY MEASUREMENT: SUMMARY %%%%%%%%%%%%%%%%%%
\section{Summary}\label{sim.summary}
In this chapter, the basic ideas for the similarity measurement were presented. The short-time Fourier transform\index{short-time fourier transform} was introduced which adds a spatial/temporal component to the "classical" Fourier transform\index{fourier transform}. A window which is multiplied to a part of the signal -- where the Hamming window was introduced as a suitable windowing function -- is moved over the entire signal while performing the Fourier transform for each window to calculate its Fourier coefficients. The concepts of step size and window width were introduced and the Hamming window and the short-time Fourier transform\index{short-time fourier transform} were deepened in this context. Using something else than a hard windowing like a box function was pointed out as important since problems would arise at the boundaries due to an abrupt change of the amplitude. The prerequisites were concluded with a formula to convert a frame number to the corresponding time and vice versa.

As a similarity measurement, two approaches were discussed: the minimization of the Euclidean distance or the maximization of the scalar product, where the latter one is used in this thesis.

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN IMAGE PROCESSING %%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\cleardoublepage\chapter{Non-Local Algorithms in Image Processing}\label{nlalgosip}
%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN IMAGE PROCESSING: OVERVIEW %%%%%%%%%%%%%%%%%%
\section{Overview}\label{nlalgosip.overview}
This chapter gives a short overview over several methods used for the task of denoising in image processing. With non-local inpainting, a method is introduced which (re-)uses patches of the image to repair noisy parts. This method is followed by NL-means, a currently hot topic in image processing. This is due to the fact that it is easy to understand and very powerful in denoising structures.

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN IMAGE PROCESSING: NON-LOCAL INPAINTING %%%%%%%%%%%%%%%%%%
\section{Non-Local Inpainting}\label{nlalgosip.nlinpainting}
Inpainting is a method for repairing damaged pictures or removing unnecessary elements from pictures. The key idea of non-local inpainting is to copy patches already present in an image or blow up structures to repair missing, unnecessary or noisy data. To find possible candidates for the repairing step, a suitable similarity measurement is used. This could be the Euclidean distance as introduced in section \ref{sim.similaritymeasurement}. When dealing with non-local inpainting the search is even done on a whole neighborhood. After that, a candidate that is categorized as similar is copied to the noisy position including a specified neighborhood. The patch to be copied doesn't necessarily have to be the best match.

The idea of non-local inpainting was used for example in \cite{efros99} where image texture is synthesized.

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN IMAGE PROCESSING: NL-MEANS %%%%%%%%%%%%%%%%%%
\section{NL-Means}\label{nlalgosip.nlmeans}
Non-local means (or short NL-means) --\index{nl-means} proposed by \cite{buades05} -- is as simple as powerful in image processing. The idea is to look for similar patches in an image, average them and repair the noisy data with the calculated averaging. This is done by first finding pixels with the same grey value as the one to be repaired and compare the geometrical configuration of their neighborhood.

For the weighting function, an exponential function is used which has the following structure (in the discrete case):
$$w(i,j) = \frac{1}{Z(i)} e^{-\frac{||v(\mathcal{N}_i) - v(\mathcal{N}_j)||^2_{2,a}}{h^2}}$$
where $Z(i)$ is the normalizing constant
$$Z(i) = \sum_j e^{-\frac{||v(\mathcal{N}_i) - v(\mathcal{N}_j)||^2_{2,a}}{h^2}}$$
and the parameter $h$ acts as a degree of filtering.

This weighting function penalizes structures which have less similarity in the geometrical configuration of their neighborhood (cf. figure \ref{nlalgosip.figure.nlmeansscheme}).

As a similarity measurement, NL-means uses the minimization of the Euclidean distance.

\begin{figure}[ht]
\centering
\includegraphics[height=0.45\textheight]{figures/buades_morel_non-local_algorithm-1.eps}
\caption[Scheme of NL-means strategy.]{Scheme of NL-means strategy. Similar pixel neighborhoods give a large weight, $w(p,q_1)$ and $w(p,q_2)$, while much different neighborhoods give a small weight, $w(p,q_3)$. \textbf{Authors:} A. Buades, B. Coll and J.-M. Morel \cite{buades05}.}
\label{nlalgosip.figure.nlmeansscheme}
\end{figure}

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN AUDIO PROCESSING %%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\cleardoublepage\chapter{Non-Local Algorithms in Audio Processing}\label{nlalgosap}
%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN AUDIO PROCESSING: OVERVIEW %%%%%%%%%%%%%%%%%%
\section{Overview}\label{nlalgosap.overview}
This chapter is dedicated to the modifications done in the context of this thesis to bring the ideas introduced in chapter \ref{nlalgosip} to audio signals. It shows how the similarity measurement is refined to match the needs to compare different frames followed by an algorithm for non-local inpainting, the modification to realize an averaging on a sample basis and a NL-means like approach. In section \ref{nlalgosap.stereofiles}, it is shortly discussed how stereo files are processed. Nevertheless, this thesis concentrates on mono files.

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN AUDIO PROCESSING: SIMILARITY MEASUREMENT %%%%%%%%%%%%%%%%%%
\section{Similarity Measurement\index{similarity measurement}}\label{nlalgosap.similaritymeasurement}
In chapter \ref{sim}, all prerequisites were made to formulate the similarity measurement used in this thesis. The only thing that has to be done is computing windowed Fourier transforms by using the Hamming window in the following way:
\begin{enumerate}
	\item Take a part of the audio signal of length $N$ ($N$: window width).
	\item Apply the Hamming window.
	\item Use a standard fast Fourier transform (FFT)\index{fast fourier transform} on this window to compute the coefficients.
	\item Compute the power spectrum for each window
		$$|\hat{f}|^2 = \left(\mbox{Re}(\hat{f})\right)^2 + \left(\mbox{Im}(\hat{f})\right)^2$$
		where $\mbox{Re}(\hat{f})$ denotes the real part and $\mbox{Im}(\hat{f})$ the imaginary part of the Fourier transformed\index{fourier transform} signal $f$.
	\item Go step size many steps forward and repeat.
\end{enumerate}
Note, this would mean for the example given in \ref{sim.stepsizewindowwidth} that every 256 samples a window of width $N = 1024$ is considered. The number of frames classified as similar is at most the user input which means if the user chooses to find 10 similar frames then the number of frames proposed as similar is at most 10 but could be less.

Furthermore, a few more refinements\index{refinement} have been made to reach a higher accuracy of the proposal of similar frames where all of the following refinements are user inputs to provide the highest flexibility possible in this context.

First of all, the noisy part of the data is excluded which is obvious since noise cannot be trusted. This is especially important if one has a larger degradation of the data because the accuracy is higher then. Of course, the user can also decide to not exclude anything, but note that in the case of this thesis, noise is an isolated but intense event. The algorithm doesn't perform any automatic noise detection, the noisy locations are known in advance.

Secondly not only the reference frame itself but a neighborhood is considered, so a non-local approach is introduced as also done in \ref{nlalgosip.nlinpainting}. This is important since a certain tone or musical event can appear in a lot of different contexts, for example the tone A can be part of G -- A -- B as well as C -- F -- A. Not considering the context could result in an unnatural listening experience when replacing one "same" tone by another since it could sound different due to its surrounding (cf. figure \ref{sim.figures.3notes}). In addition to that, one has to make sure that the algorithm doesn't find similar frames that are very close to the reference frame when performing the search on a neighborhood. To overcome this problem, a minimal distance for the search is introduced. Let's denote this minimal distance with $d$ and the reference frame with $ref$. Then only the frames that do not lie in the interval $[ref-d, ref+d]$ are considered for the similarity search.

A third refinement is to require a certain distance between the results in the similarity list since it is expected that frames cluster around similar matches. This distance is currently fixed to 10 which gives good results.

\begin{figure}[ht]
\centering
\includegraphics[height=0.09\textheight]{figures/3notes-example.eps}
\caption[Example for two different occurrences of the tone A.]{Example for two different occurrences of the tone A. \textbf{Left:} G -- A -- B (precisely: g' -- a' -- b'). \textbf{Right:} C -- F -- A (precisely: c'' -- f' -- a').}
\label{sim.figures.3notes}
\end{figure}

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN AUDIO PROCESSING: NON-LOCAL INPAINTING %%%%%%%%%%%%%%%%%%
\section{Non-Local Inpainting}\label{nlalgosap.nlinpainting}
Non-local inpainting for audio signals is inspired by the ideas of \cite{efros99}. After having found frames that are similar to the reference frame, the program replaces the neighborhood -- specified by an user input -- around the reference frame including the reference frame itself by the same neighborhood around the selected similar frame, also including this one. No mirroring at the boundaries is used. Assuming mirroring boundary conditions\footnote{for PDE-based methods these are Neumann boundary conditions} for an image processing problem is fine, but in the case of audio signals, this is not a good choice. Instead, zero-padding is used here, because when mirroring at the boundaries, the music would be analyzed in a "reverse order" when passing the boundary.

Suppose, the user specified a neighborhood of $k$ frames. Then in total $2k+1$ frames are replaced: $k$ frames left to the reference frame, the reference frame itself and $k$ frames right to the reference frame. To do so, the start and end point of the reference frame and the similar frame in the WAV data are calculated via the formulae
\begin{eqnarray*}
	start\_ref & = & (ref - n) \times step\: size \\
	end\_ref & = & (ref + n) \times step\: size \\
	start\_frame & = & (frame - n) \times step\: size \\
	end\_frame & = & (frame + n) \times step\: size
\end{eqnarray*}
where $ref$ is the reference frame, $frame$ the similar frame and $n$ the neighborhood.
An example shows how this works. Imagine to have a $step\: size = 256$, the reference frame is at 14298 and the neighborhood to include should be 515. Then the algorithm replaces the slots $start\_ref$ until $end\_ref$ in the original WAV data:
\begin{eqnarray*}
	start\_ref & = & (14298 - 515) \times 256 \\
	& = & 3528448 \\
	end\_ref & = & (14298 + 515) \times 256 \\
	& = & 3792128
\end{eqnarray*}

This also holds for the following approaches in \ref{nlalgosap.avgsample}, \ref{nlalgosap.nlmeans} and \ref{nlalgosap.szlam} since here only the data is modified and not the method how to repair noisy parts.

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN AUDIO PROCESSING: AVERAGING ON SAMPLE BASIS %%%%%%%%%%%%%%%%%%
\section{Averaging on a Sample Basis}\label{nlalgosap.avgsample}
With non-local inpainting as explained in \ref{nlalgosap.nlinpainting}, only a selected frame is filled in. Now, not only a selected frame is used, but all the frames found as similar are averaged in the sense of the arithmetic mean where the result of this is copied at the position of the noisy signal, also including a certain neighborhood.

This approach can be seen as a weighted averaging with a fixed weighting function
$$w = \frac{1}{frames}$$
where $frames$ is the number of frames classified as similar.

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN AUDIO PROCESSING: NL-MEANS %%%%%%%%%%%%%%%%%%
\section{NL-Means}\label{nlalgosap.nlmeans}
In principle, NL-means is a further development of averaging on a sample basis introduced in section \ref{nlalgosap.avgsample}. Instead of using a fixed weighting function, an adaptive weighting with an exponential function is used here.

Since the original NL-means algorithm uses the minimization of the Euclidean distance where the maximization of the scalar product is used for this thesis, the weighting function has to be slightly changed.
%Note, that another change to the original NL-means setting is that the noise appears isolated and intense as already mentioned in \ref{nlalgosap.similaritymeasurement}.
The program gives a list of similar frames with their corresponding scalar products. These are used for the weighting function in the following way:
$$w(cur) = e^{-\lambda \cdot \frac{best - cur}{best}}$$
where $cur$ is the scalar product as stated in \ref{sim.similaritymeasurement} of the currently observed frame, $best$ the scalar product of the best match (also in the sense of \ref{sim.similaritymeasurement}) and $\lambda$ a threshold parameter.

The threshold parameter $\lambda$ controls how fast the exponential function decreases. This is an important parameter since it determines in which way the similar frames are considered for the NL-means approach. Choosing a small value for $\lambda$ means to consider more frames, choosing it large means to consider less frames (since the exponential function decreases faster for large $\lambda$). Another aspect that should be considered is the choice of the parameters step size and window width (cf. \ref{sim.stepsizewindowwidth}). Depending on them it could happen that $\lambda$ has to be slightly changed.

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN AUDIO PROCESSING: NL-MEANS ON CONTINUOUS NOISY SIGNALS %%%%%%%%%%%%%%%%%%
\section{NL-Means on Continuous Noisy Signals}\label{nlalgosap.szlam}
At the end of the development of this thesis, a preprint by Arthur Szlam appeared \cite{nlmeansaudio} which is also concerned with using the NL-means algorithm on audio data. In his work, he considers the whole signal to contain moderate Gaussian white noise where this thesis deals with isolated noisy events. Nevertheless, it is possible to adapt to this setting since both approaches are similar.

The only modification is to perform the similarity search for each frame using a small neighborhood without excluding frames and iteratively go over the whole signal frame by frame. For each similarity list, the NL-means approach developed during this thesis is applied for the denoising step where a special parameter setting is employed to do so. This parameter setting is changed in two parameters: first of all, the algorithm should not consider any neighborhood for the repairing, meaning to exchange only the currently observed frame, and secondly not excluding any frames when doing the NL-means averaging. The latter is due to the fact that excluding (noisy) frames only makes sense if the noise is an isolated event in the audio file which is not the case here.

In all other parameters the algorithm behaves as explained in section \ref{nlalgosap.nlmeans}.

%%%%%%%%%%%%%%%%%% NON-LOCAL ALGORITHMS IN AUDIO PROCESSING: STEREO FILES %%%%%%%%%%%%%%%%%%
\section{Stereo Files\index{stereo files}}\label{nlalgosap.stereofiles}
In a stereo file, both channels cannot be treated separately for obvious reasons. To simplify this problem, the file is processed internally as a mono file. This is done by averaging the two channels in the sense of the arithmetic mean. Afterwards, when writing back the file, the data is doubled to both channels so that a (pseudo) stereo file comes out again.

%%%%%%%%%%%%%%%%%% EXPERIMENTS %%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\cleardoublepage\chapter{Experiments\index{experiments}}\label{experiments}
%%%%%%%%%%%%%%%%%% EXPERIMENTS: OVERVIEW %%%%%%%%%%%%%%%%%%
\section{Overview}\label{experiments.overview}
This chapter summarizes the experiments done during the development of this thesis. It delivers some insights in how the memory requirements and the runtime behavior evolve under two different configurations and shows methods that are candidates to repair defects in music. %The latter is of big importance, since it fulfills two goals of the thesis, namely whether image processing methods work and which ones actually do.

Here is a list of files that are used for the experiments where their corresponding degradation with an approximate time location in the audio file is stated in brackets.
\begin{itemize}
	\item \fname{cyftlt-mono-short\_sine.wav} (sine tone, time: 1:53.14 -- 1:53.23),
%	\item \fname{cyftlt-mono-middle\_sine1.wav} (sine tone, time: 1:52.99 -- 1:54.00),
%	\item \fname{cyftlt-mono-middle\_sine2.wav} (sine tone, time: 1:23.98 -- 1:24.96),
	\item \fname{cyftlt-mono-long\_sine.wav} (sine tone, time: 1:20.01 -- 1:25.00),
	\item \fname{cyftlt-long\_sine.wav} (sine tone, time: 1:20.01-- 1:25.00), \\
		\textit{(corresponding stereo file to \fname{cyftlt-mono-long\_sine.wav})}
	\item \fname{piano1-mono-white.wav} (white noise, time: 0:02.01 -- 0:03.02),
%	\item \fname{piano2-mono-sine.wav} (sine tone, time: 0:01.98 -- 0:03.09),
	\item \fname{piano3-mono-sine.wav} (sine tone, time: 0:03.75 -- 0:04.70),
	\item \fname{piano3-mono-white.wav} (white noise, time: 0:04.40 -- 0:04.45)
%	\item \fname{t-style-mono-white\_sine.wav} (white noise, time: 0:09.95 -- 0:10.41, and sine tone, time:  0:59.04 -- 0:59.63).
\end{itemize}

The files listed above were all synthetically created by using the MIDI sequencer software Propellerheads Reason 4 \cite{propreason} and edited afterwards with Audacity \cite{audacity} to insert the noise.

Also, two audio files from the CD "Elton John: A Piano Tribute" by Boko Suzuki are used as real-world examples where they are also edited afterwards with Audacity. These are:
\begin{itemize}
	\item \fname{candle\_in\_the\_wind-mono-silence.wav} (complete silence, time: 0:46.50 -- 0:47.00)
	\item \fname{your\_song-mono-white.wav} (white noise, time: 1:31.80 -- 1:32.60)
\end{itemize}

The type of degradation doesn't matter if the noisy part is left out which is possible as already mentioned in \ref{nlalgosap.similaritymeasurement}. In current experiments, only piano music was used.% except for the file \fname{t-style-mono-white\_sine.wav} which contains mostly synthetic drums with some brass insertions.

%All the experiments are also done with the only stereo file \fname{cyftlt-long\_sine.wav} as input file. Differences in the results in comparison to the case that the mono file (\fname{cyftlt-mono-long\_sine.wav}) was used as input might be due to the averaging for stereo files as described in \ref{nlalgosap.stereofiles}.

%%%%%%%%%%%%%%%%%% EXPERIMENTS: PARAMETER SELECTION %%%%%%%%%%%%%%%%%%
\section{Parameter Selection for Step Size and Window Width\index{parameter selection}}\label{experiments.stepsizewindowwidth}
As already mentioned in \ref{sim.stepsizewindowwidth}, the wave file is processed by going through the data in certain steps while looking at a window of a certain width for each step. Two different configurations have been explored. In the first configuration, the step size was set to 256 and the window width to 1024, resulting in an overlap of 75\%. It is referred to this configuration by using \config{1}. In the second configuration, the step size was set to 2048 and the window width to 4096, resulting in an overlap of 50\%. It is referred to this configuration by using \config{2}.

%Unfortunately not all the files could be reconstructed with the first parameter setting during the development of the thesis. The file \fname{t-style-mono-white\_sine.wav} has white noise in the first half and a degradation by a sine tone in the second half. With the first configuration only the white noise could be removed.
%
%Using the second configuration, the white noise on the one hand side and the sine tone on the other hand side in \fname{t-style-mono-white\_sine.wav} could be removed but not both.

\subsection{Memory Requirements\index{memory requirements}}\label{experiments.stepsizewindowwidth.memrequirements}
The first configuration with a step size of 256 and a window width of 1024 works quite well. Unfortunately it needs for a 21 MB wave file in mono\footnote{\fname{\footnotesize cyftlt-mono-long\_sine.wav} was used in this example.} -- 4:04 minutes of piano music -- about 300 MB of main memory which is pretty huge in comparison to the effective file size.

The second configuration with a step size of 2048 and a window width of 4096 works as good as the first one, but the memory requirements drop for the same file as above from about 300 MB to about 165 MB.

%At the beginning of the thesis, the step size was set to 50 and the window width to 1024 resulting in a memory requirement of more than 3 GB for the same 21 MB file as above.

%These relatively small values in comparison to the 3 GB are possible because
With a straightforward implementation without doing any optimization, instead of the aforementioned 300 MB even about 530 MB would be needed, but two tricks are used to save memory. The first trick is not to use a small array for the real part, a small array for the imaginary part and a small array for the spectrum of the Fourier transform for each window but to store all the data in a large array for all the real parts, a large array for all the imaginary parts and a large array for all the spectra. Using pointers helps to state which values belong to which window. This means that for each window three pointers are used in total: one for the real part, one for the imaginary part and one for the spectrum. All the data is arranged in order which means that all the values between two pointers -- including the first one of the two -- belong to the same window. It is expected that memory is saved in this way since the compiler always "rounds" to the next power of 2 when allocating memory. Allocating three arrays containing 513 slots of floats each results in allocating three times 1024 slots of floats. Allocating one big array would result in 2048 slots of floats\footnote{$3 \times 513 = 1539 \leadsto 2048$} instead of 3072 slots. This becomes even more important if this allocation step is done more than 1,000 or 10,000 times.

The second trick is based on the fact that the Fourier transform\index{fourier transform} is symmetric. The symmetry makes it possible to throw away half of the data and recompute it later when needed. For this thesis, the recomputation will not be necessary.

The resulting memory requirements are in fact expected. To verify this, an exemplary calculation is made for \config{1} where \fname{cyftlt-mono-long\_sine.wav} is used as input file. The effective data size of this file is 21,520,800 bytes and it has 16 bits per sample.
\begin{eqnarray*}
	datasize & = & \left\{ \begin{array}{ll} 21520800 & \mbox{, bits per sample = 8} \\ 
21520800 / 2 & \mbox{, bits per sample = 16} \\ 21520800 / 3 & \mbox{, bits per sample = 24}\end{array}\right. \\
	arraysize & = & datasize / step\: size \\
	& = & 10760400 / 256 \\
	& = & 42032.8125 \approx 42033 \\
	width & = & 1024 \\
	ft\_size & = & (width / 2) + 1 = 513
\end{eqnarray*}
Now it is possible to calculate the whole memory requirement for this file which is given in table \ref{experiments.table.examplecalculation}.
\begin{table}[ht]
\centering
\topcaption{Example calculation for the memory requirement of \fname{cyftlt-mono-long\_sine.wav}.}
\begin{tabular}{l|lcr}
Description & Size & & [bytes]  \\ \hline
WAV data array & $datasize \times \mbox{sizeof(float)}$ & & 43041600 \\
real part of FT data & $arraysize \times ft\_size \times \mbox{sizeof(float)}$ & + & 86251716 \\
imaginary part of FT data & $arraysize \times ft\_size \times \mbox{sizeof(float)}$ & + & 86251716 \\
spectra of FT data & $arraysize \times ft\_size \times \mbox{sizeof(float)}$ & + & 86251716 \\
array with similar frames & $how\_many\_similar\_frames \times \mbox{sizeof(int)}$ & + & 40 \\
array with distances & $how\_many\_similar\_frames \times \mbox{sizeof(float)}$ & + & 40 \\ \hline \hline
& & = & 301796828 \\
& & $\approx$ & 287.82 MB
\end{tabular}
\label{experiments.table.examplecalculation}
\end{table}
Furthermore, the operating system needs some extra space for the memory management which increases the calculated requirement (287.82 MB) to a real memory requirement of 288.66 MB. To conclude this example it has to be mentioned that a few helper arrays are created for computational purposes and destroyed immediately after the computation. These are in the range of about 80 MB\footnote{effective data size $\times$ sizeof(float) = 21520800 bytes $\times$ 4 =  86083200 bytes $\approx$ 82 MB} which increases the whole main memory requirement to a worst case maximum of 400 MB (again including space used by the operating system for the memory management) during program run for this file.

\subsection{Runtime\index{runtime}}\label{experiments.stepsizewindowwidth.runtime}
The runtime of the program clearly depends on several factors. The most important one is the dependency on the problem itself, i.e.\ the size of the file being processed, the size of the neighborhood, the extent of the noise, whether a certain part is excluded and so on. The measurements here should give a flavor of how fast the program approximately is. All files have been processed on an Apple MacBook Pro with a 2.2 GHz Intel Core 2 Duo and 2 GB of RAM.

Table \ref{experiments.table.runtimecomparison1} corresponds to the wave file already mentioned above.
Please note that the approximate location in the piece of music is stated in brackets in the format (mm:ss). Table \ref{experiments.table.runtimecomparison2} shows the same scenario for a 700 KB wave file.
\begin{table}[ht]
\centering
\topcaption[Runtime comparison for \fname{cyftlt-mono-long\_sine.wav}]{Processing of \fname{cyftlt-mono-long\_sine.wav}, duration: 4:04 minutes (size 21 MB).}
\begin{tabular}{l|l|l}
	\textit{step size / window width} & 256 / 1024 & 2048 / 4096 \\ \hline \hline
	Reference frame & 14298 (1:23) & 1787 (1:23) \\ \hline
	Minimal search distance & 10 & 2 \\ \hline
	Search neighborhood & 515 ($\approx$ 3 sec.) & 65 ($\approx$ 3 sec.) \\ \hline
	Frames to exclude & 13781 -- 14643 (1:20 -- 1:25) & 1723 -- 1830 (1:20 -- 1:25) \\ \hline
	Replacement neighborhood & 515 & 65 \\ \hline
	Runtime & $\approx$ 28 seconds & $\approx$ 7 seconds
\end{tabular}
\label{experiments.table.runtimecomparison1}
\end{table}

\begin{table}[ht]
\centering
\topcaption[Runtime comparison for \fname{piano3-mono-sine.wav}]{Processing of \fname{piano3-mono-sine.wav}, duration: 0:08 minutes (size 700 KB).}
\begin{tabular}{l|l|l}
	\textit{step size / window width} & 256 / 1024 & 2048 / 4096 \\ \hline \hline
	Reference frame & 861 (0:05) & 107 (0:05) \\ \hline
	Minimal search distance & 10 & 2 \\ \hline
	Search neighborhood & 525 ($\approx$ 3 sec.) & 65 ($\approx$ 3 sec.) \\ \hline
	Frames to exclude & 646 -- 810 (0:03.75 -- 0:04.7) & 81 -- 101 (0:03.76 -- 0:04.7) \\ \hline
	Replacement neighborhood & 175 & 22 \\ \hline
	Runtime & $\approx$ 2 seconds & $\approx$ 0.5 seconds
\end{tabular}
\label{experiments.table.runtimecomparison2}
\end{table}

Furthermore the program should give the 10 best results and the best result was chosen for the replacement using non-local inpainting. Of course, only the computation time is measured.

Note, that the coarser scale is about four times faster while giving the same listening experience in the result.

%%%%%%%%%%%%%%%%%% EXPERIMENTS: NON-LOCAL INPAINTING %%%%%%%%%%%%%%%%%%
\section{Non-Local Inpainting\index{experiments!non-local inpainting}}\label{experiments.nlinpainting}
If the similarity measurement provides a good result, non-local inpainting performs well from a musical point of view. In some cases, non-local inpainting can even reconstruct the noisy part such that one cannot tell a big difference to the original, non-noisy sound file except for a small click at the cutting points that could be avoided by using a cross-fade which can be understood as a weighting function. A cross-fade is the application of two functions to a signal where one function linearly goes from 1 to 0 (fade-out) and the other linearly from 0 to 1 (fade-in).
%The center of the cross-fade -- i.e.\ the point where both function values are 0.5 -- doesn't have to be at the cutting point.
Having this, a smooth transition between two signal parts is created whose result makes the discontinuity at a cutting point in most cases imperceptible.

Figures \ref{sim.figure.cyftlt-mono-simple} and \ref{sim.figure.piano3-mono-simple} show exemplarily how a noisy signal looks like and how it might look after performing non-local inpainting\index{experiments!non-local inpainting}.

As already explained in section \ref{nlalgosap.nlinpainting}, a similar patch is searched and inserted using a specified neighborhood that is also copied.

In the experiments it turned out that the inpainting approach has a disadvantage in some settings which is depicted for \fname{piano3-mono.wav} in figure \ref{sim.figure.piano3-mono-simple}: it either cannot completely repair the defect or starts repairing at the beginning of the noise, resulting in a shift of the inserted data to the left.
%\fname{piano3-mono.wav} contains actually two chords (A minor and E minor) where the first and the third chord are A minor and the other two E minor. The sound file \fname{piano3-mono-sine.wav} is noisy in such a way that the degradation starts shortly before the third chord. The program finds a similar frame which is the first chord of this short sequence. The problem is that it cannot fill in information at the beginning of the noise (before the third chord), because there is obviously no data before the first chord (before time location 0 seconds). This means that the algorithm either lets a part of the noise untouched or cuts a part of the noise out -- resulting in a shift of the whole frame a little bit to the left --, depending on the parameter setting, especially on the choice of the reference frame. This shift only happens if some data which would be needed for the inpainting is missing. In some examples, moving the reference frame, around which the neighborhood for the search and the replacement is established, to the left or the right can be a remedy.
Figure \ref{sim.figure.piano3-mono-simple-schematic} shows a schematic drawing of how the non-local inpainting approach works if a part of the noise is untouched. As one can see, some information cannot be filled in due to the fact that the patch used for the inpainting step overlaps to a region where no data is present. Figure \ref{sim.figure.piano3-mono-simple-schematic-cutout} shows how the non-local inpainting works if the repairing starts at the beginning of the noise. The type of repairing depends on the selection of the reference frame and the neighborhood used for the replacement.

Considering \fname{cyftlt-mono-long\_sine.wav}, no problems in repairing the defect appeared. Here it is important to choose a neighborhood which is on the one hand large enough to find a frame that is similar and on the other hand large enough to repair the whole defect. Note, it must always be satisfied that the replacement neighborhood is not greater than the search neighborhood. The parameters that worked best in the experiments are stated in table \ref{experiments.table.runtimecomparison1}. These parameters also work for the file \fname{cyftlt-long\_sine.wav} which is in stereo.

\begin{figure}[ht]
\centering
\includegraphics[height=0.234\textheight]{figures/cyftlt-mono.eps} \;
\includegraphics[height=0.234\textheight]{figures/cyftlt-mono-test4.eps} \\[0.5cm]
\includegraphics[height=0.234\textheight]{figures/cyftlt-mono-test4-corrected-simple-256.eps} \;
\includegraphics[height=0.234\textheight]{figures/cyftlt-mono-test4-corrected-simple-2048.eps}
\caption[\fname{cyftlt-mono-long\_sine.wav} corrected with non-local inpainting.]{Correction with non-local inpainting for \fname{cyftlt-mono.wav} (4:04 minutes). \textbf{Top left:} Original file. \textbf{Top right:} Original degraded with a sine tone of 440 Hz (\fname{cyftlt-mono-long\_sine.wav}). \textbf{Bottom left:} Corrected version with a step size of 256 and a window width of 1024. \textbf{Bottom right:} Corrected version with a step size of 2048 and a window width of 4096. \textbf{Visualization:} using RavenLite 1.0 \cite{ravenlite}.}
\label{sim.figure.cyftlt-mono-simple}
\end{figure}

\begin{figure}[ht]
\centering
\begin{pspicture}(0,0)(12,9)
\rput(1.0,6.5){\psframe[fillstyle=crosshatch](0.5,0.5)(1.0,1.5)}
\rput(1.0,6.5){\psframe[fillstyle=solid,fillcolor=lightorange](1.0,0.5)(3.0,1.5)}
\rput(2.0,6.5){\psframe[fillstyle=solid,fillcolor=lightgreen](2.0,0.5)(4.0,1.5)}
\rput(3.0,6.5){\psframe[fillstyle=solid,fillcolor=lightorange](3.0,0.5)(5.0,1.5)}
\rput(4.0,6.5){\psframe[fillstyle=solid,fillcolor=lightgreen](4.0,0.5)(6.0,1.5)}
\rput(4.0,6.5){\psframe[fillstyle=crosshatch](6.0,0.5)(6.5,1.5)}
\rput(3.0,7.5){\textsf{1}}
\rput(5.0,7.5){\textsf{2}}
\rput(7.0,7.5){\textsf{3}}
\rput(9.0,7.5){\textsf{4}}
\rput(3.0,5.5){\psframe[fillstyle=solid,fillcolor=red](2.5,0.5)(4.1,1.5)}
\rput(1.0,5.5){\psframe[fillstyle=solid,fillcolor=nicegreen](0.5,0.5)(2.1,1.5)}
\psline[linestyle=dashed](2.0,6.0)(2.0,7.0)
\psline[arrowsize=10pt]{->}(6.0,5.5)(6.0,3.5)
\rput(1.0,1.5){\psframe[fillstyle=crosshatch](0.5,0.5)(1.0,1.5)}
\rput(1.0,1.5){\psframe[fillstyle=solid,fillcolor=lightorange](1.0,0.5)(3.0,1.5)}
\rput(2.0,1.5){\psframe[fillstyle=solid,fillcolor=lightgreen](2.0,0.5)(4.0,1.5)}
\rput(3.0,1.5){\psframe[fillstyle=solid,fillcolor=lightorange](3.0,0.5)(5.0,1.5)}
\rput(4.0,1.5){\psframe[fillstyle=solid,fillcolor=lightgreen](4.0,0.5)(6.0,1.5)}
\rput(4.0,1.5){\psframe[fillstyle=crosshatch](6.0,0.5)(6.5,1.5)}
\rput(3.0,2.5){\textsf{1}}
\rput(5.0,2.5){\textsf{2}}
\rput(6.6,2.5){\textsf{1}}
\psline(7.1,2.0)(7.1,3.0)
\rput(7.6,2.5){\textsf{3}}
\rput(9.0,2.5){\textsf{4}}
\rput(3.0,0.5){\psframe[fillstyle=solid,fillcolor=red](2.5,0.5)(3.0,1.5)}
\rput(3.0,0.5){\psframe[fillstyle=solid,fillcolor=nicegreen](3.0,0.5)(4.1,1.5)}
\end{pspicture}
\caption[Schematic of the non-local inpainting when not repairing the whole defect.]{Schematic of how the non-local inpainting approach works in the case of \fname{piano3-mono-sine.wav}. The crossed areas denote the beginning and the end of the music file. The chords are denoted by numbers, where same colors indicate same chords. The red box denotes the noise where the green one denotes the part of music that could be used for the inpainting step. \textbf{Top:} Noisy music file with marked candidate for inpainting. One can see that some information cannot be filled in due to the fact that the green box overlaps to a region where no data is present. \textbf{Bottom:} Same file after non-local inpainting when not repairing the whole defect.}
\label{sim.figure.piano3-mono-simple-schematic}
\end{figure}

\begin{figure}[ht]
\centering
\begin{pspicture}(0,0)(12,9)
\rput(1.0,6.5){\psframe[fillstyle=crosshatch](0.5,0.5)(1.0,1.5)}
\rput(1.0,6.5){\psframe[fillstyle=solid,fillcolor=lightorange](1.0,0.5)(3.0,1.5)}
\rput(2.0,6.5){\psframe[fillstyle=solid,fillcolor=lightgreen](2.0,0.5)(4.0,1.5)}
\rput(3.0,6.5){\psframe[fillstyle=solid,fillcolor=lightorange](3.0,0.5)(5.0,1.5)}
\rput(4.0,6.5){\psframe[fillstyle=solid,fillcolor=lightgreen](4.0,0.5)(6.0,1.5)}
\rput(4.0,6.5){\psframe[fillstyle=crosshatch](6.0,0.5)(6.5,1.5)}
\rput(3.0,7.5){\textsf{1}}
\rput(5.0,7.5){\textsf{2}}
\rput(7.0,7.5){\textsf{3}}
\rput(9.0,7.5){\textsf{4}}
\rput(3.0,5.5){\psframe[fillstyle=solid,fillcolor=red](2.5,0.5)(4.1,1.5)}
\rput(1.0,5.5){\psframe[fillstyle=solid,fillcolor=nicegreen](0.5,0.5)(3.5,1.5)}
\psline[linestyle=dashed](2.0,6.0)(2.0,7.0)
\psline[arrowsize=10pt]{->}(6.0,5.5)(6.0,3.5)
\rput(1.0,1.5){\psframe[fillstyle=crosshatch](0.5,0.5)(1.0,1.5)}
\rput(1.0,1.5){\psframe[fillstyle=solid,fillcolor=lightorange](1.0,0.5)(3.0,1.5)}
\rput(2.0,1.5){\psframe[fillstyle=solid,fillcolor=lightgreen](2.0,0.5)(4.0,1.5)}
\rput(3.0,1.5){\psframe[fillstyle=solid,fillcolor=lightorange](2.5,0.5)(4.5,1.5)}
\rput(4.0,1.5){\psframe[fillstyle=solid,fillcolor=lightgreen](3.5,0.5)(6.0,1.5)}
\rput(4.0,1.5){\psframe[fillstyle=crosshatch](6.0,0.5)(6.5,1.5)}
\rput(3.0,2.5){\textsf{1}}
\rput(4.75,2.5){\textsf{2}}
\rput(6.5,2.5){\textsf{1}}
\rput(7.75,2.5){\textsf{2}}
\psline(8.0,2.0)(8.0,3.0)
\rput(9.0,2.5){\textsf{4}}
\rput(3.0,0.5){\psframe[fillstyle=solid,fillcolor=nicegreen](2.5,0.5)(5.0,1.5)}
\end{pspicture}
\caption[Schematic of the non-local inpainting when trying to repair the whole defect.]{Schematic of how the non-local inpainting approach works in the case of \fname{piano3-mono-sine.wav}. The crossed areas denote the beginning and the end of the music file. The chords are denoted by numbers, where same colors indicate same chords. The red box denotes the noise where the green one denotes the part of music that could be used for the inpainting step. \textbf{Top:} Noisy music file with marked candidate for inpainting. One can see that some information cannot be filled in due to the fact that the green box overlaps to a region where no data is present. \textbf{Bottom:} Same file after non-local inpainting when starting to repair the defect at the beginning of the noise.}
\label{sim.figure.piano3-mono-simple-schematic-cutout}
\end{figure}

\begin{figure}[!ht]
\centering
\includegraphics[height=0.234\textheight]{figures/piano3-mono.eps} \;
\includegraphics[height=0.234\textheight]{figures/piano3-mono-test.eps} \\[0.5cm]
\includegraphics[height=0.234\textheight]{figures/piano3-mono-test-corrected-simple-256.eps} \;
\includegraphics[height=0.234\textheight]{figures/piano3-mono-test-corrected-simple-2048.eps} \\[0.5cm]
\includegraphics[height=0.234\textheight]{figures/piano3-mono-test-corrected-simple-256-2.eps} \;
\includegraphics[height=0.234\textheight]{figures/piano3-mono-test-corrected-simple-2048-2.eps}
\caption[\fname{piano3-mono-sine.wav} corrected with non-local inpainting.]{Correction with non-local inpainting for \fname{piano3-mono.wav} (0:08 minutes). \textbf{Top left:} Original file. \textbf{Top right:} Original degraded with a sine tone of 330 Hz (\fname{piano3-mono-sine.wav}). \textbf{Middle left:} Corrected version with a step size of 256, a window width of 1024 and a replacement neighborhood of 175. \textbf{Middle right:} Corrected version with a step size of 2048, a window width of 4096 and a replacement neighborhood of 22. \textbf{Bottom left:} Corrected version with a step size of 256, a window width of 1024 and a replacement neighborhood of 263. \textbf{Bottom right:} Corrected version with a step size of 2048, a window width of 4096 and a replacement neighborhood of 33.}
\label{sim.figure.piano3-mono-simple}
\end{figure}

Both, \fname{cyftlt-mono-long\_sine.wav} and \fname{piano3-mono-sine.wav}, are somehow extreme examples. In the case of \fname{cyftlt-mono-long\_sine.wav} about five seconds of data is completely destroyed and should be reconstructed which is a pretty tough task. In the case of \fname{piano3-mono-sine.wav} the difficulty clearly lies in the fact that the best matching patch for the defect is exactly at the beginning of the file. From this viewpoint, non-local inpainting works great with the right parameter setting. Unfortunately, finding the right parameter setting requires a lot of "tweaking the knobs" for some files at the moment since the program currently asks a lot of parameters that give various possibilities to experiment. This has also been encountered with the file \fname{piano1-mono-white.wav}.

In the following, the performance of the algorithm on more realistic problems is investigated. These experiments stand in contrast to the introduction of distortions of artificial character, like long defects. \fname{piano3-mono-white.wav} is an example where only a short distortion by white noise of size 0.05 seconds is present. To repair this file is not difficult, but in \config{1} some clicking noise of low intensity is introduced at the location where the inpainting is performed. In \config{2}, one can also hear clicking noise, but it is very short in its extent and even lower in its intensity in comparison to \config{1}.
%, but in the case of this file one has to be careful when choosing the parameters: to search for similar frames can result in a best similar frame (frame 749 in \config{1}) very close to the defect (frames 758 -- 767 in \config{1}). In this case, inserting a too large neighborhood gives the effect that the same patch is inserted repeatedly to repair the defect. This is expected since the program ignores the noisy frames which means that some data is left out which would be needed for the repairing step. % A concrete example clarifies this easily. If the reference frame is number 749, the frames 758 until 767 are excluded and a replacement neighborhood of 30 is chosen, the algorithm tries to repair the defect using data from frames 719 until 779 where the frames 758 until 767 are ignored. This obviously results in a lack of data. In this case it helps to take frame 760 as reference frame and to insert using only a neighborhood of 9.

%For \config{2}, such a behavior could not be reproduced. Tests were also performed with the file \fname{cyftlt-mono-short\_sine.wav} while giving comparable results.
%, but the task of correction becomes difficult for files with only short distortions. In case of the file \fname{piano3-mono-white.wav}, frame 97 is chosen as reference frame, the noisy part is from frame 95 until 96. It was encountered that using a neighborhood of 2 frames is not enough to repair the defect where a neighborhood of 3 seems to work.

%Such a behavior is easier to produce with files that have smaller defects. A file with a larger defect is not that sensitive to the parameters since such a defect is usually in the range of more than just a few frames, so performing non-local inpainting using a neighborhood that differs by one frame is not that problematic as it is for files with a smaller defect.

When having short noisy parts it is also worth to investigate the situation where no frames are excluded. In most cases, the results are comparable in quality to the ones created with an exclusion of the noisy part. Among others, not excluding anything was tested with the two files \fname{candle\_in\_the\_wind-mono-silence.wav} and \fname{your\_song-mono-white.wav}. For the file \fname{candle\_in\_the\_wind-mono-silence.wav}, the results are better when excluding the noisy frames where for the test file \fname{your\_song-mono-white.wav} it is interestingly the other way round. In the latter case, the version where the noise is not excluded sounds more "natural". This is due to the fact that the noise is in the middle of a part that only contains a piano chord which decreases in volume. The algorithm finds -- if no frames are excluded -- similar frames located around the noisy part, so low structures are reproduced. Nevertheless, this repairing is accompanied by low clicking noise.

%%%%%%%%%%%%%%%%%% EXPERIMENTS: AVG ON SAMPLE BASIS %%%%%%%%%%%%%%%%%%
\section{Averaging on a Sample Basis\index{averaging}\index{sample}}\label{experiments.avgonsamples}
Since only different data is used for the repairing step in this approach, it also suffers from the shifting problem that was exemplarily described for \fname{piano3-mono-sine.wav} in section \ref{experiments.nlinpainting}.

When performing averaging on a sample basis with the same weight for every sample point, the number of the data to be averaged plays an important role. Experiments have shown that the algorithm is relatively good in reconstructing something harmonically close to the original while on the other hand providing an unnatural listening experience. For the test file \fname{cyftlt-mono-long\_sine.wav} and the corresponding stereo version \fname{cyftlt-long\_sine.wav} the task of averaging similar frames results in something that can be called chaotic when expecting something musical: different pieces of music overlap that do not really fit together. The chaotic behavior can sometimes be compared to having a few musicians playing different parts of a piece of music at the same time. %Here the problem is that the other frames have a distance to the reference frame which is large enough to stand at the fourth or higher position in the similarity list, but these frames are far away so that they cannot be possible candidates for the noisy frame.
For the case that three or less similar frames are considered, the result is repairing the noisy part from a musical viewpoint in a better way whereas the problem exists that some frames are a little bit shifted. The listening experience can be compared to a chorus effect\footnote{chorus: the perception of similar sounds from multiple sources as a single, richer sound.} in the mono case for \config{1} and to the impression that a few melodies run in parallel for \config{2} (also in mono) as well as for \config{1} in the stereo case. In \config{2}, the repairing of the stereo file gives a quite "normal" playback.

In \config{1}, the files \fname{candle\_in\_the\_wind-mono-silence.wav} and \fname{your\_song-mono-white.wav} are restored harmonically pretty well while still giving the "chaotic behavior" as mentioned above. Interestingly, it doesn't make a big difference whether the noisy frames are excluded or not: one cannot judge which type of repairing is the better one. Similar results were achieved when using \fname{cyftlt-mono-short\_sine.wav} or \fname{piano3-mono-white.wav} as test files. %In \config{1}, \fname{piano3-mono-sine.wav} can only be repaired if one excludes the noisy frames. If one does not exclude them, the algorithm either doesn't find any similar frames or gives frames that reproduce parts of the noise when doing the averaging step.

In general, \config{2} gives the same listening experience as already described for \config{1}, except for \fname{piano3-mono-sine.wav} where \config{2} gives better results than \config{1}.

From a musical point of view, the listening experience is not like one would expect a song to be. One problem is that the rhythmic structures of the different frames don't match, another one that parts with different melodies are mixed. Since the program doesn't have any previous knowledge of musical structures, it cannot fit the different rhythmic and melodic structures. From a computer science point of view the algorithm works better than expected since it finds structures that fit in terms of their tuning (harmonically). Not knowing the song might result in acceptance of the repairing, except for the fact that one might again perceive a small click at the point where the new data is connected to the old data which can be avoided as explained in section \ref{experiments.nlinpainting}.

Also, it was encountered that the averaged patch turns more and more quiet the more similar frames are specified to consider. Averaging the five best results is louder than averaging the 50 best results if all other parameters stay unaltered. This happens due to the cancellation of waveforms with different phases.

%%%%%%%%%%%%%%%%%% EXPERIMENTS: NL-MEANS %%%%%%%%%%%%%%%%%%
\section{NL-Means\index{experiments!nl-means}\index{nl-means}}\label{experiments.nlmeans}
Since the NL-means approach is a further development of the averaging on a sample basis method, it basically suffers from the same problems described in section \ref{experiments.avgonsamples}. Also, the shifting problem investigated in section \ref{experiments.nlinpainting} still exists. This is again due to the fact that just the data used for the repairing step is different.

Experiments have shown that the threshold parameter $\lambda$ significantly contributes to the final result by also partially overcoming the problems like the "chaotic behavior" as mentioned in section \ref{experiments.avgonsamples}. Choosing a  higher threshold results in a better -- for an image one would say "sharper" -- denoising. Of course, choosing $\lambda$ too large almost results in the non-local inpainting approach presented in section \ref{nlalgosap.nlinpainting} since the exponential function weights the best match always with 1\footnote{$\exp(-\lambda \cdot \frac{best - cur}{best}) = 1$ for $best = cur$} while all other matches receive weights close to 0 (because of the large $\lambda$).

The volume problem as presented at the end of section \ref{experiments.avgonsamples} doesn't appear with this approach. This is due to the fact that the exponential function can be scaled using $\lambda$ and this strongly influences the weighting of the different samples. Choosing a small decrease\footnote{This exponential function is decreasing because of the negative sign in the exponent of the exponential function (cf. section \ref{nlalgosap.nlmeans}).} of the function -- i.e.\ a very tolerant threshold parameter --, the first samples of the list get a high weight, resulting in an almost unweighted addition of all the suggested frames. If a lot of frames with distances close to each other cluster in combination with a small decrease of the exponential function, this can result in over- and undershoots, appearing as oversteer in the sound file.

Choosing a higher decrease of the exponential function ($\lambda$ should be larger) clearly performs better than the averaging on a sample basis not only in terms of the tuning of the different frames but also in terms of their "fitting". This is obvious since choosing a more radical weighting function almost doesn't consider frames that are not on the first positions in the similarity list, i.e.\ frames that do not have a high similarity.

Having a sound file that contains a lot of loud structures, $\lambda$ should be chosen higher, because adding high values (loud structures) and weighting them with an exponential function using a small $\lambda$ results in over- and undershoots quite fast. The opposite is also true: having a sound file that has not much loud structures, $\lambda$ should be chosen smaller. Furthermore it always has to be considered which configuration of the step size and window width is used. Depending on that, differences in choosing $\lambda$ can appear, too. This point is also discussed in the following experiments.

%Based on this general knowledge of the NL-means approach, the different test files can be investigated in more detail.

First, let's investigate \config{1}. The files \fname{cyftlt-mono-short\_sine.wav}, \fname{piano1-mono-white.wav} and \fname{piano3-mono-white.wav} are denoised quite well.
%The results are similar to what is explored in section \ref{experiments.avgonsamples} except for the "chaotic behavior" which is hardly present in this approach. This makes the files sound more convenient after the denoising step.
Nevertheless, one can hear an abrupt "discontinuity" in the melody. Besides, it doesn't make a big difference whether one excludes the noisy part or not since one cannot judge which result is the better one -- they are both convincing.% This shows that the NL-means approach is not that sensitive to noise, at least if the noise is not too large in its extend.

For \fname{candle\_in\_the\_wind-mono-silence.wav} and \fname{your\_song-mono-white.wav} one achieves also good denoising results. With these two files it is important to choose a large $\lambda$ since both files are very loud and dense in comparison to other files tested during the development of this thesis. For \fname{candle\_in\_the\_wind-mono-silence.wav}, $\lambda \geq 80$ is a good choice and for \fname{your\_song-mono-white.wav}, $\lambda \geq 100$ is a good point to start with. Also, for these two files it is possible to denoise without excluding noisy frames. Denoising \fname{your\_song-mono-white.wav} gives again better results when not excluding the noisy frames (cf. results in section \ref{experiments.nlinpainting}).

\fname{cyftlt-mono-long\_sine.wav} can be denoised with similar parameters as stated in table \ref{experiments.table.runtimecomparison1} and $\lambda \geq 30$ very well. For the stereo file \fname{cyftlt-long\_sine.wav} one can use the same parameters but has to choose $\lambda \geq 60$ to achieve the same result as for the mono case. This might be due to the basic averaging approach done for stereo files as introduced in section \ref{nlalgosap.stereofiles}.

When denoising \fname{piano3-mono-sine.wav} with the same parameters as given in table \ref{experiments.table.runtimecomparison2} and $\lambda \geq 30$, one can hardly tell a difference between the NL-means approach and the non-local inpainting.

Let's look at \config{2}. Interestingly, the files \fname{piano1-mono-white.wav}, \fname{piano3-mono-white.wav} and \fname{cyftlt-mono-short\_sine.wav} give better denoising results in comparison to \config{1} when using a smaller $\lambda$.  Choosing $\lambda$ around 10 already suffices to get a result that better fits the volume of the patch inserted in comparison to the whole piece of music. When expecting the repaired files to sound convenient, one has to choose $\lambda \geq 40$ for \fname{cyftlt-mono-short\_sine.wav}.

With the two files \fname{candle\_in\_the\_wind-mono-silence.wav} and \fname{your\_song-mono-white.wav}, one can achieve a better denoising for a small $\lambda$, too. \fname{candle\_in\_the\_wind-mono-silence.wav} can already be denoised acceptably using $\lambda = 10$ where a $\lambda$ around 25 is needed to repair the defect in \fname{your\_song-mono-white.wav} quite well. Nevertheless, one has the feeling that something is used for the denoising that really doesn't fit here in terms of the melodic structure. Better results can be achieved when choosing $\lambda \geq 25$ for \fname{candle\_in\_the\_wind-mono-silence.wav} and $\lambda \geq 80$ for \fname{your\_song-mono-white.wav}.

As expected, it is also possible with this approach to not exclude any noisy frame in case of the test files with a short degradation. Again, it cannot be judged which denoising variant is the better one.

For \fname{piano3-mono-sine.wav}, the parameters in table \ref{experiments.table.runtimecomparison2} also work here where $\lambda$ can be chosen relatively small: something around 10 is a good point to start with.

The file \fname{cyftlt-mono-long\_sine.wav} can be denoised by the same parameters as stated in table \ref{experiments.table.runtimecomparison1}. For $\lambda = 20$, one can already get a good result and for $\lambda \geq 30$ the result for the NL-means approach is that good that it almost cannot be decided whether the non-local inpainting or the NL-means approach is used in the denoising step. Surprisingly, $\lambda = 30$ is also adequate for the stereo case (\fname{cyftlt-long\_sine.wav}) in this configuration.

%%%%%%%%%%%%%%%%%% EXPERIMENTS: NL-MEANS ON CONTINUOUS NOISY SIGNALS %%%%%%%%%%%%%%%%%%
\section{NL-Means on Continuous Noisy Signals}\label{experiments.szlam}
The preprint by Szlam deals with files that are completely degraded by moderate Gaussian noise. After running the algorithm on this kind of data, one can perceive that the Gaussian noise is reduced, but also a lot of clicking noise is introduced. This might be due to the fact that the algorithm is not optimized for such problems. Interestingly, the clicking noise is not always reduced when iterating a few times. It can even be the case that the more iterations are done, the more clicking noise is introduced. This can be explained by the following situation. The algorithm runs over the whole signal for the first time. After that, a few appearances of clicking noise can be noticed in the result. If the algorithm is iterated, it can happen that such a clicking noise is in the (small) search neighborhood of the currently observed frame, meaning that a frame is searched that contains noise. As a consequence, this noise contributes to the averaging used to repair the current frame, probably resulting in more noise, depending on how the noisy frames are weighted.

%%%%%%%%%%%%%%%%%% EXPERIMENTS: SUMMARY %%%%%%%%%%%%%%%%%%
\section{Summary\index{experiments!summary}}\label{experiments.summary}
This chapter investigated the memory requirements and the runtime of the developed algorithm under two different parameter settings. The first parameter setting introduced an 75\% overlap of the data where the other one a 50\% overlap of the data. The memory requirements were exactly expected in this way which was shown in a simple calculation. Concerning the runtime, it turned out that the parameter setting with the 50\% overlap was four times faster than the other one by giving approximately the same results.

Furthermore, three methods to repair noisy data were investigated in detail: non-local inpainting, averaging on a sample basis and NL-means. It turned out that all the methods strongly depend on the proposals made by the similarity measurement. Non-local inpainting works well, if the proposal was good. Sometimes it even can reconstruct the noisy part in such a way that the repaired signal comes very close to the original (non-noisy) file.

With the approach to average on a sample basis one can get harmonically good results. The problem from a musical point of view is that the approach is pretty sensitive as far as the number of similar frames to search for is concerned.

The NL-means approach works good as long as the threshold parameter $\lambda$ is chosen in such a way that the involved exponential function decreases fast enough.

Also, an approach similar to the one by Szlam \cite{nlmeansaudio} is investigated in the experiments. Here one can perceive sudden appearances of clicking noise. A more detailed investigation of this phenomenon could not be carried out within the time frame of this thesis.

%%%%%%%%%%%%%%%%%% CONCLUSION / FUTURE WORK %%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\cleardoublepage\chapter{Conclusion and Future Work}\label{final}
%%%%%%%%%%%%%%%%%% CONCLUSION / FUTURE WORK: CONCLUSION %%%%%%%%%%%%%%%%%%
\section{Conclusion\index{conclusion}}\label{final.conclusion}
As presented in this thesis, image processing ideas can be used fruitfully to analyze music. It was presented how the tools like the Fourier transform\index{fourier transform} have to be changed to fit the needs of audio analysis. By windowing and going forward in time, having different windows overlap each other (sliding window) to get more than one contribution to the currently observed part, one can subdivide the whole signal into separate windows and compute the power spectrum for each window. Of course, computing the power spectrum implies to perform a Fourier transform using the data of the corresponding window as input.

Having the basic ingredients like the short-time Fourier transform\index{short-time fourier transform} as the modification of the "classical" Fourier transform and the Hamming window as a windowing function, one can interpret the power spectrum of each window as a one-dimensional vector which can be used for the similarity measurement. In a first step, the scalar product of two vectors -- the power spectrum of the reference frame and the power spectrum of the currently observed frame -- was normalized using the vector norm of both vectors. To find out which frames are similar, the distances between the scalar product of the reference frame and the currently observed frame were computed where two frames are similar if their distance is maximal.

This work showed that it is possible to use methods known from image processing and modify them to do audio processing. It turned out that non-local inpainting works well if the proposed similar frame is good, averaging on a sample basis repairs the defect at least in a harmonic sense and that the NL-means approach is controlled by a threshold parameter $\lambda$ which significantly contributes to the result: if $\lambda$ is chosen well the results are good.

%%%%%%%%%%%%%%%%%% CONCLUSION / FUTURE WORK: FUTURE WORK %%%%%%%%%%%%%%%%%%
\section{Future Work\index{future work!overview}}\label{final.futurework}
So far, only the maximization of the scalar product is used as a similarity measurement. This approach is sensitive to loud structures, in other words it prefers them. If a melody appears at a certain location very muted and at another location pretty loud, the latter one would be preferred. Here, some efforts can be made to make the similarity measurement more robust against the volume of the different patches. Maybe also other similarity measurements exist that can be used to find similar frames. The use of a similarity matrix as proposed by \cite{foote} and used for example in \cite{musicsum} might be an intuitive possibility.

Also, repairing multiple degradations at the same time -- i.e.\ in one run -- could be a possibility to make the denoising process more comfortable. A basic approach would be to use an iteration during the program run. This might not be the most efficient way, but would work.

The short-time Fourier transform has some drawbacks, e.g.\ that the frequency resolution is not sufficient to separate musical notes of low frequency. A possible remedy is to use several short-time Fourier transforms that work at different sampling rates with different window sizes to increase the frequency resolution for lower notes, see e.g.\ \cite{mueller}.

It would also be possible to do an alternative approach by not using the short-time Fourier transform, but to use a wavelet-based approach: it gives a good time resolution for high-frequency events and a good frequency resolution for low-frequency events.

Another possible work for the future is to make the software more user-friendly. Maybe the number of parameters can be reduced. This might be possible by establishing a dependency between the neighborhood which is considered for the search and the neighborhood which is effectively replaced then.

Arthur Szlam proposes in \cite{nlmeansaudio} to run the NL-means algorithm on speech where Gaussian noise is used for the degradation of the whole signal. Since first attempts to include the idea by \cite{nlmeansaudio} didn't work well so far, it could be worth to invest more effort into changing the algorithms to perform better on such a setting. This was not possible within the time frame of this thesis.

%%%%%%%%%%%%%%%%%% APPENDIX %%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\cleardoublepage
\begin{appendix}
%%%%%%%%%%%%%%%%%% APPENDIX: WAVE FILES %%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\chapter{Wave Files\index{wave file}}\label{appendix.wavfiles}

\section{Wave File Format\index{wave file!file format}}\label{appendix.wavfiles.wavefileformat}
The wave file format \cite{wavformat} was developed by Microsoft and IBM and is nowadays the standard audio file format for storing an uncompressed audio file on a computer. It is based on the RIFF bitstream format \cite{riffformat} which allows to store the data in different chunks. The default bitstream encoding is the Microsoft Pulse Code Modulation (PCM) format. Unfortunately, the format of a wave file is not uniquely defined because it can have a lot of custom chunks. This thesis only considers the following format where all other types of chunks are not processed:
\begin{table}[ht]
\centering
\topcaption[The WAV file format]{The WAV file format. \textbf{Adapted from:} Wikipedia \cite{wavformat}.}
\begin{tabular}{p{1.5cm}|l|p{1.8cm}|l}
	Position [bytes] & Field Name & Field Size [bytes] & Description / Contents \\ \hline
	0 & Chunk ID & 4 & "RIFF" \\ \hline
	4 & File Size & 4 & Entire File Size - 8 \\ \hline
	8 & File Format & 4 & "WAVE" \\ \hline
	12 & SubChunk1 ID & 4 & "fmt " (header signature) \\ \hline
	16 & SubChunk1 Size & 4 & 16 for PCM files. \\ \hline
	20 & Audio Format & 2 & 1 for uncompressed audio. \\ \hline
	22 & Num of Channels & 2 & 1 = mono, 2 = stereo, ... \\ \hline
	24 & Sample Rate & 4 & 44100 Hz for CD quality \\ \hline
	28 & Byte Rate & 4 & Sample Rate $\times$ Block Alignment \\ \hline
	32 & Block Alignment & 2 & Num of Channels $\times$ Bits Per Sample $\div$ 8 \\ \hline
	34 & Bits Per Sample & 2 & 8, 16 or 24 \\ \hline
	36 & SubChunk2 ID & 4 & "data" (header signature) \\ \hline
	40 & Data Size & 4 & Number of bytes following the header. \\ \hline
	\multicolumn{4}{c}{\bfseries \itshape DATA} \\ \hline
\end{tabular}
\end{table}

\noindent In figure \ref{appendix.figure.72bytesexamplewavefile}, an example for a possible data arrangement of a WAV file is depicted.
\begin{figure}[ht]
\centering
\includegraphics[height=0.48\textheight]{figures/wave-bytes.eps} \\
\caption[Example of a WAV file (first 72 bytes)]{First 72 bytes of an example WAV file. \textbf{Source:} \url{http://ccrma.stanford.edu/courses/422/projects/WaveFormat/}.}
\label{appendix.figure.72bytesexamplewavefile}
\end{figure}

\section{Meaning of the Data\index{wave file!meaning}}\label{appendix.wavfiles.meaning}
A WAV file is a discrete version of an audio signal and describes the development of an oscillation in time. The quality of a wave file is determined by the sample rate. An example for a common visualization of a WAV file is given in figure \ref{appendix.figure.examplevisualisation}.
\begin{figure}[ht]
\centering
\includegraphics[height=0.31\textheight]{figures/visualisation-example.eps} \quad \quad
\includegraphics[height=0.31\textheight]{figures/visualisation-example-zoom.eps} \\
\includegraphics[height=0.31\textheight]{figures/visualisation-example-spectrogram.eps} \quad \quad
\includegraphics[height=0.31\textheight]{figures/visualisation-example-spectrogram-zoom.eps} \\
\caption[Visualization of a WAV file]{Example for a visualization of a WAV file with a sampling rate of 44100 Hz. \textbf{Left:} First three chords of \fname{cyftlt-mono.wav}. \textbf{Right:} Zoom into the first chord of the same file. \textbf{Top:} Waveform representation. The x-axis depicts the time in seconds where the y-axis shows the amplitude. \textbf{Bottom:} Frequency representation. The x-axis depicts the time in seconds where the y-axis shows the frequency distribution. Colors give the intensity of a certain frequency. The blue color stands for a high intensity going over red and yellow to white which stands for a low intensity.}
\label{appendix.figure.examplevisualisation}
\end{figure}

Assuming to have a stereo file -- i.e.\ having two channels --, the data of a WAV file is arranged as depicted in figure \ref{appendix.figure.samplesframespic}. Here can be seen that two channel samples are combined to build a sample and N samples are combined to build one frame.

In the audio sector, the "channel samples" in figure \ref{appendix.figure.samplesframespic} are often called "samples" and the "samples" in figure \ref{appendix.figure.samplesframespic} are called "frames". Since one needs a natural expression that builds on top of these two concepts, the renaming is performed in the presented way.

WAV files are stored in general in little endian where the least significant bit stands at the first position. If the length cannot be divided by 8, a zero-padding is applied. Figure \ref{appendix.figure.zeropaddingforwavfiles} shows this nicely.

For a more detailed description of the waveform representation, see section 2.1.2 in \cite{mueller}.
\begin{figure}[ht]
\centering
\begin{pspicture}(0,0)(16,5)
\psframe[fillstyle=solid, fillcolor=lightgrey](0,0)(16,4)
\rput(2.0,0.5){\textsf{\small Channel Sample}}
\rput(2.0,2.0){\textsf{\small Sample}}
\rput(2.0,3.5){\textsf{\small Frame}}
\rput(4.5,0.5){\psframebox{\textsf{\small ch0}}}
\rput(6.0,0.5){\psframebox{\textsf{\small ch1}}}
\rput(5.25,2.0){\textsf{\small 0}}
\rput(8.0,0.5){\psframebox{\textsf{\small ch0}}}
\rput(9.5,0.5){\psframebox{\textsf{\small ch1}}}
\rput(8.75,2.0){\textsf{\small 1}}
\rput(11.25,0.5){\textsf{\small ...}}
\rput(11.25,2.0){\textsf{\small ...}}
\rput(13.0,0.5){\psframebox{\textsf{\small ch0}}}
\rput(14.5,0.5){\psframebox{\textsf{\small ch1}}}
\rput(13.75,2.0){\textsf{\small N}}
\psframe[fillstyle=solid, fillcolor=white](4.05,3.1)(14.95,3.8)
\rput(9.5,3.5){\textsf{\small M}}
\end{pspicture}
%\includegraphics[height=0.11\textheight]{figures/WAV-frame.eps} \\
\caption[\textit{Frames} -- \textit{Samples} -- \textit{Channel samples} difference for a stereo WAV file.]{Difference between \textit{frames}, \textit{samples} and \textit{channel samples} for a stereo WAV file. In case of this thesis, M starts with 1 and N is the window width. \textbf{Adapted from:} Wikipedia \cite{wavformat}.}
\label{appendix.figure.samplesframespic}
\end{figure}

\begin{figure}[ht]
\centering
\includegraphics[height=0.09\textheight]{figures/WAV-bitordering.eps} \\
\caption[Example for the bit alignment of a 12-bit sample.]{Example for the bit alignment of a 12-bit sample. The 12 bits are padded by zeros to get 16 bits (which can be divided by 8). \textbf{Source:} Wikipedia \cite{wavformat}.}
\label{appendix.figure.zeropaddingforwavfiles}
\end{figure}

%%%%%%%%%%%%%%%%%% APPENDIX: DVD CONTENTS %%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\chapter{DVD Contents}\label{appendix.contents}
The attached DVD contains all the files used for this thesis including their denoised versions. These are located in the folder \texttt{experiments} which contains the following subfolders: \\
\begin{center}
\begin{tabular}{|lclcl|}
	\hline
	\texttt{experiments} & & & & \\
	& $\hookrightarrow$ & \texttt{audio\_sources} & & \\
	& $\hookrightarrow$ & \texttt{avg\_samples} & & \\
	& & & $\hookrightarrow$ & \texttt{2048-4096} \\
	& & & $\hookrightarrow$ & \texttt{256-1024} \\
	& $\hookrightarrow$ & \texttt{nl\_inpainting} & & \\
	& & & $\hookrightarrow$ & \texttt{2048-4096} \\
	& & & $\hookrightarrow$ & \texttt{256-1024} \\
	& $\hookrightarrow$ & \texttt{nl\_means} & & \\
	& & & $\hookrightarrow$ & \texttt{2048-4096} \\
	& & & $\hookrightarrow$ & \texttt{256-1024} \\
	& $\hookrightarrow$ & \texttt{nl\_means-szlam} & & \\
	& & & $\hookrightarrow$ & \texttt{2048-4096} \\
	& & & $\hookrightarrow$ & \texttt{256-1024} \\ \hline
\end{tabular}
\end{center}
\ \\
\noindent The folder \texttt{audio\_sources} contains all the input files used in the experiments.

\noindent In the subfolders of \texttt{nl\_means-szlam}, the following files can be found (except for the clean version):
\begin{center}
\begin{tabular}{|l|l|l|c|}
\hline
\textbf{clean version} & \textbf{noisy version} & \textbf{denoised version} & \textbf{iteration} \\ \hline
\fname{piano1-mono.wav} & \fname{piano1-mono-noisy.wav} & \fname{piano1-mono-noisy-corr-i1.wav} & 1 \\ \hline
&  & \fname{piano1-mono-noisy-corr-i2.wav} & 2 \\ \hline
&  & \fname{piano1-mono-noisy-corr-i3.wav} & 3 \\ \hline
\fname{piano3-mono.wav} & \fname{piano3-mono-noisy.wav} & \fname{piano3-mono-noisy-corr-i1.wav} & 1 \\ \hline
& & \fname{piano3-mono-noisy-corr-i2.wav} & 2 \\ \hline
& & \fname{piano3-mono-noisy-corr-i3.wav} & 3 \\ \hline
\end{tabular}
\end{center}

\noindent Each subfolder of \texttt{avg\_samples}, \texttt{nl\_inpainting} and \texttt{nl\_means} contains the following denoised versions:
\begin{center}
\begin{tabular}{|l|l|}
\hline
\textbf{noisy version} & \textbf{denoised version} \\ \hline
\fname{cyftlt-mono-short\_sine.wav} & \fname{cyftlt-mono-short\_sine-corr.wav} \\ \hline
\fname{cyftlt-mono-short\_sine.wav} & \fname{cyftlt-mono-short\_sine-corr-1.wav} \\ \hline
\fname{cyftlt-mono-long\_sine.wav} & \fname{cyftlt-mono-long\_sine-corr.wav}  \\ \hline
\fname{cyftlt-long\_sine.wav} & \fname{cyftlt-long\_sine-corr.wav} \\ \hline
\fname{piano1-mono-white.wav} & \fname{piano1-mono-white-corr.wav} \\ \hline
\fname{piano3-mono-sine.wav} & \fname{piano3-mono-sine-corr-version1.wav} \\ \hline
\fname{piano3-mono-sine.wav} & \fname{piano3-mono-sine-corr-version2.wav} \\ \hline
\fname{piano3-mono-white.wav} & \fname{piano3-mono-white-corr.wav} \\ \hline
\fname{piano3-mono-white.wav} & \fname{piano3-mono-white-corr-1.wav} \\ \hline
\fname{candle\_in\_the\_wind-mono-silence.wav} & \fname{candle\_in\_the\_wind-mono-silence-corr.wav} \\ \hline
\fname{candle\_in\_the\_wind-mono-silence.wav} & \fname{candle\_in\_the\_wind-mono-silence-corr-1.wav} \\ \hline
\fname{your\_song-mono-white.wav} & \fname{your\_song-mono-white-corr.wav} \\ \hline
\fname{your\_song-mono-white.wav} & \fname{your\_song-mono-white-corr-1.wav} \\ \hline
\end{tabular}
\end{center}
Files in this table that carry a "\fname{-1}" at the end of their name are generated without excluding noisy frames where all others are created with the exclusion of the noisy part. \\

\noindent The parameter settings can be found in the files that have a "\fname{.txt}" attached to the name of the denoised version, for example \fname{candle\_in\_the\_wind-mono-silence-corr.wav.txt}.

\end{appendix}

%\cleardoublepage
%\listoffigures
%\listoftables

%\printindex
\cleardoublepage
% Ignore underfull hbox warnings for the bibtex file (there are many URLs, this will be ok)
\hbadness=10000
\bibliographystyle{plain}
\bibliography{thesis}\addcontentsline{toc}{chapter}{References}
\hbadness=1000

\end{document}
