\section{A detailed study of possible variants
	\label{sec:study} } 		This part discusses several sound variants for each
step of the algorithm.  It gives experimental evidence that  the choices taken in
the algorithm are the best in terms of PSNR.


\subsection{Grouping}


\subsubsection{Color space transform}


The  $Y_0U_0V_0$ space will be compared to $RBB$, for both steps. When $RGB$ is
chosen in the algorithm,
\begin{itemize}
	\vspace{-3mm}\item the distance is computed on all channels like in
\eqref{eq_dist2};
	\vspace{-3mm}\item the collaborative filtering is done on each channel
separately;
	\vspace{-3mm}\item $N_{\hard}$ is increased to avoid having a
non-invertible matrix.
\end{itemize}

\begin{center}
	\begin{tabular}{||c||c|c||c|c||c|c||c|c||}
		\hline
		Step 1 / Step 2 & \multicolumn{2}{c||}{$RGB$ / $RGB$} & \multicolumn{2}{c||}{$Y_0U_0V_0$ / $RGB$} & \multicolumn{2}{c||}{$RGB$ / $Y_0U_0V_0$} & \multicolumn{2}{c||}{$Y_0U_0V_0$ / $Y_0U_0V_0$}\\
		\hline
		$\sigma$ & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE}\\
		\hline
		\hline
		2 & {\bf 46.10} & {\bf 1.26} & 46.04 & 1.27 & 45.83 & 1.30 & 45.80 & 1.31\\
		\hline
		5 & {\bf 39.89} & {\bf 2.58} & 39.86 & 2.59 & 39.66 & 2.65 & 39.64 & 2.66\\
		\hline
		10 & 35.39 & 4.33 & {\bf 35.42} & {\bf 4.32} & 35.22 & 4.42 & 35.25 & 4.41\\
		\hline
		20 & 31.10 & 7.10 & {\bf 31.30} & {\bf 6.94} & 31.00 & 7.19 & 31.18 & 7.03\\
		\hline
		30 & 28.73 & 9.33 & {\bf 28.93} & {\bf 9.11} & 28.65 & 9.41 & 28.85 & 9.20\\
		\hline
		40 & 27.23 & 11.08 & {\bf 27.47} & {\bf 10.78} & 27.18 & 11.15 & 27.43 & 10.84\\
		\hline
		60 & \emph{23.87} & \emph{16.34} & {\bf 25.54} & {\bf 13.48} & \emph{23.82} & \emph{16.43} & 25.52 & 13.50\\
		\hline
		80 & \emph{22.96} & \emph{18.13} & 24.24 & 15.66 & \emph{22.92} & \emph{18.23} & {\bf 24.24} & {\bf 15.65}\\
		\hline
		100 & \emph{22.14} & \emph{19.93} & 23.24 & 17.56 & \emph{22.10} & \emph{20.02} & {\bf 23.25} & {\bf 17.54}\\
		\hline
	\end{tabular}
	
	
{\scriptsize In {\bf bold} the best PSNR for a given $\sigma$. In \emph{italic} results with a lot of non-inversible matrix in the first step.}
\end{center}
Despite the fact that $N_{\hard}$ has been increased in the case where $RGB$ is
chosen for the first step, in practice the matrix $\bC_{\tilde P}$ is often not
invertible. This explains why the result is that bad for high values of the noise
when $RGB$ is chosen for the first step.


\subsection{Collaborative Filtering}


\subsubsection{The homogeneous area criterion}
One of the  innovations in NL-Bayes is the detection of the homogeneous areas
 in the first step. In order to show its relevance, here are some
results with and without this criterion, in both steps:

\begin{center}
	\begin{tabular}{||c||c|c||c|c||c|c||c|c||}
		\hline
		Step 1 / Step 2 & \multicolumn{2}{c||}{No / No} & \multicolumn{2}{c||}{Yes / No} & \multicolumn{2}{c||}{No / Yes} & \multicolumn{2}{c||}{Yes / Yes}\\
		\hline
		$\sigma$ & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE}\\
		\hline
		\hline
		2 & {\bf 46.04} & {\bf 1.27} & {\bf 46.04} & {\bf 1.27} & {\bf 46.04} & {\bf 1.27} & {\bf 46.04} & {\bf 1.27}\\
		\hline
		5 & 39.89 & 2.58 & {\bf 39.90} & {\bf 2.57} & 39.88 & 2.58 & 39.89 & 2.58\\
		\hline
		10 & 35.36 & 4.35 & {\bf 35.39} & {\bf 4.33} & 35.37 & 4.34 & 35.35 & 4.35\\
		\hline
		20 & 31.05 & 7.14 & 31.27 & 6.96 & {\bf 31.29} & {\bf 6.95} & 31.26 & 6.98\\
		\hline
		30 & 28.68 & 9.38 & {\bf 29.01} & {\bf 9.04} & {\bf 29.01} & {\bf 9.04} & 28.97 & 9.08\\
		\hline
		40 & 27.05 & 11.32 & {\bf 27.48} & {\bf 10.78} & 27.47 & 10.79 & 27.42 & 10.85\\
		\hline
		60 & 25.39 & 13.70 & {\bf 25.58} & {\bf 13.41} & 25.55 & 13.45 & 25.45 & 13.62\\
		\hline
		80 & 24.14 & 15.83 & {\bf 24.26} & {\bf 15.62} & 24.16 & 15.80 & 23.98 & 16.12\\
		\hline
		100 & 23.09 & 17.86 & {\bf 23.27} & {\bf 17.49} & 23.15 & 17.73 & 22.93 & 18.20\\
		\hline
	\end{tabular}
	
	
{\scriptsize In {\bf bold} the best PSNR for a given $\sigma$.}
\end{center}
One can see that the homogeneity detection is  useful for medium and high values of
noise. On an image with many homogeneous areas, the application of this detection
avoids artifacts, as one can see on the following image for a medium value of
noise: 20.

\ifpdf
\begin{center}
	\begin{tabular}{cc}
		\includegraphics[scale=1.35]{images/dice_sub.png} &
		\includegraphics[scale=1.35]{images/dice_noisy_sub.png} \\
		Original image & Noisy image $\sigma = 30$\\
		\includegraphics[scale=1.35]{images/dice_denoised_false_false_sub.png} &
		\includegraphics[scale=1.35]{images/dice_denoised_true_false_sub.png} \\
		No / No $|$ PSNR = 33.93 / RMSE = 5.13 & Yes / No $|$ PSNR = 38.82 / RMSE = 2.92\\
		\includegraphics[scale=1.35]{images/dice_denoised_false_true_sub.png} &
		\includegraphics[scale=1.35]{images/dice_denoised_true_true_sub.png} \\
		No / Yes $|$ PSNR = 38.69 / RMSE = 2.96 & Yes / Yes $|$ PSNR = 38.36 / RMSE = 3.08\\		
	\end{tabular}
\end{center}
\fi

\subsubsection{Diagonalizing the covariance matrix}


As presented in  section \ref{subsec:nl_pca}, $\bC_{\tilde P}$ and $\bC_{\tilde
P}^{\basic}$ can be diagonalized with the use of a PCA on the 3D block $\mP(\tilde
P)$ and $\mP^{\basic}(\tilde P)$, which leads to an algorithm which we called
NL-PCA. The principal difference between NL-PCA and NL-Bayes is in the
collaborative filtering part, as detailed in \ref{subsec:nl_pca}. All the rest is
exactly the same.  Here is presented the difference between NL-PCA and NL-Bayes on
three (noiseless) images, to which noise was added. The images are displayed below.
\ifpdf
\begin{center}
	\begin{tabular}{c c}
		\includegraphics[scale=0.3]{images/dice.png} &
		\includegraphics[scale=0.3]{images/flowers.png} \\
		Dice & Flowers \\
		\multicolumn{2}{c}{\includegraphics[scale=0.3]{images/traffic.png}} \\
		\multicolumn{2}{c}{Traffic}\\
	\end{tabular}
\end{center}
\fi


\begin{changemargin}{-0.75cm}{0cm}
\begin{center}
	\begin{tabular}{||c||c|c||c|c||c|c||c|c||c|c||c|c||}
		\hline
		 & \multicolumn{4}{c||}{Dice} & \multicolumn{4}{c||}{Flowers} & \multicolumn{4}{c||}{Traffic}\\
		 \hline
		 & \multicolumn{2}{c||}{NL-PCA} & \multicolumn{2}{c||}{NL-Bayes} & \multicolumn{2}{c||}{NL-PCA} & \multicolumn{2}{c||}{NL-Bayes} & \multicolumn{2}{c||}{NL-PCA} & \multicolumn{2}{c||}{NL-Bayes}\\
		\hline
		$\sigma$ & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE}\\
		 \hline
		 2 & 48.85 & 0.92 & {\bf 49.08} & {\bf 0.90} & 47.59 & 1.06 & {\bf 47.77} & {\bf 1.04} & 45.00 & 1.43 & {\bf 45.25} & {\bf 1.39}\\
		 \hline
		 5 & 45.84 & 1.30 & {\bf 45.92} & {\bf 1.29} & 43.35 & 1.73 & {\bf 43.41} & {\bf 1.72} & 39.42 & 2.73 & {\bf 39.59} & {\bf 2.67}\\
		 \hline
		 10 & 43.17 & 1.77 & {\bf 43.31} & {\bf 1.74} & 39.66 & 2.65 & {\bf 39.83} & {\bf 2.60} & 35.40 & 4.33 & {\bf 35.49} & {\bf 4.29}\\
		 \hline
		 20 & {\bf 40.68} & {\bf 2.36} & 40.56 & 2.39 & 36.33 & 3.89 & {\bf 36.42} & {\bf 3.85} & 31.28 & 6.96 & {\bf 31.48} & {\bf 6.80}\\
		 \hline
		 30 & {\bf 38.83} & {\bf 2.92} & 38.81 & 2.92 & 34.16 & 5.00 & {\bf 34.20} & {\bf 4.97} & 29.20 & 8.84 & {\bf 29.34} & {\bf 8.70}\\
		 \hline
		 40 & {\bf 37.35} & {\bf 3.46} & {\bf 37.35} & {\bf 3.46} & 32.52 & 6.03 & {\bf 32.59} & {\bf 5.98} & 27.80 & 10.39 & {\bf 27.87} & {\bf 10.30}\\
		 \hline
		 60 & 35.60 & 4.23 & {\bf 35.62} & {\bf 4.22} & 30.72 & 7.42 & {\bf 30.84} & {\bf 7.32} & 25.77 & 13.12 & {\bf 26.01} & {\bf 12.77}\\
		 \hline
		 80 & 34.53 & 4.79 & {\bf 34.60} & {\bf 4.75} & 29.28 & 8.76 & {\bf 29.47} & {\bf 8.57} & 24.62 & 14.98 & {\bf 24.75} & {\bf 14.76}\\
		 \hline
		 100 & 33.46 & 5.41 & {\bf 33.48} & {\bf 5.40} & 28.15 & 9.98 & {\bf 28.26} & {\bf 9.85} & 23.76 & 16.54 & {\bf 23.85} & {\bf 16.37}\\
		 \hline
	\end{tabular}
\end{center}
\end{changemargin}
The table shows that NL-Bayes is slightly better than NL-PCA. Nevertheless, the
results of NL-PCA could be improved by adapting the parameters, and adding a weight
to the aggregation part, like BM3D does. Indeed the value of $N_{\hard}$ and
$N_{\wien}$ is not adapted to NL-PCA: this parameter has large values to avoid
non-invertible matrices, but the PCA can be hedged if patches in $\mP(\tilde P)$
are not that similar. Moreover, $\beta_{\hard}$ and $\beta_{\wien}$ need to be
adapted too.  NL-Bayes is faster than NL-PCA by an average factor of 50\%, due to
the fact that there is only one matrix inversion, and not a PCA.


\subsubsection{Ideal Wiener and upper bounds for the performance}


There is a significantly PSNR improvement by using the second step, because the
covariance matrix is better estimated. To judge the contribution of this second
step better, it is possible to compare it with an ideal Wiener filter, which is
obtained when the original noise-free image is taken as oracle reference, i.e. as
the output of the first step. This ideal Wiener filter is the best possible
estimate for the second step of this algorithm. It is therefore interesting to see
how far we stand from this ideal estimate with the current one:


\begin{center}
  \begin{tabular}{||c||c|c||c|c||}
   \hline
     & \multicolumn{2}{c||}{Algorithm} & \multicolumn{2}{c||}{Ideal Wiener}\\
   \hline
   $\sigma$ & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE}\\
   \hline
   \hline
   2 & 45.98 & 1.28 & {\bf 47.40} & {\bf 1.09}\\
   \hline
   5 & 39.89 & 2.58 & {\bf 41.50} & {\bf 2.15}\\
   \hline
   10 & 35.45 & 4.30 & {\bf 37.28} & {\bf 3.49}\\
   \hline
   20 & 31.26 & 6.97 & {\bf 33.42} & {\bf 5.44}\\
   \hline
   30 & 28.96 & 9.09 & {\bf 31.42} & {\bf 6.85}\\
   \hline
   40 & 27.46 & 10.81 & {\bf 30.13} & {\bf 7.95}\\
   \hline
   60 & 25.58 & 13.41 & {\bf 27.97} & {\bf 10.19}\\
   \hline
   80 & 24.29 & 15.57 & {\bf 26.66} & {\bf 11.85}\\
   \hline
   100 & 23.25 & 17.55 & {\bf 25.80} & {\bf 13.08}\\
   \hline
   \end{tabular}
\end{center}
Of course, the Wiener filter using the noise-free image as oracle is better than
the filter using the basic estimate obtained after the first step. One can see that
there is a large room for improvement for this first step, of 2 to 3 dBs. The
images below compare the visual performance for different values of the noise.
\ifpdf
\begin{changemargin}{-1.5cm}{0cm}
\begin{center}
	\begin{tabular}{c c}
		\includegraphics[scale=2.]{images/Ideal_wiener/valldemossa_half_part.png} & 		
		\includegraphics[scale=1.5]{images/Ideal_wiener/valldemossa_half_noisy_10_part.png} \\
		Original image & Noisy image ($\sigma = 10$)\\
	%\end{tabular}
	%\begin{tabular}{c c}
		\includegraphics[scale=1.5]{images/Ideal_wiener/valldemossa_half_nl-bayes_with_10_part.png} &
		\includegraphics[scale=1.5]{images/Ideal_wiener/valldemossa_half_nl-bayes_ideal_10_part.png}\\
		NL-Bayes ($\sigma = 10$)& Ideal Wiener ($\sigma = 10$)\\
	\end{tabular}
	\begin{tabular}{c c}
		\includegraphics[scale=2.]{images/Ideal_wiener/valldemossa_half_part.png} & 		
		\includegraphics[scale=1.5]{images/Ideal_wiener/valldemossa_half_noisy_30_part.png} \\
		Original image & Noisy image ($\sigma = 30$)\\
	%\end{tabular}
	%\begin{tabular}{c c}
		\includegraphics[scale=1.5]{images/Ideal_wiener/valldemossa_half_nl-bayes_with_30_part.png} &
		\includegraphics[scale=1.5]{images/Ideal_wiener/valldemossa_half_nl-bayes_ideal_30_part.png}\\
		NL-Bayes ($\sigma = 30$)& Ideal Wiener ($\sigma = 30$)\\
	\end{tabular}
	\begin{tabular}{c c}
		\includegraphics[scale=2.]{images/Ideal_wiener/valldemossa_half_part.png} & 		
		\includegraphics[scale=1.5]{images/Ideal_wiener/valldemossa_half_noisy_80_part.png} \\
		Original image & Noisy image ($\sigma = 80$)\\
	%\end{tabular}
	%\begin{tabular}{c c}
		\includegraphics[scale=1.5]{images/Ideal_wiener/valldemossa_half_nl-bayes_with_80_part.png} &
		\includegraphics[scale=1.5]{images/Ideal_wiener/valldemossa_half_nl-bayes_ideal_80_part.png}\\
		NL-Bayes ($\sigma = 80$)& Ideal Wiener ($\sigma = 80$)\\
	\end{tabular}
\end{center}
\end{changemargin}
\fi

\subsection{The ``paste'' option}


To speed up the algorithm, a paste trick has been used. Whenever a patch $\tilde Q
\in \mP(\tilde P)$ has an estimate, it is no more processed as a reference patch.
One could fear that this trick  produces artifacts and has an impact on the PSNR.
To check that, we will compare for both steps this paste option, denoted by
``\emph{paste}'' in the following, and another trick used in BM3D. This other
trick, denoted by ``\emph{step}'' divides approximately the number of processed
reference patches by nine, by taking a 3 pixels scanning step row and column.

\begin{center}
	\begin{tabular}{||c||c|c||c|c||c|c||c|c||}
		\hline
		Step 1 / Step 2 & \multicolumn{2}{c||}{\emph{Step} / \emph{Step}} & \multicolumn{2}{c||}{\emph{Paste} / \emph{Step}} & \multicolumn{2}{c||}{\emph{Step} / \emph{Paste}} & \multicolumn{2}{c||}{\emph{Paste} / \emph{Paste}}\\
		\hline
		$\sigma$ & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE}\\
		\hline
		\hline
		2 & 45.99 & 1.28 & 46.00 & 1.28 & {\bf 46.03} & {\bf 1.27} & {\bf 46.03} & {\bf 1.27}\\
		\hline
		5 & 39.81 & 2.61 & 39.84 & 2.59 & {\bf 39.87} & {\bf 2.59} & {\bf 39.87} & {\bf 2.59}\\
		\hline
		10 & 35.33 & 4.36 & 35.40 & 4.33 & 35.41 & 4.32 & {\bf 35.43} & {\bf 4.31}\\
		\hline
		20 & 31.25 & 6.98 & 31.27 & 6.96 & 31.30 & 6.94 & {\bf 31.31} & {\bf 6.93}\\
		\hline
		30 & 28.97 & 9.08 & 28.98 & 9.06 & 29.01 & 9.03 & {\bf 29.02} & {\bf 9.02}\\
		\hline
		40 & 27.35 & 10.94 & 27.39 & 10.89 & 27.40 & 10.87 & {\bf 27.43} & {\bf 10.84}\\
		\hline
		60 & 25.47 & 13.58 & 25.52 & 13.51 & 25.51 & 13.53 & {\bf 25.53} & {\bf 13.48}\\
		\hline
		80 & 24.16 & 15.79 & 24.22 & 15.68 & 24.20 & 15.73 & {\bf 24.24} & {\bf 15.66}\\
		\hline
		100 & 23.24 & 17.55 & {\bf 23.28} & {\bf 17.47} & 23.26 & 17.52 & 23.27 & 17.50\\
		\hline
	\end{tabular}
	
	
{\scriptsize In {\bf bold} the best PSNR for a given $\sigma$.}
\end{center}
There no significant loss in PSNR by using both acceleration tricks. The fact that
the use of the ``\emph{paste}'' option improves things could be explained by the
fact that in a area with many details, patches are very different in a very small
area. Then almost every patch will be treated as a reference patch, while with the
``\emph{step}'' trick only 1 patch out of 9 will be treated, and then very small
details will be processed worse. The use of this ``\emph{paste}'' trick speeds up a
bit more the algorithm than the ``\emph{step}'' trick, by almost 30\%, depending on
the percentage of homogeneous areas in the noisy image.


\subsection{Influence of the second step}
Using a second step to obtain a better covariance matrix improves a lot the final
result, as we can see in the following table:
\begin{center}
	\begin{tabular}{||c||c|c||c|c||}
		\hline
		 & \multicolumn{2}{c||}{First step} & \multicolumn{2}{c||}{Second step}\\
		\hline
		$\sigma$ & {\scriptsize PSNR} & {\scriptsize RMSE} & {\scriptsize PSNR} & {\scriptsize RMSE}\\
		\hline
		\hline
		2 & 45.65 & 1.33 & 46.03 & 1.27\\
		\hline
		5 & 39.41 & 2.73 & 39.88 & 2.58\\
		\hline
		10 & 34.84 & 4.62 & 35.45 & 4.30\\
		\hline
		20 & 30.47 & 7.64 & 31.24 & 6.99\\
		\hline
		30 & 28.15 & 9.97 & 28.99 & 9.06\\
		\hline
		40 & 26.58 & 11.95 & 27.46 & 10.80\\
		\hline
		60 & 24.15 & 15.80 & 25.50 & 13.53\\
		\hline
		80 & 22.87 & 18.32 & 24.25 & 15.64\\
		\hline
		100 & 21.92 & 20.43 & 23.27 & 17.51\\
		\hline
	\end{tabular}
\end{center}
