About quantization

The process of requantization (generally, but inaccurately, described as "quantization") plays an important role in how JPEG encoding reduces the number of bits required to describe an image.

But there are common misunderstandings about just how it does that. I'll try and clear some of those up.

************

Quantization

Quantization (often called quantizing, a perfectly-good synonym) refers to the process of taking a quantity that is continuous (that is, can take on any value we can imagine, albeit perhaps over a finite range) and restating it as if it were composed on an integral number of some unit (that unit being considered a quantum, thus the name).

My body temperature might be 98.6283618274691820...° F. But if I measure it with my handy digital fever thermometer, it reports is as "98.6°F". The continuous value has been quantized to units of 0.1° F.

Precision

We can say that the temperature, as measured and reported, has a precision of 0.0° F. If it had been quantized to units of 0.01° F, we could say that its precision was 0.01° F. Qualitatively, we can speak of the precision with a larger unit as "coarser", or with a smaller unit as "finer".

Requantization

Suppose we have a list of the weights of four lathes being readied for shipment by rail. The weights in pounds are (always integers - that's the precision of our weighing department):

4356
2780
4875
5125

We want to send the list to a logistics broker, who will arrange for the shipment. If we send the list as is, it will take 16 decimal digits (never mind delimiters and such).

But the broker doesn't need to know the weights to such precision. The freight tariffs all work in hundreds of pounds.

Now we heard that if we make the data have a more coarse precision, we will need fewer digits to transmit it. Lets try that.

We will requantize the data to a precision of 100 units, giving:

4300
2700
4800
5100

Now we send it, but that still takes 16 decimal digits, What went wrong?

Attaining the reduction in the required number of digits.

Well, to actually reap the advantage of the more coarse representation, we need to send:

43
27
48
51

That will only take 8 decimal digits.

The broker, knowing that we send weights quantized to 100s, multiplies each by 100, getting:

4300
2700
4800
5100

the numbers that he needs. (It is only at this point that true quantization of the four numbers has been accomplished.)

Where does the advantage come from?

Note that it is not the fact that the data is now more coarsely quantized that actually leads to the saving in number of digits to be sent. It is that the numbers are now smaller (which of course is only possible, with integer values, if we accept that they are more coarsely quantized, compared to their size).

Best regards,

Doug

Hi Doug,

Thanks for the examples. Presumably in reality a value such as your 2780 would actually or get quantised as 2800 (or 28), rather than 2700, or does quantising just remove precision without regards to rounding? The former would obviously be preferable, but I suspect the latter easier from an algorithm point of view.

Thanks,
Andrew

Hi, Andrew,

Andrew Stannard said:

Thanks for the examples. Presumably in reality a value such as your 2780 would actually or get quantised as 2800 (or 28), rather than 2700, or does quantising just remove precision without regards to rounding? The former would obviously be preferable, but I suspect the latter easier from an algorithm point of view.

Click to expand...

Well, it can be done both ways (true rounding being "better" in many cases), but I did not mean to imply one or other by my example. I just wasn't careful about the numbers I used. I should have used examples where either procedure gave the same result, since that difference is not what I was trying to illuminate!

Thanks for calling attention to that.

Actually, to fit with my "story", where the numbers were used to determine freight costs, in reality we would probably want to "round up", so the story isn't the best one either!

Best regards,

Doug

As a follow on, we might ask, "To what precision is this number stated: '4500'?"

The answer is, we can't tell by looking at it; we must know the circumstances of its birth. If this quantity is only allowed to have values that are integer multiples of 100, then it is to a precision of 100.

If so, and if the largest value that this quantity can have is 9900, then can't we convey it to somebody in only two decimal digits?

The answer is yes, but only if we are a little clever. We of course can't send "4500", which takes four digits. (Duh!) But we can send "45" (although the recipient must understand what the unit is to be able to work with the number).

So how do we take a bunch of numbers, none over 9900, that we only need to know to
"hundreds", requantize them to that precision, and send them compactly to another place?

Well, here's one description:

a. Round the number to the precision unit (100): 5435->5400 [The number is now at reduced precision]

b. Divide that by the precision unit: 5400->54 [The number, at reduced precision, is now "compacted"]

c. Send that: 54 (be sure the recipient knows what the "unit" is)

d. The recipient multiplies the number by the precision unit (100): 54->5400 [This is the number, at reduced precision, that we assume the recipient needs to use]

But here's another description with step a expanded:

a1. Divide the number by the precision unit (100): 5430->54.35

a2. Round that to an integer: 54.35->54

a3. Multiply that by the precision unit (100): 54->5400 [the number is now at reduced precision]

b. Divide that by the precision unit (100): 5400->54 [the number, at reduced precision, is now "compacted"]

c. Send that: 54 (be sure the recipient knows what the "unit" is).

d. The recipient multiplies the number by the precision unit (100): 54->5400 [This is the number, at reduced precision, that we assume the recipient needs to use]

But doing a3 and then b seems dumb. Instead we can just do:

a1. Divide the number by the precision unit (100): 5430->54.35

a2. Round that to an integer: 54.35->54 [the number is now at reduced precision and compacted]

c. Send that: 54 (be sure the recipient knows what the "unit" is.

d. The recipient multiplies the number by the precision unit (100): 54->5400 [This is the number, at reduced precision, that we assume the recipient needs to use]

Note that in the JPEG specification, step d is called "dequantizing". That is not apt.

While this step does increase the precision to which the number is held (remember, this is internal to the JPEG decoder, so there is no "cost" to that, and doing so is needed to make the math work properly), it does not increase the precision of the number! It lost its original precision at step a2. Like virginity, precision, once lost, is not to be regained.

Best regards,

Doug

Hi,

Thanks for the clarification regarding rounding. It would be interesting to see what is done in real-time compression (e.g. Video streaming). I'd imagine that in those circumstances it is considerably more efficient to just throw away a few of the least significant bits than worrying about rounding up or down.

Regards,
Andrew

In physical science we call this "significant digits", as quantization has a more precise meaning. As in the sentence "The energy of a bound electron is quantized." The algorithm of reducing a number from a calculation to it's significant digits based on the precision of it's measurement is also about four discrete steps long.

Hi, Chris,

Chris Heilman said:

In physical science we call this "significant digits",. . .

Click to expand...

Quite. I avoided that phrase in my note just for "simplicity".

... as quantization has a more precise meaning. As in the sentence "The energy of a bound electron is quantized." The algorithm of reducing a number from a calculation to it's significant digits based on the precision of it's measurement is also about four discrete steps long.

Click to expand...

Indeed!

As you well recognize, often in these areas I face the dilemma of trying to be fully rigorous while still maintaining "accessibility".

And (as you often see me comment), in many of the areas we encounter, the use of terminology is rather "mindless".

For example, in the JPEG encoding scheme, at one point certain a certain DCT coefficient is encoded based on its change from block to block, a process to which is applied the moniker "differential pulse code modulation". This is a term borrowed from the field of digital encoding of audio or video waveforms, and not a very good term there anyway (it emerged in a curious historical way), but which has almost no relationship to what is being done in JPEG.

Thanks for your insights.

Best regards,

Doug