【文章內(nèi)容簡介】 像傳輸 ? 壓縮和解壓縮速度相同 – 非對稱壓縮 ? 解壓縮實時，壓縮非實時，如 CD－ ROM的制作與播放 ? 壓縮比解壓縮速度慢 – 數(shù)據(jù)的計算量 ? 壓縮和解壓縮都需要大量的計算 ? 通常解壓縮比壓縮的計算量小 壓縮方法簡潔說明 特點 描述 無損的 無失真地準(zhǔn)確地恢復(fù)原始數(shù)據(jù) 有損的 有失真 幀內(nèi) 獨立地完成幀的編碼 幀間 參照前、后幀對幀進行編碼，并考慮 幀之間的時間冗余 對稱 編碼及譯碼的訪問幾乎相等 不對稱 編碼時間比譯碼時間長很多 實時 編 譯碼延遲不應(yīng)該超過 50ms 數(shù)據(jù)壓縮與解壓縮常用算法 數(shù)據(jù)壓縮方法的分類 ? 數(shù)據(jù)壓縮方法也稱編碼方法 ? 按是否產(chǎn)生失真分 – 無失真編碼：可逆編碼，無損壓縮 – 有失真編碼：不可逆編碼，有損壓縮 ? 按原理分 – 預(yù)測編碼 ? 針對空間冗余和時間冗余 ? 利用已被編碼的點的值預(yù)測鄰近的點的值 – 變換編碼 ? 針對空間冗余和時間冗余 ? 將圖像或時域信號變換到頻域上，再進行壓縮 – 子帶編碼：分頻帶編碼 ? 將數(shù)據(jù)變換到頻域后，按頻率分帶，分別量化 ? 語言和圖像 – 信息熵編碼 ? 概率大的符號用短碼字表示，反之用長碼字表示 ? 哈夫曼編碼 – 行程編碼：游程編碼、運行長度編碼 ? 相同值的連續(xù)串用該值和串長代替 ? 如 MDDDDDDDDDDG用 M!10DG表示 000011111000用 0453表示，第 1位 0表示該串首碼是 0，第 2位 4表示有 4個 0，第 3位 5表示 5個 1，第 4位 3表示 3個 0。因為二進制非 0即 1。 壓縮方法分類 哈夫曼編碼 ? 最佳編碼定理 – 哈夫曼 1952年提出 – 內(nèi)容：在變字長編碼中，對于出現(xiàn)概率大的信息符號編以短字長的碼，對于概率小的符號編以長字長的碼。如果碼字長度嚴(yán)格按所對應(yīng)符號出現(xiàn)概率大小逆序排列，則平均碼字長度一定小于其他以任何符號順序排列方式得到的平均碼字長度。 ? 哈夫曼編碼方法 – 根據(jù)以上定理而得到的一種編碼方法 – 步驟 ? ，給最后兩個符號賦予一個二進制碼，概率大的賦 1，小的賦 0（反之亦可） ? ，重復(fù)上一步 ? 2，直到最后只剩下兩個概率為止 ? 0,1反序排出即可 哈夫曼編碼方法過程演示 A1 A2 A3 A4 A5 A6 A7 符號 概率 P 1 0 1 0 1 0 1 0 1 0 0 1 1 編碼 01 00 111 110 101 1001 1000 可以看出，概率大的符號其編碼短，概率小的符號其 編碼長，符號使用其編碼來表示，達到數(shù)據(jù)壓縮目的。 哈夫曼編碼結(jié)果分析 ? 碼字的平均長度 _ 7 N=∑niP(ai)= i=1 ? 信息符號的熵值 7 H(a)=∑P(ai)log2P(ai) = i=1 ? 可見，哈夫曼編碼結(jié)果，其平均長度接近于信息符號的熵值，但是仍有冗余 編碼 01 00 111 110 101 1001 1000 碼長 n 2 2 3 3 3 4 4 例如 ： 信源有四個符號： X a1 a2 a3 a4 1/2 1/4 1/8 1/8 信息熵： H(x)= 1/2log2(1/2)1/4log2 (1/4)(1/8log2 (1/8) ?2= bit/字符 采用哈夫曼編碼（二進制編碼） a1 a2 a3 a4 0 10 110 111 平均碼長： L= (1/2) ? 1+(1/4) ? 2+(1/8) ? 3 ? 2 = bit/字符 編碼效率： ?=a1 a2 a3 a4 1/2 1/4 1/8 1/8 符號 概率 0 1 1/4 0 1 1/2 0 1 1 編碼 0 10 110 111 4個符號 采用 PCM編碼： R= log24=2 bit a1 a2 a3 a4 00 01 10 11 L=2 ??Pi = 2 編碼效率： ?=H(x)/L= ? 哈夫曼編碼的特點 – 其實就是數(shù)據(jù)結(jié)構(gòu)中的二叉樹形式 – 無歧義性 ， 能正確地恢復(fù)原信號 – 構(gòu)造出來的碼不唯一 ? 有兩種賦值方式：概率大的賦 1， 小的賦 0， 反之亦可 ? 兩符號概率相等時 ， 其排列順序隨機 ， 造成編碼不唯一 – 編碼出來的字長不統(tǒng)一 ， 硬件實現(xiàn)困難 – 對不同的信號源 ， 編碼效率不同 ， 等概率信源 ， 效率最低 – 編碼后形成一個哈夫曼編碼表 ， 若正確解碼必須有此碼表 ， 于是在傳送過程中也要傳送此碼表 預(yù)測編碼 ? 原理 – 利用以往的樣本值對新樣本值進行預(yù)測 – 將新樣本值的實際值與其預(yù)測值相減，得到誤差值 – 對該誤差值進行編碼，傳送此編碼即可 – 理論上數(shù)據(jù)源可以準(zhǔn)確地用一個數(shù)學(xué)模型表示，使其輸出數(shù)據(jù)總是與模型的輸出一致，因此可以準(zhǔn)確地預(yù)測數(shù)據(jù)，但是實際上預(yù)測器不可能找到如此完美的數(shù)學(xué)模型 ? 典型方法 – DPCM：差分脈沖調(diào)制預(yù)測， Differential Pulse Code Modulation – ADPCM：自適應(yīng)差分脈沖調(diào)制預(yù)測， Adaptive Differential Pulse Code Modulation 差分脈沖調(diào)制（ DPCM）預(yù)測原理圖 量化器 預(yù)測器 譯碼器 預(yù)測器 － ＋ ＋ 編碼器 發(fā)送端 接收端 Xn dn ^ Xn Xn’ dn’ dn’ ^ Xn Xn’ 差分脈沖調(diào)制（ DPCM）預(yù)測 ? 是降低每個像素所需平均比特數(shù)的最使用的方法 ? 說明 – 發(fā)送端預(yù)測器帶有存儲器，把 tn時刻以前的采樣值 x1, x2, x3, xn1存儲起來并據(jù)此對 xn進行預(yù)測，得到預(yù)測值 – dn為 xn與 的差值， dn’ 為 dn經(jīng)量化器量化的值 – xn’ 是接收端的輸出信號 – 誤差 qn為 qn= xn xn’ = xn( +dn’ )=(xn ) dn’ = dn dn’ 實際上就是發(fā)送端的量化器對誤差量化的誤差 對 dn’ 的量化越粗糙，壓縮比越高，失真越大 ^ Xn ^ Xn ^ Xn ^ Xn ? 對于圖像預(yù)測編碼 – Xn表示被預(yù)測的像素， x1, x2, x3, xn1則是根據(jù)不同的預(yù)測方案被選出來的已知像素點 – 一維預(yù)測：同一行 – 二維預(yù)測：不同行 – 三維預(yù)測：不同幀 – 一維預(yù)測利用像素之間在水平方向 上的相關(guān)性。在水平方向上亮度變 化緩慢地圖像效果好。但是有亮度 突變就不行。 圖中黑白條： =x1=0(黑色 ) 可采用二維預(yù)測 ： x4x5 1 =x1+———— = —— 2 2 差分脈沖調(diào)制（ DPCM）預(yù)測 X5 X4 X3 X2 X1 Xn x1 xn ^ Xn ^ Xn + ^ Xn 差分脈沖調(diào)制（ DPCM）預(yù)測 ? 輸入數(shù)據(jù)為平穩(wěn)的隨機過程 ? 預(yù)測器的設(shè)計是預(yù)測編碼系統(tǒng)的核心：預(yù)測參數(shù) ? 無損壓縮，對預(yù)測誤差的量化是造成圖像質(zhì)量下降的主要原因 自適應(yīng)差分脈沖調(diào)制（ ADPCM）預(yù)測 ? 輸入數(shù)據(jù)不是平穩(wěn)的隨機過程 ? 自適應(yīng)預(yù)測 ? 定期重新調(diào)整預(yù)測器的預(yù)測參數(shù)，使預(yù)測器隨輸入數(shù)據(jù)的變化而變化 ? 自適應(yīng)改變量化器的量化階數(shù)，用小量化階量化小差值，大量化階量化大差值 ? 分為線性自適應(yīng)預(yù)測與非線性自適應(yīng)預(yù)測兩種 差分脈沖調(diào)制（ DPCM）預(yù)測示例 例如 ， 取一序列為 10， 12， 14， 16， 18， 20。 （ 例如亮度變化緩慢的圖像的亮度值 ） 由于其中所有數(shù)字都不相同 ， 但是是一個等差的數(shù)列 ， 所以行程編碼和哈夫曼對其不產(chǎn)生壓縮效果 。 先用 DPCM方法 ， 其預(yù)測器的預(yù)測參數(shù)為 Xn=Xn1， 則其誤差值得到一個新的序列 10， 2， 2， 2， 2， 2。 然后再使用行程編碼方法對這個新序列進行壓縮 ， 壓縮結(jié)果為 10(5,2)。 LZ77壓縮編碼 ? 1977年由兩個以色列人 Lempel,Ziv提出 ， 1984年由 Welch改進 ， 成為 LZW算法 ? 先進的無損數(shù)據(jù)壓縮技術(shù) ， 壓縮和解壓縮速度快 ? LZ77技術(shù)特點 – 穩(wěn)定 ， 有效 ， 快速 – 有時壓縮后比壓縮前文件大 ? 應(yīng)用 – 應(yīng)用在幾乎日常使用的所有通用壓縮工具中 ， ARJ，PKZip， WinZip， RAR， ACE以及 GIF圖像文件等 – 某些硬件如網(wǎng)絡(luò)設(shè)備中內(nèi)置的壓縮算法 LZ77壓縮編碼 ? 基本原理 – 建立一個轉(zhuǎn)換表（串表）。通過簡單的代碼來替換比較復(fù)雜的字串，把一個字符串映射為一定長度的編碼，并用一個轉(zhuǎn)換表（串表）記錄這些替換關(guān)系。 – 將已經(jīng)編碼過的信息作為字典，如果要編碼的字符串曾經(jīng)出現(xiàn)過，就輸出該字符串的出現(xiàn)位置及長度，否則輸出新的字符串。 – 解壓縮時，自動建立與壓縮時一樣的串表 – 簡單概括：就是字典壓縮，串表即字典 索引碼 字符串 索引碼 字符串 CX 操作系統(tǒng) DM 多媒體 SK 數(shù)據(jù)庫 SJ 數(shù)據(jù)結(jié)構(gòu) LZ77壓縮編碼 P=(5,3) 輸出：吃葡萄不吐 (4,2)皮， (6,1)(10,1)(10,2)倒 (10,4) 輸入：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮 變換編碼 ? 原理 – 為達到目的，可以通過不同的路徑 —— 殊途同歸 – 例如：數(shù)學(xué)計算機中，經(jīng)常利用某些數(shù)學(xué)函數(shù)略加轉(zhuǎn)換可以找出一條計算的捷徑。 乘法： 1000000X100000＝ 100000000000 運算時，數(shù)據(jù)很大，可以變成對數(shù)進行加法 1000000 X 100000＝ 100000000000 取對數(shù) lg106 取對數(shù) lg105 取指數(shù) 1011 6 ＋ 5 ＝ 11 算法變換 變換編碼 ? 基本概念 – 先對信號進行某種函數(shù)變換 ，從一種域 （ 空間 ） 變換到另一種域 （ 空間 ） ， 再對變換后的信號進行編碼處理 – 以聲音圖像為例 ， 由于聲音圖像大部分信號都是低頻信號 ， 在頻域中信號較集中 ，因此將時域信號變換到頻域 ，再對其進行采樣 、 編碼 0 X1 X2 變換去掉相關(guān)性示意圖 相鄰采樣值 x1,x2各用 3bit編碼，有 64種合成可能，變換后， X1’ ,X2’合成種類減少。 X1’ X2’ 變換編碼原理框圖 變換 量化 譯碼器 預(yù)測器 編碼器 發(fā)送端 接收端