【正文】 統(tǒng)計(jì)編碼 信源符號(hào) 概率 初始編碼間隔 A [ 0, ) B [ , ) C [ , ) D [ , 1 ) 01ADCB輸入 CADACDB輸出算術(shù)編碼 在實(shí)際應(yīng)用中，用二進(jìn)制小數(shù)表示算術(shù)編碼的結(jié)果。 第 三 章 多媒體數(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 ,）。 （ 2）算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔 0， 1中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 2 統(tǒng)計(jì)編碼 前面所介紹的無損編碼技術(shù)只能在 己知信源的統(tǒng)計(jì)規(guī)律 是有效應(yīng)用，但在壓縮的很多時(shí)候事先并不知道這些規(guī)律。 必須滿足的幾個(gè)條件： ?編碼器自適應(yīng)程序造成的延遲和復(fù)雜性必須能夠被系統(tǒng)所接受； ?信源的統(tǒng)計(jì)特征必須足夠平穩(wěn)； ?在編碼器和解碼器中事先統(tǒng)一好自適應(yīng)程序，使解碼器在無損的解碼數(shù)據(jù)流中保持與編碼器同步，而不需要編碼器另送一組信息來描述其適應(yīng)過程。 劃分：許多靈活的無損編碼方案都是把信源符號(hào)劃分成一系列的段，然后產(chǎn)生壓縮編碼代表這些段。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 為了更好地說明 LZ77算法的原理，首先介紹算法中用到的幾個(gè)術(shù)語： 1. 輸入數(shù)據(jù)流 (input stream)：要被壓縮的字符序列。 3. 編碼位置 (coding position)：輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，指前向緩沖存儲(chǔ)器中的開始字符。 5. 窗口 (window)：指包含 W個(gè)字符的窗口，字符是從編碼位置開始向后數(shù)也就是最后處理的字符數(shù)。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 LZ77編碼算法的核心是查找從前向緩沖存儲(chǔ)器開始的最長的匹配串。 2. 查找窗口中最長的匹配串。 4. 如果前向緩沖存儲(chǔ)器不是空的，則把編碼位置和窗口向前移 (Length+1)個(gè)字符，然后返回到步驟 2。冗余信息表現(xiàn)在兩個(gè)方面： 一是空指針；二是編碼器輸出額外的字符，這種字符是可能包含在下一個(gè)匹配串中的字符。它的思想是如果匹配串的長度比指針本身的長度長就輸出指針，否則就輸出真實(shí)字符。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78編碼 與 LZ77相比， LZ78方法維護(hù)了一張“詞典”。在譯碼的過程中，從碼字流中重構(gòu)詞典。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78編碼 00010110000010100100100010011 LZ78劃分結(jié)果： 0， 00， 1， 01， 10， 000， 010， 編碼的過程中可以構(gòu)造出一顆 LZ78樹（即詞典），編碼器輸出節(jié)點(diǎn)的序號(hào)和“向左”或“向右”的信息。 段 K：可以用編碼樹中其父節(jié)點(diǎn)的序列以及其位于其父節(jié)點(diǎn)的左支還是右支來表示，這樣，編碼器就可以向解碼器精確的指出下一段。解碼器建立樹的信息被包含在連續(xù)的段中。在編碼器和解碼器端都遵守事先約定的構(gòu)建方法。同時(shí)，解碼器也能與編碼器同步的建立 LZ78樹。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 LZ78編碼 編碼器中指定段 K需要多少二進(jìn)制數(shù)？ 在編碼器開始劃分 K段時(shí)，樹上已經(jīng)有 K個(gè)節(jié)點(diǎn)了（根節(jié)點(diǎn)，節(jié)點(diǎn) 1到節(jié)點(diǎn)K－ 1）。 上例的編碼效率： 28位，編碼以后必須用 40個(gè)二進(jìn)制書來表示這個(gè) 28位的序列 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78編碼 改進(jìn)：在二進(jìn)制數(shù)字的劃分中，當(dāng)一個(gè)節(jié)點(diǎn)第二次被指定為新段的父節(jié)點(diǎn)時(shí)，表示這個(gè)段將有一個(gè)新的終結(jié)節(jié)點(diǎn)，原來的這個(gè)父節(jié)點(diǎn)不可能第三次的被指定為父節(jié)點(diǎn)，同時(shí)，不用記錄最后表示“方向”的這一位，一定是“填空”。 壓縮最后一位的改進(jìn)法被稱為 LZ78S?？梢允褂?403＝ 37個(gè)二進(jìn)制數(shù)來編碼 28個(gè)源字符。左右都已經(jīng)有節(jié)點(diǎn)的節(jié)點(diǎn)，稱為“死節(jié)點(diǎn)”。 上例中， LZ78E描述 11段所需的二進(jìn)制數(shù)字的編碼位數(shù)為 36。進(jìn)一步降低編碼所需要的二進(jìn)制位。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78EP編碼和 LZ78SEP編碼 試圖用一個(gè)更小的數(shù)表示 L（ k），以描述 LZ78劃分。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZW編碼 W表示一個(gè)人的姓。解碼器比編碼器晚一步更新。在二進(jìn)制數(shù)據(jù)中， LZW樹最初由根節(jié)點(diǎn)以及表示 0、 1的兩個(gè)子節(jié)點(diǎn)構(gòu)成。這個(gè)子節(jié)點(diǎn)的數(shù)字等于要?jiǎng)澐值臄?shù)據(jù)部分的第一個(gè)字符。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 k?1?k?LZW編碼 例： 00010110000010100100100010011 見 LZW編解碼示意圖 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZW編碼 效率分析： 要用 [ log2(k+2) ] 個(gè)二進(jìn)制數(shù)表示。 如果預(yù)測比較準(zhǔn)確，則誤差會(huì)接近 0。 兩種典型的預(yù)測編碼： DPCM和 ADPCM 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 4 預(yù)測編碼 DPCM編碼：量化實(shí)際值和預(yù)測值的差，達(dá)到壓縮的目的。在一定的量化級(jí)數(shù)下減少量化誤差或在同樣的誤差條件下壓縮數(shù)據(jù)率，根據(jù)信號(hào)分布均勻的特點(diǎn)，系統(tǒng)具有隨輸入信號(hào)的變化而改變量化區(qū)間大小，以保持輸入給量化器的信號(hào)基本均勻的能力，這種能力稱為自適應(yīng)量化。自適應(yīng)預(yù)測：隨著編碼區(qū)間的不同，預(yù)測參數(shù)自適應(yīng)地變化。在變換編碼中，原始數(shù)據(jù)從初始空間或者時(shí)間域進(jìn)行變換，使得信號(hào)中最重要的部分在變換后的域中易于識(shí)別，并且集中出現(xiàn)，便于編碼。 譯碼時(shí)則借助于一定的規(guī)則或模型，按照一定的算法將這些基元或參數(shù)再“綜合”成原數(shù)據(jù)的一個(gè)逼近。 一般來說，這種編譯碼器的復(fù)雜程度比較低，數(shù)據(jù)速率在 16Kbps時(shí)可以取得較好的質(zhì)量。 波形編譯碼又可以分為時(shí)域法（ time domain approach）和頻域法(frequency domain approach)兩類。 第 三 章 多媒體數(shù)據(jù)壓縮 2. 音頻的壓縮 2. 1 音頻壓縮編碼的基本方法 2. 1. 2 波形編譯碼 PCM 均勻量化：如果采用相等的量化間隔對(duì)采樣得到的信號(hào)作量化，那么這種量化方法稱為均勻量化。 均勻量化面臨的問題：為了適應(yīng)幅度大的輸入信號(hào)，同時(shí)又要滿足精度要求，就需要增加樣本的位數(shù)。 為了克服這個(gè)不足，就出現(xiàn)了非均勻量化的方法，也叫做非線性量化。 這樣就可以在滿足精度要求的情況下用較少的位數(shù)來完成量化?，F(xiàn)在較常用的有兩種， μ律和 A律。 A律，分段函數(shù)。 根據(jù)：認(rèn)為在話音樣本之間存在相關(guān)性。這就是差分脈沖編碼調(diào)制的基礎(chǔ) —— 對(duì)預(yù)測的樣本值與原始的樣本值之差進(jìn)行編碼。 改進(jìn)的方法之一就是使用自適應(yīng)的預(yù)測器和量化器，這就產(chǎn)生了自適應(yīng)差分脈沖編碼調(diào)制 ADPCM（ adaptive differential PCM, ADPCM ）。帶寬：頻率的變化范圍。 對(duì)每個(gè)子帶中的音頻信號(hào)采用單獨(dú)的編碼方案去編碼。 在接收端譯碼時(shí)，將每個(gè)子帶的代碼單獨(dú)譯碼，然后把他們組合起來，還原成原來的音頻信號(hào)。 2. 可根據(jù)每個(gè)子帶信號(hào)在感覺上的重要性，對(duì)每個(gè)子帶采用不同的編碼方法。在不用的應(yīng)用需求中可以使用不同的算法。 對(duì)于音樂和聲音數(shù)據(jù)，雙聲道能在第三層以約 64Kbps速率很好地編碼。 第 三 章 多媒體數(shù)據(jù)壓縮 2. 音頻的壓縮 2. 4 MPEG音頻編碼方法 第 三 章 多媒體數(shù)據(jù)壓縮 2. 音頻的壓縮 2. 4 MPEG音頻編碼方法 在 MPEG－ 2標(biāo)準(zhǔn)中，對(duì)音頻編碼進(jìn)行了擴(kuò)充。 另一種稱為 MPEG－ 2 AAC(Advanced Audio Coding)，它與 MPEG－ 1聲音格式不兼容。這種方法稱為截?cái)喾ā? 顏色查找表：產(chǎn)生顏色表，圖像的每個(gè)象素點(diǎn)記錄一個(gè)表的位置號(hào)。當(dāng)圖像顏色較少是采用這種方法可以得到很好的壓縮效果。 第 三 章 多媒體數(shù)據(jù)壓縮 3. 視覺類媒體壓縮 3. 3 JPEG—— 混合壓縮 JPEG的名稱： Joint Photographic Coding Experts Group（ 聯(lián)合圖片專家組 ）， 它是由 ISO標(biāo)準(zhǔn)化組織下的小組和 CCITT 聯(lián)合成立的，致力于靜止圖像的壓縮研究。 JPEG壓縮，靜態(tài)