VII. Data Compression (A)

Presentation on theme: "VII. Data Compression (A)"— Presentation transcript:

1 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.

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

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

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

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

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

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

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

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

10 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 編碼技術相關)

11 253 JPEG： 影像編碼的國際標準 全名： Joint Photographic Experts Group JPEG 官方網站： 參考論文：G. K. Wallace, “The JPEG still picture compression standard,”  IEEE Transactions on Consumer Electronics,  vol. 38, issue 1, pp , 1992. JPEG 的 FAQ 網站： JPEG 的 免費 C 語言程式碼： 一般的彩色影像，可以壓縮 12~20 偣。 簡單的影像甚至可以壓縮超過 20 倍。

12 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 壓縮率較低

13  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 : : 2 : : 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

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

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

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

17  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

18 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:

19 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.

20 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 , Nov

21  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

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

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

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

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

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

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

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