四川大學(xué)多媒體課件3

1、數(shù) 據(jù) 壓 縮一、Information Theory二、Why Compression ?三、How to Compress?四、Lossless Compression五、Lossy Compression六、JPEG七、JPEG2000八、MPEG standards1. MPEG Video2. Scalable MPEG-2 Video3. MPEG Audio1一、信息理論概述信息理論之父為什么壓縮?如何壓縮?無損壓縮 Lossless compression有損壓縮 Lossy compression圖象 Image視頻 Video聲音 Audio未來?2信息理論之父 Claud

2、e ShannonBorn: 30 April 1916 in Gaylord, Michigan, USADied: 24 Feb 2001 in Medford, Massachusetts, USA3信息理論之父 Claude Shannon (續(xù))The founding father of electronic communications ageAmerican mathematical engineerIn 19361940, MIT: Masters thesis, A symbolic analysis of relay and switching circuitsDocto

3、ral thesis: on theoretical geneticsIn 1948: A mathematical theory of communication, landmark, climax(An important feature of Shannons theory: concept of entropy )4二、為什么壓縮? 任務(wù)：存儲和傳送多媒體信息.Example:(1) Text: Word documentchp09.doc:12.3 MBchp09.zip: 907 KB (WinZip 8.0)chp09.rar: 767 KB (WinRAR 2.7, Finla

4、nd)5為什么壓縮? (續(xù))(2) Digital camera (image), Card with 64 MBpicture: 1280 pixels/line960 lines/picture3 B/pixel 3.6864 MB/pictureTotal (without compression): 64 MB/(3.6864 MB/picture) 17 picturesTotal (with compression)：198 picturesCompression ratio: 198/52 11.647 picture: 640 4803：0.9216 MB/pictureTot

5、al (without compression): 69 picturesTotal (with compression)：663 picturesCompression ratio: 663/69 9.54726為什么壓縮? (續(xù))(3) Audio: e.g.CD-Audio： 44 100 samples/s 16 B/samples 2(left, right) = 1.4112 Mb/s !MP3: - Near CD: 96 kb/s Compression ratio: 15:1 - CD: 112 128 kb/s Compression ratio: 10 12:1 7為什么

6、壓縮? (續(xù))(4) Video, e.g. DVD-Video: (假設(shè)子采樣為 4:2:2)Y(亮度):720576258 83 Mb/s (PAL)720480308 83 Mb/s (NTSC) Cr(紅色差), Cb(藍(lán)色差):2360576258 83 Mb/s (PAL)2360480308 83 Mb/s (NTSC)Total: 166 Mb/s !Average bit rate: 4.1 Mb/s Compression ratio: 40:18為什么壓縮? (續(xù))解決辦法: 更高帶寬 減少傳輸位數(shù)來傳送未壓縮信息內(nèi)容？其他 ?9 文件編碼（coding ）減少存儲空間和

7、傳輸時間普遍使用的文本、圖象、聲音、視頻（text, images, sound, ，video）文件轉(zhuǎn)換成bit數(shù)較少的文件這種壓縮文件（compressed files）以后可以擴(kuò)展成為原來形式，顯示或執(zhí)行為什么壓縮? (續(xù))10壓縮算法更適合某種類型文件的壓縮算法，如：JPEG, GIF圖象MPEG視頻通用壓縮算法（不考慮數(shù)據(jù)表達(dá)的類型），如：zip and pkzip for DOSstuffit for Macintosh operating systemsandcompress (using gzip) for UNIX operating systems.為什么壓縮? (續(xù))11

8、三、如何壓縮?數(shù)據(jù)（Data）:數(shù)據(jù)冗余（Data Redundancy）聲音（Audio）: 人聽覺系統(tǒng)能力數(shù)據(jù)冗余視頻（Video）: 人視覺系統(tǒng)能力數(shù)據(jù)冗余12壓縮類型無損壓縮Lossless (entropy coding)不丟失信息 (即, 信號解壓decompression后完全復(fù)原)產(chǎn)生可變長位（variable bit-rate）不保證實際上減少數(shù)據(jù)長度有損壓縮 Lossy丟失某些信息 (即, 解壓decompression后信號不能完全復(fù)原)產(chǎn)生任意固定位constant bit-rate13數(shù)據(jù)源Data Sources數(shù)據(jù)源有N個符號組成每個符號用 log2N 位表示 聲

9、音speech: 16 bits/sample: N = 216 = 65,536 symbols 彩色圖象color image: 38 bits/sample: N = 22 4 = 1.6777216106 symbols 88的 圖象塊: 864 bits/block: N = 2512 = 1077 symbols14四、無損壓縮Lossless Compression編碼：把每個符號“翻譯”成一個二進(jìn)制碼（binary codeword）每個二進(jìn)制碼可以不同長度，目標(biāo)是平均碼長最小。減少平均碼長的基本思路：出現(xiàn)次數(shù)多的符號翻譯成較短二進(jìn)制碼；出現(xiàn)次數(shù)少的符號翻譯成較長二進(jìn)制碼mor

10、e frequently symbols shorter codewords less frequently symbols longer codewords15熵 ：符號i在信息源中出現(xiàn)的概率l(i) ： 符號i的二進(jìn)制碼長度平均碼長 L=iN=1 p(i) l(i)16熵熵的定義 (Entropy):熵是信息源平均信息量，是信息源的特性當(dāng)所有符號概率相等時，熵的最大值為log2N ；當(dāng)符號概率相差大時，熵的值較小。冗余量：iN=1 p(i) l(i)-H最優(yōu)碼：冗余量最小的編碼 編碼符號的平均二進(jìn)制碼長度 信息源的熵（entropy H ）(熵是最小平均碼長) 17熵 0.25,0.25,

11、0.25,0.25 1,0,0,018熵假定：某些符號出現(xiàn)概率比其他符號大例：N = 8 symbols: a,b,c,d,e,f,g,h, 3 bits per symbol (N =23=8)P(a) = 0.01 P(b) =0.02 P(c) =0.05 P(d) =0.09 P(e) =0.18 P(f) =0.2P(g) =0.2 P(h) =0.2519Huffman coding20Huffman coding平均代碼長度 (編碼前):熵:平均代碼長度 ( Huffman coding):21Shannon-Fano coding符號出現(xiàn)的次數(shù)分配的代碼需要的位數(shù)A15 (0.

12、375)1.41500030B7 (0.175)2.51450114C7 (0.175)2.51451014D6 (0.150)2.736911018E5 (0.125)3.00001111522Shannon-Fano codingShannon-Fano 算法步驟：Step1：將源符號及其概率按非增次序排列；Step2：將符號分成概率和最接近的兩組（各1/2），第1組以0開始編碼，第2組以1開始編碼；Step3：每組重復(fù)Step2，在已有編碼后按規(guī)則追加0/1，直到每個組只有一個符號時，算法終止。優(yōu)點： 簡單；不保證最優(yōu)； H+1平均碼長H23Shannon-Fano coding & H

13、uffman coding例124Huffman coding靜態(tài)Huffman編碼算法步驟：Step1：以每個源符號的概率為權(quán)，組成N個只有根節(jié)點的二叉樹的集合；Step2：將2個權(quán)值最小的二叉樹wi和wj,合并成一個根為wi+wj,的二叉樹，其左、右子樹分別為wi和wj, ，將wi+wj 插入到集合中，并將wi和wj從集合中刪除；Step3：重復(fù)Step2，直到集合只有一個權(quán)值；Step4：從根到每一葉子節(jié)點（源符號）路徑上（左0右1）的字符串即為該符號的編碼。評價： 最優(yōu)碼（最小冗余）25Shannon-Fano coding & Huffman coding例2：“aa bbb ccc

14、c ddddd eeeeee fffffffgggggggg”26Shannon-Fano coding & Huffman coding 例2：“aa bbb cccc ddddd eeeeee fffffffgggggggg”27數(shù)據(jù)壓縮的模型建立建立模型（modeling）： 給消息源中每一符號指定概率建立模型的方式:靜態(tài)的(static)：對所有信息源使用同一模型； 半自適應(yīng)的：對每一信息源使用一種模型（壓縮之前掃描一遍信息源或其樣本） ； 自適應(yīng)的（adaptive）：最初按照某一假定模型，在壓縮/解壓進(jìn)行中，同步更改模型（即增、減所壓縮/解壓符號的概率）28數(shù)據(jù)壓縮的模型建立數(shù)據(jù)壓

15、縮： a-b數(shù)據(jù)壓縮的方法:靜態(tài)的：采用“靜態(tài)的”和“半自適應(yīng)的”的modeling方式建立模型，a的任何出現(xiàn)都被轉(zhuǎn)換成同一b；自適應(yīng)的：采用 “自適應(yīng)的”的modeling方式建立模型， a的不同出現(xiàn)可能被轉(zhuǎn)換成不同b；29adaptive Huffman coding基本思想： 以自適應(yīng)的modeling，對迄今出現(xiàn)的信息進(jìn)行概率估算，以Huffman編碼樹實現(xiàn)編碼。具體做法： 編碼/譯碼雙方維護(hù)隨壓縮/解壓進(jìn)行不斷更改的Huffman編碼樹，使之一直保持是迄今壓縮/解壓的源信息整個源信息的前綴部分構(gòu)成的Huffman編碼樹。30adaptive Huffman coding算法FGK：（

16、Faller1973,Gallager1978,Knuth1985）基本準(zhǔn)則“sibling”性質(zhì)：一個有p個節(jié)點的二分樹是一Huffman樹當(dāng)且僅當(dāng)：1、p個葉節(jié)點有非負(fù)權(quán)值，每一內(nèi)節(jié)點的權(quán)值為它的兒子的權(quán)值之和；2、葉節(jié)點以權(quán)值的非增次序編號，節(jié)點2j-1和節(jié)點2j是兄弟（sibling），它們共同的父節(jié)點有較大的編號。31adaptive Huffman coding算法FGK： 初始一個0-節(jié)點； k 種符號，k+1個節(jié)點（一個為0節(jié)點）； 第i步：若ai(當(dāng)前符號)為k中的一個，則傳ai的編碼;若ai為新出現(xiàn)符號，則將0-節(jié)點分裂：其左子樹為0-節(jié)點，右子樹為ai，并且增加相應(yīng)權(quán)值，

17、重新計算樹， 保持“sibling”性質(zhì)。32adaptive Huffman coding算法FGK： 初始一個0-節(jié)點； k 種符號，構(gòu)成k+1個節(jié)點（一個為0節(jié)點）的Huffman樹； 第i步：若ai(當(dāng)前符號)為k中的一個，則傳ai的編碼;若ai為新出現(xiàn)符號，則傳0-節(jié)點的編碼以及ai 本身，并將0-節(jié)點分裂：其左子樹為0-節(jié)點，右子樹為ai；然后增加相應(yīng)權(quán)值，重新計算樹， 保持“sibling”性質(zhì)。33算術(shù)編碼（Arithmetic Coding）例：輸入“AADB#”(結(jié)果：.0325 或.0326 或.0327)0, .2)- 0, .04)- .028, .036)- .02

18、96, .0328) -.03248, .0328）符號概率累積概率間隔msgleft,msgright)A.2.20, .2)B.4.6.2, .6)C.1.7.6, .7)D.2.9.7, .9)#.11.00.9, 1.0)34算術(shù)編碼消息用0到1之間的實數(shù)進(jìn)行編碼。0，1）兩個基本的參數(shù)：符號的概率編碼間隔數(shù)據(jù)源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，從而決定了符號壓縮后的輸出。35算術(shù)編碼編碼輸出：可以是最后一個間隔中的任意數(shù)。 結(jié)束：壓縮方發(fā)送消息的長度；添加一個專門的終止符；36算術(shù)編碼幾個問題：運算中出現(xiàn)溢出比例縮放解決。 只產(chǎn)生一個碼字，譯碼器在接受到表示這個實數(shù)的所有位之前不能進(jìn)行譯碼。 對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯錯。延遲前面位