數(shù)字壓縮技術(shù)

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

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

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

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

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

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

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

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個(gè)灰度等級(jí)，40個(gè)像素。代碼 出現(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）霍夫曼編碼特點(diǎn) 碼不唯一。 碼字變長(zhǎng)（硬件實(shí)現(xiàn)不大方便）,但不需要另外附加同步代 碼。（在壓縮文件中查找或調(diào)用內(nèi)容困難）。 概率分布不同，編碼效率不同。（效率比香農(nóng)-范諾編碼高） （概率分布不 均勻,效率高；概率分布 均勻,效率低，一般不用） Huffman編碼表解碼要用 傳輸要考慮編碼表所占比特率數(shù) 若編碼基于大量概率統(tǒng)計(jì)，傳輸可省去Huffman編碼表 使用缺省的Huffman編碼表 霍夫曼碼沒(méi)有錯(cuò)誤保護(hù)功能三、算術(shù)

10、編碼 在圖象數(shù)據(jù)壓縮標(biāo)準(zhǔn)（JPEG等）中扮演重要角色。 消息：用01之間實(shí)數(shù)進(jìn)行編碼。 算術(shù)編碼參數(shù)：符號(hào)的概率和它的編碼間隔。 （1）例：假設(shè)信源符號(hào)為 00, 01, 10, 11 其相應(yīng)概率 分別為 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個(gè)子間隔 。 符號(hào) 概率初始編碼間隔 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)二進(jìn)制消息序列 10 00 11 00 10 11 01.第一個(gè)符號(hào)為10,它的編碼范圍:

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

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

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

14、這個(gè)間隔分成如下子間隔： 令 ， ， 然后轉(zhuǎn)到步驟 例：輸入序列 ： ， ， i1ii1n1ni1i1i1n1nn,nn)PdI ,PdI )rl InlL nrR nnlrdnX2a1a3a比較 和22vu22vu輸入的第一個(gè)符號(hào): , 則 i =2, 定義初始間隔： 符號(hào)概率 初始編碼間隔 =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左、右邊界二進(jìn)制表示：L=0.5

15、=0.1(B) R=0.75=0.11(B)。按步驟， ，發(fā)送1， 轉(zhuǎn)到步驟 22vu11vu 輸入第三個(gè)字符： ， 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， 轉(zhuǎn)到步驟0vu2233vu 輸入第二個(gè)字符： ， 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， ， 轉(zhuǎn)到步驟.0vu3366vu 1vu441vu55發(fā)送編碼: 10011+結(jié)束符。特點(diǎn): 1) 對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字(0，1）中的一個(gè)實(shí) 數(shù)），譯碼器需接收所有位才能譯碼。 2）對(duì)錯(cuò)誤敏感。一位錯(cuò)，整個(gè)消息譯錯(cuò)。 3）精度問(wèn)題。不可能無(wú)限長(zhǎng)。 12位、32位、64位精度， 比例縮放。四、行程編碼（Run length encoding ，RLE） 長(zhǎng)度編碼，游程編碼。（無(wú)損壓縮） 相同灰度值相鄰像元長(zhǎng)度為：“行程”。 如：一幅灰度圖象，第n行像素11552200000735238 用RLE編碼方法得到代碼70

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

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

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

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

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