【正文】 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 2. 音頻的壓縮 3. 視覺類媒體壓縮 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 1 數(shù)據(jù)壓縮技術(shù)的性能指標(biāo) 評價數(shù)據(jù)壓縮技術(shù)的 3個關(guān)鍵指標(biāo)： ?壓縮比：輸入、輸出數(shù)據(jù)量之比。 ?質(zhì)量：無損和有損。無損沒有信息的損失，所以質(zhì)量不是衡量的標(biāo)準(zhǔn)。有損：通過損失一些細(xì)節(jié)的、對人的感觀來說不重要的信息提高壓縮比，分為主觀評價和客觀評價?？陀^評價：方差、新噪比等。 ?壓縮和解壓縮的速度：實(shí)時的采集系統(tǒng)中，壓縮速度很重要。否則會丟失信息。而存儲回放中，結(jié)壓縮的速度顯得比壓縮的速度重要，因?yàn)榻鈮嚎s面對大多數(shù)用戶的實(shí)時需求。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 2 數(shù)據(jù)冗余的類型與壓縮方法分類 需要壓縮的原因是因?yàn)樾畔?shù)據(jù)存在著冗余。冗余，數(shù)據(jù)量和信息量不成正比。 空間冗余：例如，相鄰象素 (水平和垂直方向 )有同樣的值。 時間冗余：時間相關(guān)媒體，幀與幀相同。 編碼冗余：同樣長度的編碼可以表示不同的信息。如黑白圖像若每個象素點(diǎn)用 8位表示； 結(jié)構(gòu)冗余：對稱的結(jié)構(gòu)如果都加以記錄的話就出現(xiàn)結(jié)構(gòu)冗余。 另外，很多成分相對于人的感覺來說重要性不一樣。因此，壓縮方法就是充分利用這些冗余和特性。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 2 數(shù)據(jù)冗余的類型與壓縮方法分類 數(shù)據(jù)壓縮方法的分類 根據(jù)解碼后數(shù)據(jù)與原始數(shù)據(jù)是否完全一致進(jìn)行分類，壓縮方法可被分為兩大類： ? 有損壓縮：減少信息量，損失的信息不能再恢復(fù) ? 無損壓縮：可 100％還原 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 信源： S ＝ {S1,…… ， Sn} 熵的概念：熵是信息量的度量方法，它表示某一事件出現(xiàn)的消息越多，事件發(fā)生的可能性就越小，相應(yīng)的，這個信息出現(xiàn)的概率小。 某個事件的信息量，用 Ii ＝ － log 2 Pi 表示。其中， Pi 表示第 i個事件的概率。 1. 3. 1 基本概念 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 信源 S的熵定義為： ? ?i2n1ii 1/PlogPH(S) ??? 1. 3. 1 基本概念 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 編碼：一個信源符號集轉(zhuǎn)換為另一個符號集 信源符號的集合： S ＝ {S1,…… ， Sn} 概率： P1， ……,Pn 碼符號集合：碼字中的元素，二進(jìn)制編碼則為 X＝｛０，１｝。 碼字的集合： W ＝ {W1,…… ， Wn} 編碼長度： L1, …… ， Ln，可分為變長碼及定長碼 1. 3. 1 基本概念 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 唯一可譯碼：任意有限長，不需分隔符的碼符號序列，能唯一譯碼 非前綴碼： W中任意碼字 Wi都不是其余碼字的前綴。非前綴碼一定是唯一可譯碼 例： 編碼方法 A：具有唯一可譯碼性 編碼方法 C：非前綴碼 編碼方法 D：具有可唯一譯碼性，但不符合非前綴碼的條件。 1. 3. 1 基本概念 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 非前綴碼一定是唯一可譯碼。反之則不然。 1. 3. 1 基本概念 信源符號 概率 編碼方法 A 編碼 B 編碼 C 編碼 D Huffman 1 Huffman 2 A1 000 0 010 0 0 0 A2 001 1 011 011 100 100 A3 010 00 00 1010 110 110 A4 011 01 100 1011 111 1010 A5 100 10 101 10000 1010 1011 A6 101 11 110 10001 10110 1110 A7 110 000 1110 10010 101110 11110 A8 111 001 1111 10011 101111 11111 平均編碼長度 編碼方法 A： 3； 編碼方法 B： 編碼方法 C : ；編碼方法 D : Huffman編碼： 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 給定信源符號集合 S及碼符號集 X，可以構(gòu)造多個唯一可譯碼。 多個編碼的比較標(biāo)準(zhǔn)： 平均編碼長度 低。如果我們用 lj 表示信源符號 aj的二進(jìn)制編碼長度，根據(jù)它的統(tǒng)計信息，平均編碼長度： ???MjjjlPl1 1. 3. 1 基本概念 結(jié)論： 對二進(jìn)制編碼方式（ 即碼符號的取值只有 0 ， 1 兩種情況） 平均編碼長度滿足 碼字的平均長度不能小于信源熵。 若采用非等長編碼：能找到一種編碼，平均長度為信源熵 ＋ 1 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 LSH ?)( 1. 3. 1 基本概念 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 包括行程編碼、 LZW編碼、 huffman編碼等。 1. 3. 2 統(tǒng)計編碼（熵編碼） 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 行程編碼： 檢測重復(fù)的比特或者字符序列，并用（字符，重復(fù)次數(shù)）來表示。 考慮的問題：字符的值重復(fù)次數(shù)，二者之間是否使用分隔符，重復(fù)的次數(shù)如何編碼（使用變長碼還是定長碼）等 1. 3. 2 統(tǒng)計編碼 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 Huffman編碼： 于 1952年提出的對統(tǒng)計獨(dú)立信源能達(dá)到最小平均碼長的編碼方法。 Huffman編碼的過程：構(gòu)造一棵編碼樹。 構(gòu)造方法： 首先找出兩個具有最小概率的節(jié)點(diǎn)，構(gòu)造一個二叉樹，以這兩個節(jié)點(diǎn)為這棵樹的葉子節(jié)點(diǎn)，根節(jié)點(diǎn)看作為新的節(jié)點(diǎn)，它的概率為兩個葉子節(jié)點(diǎn)概率之和；此跟節(jié)點(diǎn)與未處理的節(jié)點(diǎn)形成新的節(jié)點(diǎn)集合，重復(fù)上面的過程，直到節(jié)點(diǎn)集合中只剩一個節(jié)點(diǎn)為止。 1. 3. 2 統(tǒng)計編碼 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 Huffman編碼 當(dāng)信源符號概率是 2的負(fù)冪次方時，編碼效率達(dá)到 100% 缺點(diǎn)： (1) Huffman編碼方法沒有錯誤保護(hù)的功能，在譯碼時，如果碼串中沒有錯誤，那么就能一個接一個地正確譯出代碼。如果出現(xiàn)錯誤，哪怕僅僅是一位的錯誤，不但這個碼本身會發(fā)生錯誤，并且會導(dǎo)致其他代碼出錯，這種現(xiàn)象稱為錯誤傳播（ error propagation）。計算機(jī)也無法去發(fā)現(xiàn)錯誤糾正錯誤。 (2) Huffman碼是變長度碼，且沒有額外同步碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼。 1. 3. 2 統(tǒng)計編碼 傳真標(biāo)準(zhǔn)中的編碼（ 3類傳真標(biāo)準(zhǔn)及 4類傳真標(biāo)準(zhǔn) CCITT Group 3 1D/2D ）： 掃描、尺寸和傳輸： 掃描：每行 1728個象素。標(biāo)準(zhǔn)掃描行寬 215mm，垂直方向 /mm,或 /mm. 尺寸： A4幅面 傳輸：用于傳輸每行掃描編碼后形成的數(shù)據(jù)位、填充位、行結(jié)束符號的時間總和，最大 20ms 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計編碼 傳真標(biāo)準(zhǔn)中的編碼（ 3類傳真標(biāo)準(zhǔn) CCITT Group 3 1D及 4類傳真標(biāo)準(zhǔn)）： 3類編碼方法采用一維編碼，掃描時統(tǒng)計游程，并將游程分為白游程及黑游程，白游程和黑游程再采用 Huffman編碼。 假設(shè)每行的第一個行程是白色的（如果不是，則發(fā)出一個長度為 0的白色游程碼），每行的結(jié)尾發(fā)出一個 EOL信號碼。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計編碼 3類傳真標(biāo)準(zhǔn) CCITT Group 3 1D 碼表中的游程， 0~64，稱為終止碼。 終止碼用于表示小于 64個像素的游程。 64， 128， 192， 256， 320…… ， 1728， 64的倍數(shù)，稱為編排碼，編排碼用于表示是 64個像素倍數(shù)的游程。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計編碼 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計編碼 白色游程 碼字 黑色游程 碼字 0 00110101 0 0000110111 1 000111 1 010 2 0111 2 11 3 1000 3 10 …… 63 00110100 63 …… EOL 000000000001 終止碼 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計編碼 白色游程 碼字 黑色游程 碼字 64 11011 64 …… 128 10010 128 …… 192 010111 192 …… 256 0110111 256 …… …… …… 1728 010011011 1728 …… 編排碼 3類傳真標(biāo)準(zhǔn) CCITT Group 3 1D 例如， 1347（ 1344+3）個白像素的游程編碼用以下兩種代碼進(jìn)行編碼： 1344（ 64 21）個白像素的編排碼 —— 011011010 3個白像素的終止碼 —— 1000 那么， 1347個白像素的壓縮位流是 0110110101000 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計編碼 4類傳真標(biāo)準(zhǔn) CCITT Group 3 2D 將掃描線每 K條放在一起進(jìn)行處理。每組 K條線中的第一條用 CCITT Group 3 1D方法編碼，這條線就成為下一條線的參考線，然后使用二維方法和一 維方法為這組 K條線中的其余掃描線編碼。 原因：橫跨相鄰兩條掃描線的圖像數(shù)據(jù)可能是冗余的。如果在一指定線上出現(xiàn)了黑白過渡，那么有可能在下一掃描線上加或減三個像素之間的位置上也出現(xiàn)相同的過渡。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計編碼 4類傳真標(biāo)準(zhǔn) CCITT Group 3 2D 編碼方法：每個 K組的第一條線采用 Group3 1D方式編碼，以作為這組 K條線中其余線的掃描線。 2D方法使用了一些附加碼的