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