# About image compression vs. DCT

I have recently started reading about image processing, my knowledge in image processing is still very limited.

What I understood that DCT can help in image compression using Huffman, JPEG or MJPEG encoding.

My question, If we have an image as below:

which means that we have only three possibilities, 1, -1 or 0 in every pixel. they are distributed randomly, what I know that every column has 4 zeros and other values either 1 or -1. they are distributed randomly.

After performing DCT transformation, Does that compression for that image can be done efficiently, Compared with the image which is full of 1 and -1 without any zeros. How far can we compress that image perfectly? Finally, which encoding algorithm can be used perfectly in that case ?

Thank you so much in advance.

I think that DCT mainly helps with samples that are spatially correlated. The DCT is a linear transform that 1)does energy compaction quite close to the theoretically optimal PCA/KLT transform (representing as much of the signal energy as possible using as few coefficients as possible) for many «typical» images, 2) it can be computed efficiently using FFT-like machinery, and 3) it has an intuitive structured interpretation that gives it meaning beyond a black box ML algorithm for the typical engineer.

See eg these discussions:

https://hydrogenaud.io/index.php/topic,53232.25.html#msg481661

When you explicitly say that there is no spatial correlation, I think that any coding that models the code probabilities is going to be optimal.

• Thank you for your reply. Could you please explain point 3 with details? What you mean "it has intuitive structured interpretation that gives it meaning beyond a black box ML algorithm for the typical engineer". Mar 2, 2020 at 4:31
• With the dct you could say that «ah, high frequency components does not matter that much to the human visual system, lets encode them with less precision». That is much harder than to say something sensible about a PCA component. Mar 2, 2020 at 4:36
• I am so sorry. I didn't get what you mean. is it possible to explain more, please? ... thanks again for your feedback. Mar 2, 2020 at 4:40
• The dct carried the idea of «frequency». Many engineers are trained and have intuition about the frequency domain where 3 Hertz is less than 100 Hertz. The dct has an ordered frequency domain interpretation. If some other transform was used, it might not have an intuitive frequency domain interpretation. Mar 2, 2020 at 4:55
• Alright. do you have any document and reference I can read about that ? Mar 2, 2020 at 9:19

they are distributed randomly, what I know that every column has 4 zeros and other values either 1 or -1

compression for that image can be done efficiently, Compared with the image which is full of 1 and -1 without any zeros

Since your spatial representation is already very sparse, it's likely that the DCT will reduce the compressability.

Simple calculation:

# naive storage

That's a matrix of $$7\cdot 8 =56$$ entries, each of which takes one of 3 states, so 2 bits per pixel, so 112 bits in total.

# non-zero position + sign storage

We can calculate the column entropy rather easily:

• For the non-zero positions, you have 8 choose 4 different options, $$\binom84=70$$; so the info in that is $$-\log_2\left(\frac1{70}\right)$$; You can store that in 7 bit without thinking much. Just write a table of all possible non-zero positions, and number that.
• If we consider the sign of the nonzero entries as bits, that's 4 bits of information.

So, the entropy in each column is $$\log_2(70)+4\approx 10.13$$ bit.

So, per column you need 11 bits, so with 7 columns in total 77 bits, and would, without any compression, have represented your whole image.

If we look at the 7 columns as whole, that's $$70^7< 2^{43}$$ possibilities of non-zero positions, i.e. we can reduce the overall storage needs to $$43+7\cdot4=71$$ bits. Again, no entropy coding necessary.

# DCT first, entropy coding later

If you do a DCT on each column, you'll need all 8 entries; every DCT bin can take at least 5 values, so it needs 3 bit each, so 24 bit per column, so 148 bits in total.

Since the $$70\cdot16$$ (see above) different possible input columns are equally likely, so are the $$70\cdot16$$ possible DCTs; the information in seeing any one of these thus is $$-\log_2\left(\frac{1}{70\cdot16}\right)\approx10.13$$ bit. Since they don't have any correlation, entropy coding can, at the very best case compress your seven columns to 70.90 bits, ie. 71 bits in storage. But that case can never be achieved – that would work with an infinitely large image, not one with but 7 columns.