# sparse representation for image denoising

When I read papers on image denoising, I always encounter sparse representation. For image denoising, we try to separate image signal from noise. It is assumed that signal is correlated and noise is uncorrelated. Sparse representation represents one signal as a linear combination of a small number of dictionary elements. It hope to use as few as non-zero coefficients to represent signal. In my view, it is appropriate for image compression. How can it is related to image denoising?

• Would you agree to the following saying (In the context of Dictionary Learning): Image Denoising and Image Compression differs by the number of Atoms in their dictionary, namely how many realizations of the data they can represent. To me, when dealing with denoising the amount of data to be lost is up to the level important details are lost. In compression, the amount of data to be lost depends on the bandwidth limitations. Given infinite bandwidth, denoising is like the Optimal Compression. This is all intuitive.
– Royi
May 11, 2016 at 15:21
• Currently I am learning sparse representation. From what I know, the dictionary for image denoising is overcomplete and the dictionary for image compression is orthogonal transforms. You mentioned that when dealing with denoising the amount of data to be lost is up to the level important details lost. My understanding is :If the contrast in the original image is below three times standard deviation of noise, the contrast will be considered as noise and will be lost. Am I right? May 12, 2016 at 4:58
• You talk about details. I just tried to convey that the concept of Compression and Denoising is the same where the only difference is how much details you are willing to give up on.
– Royi
May 12, 2016 at 7:00

I will start the explanation from the compression viewpoint. There are two main types: lossless compression, and lossy compression. Noise, at least divergence or loss from the original data, arises only with lossy compression.

When one considers the original data as the "clean" reference, lossy compression adds a amount of loss related (generally vaguely increasing) to the compression ratio allowed.

However, it is interesting to take another perspective, which I borrow from Filtering Random Noise from Deterministic Signals via Data Compression, 1995, B. K. Natarajan, that I found influential.

The main idea starts from the observation that noise (with a sense of randomness, lack of predictability) is hard to compress, while structured signals possess a certain amount of correlation that somehow can be compacted. In other words, when data is easy to compress, it is likely to be structured.

This led Natarajan to the definition of Occam filters, a name related to W. of Ockham and his (alleged) law of parsimony. Starting from noisy data, one compresses it to a loss close to the original noise power. If the compression system is well designed, this tends to remove (partly) some noise from the original signal. Shocking enough, lossy compression can denoise, killing two birds (denoising and compression) with one stone. This can be found for instance in Adaptive wavelet thresholding for image denoising and compression, 2000, where the noise limit can be made adaptive.

Sparse representations, such as the wavelets above, but other transforms as well, have been found since effective at concentrating the energy of the structured signals, and at spreading or whitening some random noises. Being sparse, the sparse representation of the image has structures easy to compress, and spread noises. The very same action of obtaining a sparse representation is a good preprocessing for both compression and denoising.

Note however that some abuse about "compression". Actual compression encompasses quantization, coefficient location, entropy coding, etc., and merely producing few large coefficients and many zeroes does not really qualify for compression.

Finally, the analogy between compression and image denoising is not valid for all images, all types and levels of noises, but it is sufficiently correct in standard cases to allow them to be taught together.

• if you have a sparse or compressible signal $x$ (in some representation $f$), and add uncorrelated noise $n$ to it, then applying $f$ on $x+n$ is not denoising per se, because for denoising you need to decide, or choose, what to keep as a signal component and what to filter as a noise. But it generally provides:

• a clearer "distinction" between them, in terms of (local) amplitude, that often simplify the use of statistical tools, or make them more robust
• better access to signal, or noise, properties, to parametrize the denoising
• orthogonal transformations are quite good, but the orthogonality limit their ability to sparsely represent signals. Overcomplete transforms induce correlations in the noise (Noise Covariance Properties in Dual-Tree Wavelet Decompositions), but as the signal coefficients are sparser, the relative amplitude of (sparse) signal coefficients and noise is (optimally) more favorable. Examples of correlated noise whitening with for instance redundant complex wavelets can be found for instance in the above reference or Removal of Correlated Noise by Modeling the Signal of Interest in the Wavelet Domain.

Of course, a lot the above assumes that the signal is sparse, that the noise is not correlated, and that you are able to find a proper representation, which is not evident in practice.

• Do you mean that the process of obtaining sparse representation is also the process of separating signal from noise. Usually orthogonal transforms are used to deccorrelate signal but can't deccorelate noise because noise is assumed to independent. In sparse representation, why an overcomplete dictionary can separate signal from noise? You mention that Sparse representations can spread or whiten some random noise. Can you clarify that? May 12, 2016 at 5:11
• I remember in one book that it says noise after orthogonal transformation follows the same distribution and only distribution parameters is changed. The noise is still independent statistically. You mean after overcomplete dictionary is performed, the noise becomes correlated. Can you give some documents on it? May 13, 2016 at 1:24
• I will try to give one example. For one 8x8 block, a wavelet or DCT can be applied and then hard/soft thresholding is performed to reduce noise. It always results in blurred edges. Can non-local means algorithm be considered as sparse representation method? It doesn't use linear combination of the dictionary. May 13, 2016 at 2:01
• @Jogging Song As I said, a sparse representation requires adapted compression or denoising methods. Standard scalar thresholding is not the best of important noises, but I feel this discussion exceeds the initial question May 13, 2016 at 8:13
• From the definition of sparse representation, one signal is represented as a linear combination of a small number of atoms. Today I encounter one paper, it says that "In the spatial domain, image sparsity arguments imply that for any image patch, there will be similar ones in other locations of the image. " NLM is not a sparse representation method, and it just utilizes image sparsity. Am I right? May 20, 2016 at 13:13

Here are two interpretations of why sparse representations are useful for denoising:

1) Your clean image is well represented by your dictionary (usually a wavelet or 2D-DCT dictionary), but the noise isn't. This means that when calculating your sparse representation from the noisy signal, you will only capture the clean signal, and not the noise.

2) Enforcing the representation vector to be sparse (i.e. with only a few non-zero elements), means that you will eventually threshold out all the other low-energy noisy components.

As you said sparse representations can be pretty useful for compression. Compression is merely about keeping the relevant information, while discarding the irrelevant one. Well denoising is about keeping the relevant part of your signal (the one that fits your model, or your dictionary), while discarding the irrelevant one (the noise).