1
$\begingroup$

For a given quality of image (or quality of compression), Multiple 8x8 JPEG images can have the same DCT (Discrete cosine transform) matrix, for a given quality of JPEG compression. I want to find the number of those 8 by 8 JPEG files which have different DCT codes.

I write the question in a different way:

Assume a set $A$ of images, which is initially empty. We consider all possible DCT's for 8 by 8 Jpegs one by one, and convert each one to an image. If the image already exists in the set $A$, we throw it away, otherwise, we put it in set $A$. After we are done with all possible DCT's, how many images are in the set $A$? (what is the cardinality of $A$?)

Wikipedia has the formula for the DCT conversion. But I cannot realize from that how to find what I need. I am wondering how to solve it or if that is already solved in the literature. Any idea?

Improve this question
$\endgroup$
7
  • $\begingroup$ I am not sure what is your task. Do you want to find the number of all 8x8 image blocks that map to given DCT with provided quality? For example given DCT matrix like this at the bottom you want to calculate the number of inputs returning this matrix? This is for one channel only? The result also depends in color format and discarded info. $\endgroup$
    – Evil
    Feb 22 '17 at 18:37
  • $\begingroup$ It depends on what quantization tables you use, quality level is not standard. $\endgroup$
    – harold
    Feb 22 '17 at 18:37
  • $\begingroup$ @harold thanks. Yes, let's assume for a given quantization table. Then, what would be the answer? $\endgroup$
    – Su20200
    Feb 22 '17 at 18:55
  • 1
    $\begingroup$ @evil Let's consider one channel only. Finding the images that map to the a given DCT is a different problem that I need help about too. Assume we have a set $A$ of images which is initially empty. We consider all DCT's one by one, and convert each one an image. If the image already exists in the set $A$, we throw it away, otherwise, we put it in set $A$. After we are done with all possible DCT's, how many images are in set $A$? $\endgroup$
    – Su20200
    Feb 22 '17 at 19:05
  • 1
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/70674/755, cstheory.stackexchange.com/q/37604/5038, math.stackexchange.com/q/2156611/14578, dsp.stackexchange.com/q/37833/5874, stackoverflow.com/q/42400916/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W.
    Feb 22 '17 at 21:34
3
$\begingroup$

Well, $8\times 8$ is simply 64 individual values.

Now, if you had a quantization matrix $Q$ (dimensions $8\times 8$) with all $1$s, you'd have 8 bit to spend on every entry in your DFT, so that's

$$(256)^{8 \times 8}=({2^8})^{(8 \times 8)} = 2^{512}$$

possible different DFTs.

Now, typically, that's not happening, since quantization matrices restrict the possible values that can end up being non-zero.

The number of possible values is relative easy to figure out: You take the maximum value for each entry, 255, and divide it by the quantization matrix value, round that down; that leads you to the number of possible combinations being

$$ N = \prod_{i = 1, j = 1}^{8,8} \left\lfloor\frac{255}{Q_{i,j}}\right\rfloor$$

Improve this answer
$\endgroup$
7
  • $\begingroup$ haha, feeling punny today, @Fat32? $\endgroup$
    – Marcus Müller
    Feb 22 '17 at 21:20
  • $\begingroup$ actually feeling sleepy! $\endgroup$
    – Fat32
    Feb 22 '17 at 21:38
  • $\begingroup$ Thanks. But, this is the total number of possible DCT matrices for a given quantization matrix Q. Note that not all of them yield a valid output JPEG, i.e, if you take the inverse DCT, you will not necessarily achieve a valid JPEG whose pixel values are in the valid range. I need the number of DCT matrices that yield a JPEG whose pixel values are in the valid range [0,255]. $\endgroup$
    – Su20200
    Mar 1 '17 at 16:51
  • $\begingroup$ @Su20200 that's not true. You can DCT any possible 8x8 pixel 8bit block, and then quantize, and then IDCT. That's always "valid". Since the Quantization method reduces the energy in any coefficient, the likelihood of actually getting a value > 255 out of the DCT is very slim, and even if that happens, I'd be surprised if JPEG didn't specify saturating logic for that case. $\endgroup$
    – Marcus Müller
    Mar 1 '17 at 18:45
  • $\begingroup$ @MarcusMüller Thank's. But, I need a precise answer that ensures nothing wrong happens after IDCT $\endgroup$
    – Su20200
    Mar 1 '17 at 19:31
1
$\begingroup$

JPEG compression basically consists of a DCT transform followed by quantization.

Hint #1:

The DCT transform is invertible (reversible; a one-to-one mapping). Only the quantization can introduce "collisions".

Hint #2:

Ignore the DCT for a moment, and focus only on the quantization step. Given the output of the quantization step, and given a particular quality level (i.e., quantization settings), can you count how many possible inputs (to the quantization step) there are that map to that output?

Now put together your answers to these two hints, and you should be able to answer your own question.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. But, this gives me is the total number of possible DCT matrices for a given quantization matrix Q. Note that not all of them yield a valid output JPEG, i.e, if you take the inverse DCT, you will not necessarily achieve a valid JPEG whose pixel values are in the valid range. I need the number of DCT matrices that yield a JPEG whose pixel values are in the valid range [0,255]. $\endgroup$
    – Su20200
    Mar 1 '17 at 16:51

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.