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