【正文】 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 5 變換編碼 通過對數據源的分析，將其分解成一系列更適合表示的“基元”，或從中提取出若干具有更本質意義的參數，編碼僅對這些基本單元或特征參數進行。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 4 預測編碼 變換編碼是有失真編碼的一種重要的編碼類型。 預測參數的最佳化依賴于信源的統計特性，要得到最佳預測參數是一件繁瑣的工作，而采用固定的預測參數往往又得不到較好性能。 ADPCM編碼：采用自適應量化或自適應預測。這樣，再同等精度要求的條件下，可以用較少的位數進行編碼，達到壓縮數據的目的。 LZWE ：截去 “ 死 ” 節(jié)點 LZWEP：在 LZWE基礎上采用前綴編碼 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 預測編碼是根據原始的離散信號之間存在著一定的關聯性的特點，利用前面的一個或多個信號對下一個信號進行預測，然后對實際值和預測值的差進行編碼。 解碼器在相應的時刻并不知道此信息，但可以根據接下來的 的信息進行相應的 LZW樹構造。 第 K個 LZW段是從未劃分部分的第一個字符開始，在當前的 LZW樹中找出一個最長的匹配， 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZW編碼 在劃分出 之后，編碼器就對 LZW樹進行更新；在 所對應的節(jié)點再擴展出 一個分支節(jié)點。 LZW樹開始時由根節(jié)點和所有的單字符量構成。 LZW的一個重要特征是采用了 Welch修正，其目的是克服發(fā)送每段最后一個未壓縮字符造成的低效率。將活節(jié)點進行前綴編碼，不考慮它們的概率特性（假設概率相等）。在本例中，LZ78SE需要 33位二進制數來完成編碼。 LZ78SE：將 LZ78E和 LZ78S結合。我們可將“死”節(jié)點截去，解碼器知道什么時候節(jié)點死掉，也就知道什么時候把節(jié)點截去，只要編碼器和解碼器采用相同的方法。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78E編碼 LZ78E：一個節(jié)點不會被第三次指定為“父節(jié)點”。 上例中，段 3是根節(jié)點的最后一個子節(jié)點，段 4是節(jié)點 1的最后一個后代，段11是節(jié)點 2的最后一個后代。這樣就可以壓縮掉一位。最簡單的編碼方法， [log2k]能夠描述其父節(jié)點，然后在加上最后一位， [log2k]+1可以描述這個段。解碼器建立樹的信息被包含在連續(xù)的段中。 段 K：可以用編碼樹中其父節(jié)點的序列以及其位于其父節(jié)點的左支還是右支來表示，這樣，編碼器就可以向解碼器精確的指出下一段。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ78編碼 00010110000010100100100010011 LZ78劃分結果： 0， 00， 1， 01， 10， 000， 010， 編碼的過程中可以構造出一顆 LZ78樹（即詞典），編碼器，輸出節(jié)點的序號和“向左”或“向右”的信息。同時，解碼器也能與編碼器同步的建立 LZ78樹。在編碼器和解碼器端都遵守事先約定的構建方法。 以二進制串為例，介紹 LZ78編碼。但是，在壓縮后的數據流中，并不需要保存這張詞典。缺點：由于輸出的壓縮數據流中包含有指針和字符本身，為了區(qū)分它們就需要有額外的標志位。 LZSS算法以比較有效的方法解決兩個冗余。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 例 第一次輸出 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 第二次輸出 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 第三次輸出 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 第四次輸出 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 第五次輸出 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 真正實現 LZ77 算法時還有許多復雜的問題需要解決，如： ? 對“ (Back_chars, Chars_length) Explicit_character”三元組的編碼方法 ? 如何查找最長匹配串 ? 窗口的最大長度 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZSS編碼 LZ77通過輸出真實字符解決了在窗口中出現沒有匹配串的問題，但這個解決方案包含有冗余信息。 3. 以“ (Pointer, Length) Characters”的格式輸出，其中 Pointer是指向窗口中匹配串的指針， Length表示匹配字符的長度， Characters是前向緩沖存儲器中的不匹配的第 1個字符。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 編碼算法的具體執(zhí)行步驟： 1. 把編碼位置設置到輸入數據流的開始位置。 6. 指針 (pointer)：指向窗口中的匹配串且含長度的指針。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ77壓縮 4. 前向緩沖存儲器 (Lookahead buffer)：存放從編碼位置到輸入數據流結束的字符序列的存儲器。 2. 2. 字符 (character)：輸入數據流中的基本單元。 LZ算法的變體，典型的兩種， LZ77和 LZ78，使用的劃分方法有所不同。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 3 通用無損信源編碼 LZ編碼： LZ編碼是一種被廣泛使用的自適應的編碼方法，它有許多變體。 因此，編碼器事先不知道數據源的概率時，可以在數據流中憑經驗逐步精確地估測。 （ 3）算術編碼是一種對錯誤和敏感的編碼方法，如果有一位發(fā)生錯誤就會導致整個消息譯碼錯誤。轉（令 2, nnnnn lrdrRlL ????第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 2 統計編碼 n Xn ＝ ai In L (二進制 ) R(二進制 ) 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 算術編碼 應注意的幾個問題： （ 1）由于實際的計算機的精度不可能無限長，運算中出現溢出是一個明顯的問題，在編碼的時候必須注意，可以采用一些方法來解決。 初始條件： 考慮一個有 M個符號的字符表集 {a1, …… ， am}，假設概率 p(ai)＝ Pi 。算術編碼用到兩個基本的參數：信源符號出現的概率和編碼的間隔。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 2 統計編碼 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 2 統計編碼 位置差異 垂直碼 3 0000010 2 000010 1 010 0 1 － 1 011 － 2 000011 － 3 0000011 算術編碼 算術編碼在圖像的壓縮中被廣泛的使用。把 a0移到 a1位置，更新其他 4個參數，回到第一步。否則，使用垂直碼編碼。把 a0移動致 b2這一列，更新其他四個參數（其中 a1和 a2不會改變），然后重復這一步。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 2 統計編碼 4類傳真標準 CCITT Group 3 2D 編碼過程： b2不是嚴格的位于 a1左邊，則進入第二步。 a0表示準備編碼的行程起始位置的像素點， a1為當前行下一個行程起始位置的像素點， a2表示再下一個行程起始位置的象素點。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 2 統計編碼 位置差異 垂直碼 3 0000010 2 000010 1 010 0 1 － 1 011 － 2 000011 － 3 0000011 4類傳真標準 CCITT Group 3 2D 二維編碼：一種循環(huán)算法，依靠 a0, a1,a2,b1,b2 五個參數的更新來循環(huán)。附加碼有 3種：垂直碼，越過碼，水平碼。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 2 統計編碼 4類傳真標準 CCITT Group 3 2D 編碼方法：每個 K組的第一條線采用 Group3 1D方式編碼，以作為這組 K條線中其余線的掃描線。 原因：橫跨相鄰兩條掃描線的圖像數據可能是冗余的。 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 2 統計編碼 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用數據壓縮方法的基本原理 1. 3. 2 統計編碼 白色游程 碼字 黑色游程 碼字 0 00110101 0 0000110111 1 000111 1 010 2 0111 2 11 3 1000 3 10 …… 63 00110100 63 …… EOL 000000000001 終止碼 第 三 章 多媒體數據壓縮 1. 數據壓縮的基本原理和方法 1. 3 常用