Random Noise Removal In Images

Question

I'm trying to remove random noise from an image. The noise is arbitrarily random so it must not necessarily follow a certain distribution (Not every pixel has the same chance of being affected by noise and not every pixel is affected by the same amount of noise). Such an image might for example look like this example image:

The usual fast'n'cheap filters (like average etc.) just do not cut it for such images. It's pretty obvious that there's still enough information in the image left for it to be reconstructible but I don't think there's yet a tool available that can actually do that. Any hints on how I could try reconstruction? Tools, algorithms?

Update 1

The closest I've come so far is this:

It's far from being good but just to show what I mean by removing the noise. The resulting image should have more or less uniform areas of about the correct colors.

An ideal outcome would roughly look like this:

Update 2

Example with little noise

Example with more noise

Update 3

PNG images:

For the lena fans out there:

Answer 1

There are a lot of ways to do image denoising.

I will give several known examples:

1. Hard/soft thrsholding of the wavelet decomposition: Do a wavelet decomposition of the image and for zero all coefficients less than some minimum value and linear the other values.

2. Non Local Means: We use the fact that for "natural images" for each patch in the image we can find very similar other patches in the image. So for each pixel we look at the neighborhood around him and we search for other pixels that has the same neighborhood and than we use those patches to calculate the value of the original pixel.using the fact that the patches are very coorelated but the noise isn't.

3. Block Match 3D: We do the same as before finding similar patches around the image and than we arrange them as a 3D block and apply wavelet thresholding. This is more complicated and you can read about this. A basic scheme for this is:

There a lot more ways and just by googling it you will get a lot of information hope this basic intro will help you enough.

Answer 2

There are various methods for denoising image signals. With a preface about image sparsity I'm going to provide some matlab code. Images are sparse in nature, not in spatial domain, but in some domains as Fourier, DCT or Wavelets domain. If you take a look at FFT of an image you'll find out only a few coefficients are non-zero, as figure below depicts fft2 of your image:

imshow(log10(abs(fftshift(fft2(Image)))),[])

and in fact image compression algorithms like JPEG take advantage of this property of images. This Sparsity property also can be exploited for denoising images. If you transform an image into wavelet domains, the random noise like the above mentioned noise tends to spread out its coefficient, however coefficients related to the image tend to concentrate to only a few bins. Therefore, the most basic, simplest technique would be sorting FFT, DCT of Wavelet coefficients of image in order of magnitude, making zero all coefficient which are smaller than a threshold and finally transforming the image back into the spatial domain. Based on this idea, some soft/hard thresholding algorithms appeared. A good Matlab implementation on this regard can be find in following page, where they provide wavelet based denosing tools:

http://eeweb.poly.edu/iselesni/WaveletSoftware/denoise.html

Another technique to take advantage of sparsity is $l_1$ regularization. Look, it is proven under some assumptions, $l_1$ norm can be used as representation for number of nonzero coefficients ($l_0$ norm, you can find the proof in Compressive Sensing literate).

Note again, random noise tend to form a non-sparse representation in transform domain (e.g white noise has flat representation in frequency). So if we define a convex optimization problem in which we try to build an image which preserve energy of noisy image and also tries to minimize number of nonzero coefficients in transform domain we would remove noise. The problem usually defined as below:

$$D = \arg \min_d ||I-d||_2 + \lambda|| f(d) ||_1 $$

Where, $D$ is denoised image, $I$ is noisy image, $f$ is transformation operator (e.g. DFT matrix) and $\lambda$ is regularization factor. The first term tries to make $D$ closer and closer to original image, and the second term tried to keep $D$ as sparse as possible. Through solving the above problem, we would remove noise from the image.

For solving this optimization problem CVX toolbox might be used. I am not sure that the code below in CVX toolbox would work, just try to give you the idea:

I=imread('J13Wn.jpg');
I=double(I);
Rn=I(:,:,1); 
Rn=imresize(Rn,[256 256]); % for out of memory error in my computer
B=dctmtx(256);
cvx_begin
variable R(256,256);
minimize(norm(Rn-R,2)+0.1*norm(B*R,1));
cvx_end

if it did not work, try this toolbox: http://www.cs.tut.fi/~foi/GCF-BM3D/