【文章內(nèi)容簡介】 Z77通過輸出真實字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個方面： 一是空指針；二是編碼器輸出額外的字符，這種字符是可能包含在下一個匹配串中的字符。 LZSS算法以比較有效的方法解決兩個冗余。它的思想是如果匹配串的長度比指針本身的長度長就輸出指針，否則就輸出真實字符。缺點(diǎn)：由于輸出的壓縮數(shù)據(jù)流中包含有指針和字符本身，為了區(qū)分它們就需要有額外的標(biāo)志位。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78編碼 與 LZ77相比， LZ78方法維護(hù)了一張“詞典”。但是，在壓縮后的數(shù)據(jù)流中，并不需要保存這張詞典。在譯碼的過程中，從碼字流中重構(gòu)詞典。 以二進(jìn)制串為例，介紹 LZ78編碼。 第 三 章 多媒體數(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)的序號和“向左”或“向右”的信息。在編碼器和解碼器端都遵守事先約定的構(gòu)建方法。 段 K：可以用編碼樹中其父節(jié)點(diǎn)的序列以及其位于其父節(jié)點(diǎn)的左支還是右支來表示，這樣，編碼器就可以向解碼器精確的指出下一段。同時，解碼器也能與編碼器同步的建立 LZ78樹。解碼器建立樹的信息被包含在連續(xù)的段中。 第 三 章 多媒體數(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)的序號和“向左”或“向右”的信息。在編碼器和解碼器端都遵守事先約定的構(gòu)建方法。 段 K：可以用編碼樹中其父節(jié)點(diǎn)的序列以及其位于其父節(jié)點(diǎn)的左支還是右支來表示，這樣，編碼器就可以向解碼器精確的指出下一段。同時，解碼器也能與編碼器同步的建立 LZ78樹。解碼器建立樹的信息被包含在連續(xù)的段中。 第 三 章 多媒體數(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段時，樹上已經(jīng)有 K個節(jié)點(diǎn)了（根節(jié)點(diǎn)，節(jié)點(diǎn) 1到節(jié)點(diǎn)K－ 1）。最簡單的編碼方法， [log2k]能夠描述其父節(jié)點(diǎn)，然后在加上最后一位， [log2k]+1可以描述這個段。 上例的編碼效率： 28位，編碼以后必須用 40個二進(jìn)制書來表示這個 28位的序列 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78編碼 改進(jìn)：在二進(jìn)制數(shù)字的劃分中，當(dāng)一個節(jié)點(diǎn)第二次被指定為新段的父節(jié)點(diǎn)時，表示這個段將有一個新的終結(jié)節(jié)點(diǎn)，原來的這個父節(jié)點(diǎn)不可能第三次的被指定為父節(jié)點(diǎn)，同時，不用記錄最后表示“方向”的這一位，一定是“填空”。這樣就可以壓縮掉一位。 壓縮最后一位的改進(jìn)法被稱為 LZ78S。 上例中，段 3是根節(jié)點(diǎn)的最后一個子節(jié)點(diǎn)，段 4是節(jié)點(diǎn) 1的最后一個后代，段11是節(jié)點(diǎn) 2的最后一個后代?？梢允褂?403＝ 37個二進(jìn)制數(shù)來編碼 28個源字符。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78E編碼 LZ78E：一個節(jié)點(diǎn)不會被第三次指定為“父節(jié)點(diǎn)”。左右都已經(jīng)有節(jié)點(diǎn)的節(jié)點(diǎn)，稱為“死節(jié)點(diǎn)”。我們可將“死”節(jié)點(diǎn)截去，解碼器知道什么時候節(jié)點(diǎn)死掉，也就知道什么時候把節(jié)點(diǎn)截去，只要編碼器和解碼器采用相同的方法。 上例中， LZ78E描述 11段所需的二進(jìn)制數(shù)字的編碼位數(shù)為 36。 LZ78SE：將 LZ78E和 LZ78S結(jié)合。進(jìn)一步降低編碼所需要的二進(jìn)制位。在本例中，LZ78SE需要 33位二進(jìn)制數(shù)來完成編碼。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78EP編碼和 LZ78SEP編碼 試圖用一個更小的數(shù)表示 L（ k），以描述 LZ78劃分。將活節(jié)點(diǎn)進(jìn)行前綴編碼，不考慮它們的概率特性（假設(shè)概率相等）。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZW編碼 W表示一個人的姓。 LZW的一個重要特征是采用了 Welch修正，其目的是克服發(fā)送每段最后一個未壓縮字符造成的低效率。解碼器比編碼器晚一步更新。 LZW樹開始時由根節(jié)點(diǎn)和所有的單字符量構(gòu)成。在二進(jìn)制數(shù)據(jù)中， LZW樹最初由根節(jié)點(diǎn)以及表示 0、 1的兩個子節(jié)點(diǎn)構(gòu)成。 第 K個 LZW段是從未劃分部分的第一個字符開始，在當(dāng)前的 LZW樹中找出一個最長的匹配， 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZW編碼 在劃分出 之后，編碼器就對 LZW樹進(jìn)行更新；在 所對應(yīng)的節(jié)點(diǎn)再擴(kuò)展出 一個分支節(jié)點(diǎn)。這個子節(jié)點(diǎn)的數(shù)字等于要劃分的數(shù)據(jù)部分的第一個字符。 解碼器在相應(yīng)的時刻并不知道此信息，但可以根據(jù)接下來的 的信息進(jìn)行相應(yīng)的 LZW樹構(gòu)造。 第 三 章 多媒體數(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) ] 個二進(jìn)制數(shù)表示。 LZWE ：截去 “ 死 ” 節(jié)點(diǎn) LZWEP：在 LZWE基礎(chǔ)上采用前綴編碼 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 預(yù)測編碼是根據(jù)原始的離散信號之間存在著一定的關(guān)聯(lián)性的特點(diǎn)，利用前面的一個或多個信號對下一個信號進(jìn)行預(yù)測，然后對實際值和預(yù)測值的差進(jìn)行編碼。 如果預(yù)測比較準(zhǔn)確，則誤差會接近 0。這樣，再同等精度要求的條件下，可以用較少的位數(shù)進(jìn)行編碼，達(dá)到壓縮數(shù)據(jù)的目的。 兩種典型的預(yù)測編碼： DPCM和 ADPCM 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 4 預(yù)測編碼 DPCM編碼：量化實際值和預(yù)測值的差，達(dá)到壓縮的目的。 ADPCM編碼：采用自適應(yīng)量化或自適應(yīng)預(yù)測。在一定的量化級數(shù)下減少量化誤差或在同樣的誤差條件下壓縮數(shù)據(jù)率，根據(jù)信號分布均勻的特點(diǎn)，系統(tǒng)具有隨輸入信號的變化而改變量化區(qū)間大小，以保持輸入給量化器的信號基本均勻的能力，這種能力稱為自適應(yīng)量化。 預(yù)測參數(shù)的最佳化依賴于信源的統(tǒng)計特性，要得到最佳預(yù)測參數(shù)是一件繁瑣的工作，而采用固定的預(yù)測參數(shù)往往又得不到較好性能。自適應(yīng)預(yù)測：隨著編碼區(qū)間的不同，預(yù)測參數(shù)自適應(yīng)地變化。 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 4 預(yù)測編碼 變換編碼是有失真編碼的一種重要的編碼類型。在變換編碼中，原始數(shù)據(jù)從初始空間或者時間域進(jìn)行變換，使得信號中最重要的部分在變換后的域中易于識別，并且集中出現(xiàn)，便于編碼。 變換編碼系統(tǒng)中壓縮數(shù)據(jù)的三個主要步驟： 變換 變換域采樣 量化 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 5 變換編碼 通過對數(shù)據(jù)源的分析，將其分解成一系列更適合表示的“基元”，或從中提取出若干具有更本質(zhì)意義的參數(shù)，編碼僅對這些基本單元或特征參數(shù)進(jìn)行。 譯碼時則借助于一定的規(guī)則或模型，按照一定的算法將這些基元或參數(shù)再“綜合”成原數(shù)據(jù)的一個逼近。 ? 量化編碼 ? 小波變換編碼 ? 分形圖像編碼 ? 子帶編碼 第 三 章 多媒體數(shù)據(jù)壓縮 1. 數(shù)據(jù)壓縮的基本原理和方法 1. 3 常用數(shù)據(jù)壓縮方法的基本原理 1. 3. 6 分析－合成編碼 第 三 章 多媒體數(shù)據(jù)壓縮 2. 音頻的壓縮 2. 1 音頻壓縮編碼的基本方法 音 頻 壓 縮 編 碼 方 法無 損 壓 縮 有 損 壓 縮H u f f m a n 編 碼行 程 編 碼波 形 編 碼 參 數(shù) 編 碼 混 合 編 碼時 域 法P C MD P C MA D P C M頻 域 法 ：子 帶 編 碼矢 量 量 化線 性 預(yù) 測 2. 1. 1 概述 第 三 章 多媒體數(shù)據(jù)壓縮 2. 音頻的壓縮 2. 1 音頻壓縮編碼的基本方法 2. 1. 2 波形編譯碼 不利用生成話音信號的任何知識而企圖產(chǎn)生一種重構(gòu)信號，它的波形與原始話音波形盡可能一致。 一般來說，這種編譯碼器的復(fù)雜程度比較低，數(shù)據(jù)速率在 16Kbps時可以取得較好的質(zhì)量。但如果數(shù)據(jù)率達(dá)不到這個要求，音質(zhì)就會下降很快。 波形編譯碼又可以分為時域法（ time domain approach）和頻域法(frequency domain approach)兩類。 第 三 章 多媒體數(shù)據(jù)壓縮 2. 音頻的壓縮 2. 1 音頻壓縮編碼的基本方法 2. 1. 2 波形編譯碼 時域法： PCM、 DPCM、 ADPCM 頻域法：子帶編碼 時域法中，最簡單的波形編碼是脈沖編碼調(diào)制（ pulse code modulation ,PCM），對輸入信號進(jìn)行采樣和量化。 第 三 章 多媒體數(shù)據(jù)壓縮 2. 音頻的壓縮 2. 1 音頻壓縮編碼的基本方法 2. 1. 2 波形編譯碼 PCM 均勻量化：如果采用相等的量化間隔對采樣得到的信號作量化，那么這種量化方法稱為均勻量化。 用這種方法量化輸入信號時，無論對大的輸入信號還是小的輸入信號一律都采用相同的量化間隔。 均勻量化面臨的問題：為了適應(yīng)幅度大的輸入信號，同時又要滿足精度要求，就需要增加樣本的位數(shù)。但是，對話音信號來說，大信號出現(xiàn)的機(jī)會并不多，增加的樣本位數(shù)就沒有充分利用。 為了克服這個不足，就出現(xiàn)了非均勻量化的方法，也叫做非線性量化。 第 三 章 多媒體數(shù)據(jù)壓縮 2. 音頻的壓縮 2. 1 音頻的壓縮編碼方法 2. 1. 2 波形編譯碼 PCM 非均勻量化：對輸入信號進(jìn)行量化時，