Scalar Quantization
Most texts give some fairly lengthy academic treatment to the subject of quantization. This article will focus on the bare essentials that a multimedia hacker needs to know in order to be productive with the concept.
Theory
Quantization in multimedia compression is primarily a matter of division (for quantization) and multiplication (for dequantization, a.k.a. requantization).
This type of quantization is also referred to as scalar quantization, as opposed to vector quantization. Many references describe quantization in an impossibly abstract mathematical manner. Implementation-wise, quantizing a number usually boils down to this:
original_number / quantization_factor = quantized_number
Dequantization entails the following operation:
quantized_number * quantization_factor = original_number (or, hopefully, some close approximation of original_number)
It's basic division and multiplication. In doing so, the numerical precision is effectively reduced. If a particular number has a range of 0..499, there are 500 possible numbers. But if the number is quantized (divided by) 5, the quantized numbers will only range from 0..99 for a total of 100 possible numbers. Dequantizing (multiplying) will also mean that there are still only 100 possible numbers:
0 5 10 15 20 25 30 … 485 490 495
Let’s look a string of numbers that might be quantized in practice:
83 13 21 5 4 2 1 5 6 2 1 2 2 1 3 1
Let’s apply a quantization factor of 5. Thus, we divide each number by 5 and throw away the remainder:
16 2 4 1 0 0 0 1 1 0 0 0 0 0 0 0
Let’s examine what just happened. First, the numbers all got a lot smaller. Smaller, or similar, numbers require less information to code using methods like differential coding. Not only that, a bunch of the numbers turned into zeros. Run Level Coding exploits this artifact of quantization.
During dequantization, the quantization factor is multiplied by each number and we get:
80 10 20 5 0 0 0 5 5 0 0 0 0 0 0 0
The original string was this:
83 13 21 5 4 2 1 5 6 2 1 2 2 1 3 1
Something happened. Namely, information was lost during the coding process. Multimedia compression algorithms are often lossy in order to achieve greater compression than they could with a lossless algorithm. Quantization is where a lot of that fabled information loss occurs. In fact, have you ever seen multimedia compressors which allow you to configure “how much compression” you want? This is where that configurability usually matters. By making the quantization factor (i.e., divisor) larger, the quantized numbers get smaller, more numbers turn into zeros, and more overall information is lost (and more compression is achieved).
While it is possible to quantize a string of numbers using just one quantization factor– and certain codecs do this– it is much more common for a codec to use a string of quantization factors, one for each of the numbers in the string to be quantized or dequantized. These strings will typically be referred to as either vectors or matrices. Using an entire quantizer vector or matrix, it is possible to throw away more information for the numbers that do not have as much effect. In this example string (now called a vector):
83 13 21 5 4 2 1 5 6 2 1 2 2 1 3 1
Note that the beginning numbers are much larger than the numbers at the end. This is often the case in situations where quantization is to be applied. The beginning numbers are more important and the numbers decrease in significance toward the end of the vector. Thus, smaller quantizers can be applied at the start of the vector, and larger quantizers can be applied at the end. For example:
2 2 2 2 3 3 3 4 4 4 5 6 7 8 9 10 11 12
In this example, the first 3 numbers will be quantized to:
41 6 10
and dequantized to:
82 12 20
which is a little more accurate than:
80 10 20
which we got when we used the uniform quantizer of 5.
What A Multimedia Hacker Needs To Know
Much multimedia compression research is focused on quantization patterns and how to apply them in such a way as to throw away just the right amount of information but not too much. As mentioned before, some codecs apply a uniform quantizer everywhere and some apply quantization vectors or matrices. Many codecs define different quantization matrices depending on which video plane is being operated upon. Some codecs encode information in a compressed video frame’s header to adjust quantizer matrices on each frame. Some codecs go even further to be able to adjust the quantization scheme on particular areas of the video frame.
Further Reading
- Wikipedia's treatment of quantization as it pertains to signal processing