1
$\begingroup$

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:

enter image description here

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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". $\endgroup$ – Fatima_Ali Mar 2 '20 at 4:31
  • $\begingroup$ 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. $\endgroup$ – Knut Inge Mar 2 '20 at 4:36
  • 1
    $\begingroup$ I am so sorry. I didn't get what you mean. is it possible to explain more, please? ... thanks again for your feedback. $\endgroup$ – Fatima_Ali Mar 2 '20 at 4:40
  • $\begingroup$ 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. $\endgroup$ – Knut Inge Mar 2 '20 at 4:55
  • 1
    $\begingroup$ Alright. do you have any document and reference I can read about that ? $\endgroup$ – Fatima_Ali Mar 2 '20 at 9:19
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ "So don't do the DCT in this synthetic example" So which one is better to be used in that case?. you said, we need 7 bits, for positions and 4 for information, it means we did use any compression technique ! right? $\endgroup$ – Fatima_Ali Mar 1 '20 at 16:30
  • $\begingroup$ Read my answer again. I specifically recommend a method. No, that's not "compression" in the sense that it doesn't use any source statistics. This is just using a sensible storage format to begin with. $\endgroup$ – Marcus Müller Mar 1 '20 at 16:33
  • $\begingroup$ .. and I specifically said that there is no transformation that improves the situation. $\endgroup$ – Marcus Müller Mar 1 '20 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.