數(shù)字壓縮技術

1、第六章 數(shù)據(jù)壓縮技術I 信息的數(shù)據(jù)量和壓縮的必要性 數(shù)字化了的圖像、視頻、音頻等信息數(shù)據(jù)量很大。數(shù)據(jù)壓縮的可能性 原始信源數(shù)據(jù)存在很大冗余度 視覺掩蓋效應(對亮度敏感,對邊緣急劇 人的生理特性 變化不敏感) 聽覺：對部分頻率信號不敏感 壓縮去掉冗余信息和一些不敏感信息。 無損壓縮 ： 源壓縮存儲傳輸解壓目的 （源與目的信息一模一樣。） 有損壓縮： 源與目的信息有差別。數(shù)據(jù)冗余的概念和分類 （1）冗余的基本概念 信息量與數(shù)據(jù)量的關系可由下式給出: I=D-du I : 信息量 D: 數(shù)據(jù)量 du : 冗余量 例:讀一篇文稿,每分鐘180字,一個漢字占兩個字節(jié)（內 碼）,每分鐘文本 數(shù)據(jù)量 360

2、b； 若對語言直接錄音, 4K28=64Kb/s (8b) 每分鐘數(shù)據(jù)量: 480Kb （2）數(shù)據(jù)冗余的類別 空間冗余 規(guī)則物體和規(guī)則背景的表面物理特性具有相關性。 時間冗余 連續(xù)播放的畫面，前后幾幀背景基本無變化。 例如：小車行駛，外型無變化。（只需小車運動矢量）。 統(tǒng)計冗余。 空間、時間冗余，把圖象信號看作概率信號時所反映出的 統(tǒng)計特性。 結構冗余。 物體表面紋理等結構。（規(guī)則圖形，冗余量大） 信息熵冗余。 熵定義：1k0i2PilogPiEiP ： 在S中出現(xiàn)的概率， 表示包含在 中的信息 量，也就是編碼 所需要的位數(shù)。 但 難預估，取位數(shù)為最多信息所需位數(shù)， 帶來信息熵冗余。 i2PL

3、OGiSiSiS1K0PP視覺冗余 人類視覺系統(tǒng)特點：對圖象場的注意是非均勻和非線性的。 a. 對亮度比對色度敏感 b. 并非圖象任何變化均能感知。 分辨能力： 灰度等級 一般圖象量化采用 灰度等級6282知識冗余。 人有先驗知識：圖象的結構等，但在計算機存儲時未考慮。其他冗余。 圖象的空間非定常特性帶來的冗余。數(shù)據(jù)壓縮的編碼方法 1、數(shù)據(jù)壓縮方法的分類 編碼過程：對原始數(shù)據(jù)經過編碼進行壓縮 解碼過程：對編碼數(shù)據(jù)進行解碼、還原壓縮處理過程（1）可逆編碼（無損壓縮） 信息非丟失型編碼 無損壓縮 解碼圖象與原始圖象嚴格相同。 基于信息熵原理，如哈夫曼編碼、算術編碼、游程編碼。 壓縮能力：與所處理圖

4、象的信息熵有關，壓縮比不太大。 應用：要求不丟失信息（醫(yī)療、衛(wèi)星圖象通信系統(tǒng)等）。（2）不可逆編碼（有損壓縮） 信息丟失型編碼 還原圖象與原始圖象存在一定誤差。 (3) 對稱壓縮壓縮算法與解壓算法一樣收發(fā)雙方以同一種速度操作，適用于實時應用場合 2、常用的壓縮編碼 預測編碼：以相鄰的且已被編碼的點對目前點進行預測估計。 基礎：同幀圖象的相鄰像素點之間相關性比較強。(4)不對稱壓縮壓縮與解壓縮速率不同如：視頻光盤針對統(tǒng)計冗余進行的壓縮。變換編碼：將圖象光強矩陣(時域信號) 系數(shù)空間(頻域) 上進行處理。 針對統(tǒng)計冗余進行的壓縮。變換信息熵編碼：概率大的信息用短碼字表示。 概率小的信息用長碼字表示

5、。分頻帶編碼：時域 頻域，按頻率分帶，用不同的量化器 進行量化。量化與向量量化編碼：模擬 數(shù)字，量化。 一次量化多個點：向量量化。 結構編碼：結構特征抽?。ㄟ吔?、輪廓、紋理），保存參數(shù)。 基于知識的編碼：利用人的知識形成規(guī)則庫，用參數(shù)描述， 實現(xiàn)圖象編碼和解碼。 某一事件信息量定義： 0P i 1 Pi 為第i個事件的概率 i2iPLOGI22LOG NiiILOG P 2、信源S的熵的定義一、香農-范諾編碼 1、熵的概念 熵是信息量的度量方法，它表示某一事件出現(xiàn)的 消息越多，事件發(fā)生的可能性就越小，也就是概率越小。特例：某信息源有N個事件，且任一事件概率均相等，為1/N，則：所傳輸?shù)南⒘渴?/p>

6、其出現(xiàn)概率的單調下降函數(shù)。例：如果從256個數(shù)中猜一個數(shù)，最少提問幾次一定可以猜到？ 第一次，“是否大于128？” 消去一半可能 共8次 也就是說，每次提問會得到1b的信息量。 因此，在256個數(shù)中選定某一個數(shù)所需要的信息量為： b8256log2信息量是指從N個相等可能事件中選出一個事件所需要的信息度量或含量，也就是在辨識N個事件中特定的一個事件的過程中所需提問“是或否”的最少次數(shù)。 根據(jù)香農理論，信源S的熵的定義： 是 在S中出現(xiàn)的概率。 是包含在 中的信息量，也是編碼 所需位數(shù)。例1：一幅圖象用256級灰度表示，若每一個像素點灰度概率為： 則編碼每個像素點需要8位。)P/1 (LOGi2

7、iSiS2561)(iSPNiiiNiiiNiiiSPLOGSPPLOGPPLOGPSH121212)()()/1 ()()(iSPiS例2、一幅灰度圖象有40個像素組成，灰度共5級，分別用符號 A、B、C、D、E表示，40個像素中出現(xiàn)灰度A的像素數(shù)有 15個，灰度B的有7個，C的有7個，D的有6個，E的有5個， 若用3位表示5個等級的灰度值，編碼這幅圖象總共需要 120 位，用香農理論，圖象熵為： )7/40(LOG)40/7()15/40(LOG)40/15()X(H22196. 2)5/40(LOG)40/5(2若平均每個灰度用2.196位表示,則圖象總共需要87.84位。用香農范諾算法

8、編碼：首先，將灰度概率從大到小排列出現(xiàn)次數(shù)（ ）分配的代 碼需要的位數(shù) A15 （0.375) 1.4150 00 30 B7 (0.175) 2.5145 01 14 C7 (0.175) 2.5145 10 14 D 6 (0.150) 2.7369 110 18 E5 （0.125) 3.0000 111 15總位數(shù):91iP壓縮比：1.3 : 1ABCDE00111100)P/ 1 (LOGi2二、霍夫曼編碼 以前舉的例2：一幅圖象5個灰度等級，40個像素。代碼 出現(xiàn)次數(shù)位數(shù)A 0 15 15B 100 7 21C 101 7 21D 110 6 18E 111 5 15 共90位 （

9、1）霍夫曼編碼步驟 P.234100.275 概率A 0.375B 0.175C 0.175D 0.150E 0.125 00.35001101壓縮比：1.33 : 1 （2）霍夫曼編碼特點 碼不唯一。 碼字變長（硬件實現(xiàn)不大方便）,但不需要另外附加同步代 碼。（在壓縮文件中查找或調用內容困難）。 概率分布不同，編碼效率不同。（效率比香農-范諾編碼高） （概率分布不 均勻,效率高；概率分布 均勻,效率低，一般不用） Huffman編碼表解碼要用 傳輸要考慮編碼表所占比特率數(shù) 若編碼基于大量概率統(tǒng)計，傳輸可省去Huffman編碼表 使用缺省的Huffman編碼表 霍夫曼碼沒有錯誤保護功能三、算術

10、編碼 在圖象數(shù)據(jù)壓縮標準（JPEG等）中扮演重要角色。 消息：用01之間實數(shù)進行編碼。 算術編碼參數(shù)：符號的概率和它的編碼間隔。 （1）例：假設信源符號為 00, 01, 10, 11 其相應概率 分別為 0.1, 0.4, 0.2 , 0.3 根據(jù)概率把間隔0,1)分 成 0，0.10），0.1，0.5），0.5，0.7），0.7，1） 4個子間隔 。 符號 概率初始編碼間隔 00 0.1 0, 0.1) 01 0.4 0.1, 0.5) 10 0.2 0.5, 0.7) 11 0.3 0.7, 1)二進制消息序列 10 00 11 00 10 11 01.第一個符號為10,它的編碼范圍:

11、0.5, 0.7)第二個符號為00,它的編碼范圍: 0 , 0.1),它的間隔取 0.5, 0.7)的第一個十分之一作為新間隔 0.5,0.52)第三個符號為11,它的編碼范圍: 0.7, 1),它的間隔取 0.5, 0.52)的最后三個的1/10 , 新間隔 0.514,0.52) 0.020.7=0.014 0.020.7+0.50.20.1+(0.20.1) 依次類推 輸出的消息編碼：最后一個間隔中的任意數(shù)。 從 0.5143876 , 0.514402)中,選一個數(shù)作為輸出。取0.5143876譯碼過程 譯碼符號 間隔0.5143876在間隔0.5, 0.7) 10 0.5, 0.7)

12、0.5143876在間隔0.5, 0.7)的第一個1/10 00 0.5, 0.52)0.5143676在間隔0.5, 0.52)的第7個1/10 11 0.514, 0.52) .譯碼消息: 10 00 11 00 10 11 01 (2)編碼算法:一個有M個符號 (i=1,2,3 ,M)的字符集,假定概率ianX輸入符號用 表示,第n個子間隔范圍用以下公式表示:,)(iiPaP1PPP)a (PM21iM1iii1ii1ni1i1i1n1nnnnPdlPdl rl I），），1-n且 和 表示 間隔左邊界的值， 表示 間隔右邊界的值， 表示 間隔長度。則編碼按以下步驟進行：首先在1和0之間

13、給每個符號分配一個初始間隔，子間隔的長 度等于它的概率。 初始子間隔的范圍用右式表示： 令 ，L= 和R=1d, 0l00, 0P0nlnrnnnlrd)PP)r ,l Ii1ii1ii, 1i111111lrd1l1rL和R的二進制表達式分別表示為： 1u若 ，不發(fā)送任何數(shù)據(jù)，轉到步驟。若 = ，就發(fā)送二進制符號 。1kkk2uL和1kkk2vR其中 和 等于“0”或“1”。 kukv比較 和1u1u1v1u1v1v2u2v2uinaX 若 ，不發(fā)送任何數(shù)據(jù)，轉到步驟 若 ，就發(fā)送二進制符號 比較直到兩個符號不相同，然后轉入步驟n+1，讀下一個符號。假設第n個輸入符號為 ，按照以 前的步驟把

14、這個間隔分成如下子間隔： 令 ， ， 然后轉到步驟 例：輸入序列 ： ， ， i1ii1n1ni1i1i1n1nn,nn)PdI ,PdI )rl InlL nrR nnlrdnX2a1a3a比較 和22vu22vu輸入的第一個符號: , 則 i =2, 定義初始間隔： 符號概率 初始編碼間隔 =0.5 0, 0.5) =0.25 0.5, 0.75) =0.125 0.75, 0.875) =0.125 0.875, 1)1a2a3a4a1p2p3p4p21ax i1ii1ii1i1, 11),75. 0 , 5 . 0)p,p)rl I則知 。25. 0d1左、右邊界二進制表示：L=0.5

15、=0.1(B) R=0.75=0.11(B)。按步驟， ，發(fā)送1， 轉到步驟 22vu11vu 輸入第三個字符： ， i =3, 子間隔：33ax i1ii1ii111i112, 22),625. 0 , 5 . 0)pdl ,pdl )rl I 得 。125. 0d2L=0.5=0.100(B) R=0.625=0.101(B)。 發(fā)送0， 轉到步驟0vu2233vu 輸入第二個字符： ， i =1, 子間隔：12axi1ii1ii221i22333),609375. 0 ,59375. 0)pdl ,pdl )r ,l I015625. 0d3L=0.59375=0.10011(B) R=

16、0.609375=0.100111(B)。 發(fā)送0， ，發(fā)送1， 發(fā)送1， ， 轉到步驟.0vu3366vu 1vu441vu55發(fā)送編碼: 10011+結束符。特點: 1) 對整個消息只產生一個碼字(0，1）中的一個實 數(shù)），譯碼器需接收所有位才能譯碼。 2）對錯誤敏感。一位錯，整個消息譯錯。 3）精度問題。不可能無限長。 12位、32位、64位精度， 比例縮放。四、行程編碼（Run length encoding ，RLE） 長度編碼，游程編碼。（無損壓縮） 相同灰度值相鄰像元長度為：“行程”。 如：一幅灰度圖象，第n行像素11552200000735238 用RLE編碼方法得到代碼70

17、31 525 31 80 變長行程編碼 （070 031 525 031 080 定長行程編碼） 編碼前：73個代碼， 編碼后：11個代碼。 壓縮比：7：1。壓縮比主要取決于圖象本身特點。 圖象中相同顏色圖象塊越大，壓縮比越高，反之，壓縮比越小。 對顏色豐富的圖象，一行上具有相同連續(xù)像素很少，若仍用 RLE編碼，則可能圖象數(shù)據(jù)反而更大。 解決方法：與其它壓縮編碼技術聯(lián)合應用。 RLE對差錯敏感（一位符號出錯會改變行程編碼的長度，從而使整個圖象出現(xiàn)偏移）。 解決方法：加行同步，列同步。五、詞典編碼（無損壓縮）dictionary encoding 有些場合，開始事先不一定知道數(shù)據(jù)統(tǒng)計特性 對這些

18、數(shù)據(jù)壓縮 通用編碼技術 詞典編碼 無損壓縮 （1）詞典編碼的思想 根據(jù)：數(shù)據(jù)包含重復代碼（文本文件等） 兩種想法：查找正在壓縮的字符序列在以前輸入的數(shù)據(jù) 中是否出現(xiàn)過，若已出現(xiàn)過，只輸出指向以前此字符串的 “指針”。 從輸入的數(shù)據(jù)中創(chuàng)建一個“短語詞典”，短語可以為任意字符組合，（不一定有具體意義，如：嚴謹、求實）。編碼數(shù)據(jù)中出現(xiàn)已在詞典中的短詞時，編碼器輸出這個詞典中的“短語”索引號。 LZW壓縮算法（J.ziv 與A.Lempel研究), welch winzip使用此法. (2)LZ77算法 術語:輸入數(shù)據(jù)流：要被壓縮的字符序列。 字符：輸入數(shù)據(jù)流中的基本單元。 編碼位置：輸入數(shù)據(jù)流中當前

19、要編碼的字符位置。 前向緩沖存儲器：存放從編碼位置到輸入數(shù)據(jù)流結束 的字符序列的存儲器。 窗口：包含W個字符的窗口，字符從編碼位置開始向 后數(shù)。 指針：指向窗口中的匹配串且含長度的指針。 算法步驟：把編碼位置設到輸入數(shù)據(jù)流開始位置。 查找窗口中最長的匹配串。 以（Pointer Length） Characters的格式輸出。 匹配串指針 匹配字符長度 不匹配的第一個字符 如果前向緩沖存儲器是不空，把編碼位置位窗口向前 移（Length +1）個字符，然后返回到步驟 （3）LZSS算法 LZ77不足：空指針冗余，編碼器輸出字符可能包含在下一 匹配串中。 LZSS算法：如果匹配串長度比指針本身大

20、，輸出指針；否 則輸出真實字符。 區(qū)分指針與字符，需要額外ID位。 步驟：把編碼位置于數(shù)據(jù)流的開始位置。 在前向緩沖存儲器中查找與窗口中最長匹配串。 Pointer =匹配串指針，Length =匹配串長度。 判斷匹配串長度Length是否大于等于最小匹配串 長度。（LengthMINLENGTH） 是：輸出指針，把編碼位置前移Length個字符。 否：輸出前向緩沖存儲器第一個字符，然后把編 碼器位置向前移動一個字符。 如果前向緩沖存儲器非空，返回步驟。例： LZSS比LZ77（在相同計算機環(huán)境下）可獲得較高的壓縮比。 譯碼同樣簡單。LZSS成為開發(fā)新算法的基礎。 文檔壓縮程序許多使用LZSS

21、的思想，如ARJ,PKZip,ZOO等。 ARJ：LZSS與哈夫曼編碼聯(lián)用。PKZip 與香農-范諾聯(lián)用（4）LZ78算法 術語：字符流：要被編碼的數(shù)據(jù)序列。 字符：字符同LZ77。 前綴：在一個字符之前的字符序列。 綴符串：前綴+字符。 碼字：碼字流中的基本數(shù)據(jù)單元，代表詞典中的 一串字符。 碼字流：碼字和字符組成的序列，是編碼器輸出。 詞典：綴符串表。 當前前綴：當前正處理的前綴（P表示）。 當前字符：當前前綴之后的字符（C表示）。 當前碼字：譯碼算法中，正處理的 碼字，用W 表示當前碼字，string. W表示當前碼字的綴 符 串。編碼步驟：開始時，詞典和當前前綴P為空。 當前字符C為字符流中下一個字符。 判斷P+C是否在詞典中， 是：P=P+C 否：輸出當前前綴對應碼字和當前字符C，把字 符串P+C添加到詞典中，令P=空。 判斷字符流中是否還有字符需編碼， 是：轉 ； 否：若當前前綴P非空，輸出P對應碼字，結束編碼。 例：譯碼步驟：開始詞典為空，（譯碼詞典在譯碼過程中從碼字 流中重構）。 當前字符W為碼字流