About image compression vs. DCT

Question

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.

Answer 1

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.

Answer 2

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.

conclusion

for your 8×7 image:

• intuitive storage format that just saves the non-zero positions + signs: 71 bits
• unachievable asymptotic compression = entropy of the source: 70.9 bits

So, in this case, there's an "obvious" storage format with negligible redundancy. Thus, entropy coding (Huffmann etc) makes no sense. And, since your original image is already very sparse, any transformation, but especially the DCT, only makes compression harder.

So don't do the DCT in this synthetic example.