資料壓縮導論
===
###### tags: `大學必修-筆記`

CH1 Introduction
===
## Compression Model

$f(x, y)$ -> Source encoder -> Channel decoder -> channel (noise) -> Channel decoder -> Source encoder -> $f(x, y)$

## 壓縮指標

* Rate -> 壓縮完後檔案的大小
* Distorsion -> 失真
* Compression ratio ($C_r$) -> $C_r = \frac{原檔案的大小}{壓縮完的大小}$

## 為什麼資料可以被壓縮？
* 三個例子
1. 看整體圖的回歸線，把點和回歸線的距離回傳
2. 先傳第一個，之後的都看和前一個差多少
3. 看符號出現的頻率，頻率越多，編碼就會越少

CH2
===
## Information
* 機率愈小的事情發生時，資訊量愈大
* 如何計算 information surprise (機率小的事件)

$$
l(p) = log\frac{1}{p} = -logp
$$

* 符合 $I$ 與 $p$ 成反比
* 符合在 independent 的時候 $p(ab) = p(a) + p(b) = p(a) * p(b)$

## Entropy
* 平均資訊量
* 資訊理論 ->
* 一個資料的訊息量一定不會小於 Entropy (資訊量)
* 無失真壓縮也一定不會小於 Entropy
$$
Entropy = \sum_{p_i = 1}^{q}p_ilog_r(\frac{1}{p_i})\\
$$

## 例子

## Markov Models

* 1st order 馬可夫
* 現在發生的機率只會跟前一個事情有關
* 不會跟更之前的事情有關
$$
P(x_n|x_{n-1}) = P(x_n|x_{n-1}, x_{n-2}, x_{n-3})
$$

* $x_{n-1}$ -> 已經知道前一個資料發生的機率
* $x_{n}$ -> 來推斷現在資料發生的機率有多少
$$
H(S_w) = −P(b|w)* log P(b|w) − P(w|w) * log P(w|w)
$$
* 平均的 Entropy
$$
H = \sum_{i=1}^{M}P(S_i)H(S_i)
$$

* 機率公式
$$
p(w) + p(b) = 1\\
p(w) = p(w) * p(w|w) + p(b) * p(w|b)\\
p(b) = p(b) * p(b|b) + p(b) * p(b|w)
$$

## Coding
* 每一個編碼方法都只會有一個解碼方法 -> unique decodability
* 能即時解碼 -> instantaneous code
* ex：非即時解碼
$a_1$ -> 0
$a_2$ -> 01
$a_3$ -> 11

會有 011111111111... 的情況
$a_1 + a_3$ $a_2 + a_3$ 兩種可能
要一直到資料全部傳完才可以知道
到底中間有多少的 1

## Test for Unique Decodability
ex：
a = 010
b = 01011

010 -> prefix
11 -> dangling suffix

* 判斷是不是 unique
* 1. Entropy 是不是不合理
* 2. dangling suffix 是不是 編碼的其中一個
* 3. Kraft Inequality
$$
\sum_{k=1}^{n} 2^{-l_i} \leq 1
$$

* prefix 一定是 unique

CH3
===
* Huffman Coding
* 由機率出現小 編到 機率出現大的
* Shannon-Fano Coding
* 由機率出現大 編到 機率出現小的
* 切一半
* 每切一刀
* 編碼長度越長
* Huffman Conding's Entropy
* 在符號數不多的時候，最沒有效率
* 編碼會太長 -> 都是整數

$$
H(S) \leq l \leq H(S)+1
$$
* redundancy
* (average length - Entropy) / Entropy
* Extended Huffman Coding
* 用在符號數不多
* 機率分佈也不平均的情況下
* 改成使用一堆符號為一組來編碼
* ex：黑黑白 -> 0
* 白白白 -> 01 ……
* 還是不太好
* Adapive Huffman Coding
* http://ben-tanen.com/adaptive-huffman/
* 在畫tree的時候有兩個原則
1. 每一個結點一定會有兩個 leaf node
2. 從左到右從下到上數字一定要越來越大(與最近的同大小換)
* Adapive Huffman Decoding
* 取前 4 碼
* 如果這 4 碼 < 10
* 再往取後一碼
* 一共把這 5 碼變成 10 進位 後 +1
* 如果這 4 碼 > 10
* 直接把這 4 碼變成 10 進位 k+10+1

CH4
===
## Arithmetic coding
* 為了解決 adapive huffman coding
* 做了一堆完全不長見符號的編碼

$$
l^{(n)} = l^{(n-1)} + (u^{(n-1)}-l^{(n-1)})F_x(X_{n-1})\\
u^{(n)} = l^{(n-1)} + (u^{(n-1)}-l^{(n-1)})F_x(X_{n})
$$
* 一開始 $l^{(0)} = 0$、$u^{(0)} = 1$
* $F_x(1) = 0.8、F_x(2) = 0.82、F_x(3) = 1$

* 如果編碼長度為二進位，編碼長度一定要為：
$$
l(x) = \left \lceil log_2(\frac{1}{P(x)}) \right \rceil + 1
$$
* Entropy
* $H(S) \leq l_a \leq H(s) + 2$

## Scaling Decoding
* 原理
* 因為二進位的關係
* 只要我們知道當第二位的數字 < 0.5
* 就可以先送兩進位 0 過去了
* 反之 > 0.5
* 就可以先送兩進位 1 過去了

* 對於解碼端效率比較好
* 做法：
* 當 upper low bound 同時 < 0.5 -> $E(x) = 2x$
* 當 upper low bound 同時 > 0.5 -> $E(x) = 2(x - 0.5)$

CH8、9 - 失真壓縮
===
## 失真壓縮
* Quantization 量化
* 固定長度碼
* Encoder mapping
* D/A convertor -> 類比的轉化為數位的編碼
* Vector Quantization -> 向量量化
* encoder-decoder -> quantizer
* 在 0, 1 時誤差會最大
* 也可以改成用在接近 0 的時候分越多
* 遠離 0 分越少
* MSQE -> 誤差公式
* $$\sum_{i=1}^{k} \int_{t_i-1}^{t_i} (x-q_i)^2p(x)dx$$

## Quantization

* 如何設計間隔使得誤變小 -> 要看看資料分部
* Uniform Quantizler
* 每一個間隔都是一樣的
* 只需考慮間隔倒底要多長就好了
* 好容易設計
* 誤差可能會比較大
* 
* Non-Uniform Quantizler
* 非常困難去設計
* 
* Midrise Quantizer
* 在量化區中「沒有」包括 0
* 
* Midtread Quantizer
* 在量化區中「有」包括 0
* 

## Uniform Quantization distributed
* step size
* $$\Delta = \frac{2X_{max}}{M} ;(X_{max} - (-X_{max}))$$
* distortion

* $$\sigma^2 = 2\sum_{i=1}^{\frac{M}{2}} \int_{(i-1)\Delta}^{i\Delta}(x-\frac{2i-1}{2}\Delta)^2\frac{1}{2X_{MAX}}dx\\
\sigma^2 = \frac{\Delta^2}{12}$$

* signal-to-noise rate (SNR) 訊號雜訊比
* 信噪比越大 -> 噪音越小
* 每多一個 bit 編碼
* SNR 就會多 6.02 dB
* 
* 課本 example 9.4.2
* Mismatch Effects
* 
* SNR() 對 input variance/device variance
* 當 input variance 和 device variance 一樣的時候最好
* 當 input variance 比 device variance 小的時候是最不好的
* 因為 SNR = S/N ，當 S 比 N 小的時候，Ratio 出來的值就會越小，反之

* Companded Quantization

* Differential Encoding
* Transform Coding
* Adaptive Quantization
* 會有平均數跳掉的問題 -> 可以用 defferentral encodeing 解決
* 但數值跟平均的 variance 會一直改變
* 為了解決上面的問題
* Forward (off - line) adaptive approach
* 把一長串編碼分段，每一段都會有一個自己的 高斯分布及平均數，用自己的數值當作處理的依據
* x -> quantizer -> y ， y -> dequantizer -> z
* 解碼器並不知道原始資料倒底是什麼
* Backward Adaptive Approach
* 

* step size 會一直變
* 如果資料一直落在 0-4 之間 -> step size 設太大 -> 要變小
* 如果資料一直落在 3-7 之間 -> step size 設太小 -> 要變大
* $\Delta = M_{l(n-1)}\Delta_{(n-1)}$
* 
* 

## Nonuniform Quantizer
### Companded Quantization
* 實際上跟本做不太到
* 但我們可以用 compressor 外加 高斯分佈，就可以做到類似 Nonuniform 的效果了
* 
* 會考(給定函數和反函數的公式算)
* 
* 

### Pulse Code Modulation
* 對於音訊來說是一個很好的壓縮方法

CH11 Differential Encoding
===
* 用資料之間的差值來編碼
* 如果單純用差值的話，誤差會不斷的累積
* 
* 應該要減掉前一個重建值才行，不能直接減掉前一個
* 
* 這是流程圖
* 

## Differential pulse code modulation (預測編碼) DPCM
* Delta Modulation
* 一維 -> 只有 01 -> 只考慮跟前一個數字是大還是小
* 明顯有缺點
* 當實際數值突然變化很大的時候 -> 誤差會很大

## ADPCM

CH12 Transform coding
===
### orthogonal transform
* Karhunen-Loeve Transform (KLT)
* Optimal transform
* function 和 images 是 dependance
* 沒有快速演算法
* Discrete Fourier Transform
* 有 Fast Fouier Transform (FFT)
* Discrete Cosine Transform
* 只使用 (DFT) 中的 cos + jsin -> cos (只用實部)
* 會考簡答題
* DCT vs DFT
* 圖像處理 DCT 之後的矩陣大的幅度系數都集中在左上角
* DFT 轉換後的圖像會出現不必要的高頻項
* https://www.zhihu.com/question/26244854
* Transform coding 最主要的功能是把一張圖片
* 化簡成一個座標軸上，方便我們分析
* 但做完這一步是不會造成失真的
* 最主要造成失真的地方是在 quantization
* 上圖 DCT 兩個重點
1. 可以把一張圖片分成很多不同的頻率相加
2. 真正的失真壓縮是在 quantizer 的時候
比如在高頻地方把所以人耳聽不到的高頻都拿掉

CH13 JPEG
===
* JPEG 的壓縮方法
* 下圖是一個 8x8 的灰階圖片
* 經過 DCT 運算得
* 給定一個 quantization table 把 DCT 的表 除以 table
* 再取整數得下面的圖
* 最後再把結果放進 huffman coding 去做編碼

## zigzag scan
* 目的把一個二維的圖轉化成一維
* 方便我們 huffman coding
## DC components & AC components
* DC components (整個 block 的平均值) -> DPCM -> zigzag 的第一個值
* AC components -> Run length code -> zigzag 之後的值
* 把這一個的 DC component 減掉 前一個的 DC component
* 得到一個數字
## run length code
* 把中間產生的 0 去掉
* 
* -> 17 (0, 8) (0, 54) (3, 97)...
## DC label
* 目的用來分群用
* 為了要加快速度
* 不然我們的 huffman code 會超極長一串
* 在哪一群裡面就要多少個 bit 去編碼
* ex：7 在第三群的最後一個 -> 第三區編碼 + 111
## huffman coding AC label
* 
* x/y -> 前面有幾個 0 / DC component 是在哪一區 + 第幾個
* x/y 直接對表
* EOB -> 1010

## 名詞定義
* Chroma Subsampling
* 人類對彩度是不敏感的
* 人類對黑白影像比較敏感
* 所以在彩色的圖上面可以在壓縮更多的東西
* YCbCr
* Quaitilation table 跟黑白的不一樣
* 可以比較粗糙一點
* Y 可以說它就是灰階開片
* Cb 是藍色色差
* Cr 是紅色色差
* 4:2:2 即是把後面兩個通道的訊號抽掉一半
* 

Reference
===
* 課本
http://dbq.multimediatech.cz/users/vitek/private/d/Introduction-to-Data-Compression-Fourth-Edition-Khalid-Sayood(www.ebook-dl.com).pdf
* Entropy
https://courses.cs.washington.edu/courses/csep521/99sp/lectures/lecture10/sld001.htm