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