\pagestyle{fancy}
\cleardoublepage\chapter{Modifications and Refinements}\label{modifications}
\Quote{In the beginner's mind there are many possibilities. In the expert's mind there are few.}{Shunryu Suzuki}

\noindent In this chapter, we want to investigate modifications and refinements to the algorithms introduced in the chapters before. The modifications address drawbacks concerning runtime or provide refinements that allow a better processing of spectrograms\index{spectrogram} in the context of chord recognition\index{chord recognition} or onset detection\index{onset detection}.

\section{Diffusion\index{diffusion}}\label{modifications.diffusion}
The diffusion tensor\index{diffusion!tensor} $D$ is the tool to control a diffusion\index{diffusion} process. We make use of the structure tensor\index{structure tensor} $J$ to compute $D$% that has the form
\begin{equation}
	D = \left(\begin{array}{cc}a & c \\ c & b\end{array}\right),
\end{equation}
where the eigenvectors of $D$ are identical to those of $J$ while the eigenvalues are recomputed to fit equations \eqref{eed_eigenvalues}--\eqref{eed_g-function} for edge-enhancing diffusion\index{diffusion!edge-enhancing} or equations \eqref{ced_eigenvalues1},\eqref{ced_eigenvalues2} for coherence-enhancing diffusion\index{diffusion!coherence-enhancing}, respectively. Since we are interested in horizontal structures in the context of chord recognition\index{chord recognition} and in vertical structures in the context of onset detection\index{onset detection}, we modify the diffusion tensor\index{diffusion!tensor} to prefer diffusion\index{diffusion} in a certain direction.

Multiplying the diffusion tensor\index{diffusion!tensor} with a matrix of the form
\begin{equation*}
	\left(\begin{array}{cc}d_\alpha & 0 \\ 0 & d_\beta\end{array}\right)
\end{equation*}
from both sides introduces anisotropy controlled by the choice of $d_\alpha$ and $d_\beta$. The \emph{modified diffusion tensor\index{diffusion!tensor}} looks as follows:
\begin{equation}
	D' = \left(\begin{array}{cc}d_\alpha & 0 \\ 0 & d_\beta\end{array}\right) \left(\begin{array}{cc}a & c \\ c & b\end{array}\right) \left(\begin{array}{cc}d_\alpha & 0 \\ 0 & d_\beta\end{array}\right) = \left(\begin{array}{cc}d_\alpha^2 a & d_\alpha d_\beta c \\ d_\alpha d_\beta c & d_\beta^2 b\end{array}\right).
\end{equation}
The weightings $d_\alpha$ and $d_\beta$ can be used to enhance or reduce the diffusion\index{diffusion} in one direction -- i.e.\ choosing a value $d_\alpha, d_\beta \geq 1$ or a value $0 \leq d_\alpha,d_\beta < 1$, respectively. In this thesis, only the values $0$ and $1$ are used to switch the diffusion process\index{diffusion} in a certain direction on or off.

\section{Morphology\index{morphology}}\label{modifications.morphology}
In Section \ref{morphology.nonflat}, we stated that for the discrete version of parabolic dilation and parabolic erosion the scalability property is not guaranteed anymore. We now present an approach to overcome this problem.

To get rid of the violation of the scalability property, we modify the scaling parameters $s_x$ and $s_y$ from equations \eqref{eq_pardil} and \eqref{eq_parero} in every iteration step. We can do this by introducing scaling parameters $s_x'$ and $s_y'$ such that it holds
\begin{eqnarray}
	s_x' & = & \frac{1}{2^k} \cdot s_x, \\
	s_y' & = & \frac{1}{2^k} \cdot s_y,
\end{eqnarray}
where $k=1, \dots, n$ is the current iteration and $n$ is the total number of iterations.

By means of parabolic dilation and parabolic erosion as given in equations \eqref{eq_pardil} and \eqref{eq_parero}, respectively, we can think of a new skeletonization approach: \emph{parabolic skeletonization}.

Let $SE_k$ correspond to $(s_x',s_y') = (\frac{1}{2^k} \cdot s_x, \frac{1}{2^k} \cdot s_y)$. Then the parabolic skeletonization reads as
\begin{equation}\label{eq_parabolic_skeletonization}
	S(f) = \sum_{k=0}^n \Big[f \ominus SE_k - f \circ SE_{k+1}\Big]_+,
\end{equation}
where we only sum up the positive contributions.

Note that this is not an exact generalization of the skeletonization algorithm \eqref{eq_skeletonization} for binary images. The idea behind both algorithms is that in the $k$-th step (i.e.\ $k$-th summand) those parts of the eroded signal $f \ominus SE_k$ should be added to the skeleton which would be destroyed in the next erosion step $f \ominus SE_{k+1}$ ``irreversibly'', i.e.\ cannot be restored by dilation. In \eqref{eq_skeletonization} these parts are detected by dilating back the signal $f \ominus SE_{k+1}$ to the level of the $k$-th erosion and comparing with $f \ominus SE_k$: the subtrahend of \eqref{eq_skeletonization} can as well be written as $(f \ominus (k+1)SE) \oplus SE$. However, as we mentioned in Section \ref{morphology.nonflat}, iterated application of discretized parabolic dilations or erosions with the structuring function $SE$ does not approximate a discretized parabolic dilation or erosion with a scaled structuring function. This poses an obstacle to direct translation of \eqref{eq_skeletonization}.

Our solution in \eqref{eq_parabolic_skeletonization} consists in dilating back $f \ominus SE_{k+1}$ in one step to the level of the initial signal $f$ and contributing to the skeleton those parts of $f \ominus SE_k$ which are \emph{not even then} restored. As $f \circ SE_{k+1}$ is not completely below $f \ominus SE_k$, the restriction to the positive part is necessary. As a consequence, \eqref{eq_parabolic_skeletonization} applied in a binary morphological setting would lose substantial contributions as compared to \eqref{eq_skeletonization}. Experiments show, however, that in conjunction with parabolic structuring functions this approach retains enough signal contributions to create a reasonable, moderately thinned version of image structures.

Furthermore, we introduce an upper bound to keep the runtime of the algorithm short. The algorithm stops at $n$ such that
\begin{equation}
	\max\big(f \ominus SE_n - f \circ SE_{n+1}\big) \leq \text{threshold}
\end{equation}
holds. In other words the algorithm stops if another step of the parabolic skeletonization as described in equation \eqref{eq_parabolic_skeletonization} would not give a much better result compared to the higher runtime.

\section{NL-Means\index{NL-means}}\label{modifications.nlmeans}
In Section \ref{nlmeans.refinements}, we have seen some refinements that can be made to improve the NL-means\index{NL-means} algorithm. Now, we introduce another modification that addresses special needs of chord recognition and onset detection.
%In this section, we state some refinements that can be made to improve the NL-means\index{NL-means} algorithm. Unfortunately, NL-means\index{NL-means} in its basic form is computationally very expensive. We look at different approaches to address this drawback in the following.
%This is due to the fact that every pixel is compared with every other pixel in the image to find a possible candidate for the denoising. To address this problem, we can restrict the search space to a ``search window''. Another possibility is to only compute the weighting in special cases and set the weights to 0 otherwise. This can be done by neighborhood classification. A further modification that improves the standard NL-means\index{NL-means} is the adaptive choice of the decay parameter $\lambda$. Its optimal value depends on how much noise is in the image. It has been shown by Brox and Cremers \cite{brox07} that there is in general no global optimum for $\lambda$ for one image. A remedy in this case is to replace the parameter $\lambda$ by a locally adaptive function. As a last refinement, we can change the size of the search and similarity window from a quadratic to a rectangular form. We investigate each of the mentioned approaches in more detail in the following.

%\subsection{Change of the Windows used by NL-Means\index{NL-means}}\label{modifications.nlmeans.change_windows}
So far, we assumed for NL-means\index{NL-means} a quadratic search and a quadratic similarity window. When it comes to applications like chord recognition or onset detection where we are interested in horizontal or vertical structures, respectively, a quadratic window is not an optimal choice. The logical consequence is to change the windows in such a way that we can have rectangular ones. Analogously to the notation in \ref{nlmeans.search_space}, we can introduce a similarity window of size $W_x \times W_y$ and a search window of size $S_x \times S_y$. Naturally, the algorithm can also deal with input images that are rectangular, i.e.\ images of size $N_x \times N_y$. 

As already stated, NL-means\index{NL-means} in its basic form is computationally very expensive and we presented different approaches to address this drawback. Considering the change of the windows as proposed in this section, the complexity of the algorithm is now $(W_x \times W_y) \times (S_x \times S_y) \times (N_x \times N_y)$ which might also lead to a dramatically reduced runtime depending on the window sizes.