The following information represents the comprehensive notes from the ‘’Video Communication Course 2022 (Part6)’’. These notes provide the fundamental concepts, principles, and practical applications covered in the course. They serve as a valuable resource for students and professionals seeking to enhance their knowledge and skills in the field of video communication.
Part6 contains the following sections
- Entropy
- Still Image Compression
- Quantization
- Components of a Quantizer
- Vector Quantization (VQ)
Entropy
In information theory, entropy refers to the average amount of information or uncertainty contained in a random variable or a message. It measures the amount of surprise or unpredictability in the outcomes of a random process. A random variable with high entropy has many equally probable outcomes and carries more information, while a random variable with low entropy has fewer possible outcomes and carries less information.
Entropy has various applications in different domains. In data compression, it is used to measure the optimal length of a code to represent a set of symbols, where more frequent symbols are assigned shorter codes to reduce the average code length. In machine learning, entropy is employed as a criterion in decision tree algorithms to determine the best splits for classification or regression tasks. It is also used in the field of image processing, cryptography, and many other areas where the quantification of randomness or uncertainty is relevant.
Overall, entropy provides a useful framework for understanding and quantifying randomness, disorder, and uncertainty across different disciplines.
<Proof>
The maximum of p*log2 (1/p) occurs at p=1/e
Consider the distribution consisting of just two events.
Let “p” be the probability of the first symbol (event).
Calculate “p”, when H(P) has the maximum value?
Design Huffman tree, and calculate entropy.
(Entropy value can represent your coding method performance)
Still Image Compression
JPEG
- Block-based
- DCT
- Quantization
- Entropy coding
VQ (Vector Quantization)
- Block-based
- Quantization
What’s the difference between JPEG & VQ?
The VQ performs better at higher compression ratios (typically, Cr > 35). JPEG is a standard for still image compression using DCT. Its theory is based on the characteristics of the human eye:
- The human eye is less sensitive to chroma than brightness.
- Human eyes are less sensitive to high-frequency information than low-frequency information.
Quantization
In Lossy compression, the simplest and most common method. Quantization plays a very important role in lossy data compression.
The purpose of quantification is usually to reduce the amount of data.
Quantization
- a process of representing a large (possibly infinite) set of values with a much smaller set.
用一些小的集合來表示一個大的（可能是無限的）集合的過程。
Scalar Quantization
- a mapping of an input value x into a finite number of output values, y （Q: x >>> y） 將輸入值 x 映射到有限數量的輸出值 y
Components of a Quantizer
Encoder
- Correspond data to their respective intervals.
將data對應到各自所在的intervals - Each interval will have its own code-word.
將data對應到各自所在的intervals - The mapping of data to interval is a many-to-one mapping, so it is irreversible (irreversible mapping)
data映射到interval是一種多對一的映射，所以是不可逆的（irreversible mapping）
Decoder
- According to code-word, give the possible value of source.
根據code-word，給出source可能產生的值 - Usually it will be the middle point in the interval.
根據code-word，給出source可能產生的值
How to find the optimal partition?
Loop through each possible value (0~100) for 8 partitions.
for i1 in range(0, 100):
for i2 in range(0, 100):
for i3 in range(0, 100):
for i4 in range(0, 100):
for i4 in range(0, 100):
for i5 in range(0, 100):
for i6 in range(0, 100):
for i7 in range(0, 100):
for i8 in range(0, 100):Vector Quantization (VQ)
Lossy compression method. Famous algorithm：LBG algorithm
Vector quantization is actually to find nearby predetermined points as a representative of an interval, thereby simplifying the amount of data.
In order to require the lowest distortion, a minority representative vector (code vector) that can be calculated to minimize the distortion is needed, and this group of code vectors is called codebook.
- Pros
- Reduced storage space.
- Has a simple decoding method, only needs to look up the table through the index (Table lookup) to complete the decoding.
- Compression is also high and has a lower bit rate.
- Better performance than JPEG within the same bit-rate. - Cons
- Time consuming. Codebook design and compression takes a lot of time. Most of the time is spent finding the nearest code vector and computing vector distances.
- And the image quality after compression is highly correlated with the quality of the codebook.
- For signals with different statistical characteristics, it is often necessary to design different codebooks before they can be used in practice.
How to deal with signal dependent?
If generate codebook with 1000 images, the codebook could be more generalize. Using larger dataset, the codebook can deal with more different incoming image.
LBG algorithm
- Pros
- Most popular
- Simplicity - Cons
- Local optimal
- Slow
Workflow:
- Determine the number of code vectors N.
- Select N code vectors at random to be the initial codebook.
- Using the Euclidean distance measure cluster the vectors around each code vector.
- Compute the new set of code vectors (codebook).
- Repeat Steps 2 and 3 until the either the representative code vectors do not change.
Thank you for taking the time to read this article, and I sincerely hope that the information provided proves to be valuable to you. Whether you are a student, professional, or simply someone interested in video communication, it is my utmost wish that these notes enhance your understanding and contribute to your success in this field. Thank you once again, and best of luck on your journey in the world of video communication!
