The Statistical Convergence Theory of Non Local Means and Its Extension

    We introduce an oracle filter for removing the Gaussian noise with weights depending on a similarity function. The usual Non-Local Means filter is obtained from this oracle filter by substituting the similarity function by an estimator based on similarity patches. When the sizes of the search window are chosen appropriately, it is shown that the oracle filter converges with the optimal rate. Based on our convergence theorems, we propose some simple formulas for the choice of the parameters. The implementation of the proposed algorithm is also straightforward and the simulations show that our algorithm improves significantly the classical NL-means and is competitive when compared to the more sophisticated NL-means filters both in terms of PSNR values and visual quality.