數(shù)據(jù)壓縮基礎(chǔ)ppt課件-閱讀頁
2024-11-18 22:14本頁面
【正文】 ? LZ77 算法在某種意義上又可以稱為“滑動窗口壓縮”，該算法將一個虛擬的，可以跟隨壓縮進程滑動的窗口作為詞典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長度。 44 LZ77編碼的基本流程 從當前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進行步驟 2，否則進行步驟 3。 其中 off 為窗口中匹配字符串相對窗口邊界的偏移， len 為可匹配的長度， c 為下一個字符，即不匹配的第一個字符。 輸出三元符號組 ( 0, 0, c )。然后將窗口向后滑動 1 個字符，繼續(xù)步驟 1。冗余信息表現(xiàn)在兩個方面，一是空指針，二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個匹配串中的字符。另外要輸出額外的標志位區(qū)分是指針還是字符。 輸出指針二元組 ( off, len)。 輸出當前字符 c， 然后將窗口向后滑動 1 個字符，繼續(xù)步驟 1。這也就是為什么這種算法成為開發(fā)新算法的基礎(chǔ)，許多后來開發(fā)的文檔壓縮程序都使用了 LZSS的思想。 ? LZSS同樣可以和熵編碼聯(lián)合使用，例如 ARJ就與霍夫曼編碼聯(lián)用，而 PKZip則與 ShannonFano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。編碼數(shù)據(jù)過程中當遇到已經(jīng)在詞典中出現(xiàn)的“短語”時，編碼器就輸出這個詞典中的短語的“索引號”，而不是短語本身。這樣一來，對字符流的編碼就變成了用碼字 (Code word)去替換字符流 (Char stream)， 生成碼字流 (Code stream)， 從而達到壓縮數(shù)據(jù)的目的。 53 LZ78編碼算法 步驟 1：將詞典和當前前綴 P都初始化為空。 步驟 3：判斷 P＋ C是否在詞典中 （ 1）如果“是”，則用 C擴展 P， 即讓 P:=P＋ C， 返回到步驟 2。在他們的研究基礎(chǔ)上， Terry 1984年發(fā)表了改進這種編碼算法的文章，因此把這種編碼方法稱為 LZW(LempelZiv Walch)壓縮編碼。 這就意味在開始時詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個字符 。 LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。 LZW編碼器的輸入是字符流 (Char stream)， 字符流可以是用 8位 ASCII字符組成的字符串，而輸出是用 n位(例如 12位 )表示的碼字流 (Code stream)， 碼字代表單個字符或多個字符組成的字符串(String)。 步驟 2：當前字符 C:=字符流中的下一個字符。 （ 2）如果“否”，則 輸出與當前前綴 P相對應(yīng)的碼字 W； 將 P＋ C添加到詞典中； 令 P:=C，并返回到步驟 2 58 LZW編碼舉例 位置 1 2 3 4 5 6 7 8 9 字符 A B B A B A B A C 步驟 位置 碼字 詞典 輸出 1 A 2 B 3 C 1 1 4 AB 1 2 2 5 BB 2 3 3 6 BA 2 4 4 7 ABA 4 5 6 8 ABAC 7 輸入數(shù)據(jù)流： 編碼過程： 59 LZW算法 LZW算法得到普遍采用，它的速度比使用 LZ77算法的速度快，因為它不需要執(zhí)行那么多的綴 符串比較操作。在 GIF圖像格式和 UNIX的壓縮程序中已經(jīng)采用了這些改進措施之后的 LZW算法。 60 預(yù)測編碼 ? 預(yù)測編碼是數(shù)據(jù)壓縮理論的一個重要分支。如果預(yù)測比較準確，那么誤差信號就會很小，就可以用較少的碼位進行編碼，以達到數(shù)據(jù)壓縮的目的。 61 DPCM編碼 預(yù)測器 xk ek xk x’k ek DPCM是有損型還是無損型關(guān)鍵看對預(yù)測誤差ek如何編碼。 求最佳線性預(yù)測的各個參數(shù) ai， 列方程組： ? ?2)( nn xxEm s e ???)1, . . . ,2,1(,0])[(2???? ??? nia xxEinn?????11niiin xax代入 得到聯(lián)立方程組： )1, . . . ,2,1(,][][11??? ???nixxEaxxEnlillin如果為一階線性預(yù)測，則可求得： ][][2111???nnn xExxEa 11 ??? nn xax64 圖像信號的預(yù)測編碼 ? 一副數(shù)字圖像可以看成一個空間點陣，圖像信號不僅在水平方向是相關(guān)的，在垂直方向也是相關(guān)的。 （ 2）二維預(yù)測（幀內(nèi)預(yù)測）：利用同一行和前面幾行的數(shù)據(jù)進行預(yù)測。 c a b x 選擇值 預(yù)測值 0 非預(yù)測 1 a 2 b 3 c 4 a+bc 5 a+(bc)/2 6 b+(ac)/2 7 (a+b)/2 d 三鄰域預(yù)測法 66 活動圖像的幀間預(yù)測編碼 ? 視頻信號的冗余度主要體現(xiàn)在空間相關(guān)性（幀內(nèi)）、時間相關(guān)性（幀間）和色度空間表示上的相關(guān)性。據(jù)統(tǒng)計 256級灰度的黑白圖像序列，幀間差值超過 3的象素數(shù)不超過 4％。 ? 幀間預(yù)測編碼技術(shù)被廣泛應(yīng)用到 、 、MPEG1和 MPEG2等視頻壓縮標準之中。 （ 2）運動物體區(qū)：可以視為由前一個畫面的某一區(qū)域的像素平移而成。 ? 運動補償預(yù)測就是將 前一個畫面的背景區(qū)＋平移后的運動物體區(qū) 作為后一個畫面的預(yù)測值。 （ 2） 運動矢量估值 ：考察前后兩個畫面，利用運動估值算法得到每個物體的位移矢量。 （ 4） 編碼 ：除了對實測值與預(yù)測值之間的差值進行編碼傳送外，還要傳送位移矢量以及區(qū)域分割信息。 X Y X’ Y’ XIDIAN 結(jié)束
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1