【正文】 3. 編碼位置 (coding position)：輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，指前向緩沖存儲(chǔ)器中的開始字符。 劃分：許多靈活的無(wú)損編碼方案都是把信源符號(hào)劃分成一系列的段，然后產(chǎn)生壓縮編碼代表這些段。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計(jì)編碼 前面所介紹的無(wú)損編碼技術(shù)只能在 己知信源的統(tǒng)計(jì)規(guī)律 是有效應(yīng)用，但在壓縮的很多時(shí)候事先并不知道這些規(guī)律。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計(jì)編碼 算術(shù)編碼 算法描述： 步驟（ 1）若輸入符號(hào) X1＝ ai ， （ i＝ 1， …… ， M），那么初始子區(qū)間定義 為 這里 P0 ＝ 0 設(shè) L ＝ l1 ， R ＝ r1 ， d1 ＝ r1－ l1， j =1 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計(jì)編碼 算術(shù)編碼 算法描述： 步驟（ 2） 將 L 和 R 轉(zhuǎn)換為二進(jìn)制小數(shù)形式， 對(duì) k = j, j+1, …… ，依次比較 Uk=Vk? ， 若相等，則輸出 Uk, j = j+1； 否則，轉(zhuǎn)步驟（ 3） 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計(jì)編碼 算術(shù)編碼 算法描述： 步驟 (3) n ＝ n＋ 1，讀入下一符號(hào)， Xn ＝ ai，將區(qū)間細(xì)分， 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計(jì)編碼 ? ? ?????? ???? ?????????iiinniiinnnnn pdlpdlrlI1111111 ,）。在算術(shù)編碼中，消息用 0到 1之間的實(shí)數(shù)進(jìn)行編碼。對(duì) a1b1進(jìn)行編碼。當(dāng) b2位于 a1的左邊時(shí)，輸出越過(guò)碼 0001。如下例所示。 2D方法使用了一些附加碼的組合為這組 K條線中的每一條編碼。每組 K條線中的第一條用 CCITT Group 3 1D方法編碼，這條線就成為下一條線的參考線，然后使用二維方法和一 維方法為這組 K條線中的其余掃描線編碼。 第 三 章 多媒體數(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，稱為終止碼。 (2) Huffman碼是變長(zhǎng)度碼，且沒(méi)有額外同步碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼。 構(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ù)上面的過(guò)程，直到節(jié)點(diǎn)集合中只剩一個(gè)節(jié)點(diǎn)為止。 若采用非等長(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編碼等。反之則不然。 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＝｛０，１｝。因此，壓縮方法就是充分利用這些冗余和特性。 時(shí)間冗余：時(shí)間相關(guān)媒體，幀與幀相同。而存儲(chǔ)回放中，結(jié)壓縮的速度顯得比壓縮的速度重要，因?yàn)榻鈮嚎s面對(duì)大多數(shù)用戶的實(shí)時(shí)需求。有損：通過(guò)損失一些細(xì)節(jié)的、對(duì)人的感觀來(lái)說(shuō)不重要的信息提高壓縮比，分為主觀評(píng)價(jià)和客觀評(píng)價(jià)。第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 2. 音頻的壓縮 3. 視覺(jué)類媒體壓縮 第 三 章 多媒體數(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ù)量之比?？陀^評(píng)價(jià)：方差、新噪比等。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 2 數(shù)據(jù)冗余的類型與壓縮方法分類 需要壓縮的原因是因?yàn)樾畔?shù)據(jù)存在著冗余。 編碼冗余：同樣長(zhǎng)度的編碼可以表示不同的信息。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 2 數(shù)據(jù)冗余的類型與壓縮方法分類 數(shù)據(jù)壓縮方法的分類 根據(jù)解碼后數(shù)據(jù)與原始數(shù)據(jù)是否完全一致進(jìn)行分類，壓縮方法可被分為兩大類： ? 有損壓縮：減少信息量，損失的信息不能再恢復(fù) ? 無(wú)損壓縮：可 100％還原 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 信源： S ＝ {S1,…… ， Sn} 熵的概念：熵是信息量的度量方法，它表示某一事件出現(xiàn)的消息越多，事件發(fā)生的可能性就越小，相應(yīng)的，這個(gè)信息出現(xiàn)的概率小。 碼字的集合： 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都不是其余碼字的前綴。 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. 2 統(tǒng)計(jì)編碼（熵編碼） 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 行程編碼： 檢測(cè)重復(fù)的比特或者字符序列，并用（字符，重復(fù)次數(shù)）來(lái)表示。 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編碼方法沒(méi)有錯(cuò)誤保護(hù)的功能，在譯碼時(shí)，如果碼串中沒(méi)有錯(cuò)誤，那么就能一個(gè)接一個(gè)地正確譯出代碼。 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è)象素。 終止碼用于表示小于 64個(gè)像素的游程。 原因：橫跨相鄰兩條掃描線的圖像數(shù)據(jù)可能是冗余的。附加碼有 3種：垂直碼，越過(guò)碼，水平碼。 a0表示準(zhǔn)備編碼的行程起始位置的像素點(diǎn)， a1為當(dāng)前行下一個(gè)行程起始位置的像素點(diǎn)， a2表示再下一個(gè)行程起始位置的象素點(diǎn)。把 a0移動(dòng)致 b2這一列，更新其他四個(gè)參數(shù)（其中 a1和 a2不會(huì)改變），然后重復(fù)這一步。把 a0移到 a1位置，更新其他 4個(gè)參數(shù)，回到第一步。算術(shù)編碼用到兩個(gè)基本的參數(shù)：信源符號(hào)出現(xiàn)的概率和編碼的間隔。轉(zhuǎn)（令 2, nnnnn lrdrRlL ????第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計(jì)編碼 n Xn ＝ ai In L (二進(jìn)制 ) R(二進(jìn)制 ) dn j 輸出 1 X1 ＝ a2 [ , ) 1 1,j++ 2 2 X2 ＝ a1 [ , ) 2 0, j++ 3 3 [ , ) 3 0,j++ 4 1,j++ 5 1,j++ 6 算術(shù)編碼 應(yīng)注意的幾個(gè)問(wèn)題： （ 1）由于實(shí)際的計(jì)算機(jī)的精度不可能無(wú)限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問(wèn)題，在編碼的時(shí)候必須注意，可以采用一些方法來(lái)解決。 因此，編碼器事先不知道數(shù)據(jù)源的概率時(shí)，可以在數(shù)據(jù)流中憑經(jīng)驗(yàn)逐步精確地估測(cè)。 LZ算法的變體，典型的兩種， LZ77和 LZ78，使用的劃分方法有所不同。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無(wú)損信源編碼 LZ77壓縮 4. 前向緩沖存儲(chǔ)器 (Lookahead buffer)：存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲(chǔ)器。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無(wú)損信源編碼 LZ77壓縮 編碼算法的具體執(zhí)行步驟： 1. 把編碼位置設(shè)置到輸入數(shù)據(jù)流的開始位置。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無(wú)損信源編碼 LZ77壓縮 例 第一次輸出 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無(wú)損信源編碼 LZ77壓縮 第二次輸出 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無(wú)損信源編碼 LZ77壓縮 第三次輸出 第 三 章 多媒體數(shù)據(jù)壓縮