# DCT and Hard Thresholding

If I have an Image and i find the DCT and then apply hard thresholding on the coefficients and then IDCT then I have attenuated the noise. Can someone please explain in detail or point me to the answer as to why this works. I understand why a filter blocking high frequency will work in denoising(because we assume that noise consists of high frequency components) but why does magnitude thresholding work?

Low-pass filtering is based on the assumption that "natural" images have more energy in the low-frequency coefficients than in the high frequency coefficients ; while noise will affect equally all coefficients. Thus, removing the high frequency coefficients will comparatively eliminate more noise than signal. The problem is that there are "legit" high-frequency coefficients in images, such as edges. Denoising by low-pass filtering will attenuate those coefficients and cause edge blurring.

The property used in magnitude thresholding is sparsity - "natural" images are very likely to have only a small set of high non-zero coefficients in the frequency domain. Adding uniform (and independent from pixel to pixel) noise is equivalent to adding a small random value to all the frequency coefficients. The result is that all the coefficients that were 0 in the original image now have a small value ; while the coefficients that were high in the original image are comparatively untouched. Thresholding the small magnitude coefficients will cancel the contribution on noise on those coefficients - though it will not recover the effect of noise on the high coefficients.

If you replace edges by transients/attacks, the same thing applies to sounds by the way.

Have a look on the following optimization problem:

$$\arg \min_{x} \frac{1}{2} {\left\| A x - y \right\|} + \lambda {\left\| x \right\|}_{0}$$

Where ${\left\| \cdot \right\|}_{0}$ is counting the number of non zero elements.

It is known that Iterative Hard Thresholding can be utilized to solve this and in some cases guaranteed to find the correct solution (See Iterative Hard Thresholding for Compressed Sensing).

Now, if you use $A$ as the DCT Dictionary (Which you can and many do) then basically what you do is trying to solve this.

This is the optimization point of view.
The reason why it works so well, the idea of sparse (Low degree of freedom) representations?
Well, the simple intuition is efficiency.
Things should be simple when one use the right tools to describe them.

Great place to have in depth look into is eDx - Sparse Representations in Signal and Image Processing: Fundamentals by Michael Elad.

DCTs are very useful at energy compaction, so simply put after a DCT of an image is resolved to a weighted some of some basis functions. After a DCT, the resulting matrix will contains multipliers for each basis function. And one can without loss of generality say that the high value coefficients are the ones that contribute significantly to the psycho-visual perception of the image by the human eye.

Low frequency noise will add to the low frequency coefficients, however high frequency noise will result in smaller magnitudes of the resulting transformed matrix's high frequency coefficients.

So when we magnitude threshold the transformed matrix, we eliminate all noise that isn't a part of the high magnitude coefficients. So some noise will still be present that may be apparent after the IDCT.

But the main idea here is in images where high frequency data is minimal, a DCT, followed by magnitude thresholding will probably do better than a typical High Pass Filter. If one can imagine an image where any frequency in the image has a real image component and a noise component, where the real image component is small or zero, a DCT followed by magnitude thresholding will eliminate that frequency component, thereby mostly targeting the noisy component.