VII. Data Compression (A) 壓縮的通則： 利用資料的一致性 資料越一致的資料，越能夠進行壓縮 [References] I. Bocharova, Compression for Multimedia, Cambridge, UK, Cambridge University Press, 2010. 酒井善則，吉田俊之原著，原島博監修，白執善編譯，“影像壓縮術” ，全華印行, 2004. 戴顯權，“資料壓縮 Data Compression,” 旗標出版社, 2007. D. Salomon, Introduction to Data Compression, Springer, 3rd ed., New York , 2004.

 7-A 壓縮的哲學： 244 (1) 利用資料的一致性，規則性，與可預測性 (exploit redundancies and predictability, find the compact or sparse representation) (2) 通常而言，若可以用比較精簡的自然語言來描述一個東西，那麼也就越能夠對這個東西作壓縮 Q: 最古老的壓縮技術是什麼？ (3) 資料越一致，代表統計特性越集中 包括 Fourier transform domain, histogram, eigenvalue ……….. 等方面的集中度

Compression technique 245 Data type Compression technique Compression rate Audio Image Video

246 思考：如何對以下的資料作壓縮 Article: Song: Voice: Cartoon: Compression: Original signal Compact representation + residual information

 7-B Compression for Images  影像的「一致性」： Space domain: 每一點的值，會和相鄰的點的值非常接近 F[m, n+1]  F[m, n], F[m+1, n]  F[m, n] Frequency domain: 大多集中在 低頻 的地方。

Lena Image 在 space domain 上的一致性 248 Lena Image 在 space domain 上的一致性 (horizontal difference) (vertical difference)

249 Histogram: 一個 vector 或一個 matrix 當中，有多少點會等於某一個值 例如：x[n] = [1 2 3 4 4 5 5 3 5 5 4] 則 x[n] 的 histogram 為 h[1] = 1, h[2] = 1, h[3] = 2, h[4] = 3, h[5] = 4

250 Lena Image 頻譜 (frequency domain) 的一致性 L[m, n] |fft2(L[m, n])| (用亮度來代表 amplitude) p q

251 影像的「頻率」：frequency in the space domain 從 m = 0 至 m = M-1 之間有 p 個週期 p = 5 larger p : more variation in the space domain

Process of JPEG Image Compression 252  7.C JPEG Standard Process of JPEG Image Compression Image 88 DCT AC係數 Zigzag Scan Huffman Coding JPEG file 4:2:2 or 4:2:0 量子化 8 × 8 (切成blocks) DC係數 差分 編碼 Huffman Coding 量子化表 檔頭 主要用到四個技術：(1) 4:2:2 or 4:2:0 (和 space domain 的一致性相關) (2) 8  8 DCT (和 frequency domain 的一致性相關) (3) 差分編碼 (和 space domain 的一致性相關) (4) Huffman coding (和 lossless 編碼技術相關)

253 JPEG： 影像編碼的國際標準 全名： Joint Photographic Experts Group JPEG 官方網站： http://www.jpeg.org/ 參考論文：G. K. Wallace, “The JPEG still picture compression standard,”  IEEE Transactions on Consumer Electronics,  vol. 38, issue 1, pp. 18-34, 1992. JPEG 的 FAQ 網站： http://www.faqs.org/faqs/jpeg-faq/ JPEG 的 免費 C 語言程式碼： http://opensource.apple.com/source/WebCore/WebCore-1C25/platform/image-decoders/jpeg/ 一般的彩色影像，可以壓縮 12~20 偣。 簡單的影像甚至可以壓縮超過 20 倍。

254  壓縮的技術分成兩種 lossy compression techniques 無法完全重建原來的資料 Examples: DFT, DCT, KLT (with quantization and truncation), 4:2:2 or 4:2:0, polynomial approximation 壓縮率較高 lossless compression techniques 可以完全重建原來的資料 Examples: binary coding, Huffman coding, arithmetic coding, Golomb coding 壓縮率較低

 7-D 4:2:2 and 4:2:0 255 R: red, G: green, B: blue Y: 亮度, Cb: 0.565(BY), Cr: 0.713(RY), 4 : 4 : 4 4 : 2 : 2 4 : 2 : 0 N N Y Y M M Y N/2 N N M/2 Cb Cb M/2 Cb M N/2 N N M/2 Cr M/2 Cr M Cr

256 24 bits/pixel  16 bits/pixel  12 bits/pixel 同樣使資料量省一半的(b)(d)圖，(d)圖和原來差不多， 然而(b)圖邊緣會有失真現象。 還原時，用 interpolation 的方式

257 原圖 直接在縱軸取一半的pixels 再還原 (a) (b)

258 4 : 2: 2 4 : 2: 0 (c) (d)

 7-E Lossy Compression Techniques -- KLT 259  7-E Lossy Compression Techniques -- KLT 複習：DFT 的優缺點 Karhunen-Loeve Transform (KLT) (similar to Principal component analysis (PCA)) 經過轉換後，能夠將影像的能量分佈變得最為集中 It is optimal, but dependent on the input  1-D Case K[u, n] = en[u] (K = [e0, e1, e2, ….., eN1] en 為 covariance matrix C 的 eigenvector mean C[m, n] = corr(x[m], x[n]) = Note: corr代表correlation

260 KLT 的理論基礎： 經過 KLT 之後，當 u1  u2 時，X[u1] 和 X[u2] 之間的 correlation 必需近於零 (即 decorrelation) 即 corr(X[u1], X[u2]) 所以 Since if for all u The above equation can be simplified as:

261 Note that is the (u1, u2)th entry of E{XXT} where Since where K is the KLT matrix where C is the covariance matrix and corr(x[m], x[n]) = To make when u1  u2 should be a diagonal matrix Therefore, the KLT transform matrix K should diagonalize C. That is, the columns of K are the eigenvectors of C.

262  2-D Case KLT 缺點: dependent on image (不實際，需要一併記錄 transform matrix) Reference W. D. Ray and R. M. Driver, “Further decomposition of the Karhunen-Loeve series representation of a stationary random process,” IEEE Trans. Inf. Theory, vol. 16, no. 6, pp. 663-668, Nov. 1970.

 7-F Lossy Compression Techniques -- DCT 263  7-F Lossy Compression Techniques -- DCT Suboptimal, but independent of the input  DCT: Discrete Cosine Transform C[0] = , C[u] = 1 for u  0 IDCT: inverse discrete cosine transform 對於大部分的影像而言， DCT 能夠近似 KLT (near optimal) 尤其是當 corr{f[m, n], f[m+, n+]} =  ||  || ,   1 時 有 fast algorithm Advantage: (1) independent of the input (2) near optimal (3) real output

264 DFT for Lena image DCT for Lena image Comparing with the DFT: (1) 能量更為集中 (2) Real output (3) 一樣都有 fast algorithm

左圖：將 DFT，DCT 各點能量(開根號)由大到小排序 右圖：累積能量 265 左圖：將 DFT，DCT 各點能量(開根號)由大到小排序 右圖：累積能量 DCT output k k Energy concentration at low frequencies: KLT > DCT > DFT

266 通常，我們將影像切成 8  8 的方格作DCT Why: N image 8 x 8 方格 M

267 References [1] N. Ahmed, T. Natarajan, and K. R. Rao, “Discrete cosine transform,” IEEE Trans. Comput., vol. C-23, pp. 90-93, Jan 1974. [2] K. R. Rao and P. Yip, Discrete Cosine Transform, Algorithms, Advantage, Applications, New York: Academic, 1990.

附錄八：量測方法的精確度常用的指標 268 方法判斷為真 事實上為真 TN FN TP FP TP (true positive): 事實上為真，而且被我們的方法判斷為真的情形 FN (false negative): 事實上為真，卻未我們的方法被判斷為真的情形 FP (false positive): 事實上不為真，卻被我們的方法誤判為真的情形 TN (true negative): 事實上不為真，而且被我們的方法判斷成不為真的情形

269 (positive prediction rate) 以抓犯人為例，TP 是有罪而且被抓到的情形，FP是無罪但被誤抓的情形，FN 是有罪但沒被抓到的情形，TN 是無罪且未被誤逮的情形 寧可錯抓一百，也不可放過一個 recall 高，但 precision 低 寧可錯放一百，也不可冤枉一個 precision 高，但 recall 低

270 Accuracy Detection error rate F-score General form of the F-score