數(shù)據(jù)壓縮基礎(chǔ)ppt課件(存儲版)
【正文】 A 步驟 位置 匹配串 輸出 1 1 －－ 0, 0, A 2 2 A 1, 1, B 3 4 －－ 0, 0, C 4 5 B 2, 1, B 5 7 ABC 5, 3, A 47 LZSS算法 ? LZ77通過輸出真實字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個解決方案包含有冗余信息。 49 LZSS編碼舉例 位置 1 2 3 4 5 6 7 8 9 10 11 字符 A A B B C B B A A B C 步驟 位置 匹配串 輸出 1 1 －－ A 2 2 A A 3 3 －－ B 4 4 B B 5 5 －－ C 6 6 BB （ 3， 2） 7 8 AAB （ 7， 3） 8 11 C C 輸入數(shù)據(jù)流： 編碼過程 MIN_LEN =2 50 LZSS算法 ? 在相同的計算機環(huán)境下， LZSS算法比 LZ77可獲得比較高的壓縮比，而譯碼同樣簡單。 ? LZ78編碼器的輸出是碼字 字符 (W,C)對，每次輸出一對到碼字流中，與碼字 W相對應(yīng)的字符串(String)用字符 C進行擴展生成新的字符串 (String)，然后添加到詞典中。 即在編碼匹配時，至少可以在詞典中找到長度為 1的匹配串。對 LZW算法進一步的改進是增加可變的碼字長度，以及在詞典中刪除老的綴 符串。 預(yù)測方程式 線性預(yù)測： 如果 ai是常數(shù)，則為時不變線性預(yù)測，否則為自適應(yīng)線性預(yù)測（ ADPCM） 最簡單的預(yù)測方程： ?????11)(kiiik xkax),. . . . . .,( 1321 kxxxxfx kk ???1??? kk xx最佳線性預(yù)測 使誤差函數(shù) 達到最小值的預(yù)測方程式叫做最佳線性預(yù)測。所以在活動圖像序列中可以利用前面的幀來預(yù)測后面的幀，以實現(xiàn)數(shù)據(jù)壓縮。 （ 3） 運動補償 ：用運動矢量補償物體的運動效果再進行預(yù)測。 68 運動補償幀間預(yù)測編碼 運動補償幀間預(yù)測從原理上包括如下幾個基本步驟： （ 1） 圖像分割 ：把圖像劃分為靜止的背景和若干運動的物體，各個物體可能有不同的位移，但構(gòu)成同一物體的所有像素的位移相同。 ? 對于每秒 25幀（ 30）的電視信號，其相繼幀之間存在極強的相關(guān)性。 ? 第 n個符號 Xn的熵滿足： ). . .|(. . . . . .)|()|()( 121211 xxxxHxxxHxxHxH nnnnnnnnn ????? ????所以參與預(yù)測的符號越多，預(yù)測就越準確，該信源的不確定性就越小，數(shù)碼率就可以降低。 步驟 3：判斷 P＋ C是否在詞典中 （ 1）如果“是”，則用 C擴展 P， 即讓 P:=P＋ C， 返回到步驟 2。 在編碼原理上， LZW與 LZ78相比有如下差別： LZW只輸出代表詞典中的字符串 (String)的碼字 (code word)。 52 LZ78算法 ? LZ78的編碼思想是不斷地從字符流中提取新的字符串 (String)， 通俗地理解為新“詞條”，然后用“代號”也就是碼字 (Code word)表示這個“詞條”。 其中 off 為窗口中匹配字符串相對窗口邊界的偏移， len 為匹配串的長度，然后將窗口向后滑動 len 個字符，繼續(xù)步驟 1。 其中 c 為下一個字符。 42 第一類詞典編碼 ? 第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的 “ 指針 ” 。 ? 行程編碼多用于黑白二值圖像的壓縮中。消息序列中元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時，就需要更多的數(shù)位來表示這個區(qū)間。 （ 2）用遞歸的方法分成兩部分，使兩個部分的概率和接近于相等。 25 聯(lián)合熵與條件熵 ? 設(shè)隨機變量 X和 Y分別取值于符號表 {a1, a2, …a m}和 {b1, b2, b3, …b n} ? 定義 X與 Y的聯(lián)合熵為： ? 定義 X關(guān)于 Y的條件熵為： ? ?? ???mjnkkjkj baPbaPYXH1 1),(l o g),(),(? ?? ???mjnkkjkj baPbaPYXH1 1)|(l o g),()|(26 離散有記憶信源的冗余 )()|( XHYXH ?)()()|()(),( YHXHXYHXHYXH ????聯(lián)合熵與其可能達到的最大值之間的差值反映了該有記憶信源所含的冗余度，這種冗余是由于隨機變量序列之間的相關(guān)性造成的。 m為字符集中字符個數(shù)。y) I(xy) )()()()。(ypxpxypxpyxpyxI ??)。比如語音信號 X(t)。 多媒體 數(shù)據(jù) 數(shù)據(jù)壓縮的必要性 5 數(shù)字音頻格式頻帶( H z)帶寬( K H z)取樣率( K H z)量化位數(shù)存儲容量 ( M B )電話200 ~ 3 4 0 0 3 .2 8 8 0 .4 8會議電視伴音 50 ~ 7 0 0 0 7 16 14 1 .6 8CD D A20 ~ 2 0 0 0 0 20 4 4 .1 16 5 .2 9 2 2DA T20 ~ 2 0 0 0 0 20 48 16 5 .7 6 2數(shù)字音頻廣播20 ~ 2 0 0 0 0 20 48 16 5 .7 6 6分鐘 數(shù)字 音 頻信號需要的存儲空間 1 6 數(shù)字電視 格 式 空間時間分辨率 取樣率(M Hz)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1