\section{Introduction}


Image denoising is the first  step of any image processing chain. If the digital
image were completely noise-free, we would have access to an infinity amount of
information. Thus, every means to increase the signal to noise ratio must be
explored. Early studies applied linear Wiener filters equivalent to a frequency
reduction of the Fourier transform. These filters are more efficient when applied
locally on the DCT (Yaroslavsky et al. \cite{DCT1}, \cite{DCT2}). More recently
studies proposed non-linear variational methods like the total variation
minimization, Rudin et al. \cite{ROF}. Still more recently several methods have
gone back to the idea of a Wiener filtering but with other linear transforms, and
propose thresholding the wavelet transform, Donoho et al.
\cite{Wavelet_thresholds}. In 2005 have appeared the so-called patch-based methods.
The Nonlocal-means method, Buades et al. \cite{NLM}, \cite{buades2006review} seems
to be one of the first of this kind, followed by other many. Patch-based denoising
methods have been understood as parsimonious but redundant representations on
patches dictionaries, as proposed by Elad et al. \cite{Elad06}, Mairal et al.
\cite{Mairal08}, \cite{mairal2008learning}, Yu et al. \cite{yu2010image}. This
parsimonious decomposition method has become a paradigm for all images restoration
tools, including also de-blurring or in-painting.


The BM3D method  (Dabov et al. \cite{BM3D}) is probably the most efficient
patch-based current method. It merges the local DCT thresholding-based method and
the non-local means method based on patches comparison. Indeed, BM3D creates a 3D
block with all patches similar to a reference patch, on which a 3D transform
thresholding is applied.


A more recent NL-means variant shares with BM3D the idea of applying a transform
threshold to the 3D block. This method, due to Zhang et al. \cite{tsid}, replaces
the DCT by an adaptive local linear transform, the principal component analysis
(PCA). The method proceeds in two identical steps which can only be distinguished
by the noise parameter that is used. Like BM3D the method creates an array of
vectors with all patches similar to a reference patch. A linear minimum mean square
error (LMMSE) method is applied on the obtained coefficients before applying the
inverse transform. Unlike for BM3D, only the estimate obtained for the reference
pixel is kept. The second step attempts to remove the noise left by the first step.
A similar enhancement for the BM3D method replacing the DCT by a local PCA on
similar blocks (with adaptive shape) has also been considered in
\cite{dabov2009bm3d}. Nevertheless, according to this paper, the performance gain
with respect to BM3D is very modest.


Nevertheless, there is another way of thinking about denoising, based on the
Bayesian approach. These Bayesian approaches have been proposed as early as 1972 in
\cite{richardson1972bayesian}. Being first parametric and limited to rather
restrictive Markov random field models \cite{Geman}, the Bayesian method has also
expanded recently to non-parametric methods. The seed for the recent non parametric
estimation methods is a now famous algorithm to synthesize textures from examples
\cite{Efros99}. The underlying Markovian assumption is that, in a textured image,
the stochastic model for a given pixel \textbf{i} can predicted from a local image
neighbourhood $P$ of \textbf{i}, which we shall call ``patch''.


As we will see in this paper, the Bayesian approach can be merged with Fourier
methods like BM3D, in a new method called NL-Bayes. A natural extension of this
method, called NL-PCA in the following, can be seen as we described it as a fusion
of BM3D and TSID, where NL-PCA begins and ends like BM3D, the only change being the
use of the PCA instead of the DCT or Bi-orthogonal spline wavelet.


Since the link with BM3D is very important, the algorithm description will follow
closely the one used in BM3D. Each step of the NL-Bayes algorithm is realized in
three parts: a) finding the image patches similar to a given image patch and
grouping then in a 3D block; b) Collaborative Filtering; then c) aggregation. The
collaborative filtering is realized in two parts: a) applying the Bayes' formula on
the 3D block; and b) repositioning the 3D block. This 3D filtering filters jointly
a group of 2D image blocks. Since these filtered patches overlap, many estimates
are obtained which need to be combined for each pixel. Aggregation is a particular
averaging procedure used to take advantage of this redundancy.


The paper is organized as follows. We introduce the Bayes' theory in Section
\ref{section:theory}. The developed image denoising algorithm is described in
Section \ref{section:implementation}. The detailed study of its parameters and
variance can be found in Section \ref{sec:study}. Experimental results and
comparison to several state-of-the-art denoising algorithm is given in Section
\ref{section:comparisons} and Section \ref{section:conclusion} contains relevant
conclusions.

A complete presentation of the theory underlying Nonlocal Bayes, and a discussion
of all related algorithms, is done in the companion paper
\cite{nonlocalbayesSIIMS}, submitted to SIIMS.
