  The Non-Local Means (NLM) image denoising algorithm pushed the limits of
denoising. But it introduced a new paradigm, according to which one could
capture the similarity of images with the NLM weights. We show that, contrary
to the prevailing opinion, the NLM weights do not allow to get a reliable
measure of the similarity in a noisy image, unless one add a locality
constraint. As an image denoising method, the Non-Local Means prove to be
local. Some works had already pointed out that to get the best denoising
performances with the NLM algorithm, one should run it locally. But no general
conclusion has been yet proposed and the only explanation that was proposed to
justify the experimental results is not sufficient. Our study based on
experimental evidence proves that, on average on natural images, the bias of
the NLM estimator is an increasing function of the radius of the similarity
searching zone. The reason for this phenomenon is that noise disrupts the order
of similarity between patches. Hence the mean squared error between the
original image and the NLM estimation, which is the sum of the bias, the
variance and the covariance of the estimator, has an absolute minimum for a
disk of radius 3 to 4 pixels.
