Natural Image Denoising and inherent limits

This work was inspired by an article published in 2011 about inherent limits in image denoising. In that article, a new method for denoising images (that has been called shotgun denoiser), based on the model of the space of natural patches derived from a large database of samples, was described. This method was only of theoretical interest, since the computational requirements to actually use it are prohibitive. In this work that method is described, analyzed and transformed to make it possible to run it on a normal computer. In order to do so, a new denoising formula has been derived, on a database of normalized patches extracted from noiseless natural images. The factorization of the probability space of the natural images allows to increment the performance of the original algorithm by severals orders of magnitude, by working with entire equivalence classes instead of single patches. Methods for further accelerating the process are described, and a survey is made on the algorithms for approximate nearest neighbour search in space with high dimensionality. An usable algorithm is then described and its performance is throughly tested over some test images. The result of this algorithm is compared to other state-of-the-art denoising methods, and although on average the method devised is a bit worse than others, in the parts of the image with more details it actually outperforms the best existing denoising algorithm