四川大學(xué)計(jì)算機(jī)學(xué)院多媒體基礎(chǔ)無損壓縮

多媒體技術(shù)基礎(chǔ)四川大學(xué)計(jì)算機(jī)學(xué)院陳虎huchen@數(shù)字化原理1模擬信號(hào)模擬信號(hào)指幅度的取值是連續(xù)的（幅值可由無限個(gè)數(shù)值表示）?，F(xiàn)實(shí)中涉及的許多媒體對(duì)象是模擬信號(hào)

例如：聲音、圖像、視頻等數(shù)字信號(hào)數(shù)字信號(hào)是人為抽象出來的在時(shí)間上的不連續(xù)信號(hào)，是離散時(shí)間信號(hào)的數(shù)字化表示，通常由模擬信號(hào)獲得。計(jì)算機(jī)處理的對(duì)象是數(shù)字信號(hào)（二進(jìn)制數(shù)“0”

和“1”）

例如：英文字符以的ASCII代碼，漢字字符的國標(biāo)GB2312-80代碼表示都是二進(jìn)制數(shù)字串多媒體系統(tǒng)的數(shù)模與模數(shù)轉(zhuǎn)換傳感器(聲音、圖像、視頻等--模擬）A/D計(jì)算機(jī)（數(shù)字）輸出設(shè)備（數(shù)字）D/A輸出設(shè)備（聲音、電視--等模擬）模數(shù)轉(zhuǎn)換-采樣概念：

從連續(xù)時(shí)間信號(hào)中提取離散樣本的過程；或者說在某些離散的時(shí)間點(diǎn)上提取連續(xù)時(shí)間信號(hào)值的過程稱為采樣。采樣按采樣間隔可分為:均勻采樣與非均勻采樣。采樣的必要性

例如，電影的連續(xù)畫面，實(shí)際上是由一組時(shí)間樣本快速播放實(shí)現(xiàn)的，數(shù)字通信系統(tǒng)，微處理器系統(tǒng)對(duì)連續(xù)時(shí)間信號(hào)的處理，都是通過采樣來實(shí)現(xiàn)的。采樣是連續(xù)時(shí)間信號(hào)和離散時(shí)間信號(hào)之間的橋梁，對(duì)連續(xù)信號(hào)而言，隨著數(shù)字處理技術(shù)的發(fā)展，越來越迫切地要求連續(xù)信號(hào)的離散化。采樣示例采樣當(dāng)取出的樣本一樣時(shí)，樣本對(duì)應(yīng)的連續(xù)時(shí)間函數(shù)卻不是唯一的。采樣此外，對(duì)同一個(gè)連續(xù)時(shí)間信號(hào)，當(dāng)采樣間隔不同時(shí)也會(huì)得到不同的樣本序列。結(jié)論：沒有任何條件限制的情況下，從連續(xù)時(shí)間信號(hào)采樣所得到的樣本序列，不能唯一地確定原來的連續(xù)時(shí)間信號(hào)，即：一個(gè)連續(xù)時(shí)間信號(hào)必須在某一種條件下才能由其樣本來表示。采樣分析采樣樣本：采樣函數(shù)：采樣分析已采樣信號(hào)的頻譜：采樣函數(shù)頻譜：原連續(xù)時(shí)間信號(hào)：采樣分析對(duì)連續(xù)時(shí)間信號(hào)在時(shí)域理想采樣，就相當(dāng)于在頻域以采樣頻率s為周期延拓，幅值減小1/T。要使頻譜不混迭，就必須使信號(hào)帶限，且上述即為時(shí)域采樣的約束條件從而我們得到怎樣抽取樣本，樣本才能唯一地表征原信號(hào)的取樣條件，下面為上述分析的一個(gè)完整總結(jié)－－采樣定理。采樣定理

設(shè)是某一個(gè)帶限信號(hào)，在||>M時(shí)，X（j）=0。如果采樣頻率

s>2

M，其中

s＝2/T,那么就唯一地由其樣本所確定。已知這些樣本值，我們能用如下辦法重建：讓采樣后的信號(hào)通過一個(gè)增益為T,截止頻率大于M，而小于（s

M）的理想濾波器，該濾波器的輸出就是。2

M稱為奈奎斯特率；

M稱為奈奎斯特頻率。數(shù)據(jù)壓縮2壓縮的必要性音頻、視頻的數(shù)據(jù)量很大，如果不進(jìn)行處理，計(jì)算機(jī)系統(tǒng)幾乎無法對(duì)它進(jìn)行存取和交換。

例如：一幅中等分辨率（640×480）的真彩色圖像（24b/像素），它的數(shù)據(jù)量約為0.9MB/幀，若要達(dá)到每秒25幀的全動(dòng)態(tài)顯示要求，每秒所需的數(shù)據(jù)量約為22MB。對(duì)于聲音也是如此，CD音質(zhì)的聲音每秒將有約為172KB的數(shù)據(jù)量。信息論1948年C.E.Shannon香農(nóng)發(fā)表了題為“通信的數(shù)學(xué)理論”的論文。運(yùn)用通信技術(shù)與概率論、隨機(jī)過程、數(shù)理統(tǒng)計(jì)的方法系統(tǒng)討論了通信的基本問題，得出了幾個(gè)重要而帶有普遍意義的結(jié)論：

1.闡明通信系統(tǒng)傳遞的對(duì)象就是信息

2.對(duì)信息給予科學(xué)的定量描述

3.提出了信息熵的概念信息論科學(xué)體系香農(nóng)信息論壓縮理論有失真信源編碼無失真信源編碼率失真理論壓縮編碼等長(zhǎng)編碼定理變長(zhǎng)編碼定理最優(yōu)碼構(gòu)成Huffman碼Fano碼傳輸理論有噪聲信道編碼理論碼構(gòu)成糾錯(cuò)碼代數(shù)編碼卷積碼網(wǎng)絡(luò)信道網(wǎng)絡(luò)信息理論網(wǎng)絡(luò)最佳碼保密理論保密系統(tǒng)的信息理論保密碼信息論之父TheFatherofInformationTheory——

ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA熵定義：設(shè)隨機(jī)變量X，取值空間Ω，Ω為有限集合。X的分布密度為p(x)，p(x)=P(X=x)x∈X，則該隨機(jī)變量的取值不確定程度，即其熵為：當(dāng)使用log2時(shí)，熵的單位為比特反映一個(gè)信源發(fā)出不同信號(hào)，具有的平均信息量。熵為什么能夠進(jìn)行壓縮

信息論認(rèn)為：若信源編碼的熵大于信源的實(shí)際熵，該信源中一定存在冗余度（信息熵冗余）。

冗余的基本概念

指信息存在的各種性質(zhì)的多余度舉例：（1）廣播員讀文稿時(shí)每分鐘約讀180字，一個(gè)漢字占兩個(gè)字節(jié)；文本數(shù)據(jù)量為360B；（2）如果對(duì)語音錄音，由于人說話的音頻范圍為20Hz到4kHz，即語音的帶寬為4kHz，若設(shè)量化位數(shù)為8bit,則一秒鐘的數(shù)據(jù)量為：

4×2×8=64kbit/s=8KB/s則一分鐘的數(shù)據(jù)是480KB。360B480KB數(shù)據(jù)冗余的類別空間冗余時(shí)間冗余統(tǒng)計(jì)冗余信息熵冗余結(jié)構(gòu)冗余知識(shí)冗余視覺冗余聽覺冗余數(shù)據(jù)冗余的類別●空間冗余規(guī)則物體和規(guī)則背景的表面物理特性都具有相關(guān)性，數(shù)字化后表現(xiàn)為數(shù)據(jù)冗余?！駮r(shí)間冗余序列圖像（如電視圖像和運(yùn)動(dòng)圖像）和語音數(shù)據(jù)的前后有著很強(qiáng)的相關(guān)性，經(jīng)常包含著冗余。在播出該序列圖像時(shí)，時(shí)間發(fā)生了推移，但若干幅畫面的同一部位沒有變化，變化的只是其中某些地方，這就形成了時(shí)間冗余。數(shù)據(jù)冗余的類別空間冗余和時(shí)間冗余是把圖像信號(hào)看作概率信號(hào)時(shí)反應(yīng)出的統(tǒng)計(jì)特性，因此，這兩種冗余也被稱為統(tǒng)計(jì)冗余?！窠y(tǒng)計(jì)冗余●信息熵冗余信息熵實(shí)際情況又稱編碼冗余。信息熵是指一組數(shù)所攜帶的信息量?！窠Y(jié)構(gòu)冗余數(shù)字化圖像中的物體表面紋理等結(jié)構(gòu)往往存在著冗余數(shù)據(jù)冗余的類別由圖像的記錄方式與人對(duì)圖像的知識(shí)差異所產(chǎn)生的冗余稱為知識(shí)冗余。●知識(shí)冗余

人類的視覺系統(tǒng)對(duì)于圖像場(chǎng)的注意在非均勻和非線性的，視覺系統(tǒng)并不是對(duì)圖像的任何變化都能感知?！褚曈X冗余

●聽覺冗余

人耳對(duì)不同頻率的聲音的敏感性是不同的，并不能察覺所有頻率的變化，對(duì)某些頻率不必特別關(guān)注，因此存在聽覺冗余。信息冗余從信息論關(guān)系中圖像信息中冗余信息，如果一個(gè)圖像的灰度級(jí)編碼，使用了多于實(shí)際需要的編碼符號(hào)，則該圖像包含了信息冗余例：如果用8位表示下面圖像的像素，我們就說該圖像存在著編碼冗余，因?yàn)樵搱D像的像素只有兩個(gè)灰度，用一位即可表示。統(tǒng)計(jì)冗余從統(tǒng)計(jì)的觀點(diǎn)，某點(diǎn)像素的灰度與其鄰域灰度有密切關(guān)系。因此任何給定的像素值，原理上都可以通過它的相鄰像素預(yù)測(cè)到，單個(gè)像素?cái)y帶的信息相對(duì)是小的。對(duì)于一個(gè)圖像，很多單個(gè)像素對(duì)視覺的貢獻(xiàn)是冗余的。例：原圖像數(shù)據(jù)：234223231238235壓縮后數(shù)據(jù)：23411-8-73空間冗余

規(guī)則物體表面有相關(guān)性，數(shù)字化后表現(xiàn)出冗余。圖像相鄰像素之間色彩、明度相同或相似，產(chǎn)生信息（有意義的內(nèi)容）冗余時(shí)間冗余時(shí)間發(fā)生了推移，若干幅畫面的同一部位沒有變化，于是產(chǎn)生了冗余結(jié)構(gòu)冗余

數(shù)字化圖像中具有規(guī)則紋理的表面產(chǎn)生的冗余。取其中一塊編碼，其余只記錄坐標(biāo)視覺心理冗余一些信息在一般視覺的處理中比其它信息的相對(duì)重要程度要小，可以忽略不計(jì)，這種信息就被稱為視覺心理冗余。33K15K數(shù)據(jù)壓縮的評(píng)價(jià)-壓縮比設(shè)：n1和n2是輸入數(shù)據(jù)和輸出數(shù)據(jù)

壓縮比為：CR=n1/n2

例如：圖像512×480，24位

輸入＝(512×480×24)/8=737280B

輸出15000B

壓縮比＝737280/15000＝49

相對(duì)數(shù)據(jù)冗余： RD=1–1/CR=(n1-n2)/n2數(shù)據(jù)壓縮的評(píng)價(jià)-壓縮質(zhì)量客觀質(zhì)量評(píng)價(jià)：壓縮過程對(duì)信息的損失能夠表示為原始信息與壓縮并解壓縮后信息的函數(shù)。（信噪比（SNR））例如，圖像中

數(shù)據(jù)壓縮的評(píng)價(jià)-壓縮質(zhì)量主觀質(zhì)量評(píng)價(jià)：以人的主觀感受作為評(píng)價(jià)標(biāo)準(zhǔn)。例如：通過視覺比較兩個(gè)圖像，給出一個(gè)定性的評(píng)價(jià)，如很粗、粗、稍粗、相同、稍好、較好、很好等，可以對(duì)所有人的感覺評(píng)分計(jì)算平均感覺分來衡量。評(píng)分評(píng)價(jià)說明1優(yōu)秀的優(yōu)秀的具有極高質(zhì)量的圖像2好的是可供觀賞的高質(zhì)量的圖像，干擾并不令人討厭3可通過的圖像質(zhì)量可以接受，干擾不討厭4邊緣的圖像質(zhì)量較低，希望能加以改善，干擾有些討厭5劣等的圖像質(zhì)量很差，尚能觀看，干擾顯著地令人討厭6不能用圖像質(zhì)量非常之差，無法觀看壓縮解壓縮速度算法復(fù)雜－壓縮解壓慢，壓縮效果好算法簡(jiǎn)單－壓縮解壓快，壓縮效果差在許多應(yīng)用中，壓縮和解壓可能不同時(shí)用，在不同的位置不同的系統(tǒng)中。所以，壓縮、解壓速度分別估計(jì)。

例如靜態(tài)圖像中，壓縮速度沒有解壓速度嚴(yán)格；動(dòng)態(tài)圖像中，壓縮、解壓速度都有要求，因?yàn)樾鑼?shí)時(shí)地從攝像機(jī)或其他設(shè)備中抓取動(dòng)態(tài)視頻。壓縮編碼的分類數(shù)據(jù)壓縮(datacompression)與信號(hào)編碼(signalcoding)往往含義相同壓縮(compress)解壓縮/還原/重構(gòu)(decompress)編碼(encode/coding)解碼/譯碼(decode)相關(guān)學(xué)科：信息論、數(shù)學(xué)、信號(hào)處理、數(shù)據(jù)壓縮、編碼理論和方法壓縮編碼的分類編碼壓縮的方法目前有很多，其分類方法根據(jù)出發(fā)點(diǎn)不同而有差異。一般根據(jù)根據(jù)解碼后數(shù)據(jù)與原始數(shù)據(jù)是否完全一致將編碼壓縮分為：無損壓縮編碼有損壓縮編碼壓縮編碼的分類無損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。有損壓縮適用于重構(gòu)信號(hào)不一定非要和原始信號(hào)完全相同的場(chǎng)合。圖像、聲音壓縮編碼的分類壓縮有損壓縮無損壓縮行程編碼LZW編碼哈夫曼編碼算術(shù)編碼無損預(yù)測(cè)編碼位平面編碼有損預(yù)測(cè)編碼分形編碼模型編碼子帶編碼神經(jīng)網(wǎng)絡(luò)編碼變換編碼K-L變換Haar變換Walsh.Hadamard變換離散余弦變換離散傅立葉變換斜變換小波變換壓縮編碼的分類從信息語義角度分為：熵編碼、源編碼和混合編碼熵編碼(entropyencoding)（也稱平均信息量編碼）

熵編碼是一種泛指那些不考慮被壓縮信息的性質(zhì)的無損編碼。它是基于平均信息量的技術(shù)把所有的數(shù)據(jù)當(dāng)作比特序列，而不根據(jù)壓縮信息的類型優(yōu)化壓縮。也就是說，平均信息量編碼忽略被壓縮信息的語義內(nèi)容。如RLE（runlengthencoding行程編碼）、LZW（Lempel-Ziv-Walch基于詞典的編碼算法）、Huffman編碼。壓縮編碼的分類源編碼(SourceCoding)

源編碼的冗余壓縮取決于初始信號(hào)的類型、前后的相關(guān)性、信號(hào)的語義內(nèi)容等。源編碼比嚴(yán)格的平均信息量編碼的壓縮率更高。當(dāng)然壓縮的程度主要取決于數(shù)據(jù)的語義內(nèi)容，比起平均信息量編碼，它的壓縮比更大。簡(jiǎn)而言之，利用信號(hào)原數(shù)據(jù)在時(shí)間域和頻率域中的相關(guān)性和冗余進(jìn)行壓縮的有語義編碼。如：預(yù)測(cè)編碼：DM、ADPCM變換編碼：DCT、DWT分層編碼：如子采樣、子帶編碼其他編碼：如矢量量化、運(yùn)動(dòng)補(bǔ)償、音感編碼壓縮編碼的分類混合編碼(hybridcoding)

混合編碼=熵編碼+源編碼大多數(shù)壓縮標(biāo)準(zhǔn)都采用混合編碼的方法進(jìn)行數(shù)據(jù)壓縮，一般是先利用信源編碼進(jìn)行有損壓縮，再利用熵編碼做進(jìn)一步的無損壓縮。如H.261、H.263、JPEG、MPEG等。壓縮編碼的分類此外，也可根據(jù)不同的依據(jù)對(duì)數(shù)據(jù)的壓縮算法進(jìn)行其它不同的分類，如：按作用域在空間域或頻率域：空間方法、變換方法、混合方法按是否自適應(yīng)：自適應(yīng)性編碼和非適應(yīng)性（靜態(tài)）編碼按碼長(zhǎng)：定長(zhǎng)碼和變長(zhǎng)碼香農(nóng)-范諾香農(nóng)-范諾編碼(Shannon–Fanocoding)在香農(nóng)的源編碼理論中，熵的大小表示非冗余的不可壓縮的信息量在計(jì)算熵時(shí)，如果對(duì)數(shù)的底數(shù)用2，熵的單位就用“香農(nóng)(Sh)”，也稱“位(bit)”

。“位”是1948年Shannon首次使用的術(shù)語。最早闡述和實(shí)現(xiàn)“從上到下”的熵編碼方法的人是Shannon(1948年)和Fano(1949年)，因此稱為香農(nóng)-范諾(Shannon-Fano)編碼法香農(nóng)-范諾編碼舉例有一幅40個(gè)像素組成的灰度圖像，灰度共有5級(jí)，分別用符號(hào)A，B，C，D和E表示。40個(gè)像素中出現(xiàn)灰度A的像素?cái)?shù)有15個(gè)，出現(xiàn)灰度B的像素?cái)?shù)有7個(gè)，出現(xiàn)灰度C的像素?cái)?shù)有7個(gè)，其余情況見表2-1(1)計(jì)算該圖像可能獲得的壓縮比的理論值(2)對(duì)5個(gè)符號(hào)進(jìn)行編碼(3)計(jì)算該圖像可能獲得的壓縮比的實(shí)際值符號(hào)ABCDE出現(xiàn)的次數(shù)157765出現(xiàn)的概率15/407/407/406/405/40香農(nóng)-范諾編碼舉例理論值按照常規(guī)的編碼方法，表示5個(gè)符號(hào)最少需要3位，如用000表示A，001表示B，…，100表示E，其余3個(gè)代碼(101，110，111)不用。這就意味每個(gè)像素用3位，編碼這幅圖像總共需要120位。按照香農(nóng)理論，這幅圖像的熵為香農(nóng)-范諾編碼舉例這個(gè)數(shù)值表明，每個(gè)符號(hào)不需要用3位構(gòu)成的代碼表示，而用2.196位就可以，因此40個(gè)像素只需用87.84位就可以，因此在理論上，這幅圖像的的壓縮比為120:87.84≈1.37:1，實(shí)際上就是3:2.196≈1.37香農(nóng)-范諾編碼舉例(2)符號(hào)編碼對(duì)每個(gè)符號(hào)進(jìn)行編碼時(shí)采用“從上到下”的方法。首先按照符號(hào)出現(xiàn)的頻度或概率排序，然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù)香農(nóng)-范諾編碼舉例（3）壓縮比的實(shí)際值按照這種方法進(jìn)行編碼需要的總位數(shù)為30+14+14+18+15＝91，實(shí)際的壓縮比為120:91≈1.32:1霍夫曼編碼霍夫曼編碼(Huffmancoding)霍夫曼(D.A.Huffman)在1952年提出和描述的“從下到上”的熵編碼方法根據(jù)給定數(shù)據(jù)集中各元素所出現(xiàn)的頻率來壓縮數(shù)據(jù)的一種統(tǒng)計(jì)壓縮編碼方法。這些元素(如字母)出現(xiàn)的次數(shù)越多，其編碼的位數(shù)就越少廣泛用在JPEG,MPEG,H.26X等各種信息編碼標(biāo)準(zhǔn)中霍夫曼編碼基本原理通過減少編碼冗余來達(dá)到壓縮的目的。統(tǒng)計(jì)符號(hào)的出現(xiàn)概率，建立一個(gè)概率統(tǒng)計(jì)表將最常出現(xiàn)(概率大的)的符號(hào)用最短的編碼，最少出現(xiàn)的符號(hào)用最長(zhǎng)的編碼?；舴蚵幋a具體步驟：步驟①：按照符號(hào)出現(xiàn)概率大小的順序?qū)Ψ?hào)進(jìn)行排序步驟②：把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)P1步驟③：重復(fù)步驟②，得到節(jié)點(diǎn)P2，P3，P4，……，PN，形成一棵樹，其中的PN稱為根節(jié)點(diǎn)步驟④：從根節(jié)點(diǎn)PN開始到每個(gè)符號(hào)的樹葉，從上到下標(biāo)上0(上枝)和1(下枝)，至于哪個(gè)為1哪個(gè)為0則無關(guān)緊要步驟⑤：從根節(jié)點(diǎn)PN開始順著樹枝到每個(gè)葉子分別寫出每個(gè)符號(hào)的代碼霍夫曼編碼舉例

aaaa

bbb

cc

d

eeeee

fffffff

432157（共22*8=176bits)霍夫曼編碼舉例

cbdafe7/225/224/222/22f=00e=10a=11b=011c=0100d=01011/221022/223/229/220113/22016/22103/2201編碼形式不唯一4/22)*log2(22/4)+(3/22)*log2(22/3)+(2/22)*log2(22/2)+(1/22)*log2(22/1)+(7/22)*log2(22/7)+(5/22)*log2(22/5)＝2.3678霍夫曼編碼舉例aaaa

bbb

cc

d

eeeee

fffffff

（共22*8=176bits)432157

經(jīng)過Huffman編碼之后的數(shù)據(jù)為：11111111011011011010001000101101010101000000000000000(共7*2+5*2+4*2+3*3+2*4+1*4=53bits)

霍夫曼編碼a10.20a20.19a30.18a40.17a50.15a60.10a70.01100.11100.2610.3500.610010110.391.00碼字碼長(zhǎng)1021120003001301030110401114平均碼長(zhǎng)：2.72熵：2.58霍夫曼編碼局限性利用霍夫曼編碼，每個(gè)符號(hào)的編碼長(zhǎng)度只能為整數(shù)，所以如果源符號(hào)集的概率分布不是2負(fù)n次方的形式，則無法達(dá)到熵極限。輸入符號(hào)數(shù)受限于可實(shí)現(xiàn)的碼表尺寸譯碼復(fù)雜需要實(shí)現(xiàn)知道輸入符號(hào)集的概率分布沒有錯(cuò)誤保護(hù)功能應(yīng)用舉例在圖像的編碼中首先計(jì)算頻率并以二叉樹方式進(jìn)行排序來獲得編碼值，其次用編碼值取代圖像數(shù)據(jù)進(jìn)入圖像文件中。編碼值的不唯一性灰度分布很不均勻和很均勻時(shí)的效率構(gòu)造性差常用的且有效的方法是：將圖像分割成若干的小塊，對(duì)每塊進(jìn)行獨(dú)立的Huffman編碼。例如：分成8×8的子塊，就可以大大降低不同灰度值的個(gè)數(shù)（最多是64而不是256）。應(yīng)用舉例8*8分塊的編碼效率為47.27%16*16分塊的編碼效率約為61%全圖的編碼效率為91.47%霍夫曼編碼Huffman編碼討論Huffman編碼是唯一可譯碼。短的碼不會(huì)成為更長(zhǎng)碼的啟始部分；Huffman編碼的平均碼長(zhǎng)接近于熵缺點(diǎn)：需要多次排序，耗費(fèi)時(shí)間算術(shù)編碼Huffman編碼的局限性：

Huffman編碼使用整數(shù)個(gè)二進(jìn)制位對(duì)符號(hào)進(jìn)行編碼，這種方法在許多情況下無法得到最優(yōu)的壓縮效果。假設(shè)某個(gè)字符的出現(xiàn)概率為80%，該字符事實(shí)上只需要-log2(0.8)=0.322位編碼，但Huffman編碼一定會(huì)為其分配一位0或一位1的編碼?？梢韵胂螅麄€(gè)信息的80%在壓縮后都幾乎相當(dāng)于理想長(zhǎng)度的3倍左右。算術(shù)編碼例1：在信源的符號(hào)數(shù)目很小的情況X:abP(X):0.90.1H=0.4690ab1a=0,b=1算術(shù)編碼例2：信源的符號(hào)的概率嚴(yán)重不對(duì)稱：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symbolHuffman編碼：a 0b 11c 10l=1.05bits/symbol冗余（Redundancy）=l-H=0.715bits/sym(213%!)算術(shù)編碼基本思想：考慮對(duì)兩個(gè)字母序列而不是單個(gè)字母編碼l=1.222/2=0.611冗余=0.276bits/symbol（27%）LetterProbabilityCodeaa0.90250ab0.0190111ac0.0285100ba0.01901101bb0.0004110011bc0.0006110001ca0.0285101cb0.0006110010cc0.0009110000算術(shù)編碼該思想還可以繼續(xù)擴(kuò)展考慮長(zhǎng)度為n的所有可能的mn

序列(已做了32)理論上：考慮更長(zhǎng)的序列能提高編碼性能實(shí)際上：字母表的指數(shù)增長(zhǎng)將使得這不現(xiàn)實(shí)例如：對(duì)長(zhǎng)度為3的ASCII序列：2563=224=16M需要對(duì)長(zhǎng)度為n的所有序列產(chǎn)生碼本很多序列的概率可能為0分布嚴(yán)重不對(duì)稱是真正的大問題：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335bits/symboll1=1.05,l2=0.611,…當(dāng)n=8時(shí)編碼性能才變得可接受但此時(shí)|alphabet|=38=6561!!!算術(shù)編碼基本思想：算術(shù)編碼不是將單個(gè)信源符號(hào)映射成一個(gè)碼字，而是把整個(gè)消息表示為實(shí)數(shù)線上的0到1之間的一個(gè)區(qū)間，其長(zhǎng)度等于該序列的概率，再在該區(qū)間內(nèi)選擇一個(gè)代表性的小數(shù)，轉(zhuǎn)化為二進(jìn)制作為實(shí)際的編碼輸出。消息序列中的每個(gè)元素都要用來縮短這個(gè)區(qū)間。消息序列中元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時(shí)，就需要更多的數(shù)位來表示這個(gè)區(qū)間。采用算術(shù)編碼每個(gè)符號(hào)的平均編碼長(zhǎng)度可以為小數(shù)算術(shù)編碼符號(hào)串編碼：將串中使用的符號(hào)表按原編碼（如字符的ASCII編碼、數(shù)字的二進(jìn)制編碼）從小到大順序排列成表。計(jì)算表中每種符號(hào)si出現(xiàn)的概率pi，然后依次根據(jù)這些符號(hào)概率大小pi來確定其在[0,1)期間中對(duì)應(yīng)的小區(qū)間范圍[xi,yi)：其中，p0=0，顯然，符號(hào)si所對(duì)應(yīng)的小區(qū)間的寬度就是其概率pi算術(shù)編碼輸入串編碼：設(shè)串中第j個(gè)符號(hào)cj為符號(hào)表中的第i個(gè)符號(hào)si，則可根據(jù)si在符號(hào)表中所對(duì)應(yīng)區(qū)間的上下限xi和yi，來計(jì)算編碼區(qū)間

Ij=[lj,rj)。其中，dj=rj-lj為區(qū)間Ij的寬度，初值l0=0，r0=1，d0=1。顯然，lj↑而dj與rj↓。串的最后一個(gè)符號(hào)所對(duì)應(yīng)區(qū)間的下限ln就是該符號(hào)串的算術(shù)編碼值.算術(shù)編碼通常，對(duì)任意序列x=x1x2…xn只需知道信源的cdf，即信源的概率模型算術(shù)編碼：編碼和解碼過程都只涉及算術(shù)運(yùn)算（加、減、乘、除）

舉例2字符概率a0.3b0.7aba要編的字符串算術(shù)編碼010.3aba[0,0.3)b[0.3,1)1.劃分范圍2.開始編碼“aba”00.3ab第一個(gè)為a，編碼范圍限制在0～0.3范圍內(nèi)1算術(shù)編碼00.30.09ab00.3ab1對(duì)已知區(qū)間進(jìn)行再次分割第二個(gè)為b，編碼范圍限制在0.09～0.3范圍內(nèi)00.30.09ab算術(shù)編碼0.090.30.153ab0ab0.3對(duì)已知區(qū)間進(jìn)行再次分割第3個(gè)為a，編碼范圍限制在[0.09,0.153)范圍內(nèi)0.090.090.153ab0.3算術(shù)編碼在[0.09,0.153)中任選一個(gè)浮點(diǎn)數(shù)來標(biāo)識(shí)這個(gè)區(qū)間，如0.15，即可表示我們要編的消息為“aba”把該浮點(diǎn)數(shù)轉(zhuǎn)變?yōu)槎M(jìn)制編碼:0010特性：區(qū)間越窄，說明符號(hào)串越長(zhǎng)，二進(jìn)制碼長(zhǎng)越長(zhǎng)舉例2假設(shè)信源符號(hào)為{00,01,10,11}，它們的概率分別為{0.1,0.4,0.2,0.3}對(duì)二進(jìn)制消息序列10001100101101…進(jìn)行算術(shù)編碼算術(shù)編碼初始化：根據(jù)信源符號(hào)的概率把間隔[0,1)分成如表2-4所示的4個(gè)子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)。其中[x,y)的表示半開放間隔，即包含x不包含y，x稱為低邊界或左邊界，y稱為高邊界或右邊界

符號(hào)00011011概率0.3初始區(qū)間[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)算術(shù)編碼確定符號(hào)的編碼范圍編碼時(shí)輸入第1個(gè)符號(hào)是10，找到它的編碼范圍是[0.5,0.7]消息中第2個(gè)符號(hào)00的編碼范圍是[0,0.1)，它的間隔就取[0.5,0.7)的第一個(gè)十分之一作為新間隔[0.5,0.52)編碼第3個(gè)符號(hào)11時(shí)，取新間隔為[0.514,0.52)編碼第4個(gè)符號(hào)00時(shí)，取新間隔為[0.514,0.5146)依此類推……消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)算術(shù)編碼算術(shù)編碼算術(shù)編碼算術(shù)編碼

算術(shù)編碼長(zhǎng)度為n的序列的算術(shù)編碼的平均碼長(zhǎng)為：算術(shù)編碼的效率高：當(dāng)信源符號(hào)序列很長(zhǎng)，平均碼長(zhǎng)接近信源的熵算術(shù)編碼在算術(shù)編碼中需要注意的問題：由于實(shí)際的計(jì)算機(jī)的精度不可能無限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問題，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此這個(gè)問題可使用比例縮放方法解決。算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔[0,1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。算術(shù)編碼

算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號(hào)的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改。開發(fā)動(dòng)態(tài)算術(shù)編碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切實(shí)際的。當(dāng)壓縮消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。帶縮放的算術(shù)編碼編碼器：一旦我們到達(dá)1.或2.，就可以忽略[0,1)的另一半還需要告知解碼器標(biāo)識(shí)所在的半?yún)^(qū)間：發(fā)送0/1比特用來指示下上界所在區(qū)間將標(biāo)識(shí)區(qū)間縮放到[0,1):E1:[0,0.5)=>[0,1); E1(x)=2xE2:[0.5,1)=>[0,1); E2(x)=2(x-0.5)注意：在縮放過程中我們丟失了最高位但這不成問題—我們已經(jīng)發(fā)送出去了解碼器根據(jù)0/1比特并相應(yīng)縮放與編碼器保持同步帶縮放的算術(shù)編碼考慮隨機(jī)變量X(ai)=i

對(duì)序列1321編碼：

Input:1321Output:

Input:-321Output:

1帶縮放的算術(shù)編碼Input:--21Output:11Input:---1Output:110Input:---1Output:1100Input:---1Output:11000

帶縮放的算術(shù)編碼假設(shè)碼字長(zhǎng)為6輸入：1100011000000.1100012=0.76562510第1位：1Output:1Input:110001100000Output:13Input:-10001100000(左移)Input:-10001100000(0.546875)Output:132Input:---001100000(左移)Input:--0001100000(左移)帶縮放的算術(shù)編碼此時(shí)解碼最后一個(gè)符號(hào)Input:----01100000(左移)Input:-----1100000(左移)Input:-----100000

(左移)Input:-----100000Output:1321應(yīng)用背景： 對(duì)于“局部冗余”的特殊類型。 主要應(yīng)用于圖象表達(dá)、處理。原因：數(shù)字化的image有大量的“局部冗余”占空間大 （一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的象素都具有相同的顏色值。）語義依賴典型：行程編碼（run-lengthencoding:RLE）差異映射(differencemapping)詞典編碼(DictionaryEncoding)語義依賴差異映射：算法思想：圖象表示為相鄰像素在亮度/顏色上的差異陣列，而不是像素本身的亮度/顏色值例[Laeseretal.1986]8bits/pixel(256brightness)3bits/pixel語義依賴詞典編碼詞典：全部詞語（words）常用詞語+詞語結(jié)束符號(hào)編碼方法：指向詞典的指針表指向詞典的指針表（常用詞語）+編碼（不常用詞語）語義依賴分解與編碼源信息代碼（長(zhǎng)度）：block->blockblock->variablevariable->blockvariable->variable例：“aabbbccccdddddeeeeeefffffffgggggggg”

block->block(120)Sourcemassage codeworda 000b 001c 010d 011e 100f 101g 110space 111分解與編碼例："aabbbccccdddddeeeeeefffffffgggggggg”variable->variable(30)

Sourcemassage codewordaa 0bbb 1ccccc 10ddddd 11eeeeeee 100fffffff 101gggggggg 110space 111分解與編碼“定義字”與“自由分解”方法定義字（defined-word）方式源信息分解的長(zhǎng)度在編碼調(diào)用之前已確定自由分解（free-parse）方式編碼算法本身決定源信息分解的長(zhǎng)度（變長(zhǎng)）分解與編碼典型算法定義字方式的：Shannon-FanocodingHuffmancodingUniversalcodes(通用碼)Arithmeticcoding(算術(shù)編碼)自由分解方式的：Lempel-ZivcodesAlgorithmBSTW行程編碼（RLE）基本原理：它通過將信源中相同符號(hào)序列轉(zhuǎn)換成一個(gè)計(jì)數(shù)字段再加上一個(gè)重復(fù)字符標(biāo)志實(shí)現(xiàn)壓縮。

行程編碼（RLE）行程編碼(RLE）算法:x1,x2,……

xn---->(

c1,l1),(

c2,l2),……

(

ck,lk)

ci:亮度/顏色li:第i行程（相同亮度/顏色的像素的序列）的長(zhǎng)度不需要存儲(chǔ)每一個(gè)象素的顏色值，而僅僅存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色的象素?cái)?shù)目就可以；或者存儲(chǔ)一個(gè)象素的顏色值，以及具有相同顏色值的行數(shù)。具有相同顏色并且是連續(xù)的象素?cái)?shù)目稱為行程長(zhǎng)度。行程編碼（RLE）例：代碼字為：（0，8),（1，3),（8，50),（1，4),(0，8）行程編碼（RLE）RLE所能獲得的壓縮比——主要是取決于圖像本身的特點(diǎn)。如果圖像中具有相同顏色的圖像塊越大，圖像塊數(shù)目越少，獲得的壓縮比就越高。反之，壓縮比就越小。RLE是無損壓縮技術(shù)。行程編碼（RLE）應(yīng)用：尤其適用于計(jì)算機(jī)生成的圖像，對(duì)減少圖像文件的存儲(chǔ)空間非常有效。（對(duì)顏色豐富的自然圖像不能單純使用RLE一種編碼方法，需要和其他的壓縮編碼技術(shù)聯(lián)合應(yīng)用。）商業(yè)數(shù)據(jù)處理（如連續(xù)多個(gè)0，空格）行程編碼（RLE）特點(diǎn)：

利用兩個(gè)字節(jié)代替連續(xù)出現(xiàn)的同一數(shù)據(jù)。通常需要在表示重復(fù)次數(shù)的字節(jié)中利用前一位或兩位作為標(biāo)志位，提示應(yīng)用程序中隨后的極為表示次數(shù)，另一字節(jié)表示重復(fù)數(shù)據(jù)的值。舉例說明：

aaaa

bbb

cc

d

eeeee

fffffff

(共22*8=176bits)

4a3b2c1d5e7f(共12*8=96bits)BMP行程編碼BI_RLE8的編碼方式：由2個(gè)字節(jié)組成，第一個(gè)字節(jié)指定使用相同顏色的象素?cái)?shù)目，第二個(gè)字節(jié)指定使用的顏色索引。此外，這個(gè)字節(jié)對(duì)中的第一個(gè)字節(jié)可設(shè)置為0，聯(lián)合使用第二個(gè)字節(jié)的值表示：

第二個(gè)字節(jié)的值為0：行的結(jié)束。

第二個(gè)字節(jié)的值為1：圖象結(jié)束。

第二個(gè)字節(jié)的值為2：其后的兩個(gè)字節(jié)表示下一個(gè)象素從當(dāng)前開始的水平和垂直位置的偏移量。

BMP行程編碼例如：

0304050602780002050102780000091E0001

這些壓縮數(shù)據(jù)可解釋為：

0304040404

05060606060606

02787878

00020501從當(dāng)前位置右移5個(gè)位置后向下移一行

02787878

0000行結(jié)束

091E1E1E1E1E1E1E1E1E1E

0001編碼圖象結(jié)束PCX行程編碼PCX簡(jiǎn)介：真彩色圖像以行為單位，按色面存放128字節(jié)的文件頭圖像數(shù)據(jù)調(diào)色板PCX行程編碼圖像數(shù)據(jù)以字節(jié)為單位進(jìn)行編碼按行進(jìn)行壓縮長(zhǎng)度在前，灰度值在后單像素沒有長(zhǎng)度值以最高兩位作為判斷是重復(fù)數(shù)還是原像素。最高兩位為1（B0除外），說明是重復(fù)數(shù)，否則，說明是原像素值

PCX行程編碼重復(fù)像素長(zhǎng)度iC最大值為26-1=63，如果遇到iC大于63的情況，則分為小于63的幾段，分別處理。如果遇到不重復(fù)的單個(gè)像素P： 如果P<0xC0（192）直接存入該像素值， 否則先存入長(zhǎng)度1，再存入像素值（192-255之間的單像素圖像不減反增）PCX行程編碼例

0X15····0X150X5A0X670X5F0X710X6911

0X35····0X350XD70XD90XCC80

[0XCB0X15]0X5A0X670X5F0X710X69

[0XFF0X35][0XD10X35][0XC10XD7][0XC10XD9][0XC10XCC]行程編碼（RLE）對(duì)于有大面積色塊的圖像，壓縮效果很好對(duì)于紛雜的圖像，壓縮效果不好，最壞情況下（圖像中每?jī)蓚€(gè)相鄰點(diǎn)的顏色都不同），會(huì)使數(shù)據(jù)量加倍，所以現(xiàn)在單純采用行程編碼的壓縮算法用得并不多二維行程編碼二維行程編碼要解決的核心問題是：將二維排列的像素，采用某種方式轉(zhuǎn)化成一維排列的方式。之后按照一維行程編碼方式進(jìn)行編碼兩種典型的二維行程編碼的排列方式二維行程編碼數(shù)據(jù)量：64*8=512(bit)二維行程編碼如果按照方式(a)掃描的順序排列的話，數(shù)據(jù)分布為：130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，134，134；133，133，132，130，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127二維行程編碼行程編碼為：

數(shù)據(jù)量：43*（3+8）=473(bit)(94.22%)（7，130），（2，130），（4，129），（2，130），（1，129）；（1，127），（1，128），（1，127），（1，129），（1，131），（1，130），（1，132），（2，134），（2，133），（1，132），（1，130），（1，129），（1，128），（1，127），（1，128），（1，127），（1，128），（1，127），（1，125），（1，126），（2，129），（1，127），（1，129），（1，133），（1，132），（1，131），（1，129），（2，130），（1，129），（3，130），（1，129），（1，130），（2，132），（2，131），（1，130），（1，126），（2，128），（2，127）比特平面編碼思想：

對(duì)于灰度或彩色圖像，如果每個(gè)像素用k位表示，將相同位上的0，1取出，就可以形成k個(gè)N*N的二值圖像。將每一個(gè)二值圖像稱為一個(gè)比特平面。希望連續(xù)的0/1出現(xiàn)的概率增大.比特平面編碼二值圖像壓縮標(biāo)準(zhǔn)靜止圖像（stillimages）包括兩類：黑白（二值）靜止圖像連續(xù)色調(diào)（彩色或灰度）靜止圖像。二值圖像壓縮方法主要用于不包含任何連續(xù)色調(diào)信息的文檔，或者連續(xù)色調(diào)信息(大多數(shù)為圖片)可以用黑白的模式來獲取的應(yīng)用。例如辦公／商業(yè)文檔，手寫文本、線條圖形、工程圖等。二值圖像壓縮標(biāo)準(zhǔn)二值圖像壓縮的標(biāo)準(zhǔn)：3類（CCITTGroup3）數(shù)字傳真標(biāo)準(zhǔn)4類（CCITTGroup4）數(shù)字傳真標(biāo)準(zhǔn)JBIG（JointBi-levelImageexpertsGroup，二值圖像聯(lián)合專家組）標(biāo)準(zhǔn)二值圖像壓縮標(biāo)準(zhǔn)G3和G4－由CCITT國家電話電報(bào)咨詢委員會(huì)(consultativecommitteeoftheinternationaltelephoneandtelegraph)的兩個(gè)小組(Group3和Group4)負(fù)責(zé)制定的，最初為傳真應(yīng)用而設(shè)計(jì)（1）G3采用一維行程長(zhǎng)度編碼；（2）行程采用Huffman編碼；（3）0－63之間的行程，用單個(gè)碼字即終止碼表示；（4）大于63的游長(zhǎng)用一個(gè)形成碼和一個(gè)終止碼組合表示。形成碼表示實(shí)際行程對(duì)64的倍數(shù)；（5）G3能達(dá)到15：1的壓縮比；（6）G4采用二維行程程度編碼，壓縮比比G3提高30％。二值圖像壓縮標(biāo)準(zhǔn)一維壓縮基本思想：1）每一行行首、尾編碼行首：用一個(gè)白行程碼開始。如果行首是黑像素，則 用零長(zhǎng)度的白00110101開始。行尾：用行尾編碼字(EOL)000000000001結(jié)束。2）圖像首、尾編碼圖像首行：用一個(gè)EOL開始。圖像結(jié)尾：用連續(xù)6個(gè)EOL結(jié)束。3）圖像內(nèi)部編碼內(nèi)部編碼：長(zhǎng)度小于63的用哈夫曼編碼，大于63的用組合編碼：大于63的長(zhǎng)度編碼+小于63的余長(zhǎng)度編碼二值圖像壓縮標(biāo)準(zhǔn)長(zhǎng)度小于63的哈夫曼編碼行程長(zhǎng)度白編碼 黑編碼0 00110101 00001101111 000111 0102 0111 113 1000 104 1011 0115 1100 001161 00110010 00000101101062 00110011 00000110011063 00110100 000001011011二值圖像壓縮標(biāo)準(zhǔn)長(zhǎng)度大于63的組合編碼

行程長(zhǎng)度白編碼 黑編碼64 11011 0000001111128 10010 000011001000192 010111 000011001001256 0110111 000001011011320 00110110 000000110011384 00110111 0000001101001600 010011010 00000010110111664 011000 00000011001001728 010011011 0000001100101二值圖像壓縮標(biāo)準(zhǔn)二維壓縮

1)基本思想：利用上一行相同改變?cè)氐奈恢?，來為?dāng)前行編碼假設(shè)相臨兩行改變?cè)匚恢孟嗨频那闆r很多且上一行改變?cè)鼐喈?dāng)前行改變?cè)氐木嚯x，小于行程的長(zhǎng)度，從而可以降低編碼長(zhǎng)度a0b1b2a1a2參考行當(dāng)前行二值圖像壓縮標(biāo)準(zhǔn)2)定義幾個(gè)重要符號(hào)：參考行：當(dāng)前處理行的前一行。改變?cè)兀号c前一個(gè)像素值不同的像素參考元素：一共有5個(gè)（當(dāng)前行3個(gè)，參考行2個(gè)）：a0：當(dāng)前處理行上，與前一個(gè)像素值不同的像素。 行首元素是本行的第一個(gè)a0a1：a0右邊下一個(gè)改變?cè)?。a2：a1右邊下一個(gè)改變?cè)?。b1：參考行上在a0右邊，且與a0值相反的改變?cè)豣2：b1右邊下一個(gè)改變?cè)?。a0b1b2a1a2參考行當(dāng)前行二值圖像壓縮標(biāo)準(zhǔn)3)編碼方法：對(duì)三種情況的三種編碼方式：（1）通過編碼方式：條件：b2在a1的左邊，排除參考行兩個(gè)改變?cè)囟荚? a1左邊的情況編碼：0001，動(dòng)作：把a(bǔ)0移到b2的下面b1b2a1a2a0新a0二值圖像壓縮標(biāo)準(zhǔn)3)編碼方法：對(duì)三種情況的三種編碼方式：（2）水平編碼方式：條件：a1到b1之間的距離大于3，放棄利用上一行編碼編碼：001+M(a0a1)+M(a1a2)，M：一維行程編碼動(dòng)作：把a(bǔ)0移到a2。a0b1b2a1a2a1b1二值圖像壓縮標(biāo)準(zhǔn)3）編碼方法：對(duì)三種情況的三種編碼方式：（3）垂直編碼方式：條件：a1到b1之間的距離小于等于3，利用上一行編碼。編碼：見CCITT二維編碼表（下頁）動(dòng)作：把a(bǔ)0移到a1a0b1b2a1a2a1b1二值圖像壓縮標(biāo)準(zhǔn)4)CCITT二維編碼表

a1與b1的距離 編碼：

a1在b1下面： 1 a1在b1右邊1個(gè) 001 a1在b1右邊2個(gè) 000011 a1在b1右邊3個(gè) 0000011 a1在b1左邊1個(gè) 010 a1在b1左邊2個(gè) 000010 a1在b1左邊3個(gè) 0000010二值圖像壓縮標(biāo)準(zhǔn)CCITTGroup3基本思想：Group3標(biāo)準(zhǔn)應(yīng)用了一種非適應(yīng)的，一維和二維混合的行程編碼技術(shù)在該編碼中，每一個(gè)K行組的最后K-1行（K=2或4），有選擇地用二維編碼方式。二值圖像壓縮標(biāo)準(zhǔn)CCITTGroup4基本思想：Group4標(biāo)準(zhǔn)是Group3標(biāo)準(zhǔn)簡(jiǎn)化或改進(jìn)版本只用二維壓縮編碼。且為非適應(yīng)二維編碼方法每一個(gè)新圖像的第一行的參考行是一個(gè)虛擬的白行二值圖像壓縮標(biāo)準(zhǔn)JBIG是“二值圖像聯(lián)合專家組（JointBi-levelImageexpertsGroup）”的簡(jiǎn)稱。它建立于1988年，是一個(gè)由國際標(biāo)準(zhǔn)實(shí)體和主要公司提名產(chǎn)生的專家組，致力于制訂二值圖像編碼標(biāo)準(zhǔn)。“聯(lián)合”指的是他們同時(shí)為ISO、IEC和ITU-T制訂標(biāo)準(zhǔn)。JBIG的正式名稱，在ISO和IEC叫ISO/IECJTC1SC29第一工作組，在ITU-T，則稱為ITU-TSG8。JBIG和JPEG一同工作，同時(shí)為JPEG和JBIG制訂標(biāo)準(zhǔn)。人們常常將他們制訂的這兩種標(biāo)準(zhǔn)分別簡(jiǎn)稱為JPEG標(biāo)準(zhǔn)和JBIG標(biāo)準(zhǔn)，或直接稱為JPEG和JBIG。二值圖像壓縮標(biāo)準(zhǔn)JBIG1在性能上有很大提高JBIG1采用順序傳輸模式來適應(yīng)瀏覽技術(shù)(數(shù)字信息檢索和恢復(fù))的要求，這項(xiàng)技術(shù)已普遍用于現(xiàn)代圖書館和網(wǎng)絡(luò)數(shù)據(jù)庫JBIG1結(jié)合了預(yù)測(cè)建模、自適應(yīng)和無損編碼等技術(shù)選擇算術(shù)編碼作為數(shù)字壓縮的基礎(chǔ)，能夠適應(yīng)所遇到的圖像統(tǒng)計(jì)概率。用細(xì)化網(wǎng)格里的黑色像素密度代表灰度，因?yàn)槿搜鄣姆直婺芰苡邢?，人的視覺系統(tǒng)會(huì)把這些小點(diǎn)平滑地聯(lián)起來。對(duì)計(jì)算機(jī)生成的圖像。JBIG1采用干凈自然的圖像邊緣來改善性能。二值圖像壓縮標(biāo)準(zhǔn)缺省的傳輸模式是順序模式在順序模式中，全分辨率圖像ID從左邊進(jìn)入，圖像經(jīng)過一連串的降低分辨率達(dá)到ID-1，…，I0。最低分辨率的水平稱為底層，所有的高一點(diǎn)的分辨率水平稱為差分層。描述底層的信息最先發(fā)送，然后是逐步向上的差分層信息。除非接收到信號(hào)中止這個(gè)過程，這樣一直到全分辨率。無損預(yù)測(cè)編碼預(yù)測(cè)編碼：

數(shù)字圖像或者音頻按照行或列從新排列后可以得到一個(gè)一位信號(hào)序列。預(yù)測(cè)編碼就是根據(jù)這個(gè)信號(hào)序列的一些已知情況來預(yù)測(cè)以后信號(hào)可能發(fā)生的情況，然后對(duì)預(yù)測(cè)的誤差進(jìn)行編碼而不是直接對(duì)信號(hào)進(jìn)行。當(dāng)預(yù)測(cè)比較準(zhǔn)確、誤差較小是，這種編碼方式就能達(dá)到數(shù)據(jù)壓縮的目的。無損預(yù)測(cè)編碼基本思想圖像相鄰像素間存在很強(qiáng)的相關(guān)性，通過觀察其相鄰像素取值，可預(yù)測(cè)一像素的大概情況。預(yù)測(cè)值和實(shí)際值存在誤差，稱為預(yù)測(cè)誤差。預(yù)測(cè)誤差的方差必然比原圖像像素的方差小，因此對(duì)預(yù)測(cè)誤差編碼必然壓縮其平均碼長(zhǎng)。對(duì)預(yù)測(cè)誤差進(jìn)行編碼的技術(shù)稱為DPCM（差分脈沖編碼調(diào)制）。無損預(yù)測(cè)編碼無損預(yù)測(cè)編碼無損預(yù)測(cè)編碼預(yù)測(cè)誤差的熵對(duì)比一幅圖像和其差分圖像的標(biāo)準(zhǔn)差和熵。不同圖像的差分圖像直方圖分布形態(tài)大致相同，只是方差有所不同。無損預(yù)測(cè)編碼預(yù)測(cè)方程式線性預(yù)測(cè)：如果ai是常數(shù)，則為時(shí)不變線性預(yù)測(cè)，否則為自適應(yīng)線性預(yù)測(cè)（ADPCM）最簡(jiǎn)單的預(yù)測(cè)方程：無損預(yù)測(cè)編碼預(yù)測(cè)器整數(shù)舍入符號(hào)編碼器預(yù)測(cè)器符號(hào)解碼器SS源數(shù)據(jù)壓縮數(shù)據(jù)恢復(fù)數(shù)據(jù)預(yù)測(cè)誤差,enfnf^nen+f^n++-fn壓縮數(shù)據(jù)無損預(yù)測(cè)編碼為實(shí)現(xiàn)無失真編碼，通常對(duì)差分進(jìn)行熵編碼（通常是Huffman編碼）；預(yù)測(cè)誤差熵編碼的步驟：建立碼表和編碼。通常采用一個(gè)通用碼表，節(jié)省建立專用碼表時(shí)間，由此帶來壓縮比損失較?。痪幋a：若對(duì)差分所有灰度建立碼表，則項(xiàng)數(shù)較多。通常對(duì)－16~16采用Huffman編碼，其他直接用前綴＋實(shí)際灰度值。無損預(yù)測(cè)編碼一副數(shù)字圖像或一段音頻可以看成一個(gè)空間點(diǎn)陣，圖像信號(hào)不僅在水平方向是相關(guān)的，在垂直方向也是相關(guān)的。根據(jù)已知樣值與待預(yù)測(cè)樣值間的位置關(guān)系，可以分為：（1）一維預(yù)測(cè)（行內(nèi)預(yù)測(cè)）：利用同一行上相鄰的樣值進(jìn)行預(yù)測(cè)。（2）二維預(yù)測(cè)（幀內(nèi)預(yù)測(cè)）：利用同一行和前面幾行的數(shù)據(jù)進(jìn)行預(yù)測(cè)。（3）三維預(yù)測(cè)（幀間預(yù)測(cè)）：利用相鄰幾幀（或不同波段）上的取樣值進(jìn)行預(yù)測(cè)無損預(yù)測(cè)編碼舉例：公式：中?。簃=2，a1=a2=1/2f={154,159,151,149,139,121,112,109,129}預(yù)測(cè)值f2=1/2*(154+159)156 e2=151–

156=-5 f3=1/2*(159+151)=155 e3=149–155=

-6 f4=1/2*(151+149)=150 e4=139–150=-11 f5=1/2*(149+139)=144 e5=121–144=

-23 f6=1/2*(139+121)=130 e6=112–130=-18 f7=1/2*(121+112)116 e7=109–116=-7 f8=1/2*(112+109)110 e8=129–110=19無損預(yù)測(cè)編碼這種壓縮算法被應(yīng)用到JPEG標(biāo)準(zhǔn)的無損壓縮模式之中，中等復(fù)雜程度的圖像壓縮比可達(dá)到2:1。cabx選擇值預(yù)測(cè)值0非預(yù)測(cè)1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三鄰域預(yù)測(cè)法無損預(yù)測(cè)編碼視頻信號(hào)的冗余度主要體現(xiàn)在空間相關(guān)性（幀內(nèi)）、時(shí)間相關(guān)性（幀間）和色度空間表示上的相關(guān)性。對(duì)于每秒30幀的視頻信號(hào)，其相繼幀之間存在極強(qiáng)的相關(guān)性。據(jù)統(tǒng)計(jì)256級(jí)灰度的黑白圖像序列，幀間差值超過3的象素?cái)?shù)不超過4％。所以在活動(dòng)圖像序列中可以利用前面的幀來預(yù)測(cè)后面的幀，以實(shí)現(xiàn)數(shù)據(jù)壓縮。幀間預(yù)測(cè)編碼技術(shù)被廣泛應(yīng)用到H.261、H.263、MPEG-1和MPEG-2等視頻壓縮標(biāo)準(zhǔn)之中。無損預(yù)測(cè)編碼運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)將前一個(gè)畫面的數(shù)值作為后一個(gè)畫面的預(yù)測(cè)值。編碼器運(yùn)動(dòng)補(bǔ)償圖像輸入運(yùn)動(dòng)矢量輸出-譯碼器幀緩存運(yùn)動(dòng)估計(jì)預(yù)測(cè)誤差輸出無損預(yù)測(cè)編碼無損預(yù)測(cè)編碼無損預(yù)測(cè)編碼無損預(yù)測(cè)編碼無損預(yù)測(cè)編碼無損預(yù)測(cè)編碼無損預(yù)測(cè)編碼詞典編碼文本中的詞用它在詞典中表示位置的號(hào)碼代替的一種無損數(shù)據(jù)壓縮方法。采用靜態(tài)詞典編碼技術(shù)時(shí)，編碼器需要事先構(gòu)造詞典，解碼器要事先知道詞典。采用動(dòng)態(tài)辭典編碼技術(shù)時(shí),編碼器將從被壓縮的文本中自動(dòng)導(dǎo)出詞典，解碼器解碼時(shí)邊解碼邊構(gòu)造解碼詞典。詞典編碼詞典編碼主要利用數(shù)據(jù)本身包含許多重復(fù)的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。我們?nèi)绻靡恍┖?jiǎn)單的代號(hào)代替這些字符串，就可以實(shí)現(xiàn)壓縮，實(shí)際上就是利用了信源符號(hào)之間的相關(guān)性。字符串與代號(hào)的對(duì)應(yīng)表就是詞典。實(shí)用的詞典編碼算法的核心就是如何動(dòng)態(tài)地形成詞典，以及如何選擇輸出格式以減小冗余第一類編碼算法第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”。LZ77算法LZ77算法在某種意義上又可以稱為“滑動(dòng)窗口壓縮”，該算法將一個(gè)虛擬的，可以跟隨壓縮進(jìn)程滑動(dòng)的窗口作為詞典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長(zhǎng)度。使用固定大小窗口進(jìn)行詞語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因?yàn)槠ヅ渌惴ǖ臅r(shí)間消耗往往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進(jìn)程滑動(dòng)詞典窗口，使其中總包含最近編碼過的信息，是因?yàn)閷?duì)大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。LZ77算法1、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動(dòng)窗口中找出最長(zhǎng)的匹配字符串，如果找到，則進(jìn)行步驟2，否則進(jìn)行步驟3。2、輸出三元符號(hào)組(off,len,c)。其中off為窗口中匹配字符串相對(duì)窗口邊界的偏移，len為可匹配的長(zhǎng)度，c為下一個(gè)字符，即不匹配的第一個(gè)字符。然后將窗口向后滑動(dòng)len+1個(gè)字符，繼續(xù)步驟1。3、輸出三元符號(hào)組(0,0,c)。其中c為下一個(gè)字符。然后將窗口向后滑動(dòng)1個(gè)字符，繼續(xù)步驟1。LZ77算法LZ77算法AABCBBABCA步驟位置匹配串輸出11－－0,0,A22A1,1,B34－－0,0,C45B2,1,B57ABC5,3,ALZSS算法LZ77通過輸出真實(shí)字符解決了在窗口中出現(xiàn)沒有匹配串的問題，但這個(gè)解決方案包含有冗余信息。冗余信息表現(xiàn)在兩個(gè)方面，一是空指針，二是編碼器可能輸出額外的字符，這種字符是指可能包含在下一個(gè)匹配串中的字符。LZSS算法的思想是如果匹配串的長(zhǎng)度比指針本身的長(zhǎng)度長(zhǎng)就輸出指針（匹配串長(zhǎng)度大于等于MIN_LENGTH），否則就輸出真實(shí)字符。另外要輸出額外的標(biāo)志位區(qū)分是指針還是字符LZSS算法1、從當(dāng)前壓縮位置開始，考察未編碼的字符，并試圖在滑動(dòng)窗口中找出最長(zhǎng)的匹配字符串，如果匹配串長(zhǎng)度len大于等于最小匹配串長(zhǎng)度（len>=MIN_LENGTH），則進(jìn)行步驟2，否則進(jìn)行步驟3。2、輸出指針二元組(off,len)。其中off為窗口中匹配字符串相對(duì)窗口邊界的偏移，len為匹配串的長(zhǎng)度，然后將窗口向后滑動(dòng)len個(gè)字符，繼續(xù)步驟1。3、輸出當(dāng)前字符c，然后將窗口向后滑動(dòng)1個(gè)字符，繼續(xù)步驟1。LZSS算法位置1234567891011字符AABBCBBAABC步驟位置匹配串輸出11－－A22AA33－－B44BB55－－C66BB（3，2）78AAB（7，3）811CC輸入數(shù)據(jù)流：編碼過程MIN_LEN=2LZSS算法在相同的計(jì)算機(jī)環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡(jiǎn)單。這也就是為什么這種算法成為開發(fā)新算法的基礎(chǔ)，許多后來開發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip,GZip,ARJ,LHArc和ZOO等等，其差別僅僅是指針的長(zhǎng)短和窗口的大小等有所不同。LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用，它的后續(xù)版本也采用霍夫曼編碼。第二類詞典編碼第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語詞典(dictionaryofthephrases)”，這種短語可以是任意字符的組合。編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語”時(shí)，編碼器就輸出這個(gè)詞典中的短語的“索引號(hào)”，而不是短語本身。LZ78算法LZ78的編碼思想是不斷地從字符流中提取新的字符串(String)，通俗地理解為新“詞條”，然后用“代號(hào)”也就是碼字(Codeword)表示這個(gè)“詞條”。這樣一來，對(duì)字符流的編碼就變成了用碼字(Codeword)去替換字符流(Charstream)，生成碼字流(Codestream)，從而達(dá)到壓縮數(shù)據(jù)的目的。LZ78編碼器的輸出是碼字-字符(W,C)對(duì)，每次輸出一對(duì)到碼字流中，與碼字W相對(duì)應(yīng)的字符串(String)用字符C進(jìn)行擴(kuò)展生成新的字符串(String)，然后添加到詞典中。LZ78算法步驟1：將詞典和當(dāng)前前綴P都初始化為空。步驟2：當(dāng)前字符C:=字符流中的下一個(gè)字符。步驟3：判斷P＋C是否在詞典中（1）如果“是”，則用C擴(kuò)展P，即讓P:=P＋C，返回到步驟2。（2）如果“否”，則輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字W和當(dāng)前字符C，即（W，C）；將P＋C添加到詞典中；令P:=空值，并返回到步驟2LZ78算法位置123456789字符ABBCBCABA步驟位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)輸入數(shù)據(jù)流：編碼過程：LZW算法J.Ziv和A.Lempel在1978年首次發(fā)表了介紹第二類詞典編碼算法的文章。在他們的研究基礎(chǔ)上，TerryA.Welch在1984年發(fā)表了改進(jìn)這種編碼算法的文章，因此把這種編碼方法稱為L(zhǎng)ZW(Lempel-ZivWalch)壓縮編碼。在編碼原理上，LZW與LZ78相比有如下差別：LZW只輸出代表詞典中的字符串(String)的碼字(codeword)。這就意味在開始時(shí)詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符。即在編碼匹配時(shí)，至少可以在詞典中找到長(zhǎng)度為1的匹配串。

LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。LZW算法

LZW編碼器(軟件編碼器或硬件編碼器)就是通過管理這個(gè)詞典完成輸入與輸出之間的轉(zhuǎn)換。LZW編碼器的輸入是字符流(Charstream)，字符流可以是用8位ASCII字符組成的字符串，而輸出是用n位(例如12位)表示的碼字流(Codestream)，碼字代表單個(gè)字符或多個(gè)字符組成的字符串(String)。LZW算法步驟1：將詞典初始化為包含所有可能的單字符，當(dāng)前前綴P初始化為空。步驟2：當(dāng)前字符C:=字符流中的下一個(gè)字符。步驟3：判斷P＋C是否在詞典中（1）如果“是”，則用C擴(kuò)展P，即讓P:=P＋C，返回到步驟2。（2）如果“否”，則輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字W；將P＋C添加到詞典中；令P:=C，并返回到步驟2LZW算法位置123456789字符ABBABABAC步驟位置碼字詞典輸出1A2B3C114AB1225BB2336BA2447ABA4558ABAC76－－－3輸入數(shù)據(jù)流：LZW算法

LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因?yàn)樗恍枰獔?zhí)行那么多的綴-符串比較操作。對(duì)LZW算法進(jìn)一步的改進(jìn)是增加可變的碼字長(zhǎng)度，以及在詞典中刪除老的綴-符串。在GIF圖像格式、TIFF圖像格式和UNIX的壓縮程序中已經(jīng)采用了這些改進(jìn)措施之后的LZW算法。

LZW算法取得了專利，專利權(quán)的所有者是美國的一個(gè)大型計(jì)算機(jī)公司—Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產(chǎn)公司之外，可以免費(fèi)使用LZW算法。GIF例子：GIF和TIFF都使用LZW壓縮法。下面以GIF為例進(jìn)行介紹：1）GIF簡(jiǎn)介（多圖像、256色）文件結(jié)構(gòu)： 文件頭信息：標(biāo)識(shí)（GIF）、版本號(hào) 屏幕描述：屏幕長(zhǎng)、寬、背景色等 全局調(diào)色板：長(zhǎng)度（256x3）//三個(gè)256色的調(diào)色板GIF

圖象描述：描述圖像塊在屏幕上的左上角位置及寬高 局部調(diào)色板:長(zhǎng)度（256x3）//三個(gè)256色的調(diào)色板，每個(gè)圖像可有一個(gè) 圖像數(shù)據(jù)：用LZW方式壓縮，用256字節(jié)的塊來存放 擴(kuò)充塊描述：有四種擴(kuò)充塊文件頭信息LZW壓縮圖像數(shù)據(jù)全局調(diào)色板屏幕描述圖像描述局部調(diào)色板擴(kuò)充數(shù)據(jù)塊GIF初始化字典輸出清除標(biāo)記LZW_CLEARTemp=空串k=從輸入流中讀一個(gè)字符是結(jié)尾標(biāo)志嗎？Temp+k在字典中嗎？輸出Temp的編碼把新串Temp+k加到字典中Temp=kTemp=Temp+k輸出Temp的編碼輸出結(jié)束標(biāo)記GIF編碼舉例：設(shè)字符集{a,b,c,d}， 串：aabdaadaa

壓縮字典 臨時(shí)串輸入串編碼

0 a T=temp+ a 1 b T=a + a0 2 c T=a + b00 3 d T=b + d 001 4 aa T=d + a 00135 ab T=a + a 6 bd T=aa + d 001347 da T=d + a