How Compression works
Author: @Hsu Tzu Ting Date: Dec 24, 2020 性質: Tech Share
- remove redundancy
Lossless Compression (無失真)
→ text and data files
RLE (Run-length encoding)
Huffman Code (bottom up)
- Uniquely decoded
- Prefix property (→ no prefix)
Shannon-Fano (top down)
LZ77
- Compression time vs. Required memory
Lossy Compression (失真)
→ multimedia data
Quantization 量化
- 將一個包含很多可能值的集合用一個較少個值的集合來表示的過程
{x | x∈R, 0 ≤ x ≤ 7} → {x | x∈Z, 0 ≤ x ≤ 7}
GIF
- 將一個包含很多可能值的集合用一個較少個值的集合來表示的過程
Transform coding
- 透過數學轉換映射到另一個值域
- 常常跟量化一起使用
RGB → YCbCr
Y: brightness of the color (明度)
→ more sensitive to the human eye
Cb: blue component relative to the green component (彩度)
→ less sensitive to the human eye
Cr: red component relative to the green component (彩度)
→ less sensitive to the human eye
example
DCT
Perceptual coding
- 壓縮的好壞誰說的算？（數學公式 or 人）
- 心理聲學 ex. Auditory masking effect
- 壓縮的好壞誰說的算？（數學公式 or 人）
Image
JPEG
- 壓縮技術
- .jpeg, . jpg, .jpe ...... 使用這個技術做圖片壓縮
Transform coding: RGB → YCbCr
Chroma subsampling 色彩採樣
- (J, a, b)
- J: horizontal sampling reference (width, usually 4)
- a: number of chrominance samples (Cr, Cb) in the first row
- b: number of changes of chrominance samples (Cr, Cb) between 1st and 2nd row
- (J, a, b)
DCT Transformation
- 8 pixels x 8 pixels
Encoding
- 壓縮技術
Video
without compression: 1920x1080pixels / frame = 2073600 pixels / frame = 60M pixels / second
Long sequence of images
- 單一 frame 的 compression → Spatial Compression (Intraframe)
- 使用圖片壓縮 → JPEG
- frame 與 frame 之間的 compression → Temporal Compression (Interframe)
- Temporal redundancy
- eg. 背景圖片，基本上連續好幾個 frame 都有
- Inter-frame Similarity
- eg. 移動的車子
- 透過移動、旋轉 patches，所以不用 retransmit
- Temporal redundancy
- 單一 frame 的 compression → Spatial Compression (Intraframe)
MPEG
- I-frame
- 資料量最大
- 不需要參考其他 frame
- 做 Spatial Copression (類似JPEG)
- P-frame
- 參考前面的 I-frame，預估移動向量
- B-frame
- 資料量最小
- 參考 I-frame, P-frame，做一些預估＆修改
- I-frame
Compression Failure
I-frame 壞掉或來不及運算更新frame
Reference
How data compression works: exploring LZ77