數(shù)據(jù)壓縮概述

數(shù)據(jù)壓縮

DataCompression教材和參考書《數(shù)據(jù)壓縮》，吳樂(lè)南編著，電子工業(yè)出版社第3版教材:參考書(Reference):

DavidSalomon著數(shù)據(jù)壓縮原理與應(yīng)用(電子工業(yè)出版社，2003年9月)KhalidSayood著數(shù)據(jù)壓縮導(dǎo)論(人民郵電出版社，2009年8月)作業(yè)及考試形式閉卷考試課程成績(jī)＝平時(shí)（40％）+期末（60％）數(shù)據(jù)壓縮技術(shù)的分類

數(shù)據(jù)壓縮的必要性

數(shù)據(jù)壓縮的基本概念第一章緒論數(shù)據(jù)壓縮的標(biāo)準(zhǔn)與應(yīng)用數(shù)字傳輸系統(tǒng)模型解決可靠性問(wèn)題，使處理過(guò)的信號(hào)在傳輸過(guò)程中不出錯(cuò)或少出錯(cuò)，即使出錯(cuò)也可以檢錯(cuò)或糾錯(cuò)。本書的研究?jī)?nèi)容屬于信源編碼，信源編碼的一個(gè)最主要的目的就是解決數(shù)據(jù)壓縮的問(wèn)題。

解決有效性問(wèn)題，主要是對(duì)信源的壓縮處理，用最少的數(shù)碼傳遞最大的信息量。信道編碼：信道編碼/信道解碼信源編碼：信源編碼/信源解碼信源編碼和信道編碼UNIX下的COMPACT程序：Winzip、RAR等：JPEG、GIF：AVI、MPEG2、MPEG4：PostScript：Huffman編碼基于字典模型的壓縮技術(shù)（LZ77、LZ78、LZW算法）灰度、彩色圖像的壓縮矢量圖像壓縮聲音視頻信號(hào)的壓縮實(shí)際應(yīng)用如果你對(duì)數(shù)據(jù)的壓縮原理感到驚訝和迷惑不解那么，這門課就給出了上述答案。課程包含詳細(xì)的算法描述，以及進(jìn)一步學(xué)習(xí)壓縮技術(shù)的有效建議……如果你想知道上述的壓縮工具是如何工作的如果你正要為自己的應(yīng)用程序添加壓縮/解壓縮模塊以最少的數(shù)據(jù)表示信源所發(fā)的信號(hào)，減少容納給定消息集合或數(shù)據(jù)采樣集合的信號(hào)空間：物理空間，如存儲(chǔ)器、磁盤、磁帶、光盤等數(shù)據(jù)存儲(chǔ)介質(zhì)；

時(shí)間空間，如傳輸給定消息集合所需的時(shí)間；電磁頻譜區(qū)域，如為傳輸給定消息集合所要求的

帶寬等。數(shù)據(jù)壓縮的定義信號(hào)集合的空域、時(shí)域和頻域空間，信號(hào)空間的幾種形式是相互關(guān)聯(lián)的，如存儲(chǔ)空間的減少也意味著傳輸效率的提高和占用帶寬的節(jié)省，只要采用某種方法來(lái)減少某一種信號(hào)空間，都能壓縮數(shù)據(jù)。

數(shù)據(jù)壓縮技術(shù)的分類

數(shù)據(jù)壓縮的必要性

數(shù)據(jù)壓縮的基本概念第一章緒論數(shù)據(jù)壓縮的標(biāo)準(zhǔn)與應(yīng)用數(shù)字傳輸系統(tǒng)的優(yōu)點(diǎn)①數(shù)字傳輸質(zhì)量高于模擬傳輸質(zhì)量，經(jīng)多次中繼不引起嚴(yán)重的噪聲累積，不受系統(tǒng)非線性影響②易于采用信道編碼技術(shù)提高傳輸?shù)目煽啃寓郾阌诶脮r(shí)分復(fù)用技術(shù)與其他通信業(yè)務(wù)相結(jié)合④易于數(shù)字加密，提高信息安全性⑤數(shù)字電路易于大規(guī)模集成⑥數(shù)字設(shè)備可靠性高，維護(hù)簡(jiǎn)便采用數(shù)字技術(shù)（或系統(tǒng)）具有許多優(yōu)越性，但也使數(shù)據(jù)量大增。數(shù)字信號(hào)的傳輸速率或比特率I為：其中：數(shù)字化信號(hào)的取樣頻率，每個(gè)取樣幅度值用R位二進(jìn)制編碼（Rbit）。可理解為：該信號(hào)在通信線路上每秒鐘應(yīng)傳送的位數(shù)，或者保存一秒鐘信號(hào)樣值所需要占用的存儲(chǔ)容量。當(dāng)取樣速率一定時(shí)，比特率(或數(shù)碼率、碼率、速率、數(shù)據(jù)率)也可簡(jiǎn)單地用R表示，意為每個(gè)樣值Rbit。一般傳輸時(shí)多用I，存儲(chǔ)時(shí)只用R。數(shù)據(jù)壓縮的必要性數(shù)字音頻格式取樣率kHz樣本精度bit頻帶Hz電話88300~3400AM廣播11.0251650~7000激光光盤（CD）44.11620~20000數(shù)字音頻磁帶（DAT）481620~20000

數(shù)字視頻信號(hào)格式數(shù)字電視格式圖像分辨率(象素)每秒幀數(shù)樣本精度bit通用中間格式（CIF）亮度信號(hào)352×288308CCIR601的亮度信號(hào)720×480/720×57630/258HDTV亮度信號(hào)一例1920×1080608數(shù)字化音頻格式數(shù)字音視頻格式數(shù)字音頻、視頻信號(hào)數(shù)據(jù)傳輸速率計(jì)算從傳輸角度：數(shù)字電話

一路廣播級(jí)的彩色數(shù)字電視(若按4:2:2（亮度/色差/色差）的分量編碼標(biāo)準(zhǔn)格式，用13.5/6.75/6.75MHz頻率采樣，每像素（pixel:pictureelement,簡(jiǎn)寫為pel）用8位編碼)：

等于3375路數(shù)字話路；

從存儲(chǔ)角度：

512×512像素、8bit/pixel黑白圖像：

512×512像素、每分量8bit/pixel的彩色圖像：一幅2230×2230×8bit的氣象衛(wèi)星紅外云圖：B為字節(jié)低高數(shù)據(jù)量一顆衛(wèi)星每半個(gè)小時(shí)即可發(fā)回一次全波段數(shù)據(jù)（5個(gè)波段），每天的數(shù)據(jù)率高達(dá)1.1GB多顆衛(wèi)星？多波段？全天候？……不進(jìn)行數(shù)據(jù)壓縮，無(wú)論傳輸或存儲(chǔ)都很難實(shí)用化，數(shù)據(jù)壓縮的好處就在于：

較快地傳輸各種信源—

時(shí)間域的壓縮；

開通更多的并行業(yè)務(wù)（電視、傳真、電話、可視圖文等）—

頻率域的壓縮；

降低發(fā)射機(jī)功率—

能量域的壓縮；

緊縮數(shù)據(jù)存儲(chǔ)容量—

空間域的壓縮。

數(shù)據(jù)壓縮的優(yōu)勢(shì)

數(shù)據(jù)壓縮技術(shù)的分類

數(shù)據(jù)壓縮的必要性

數(shù)據(jù)壓縮的基本概念第一章緒論數(shù)據(jù)壓縮的標(biāo)準(zhǔn)與應(yīng)用圖1.2數(shù)據(jù)壓縮的一般步驟

建立一個(gè)數(shù)學(xué)模型，能夠更緊湊或更有效地“重新表達(dá)”規(guī)律性不那么明顯的原始數(shù)據(jù)；

把模型參數(shù)量化為有限的精度（二次量化，與原始數(shù)據(jù)的量化不同）；

對(duì)模型參數(shù)的量化表示或消息流進(jìn)行碼字分配，以得到盡可能緊湊的壓縮碼—“熵編碼(EntropyCoding)”；

數(shù)據(jù)壓縮的一般方法

預(yù)測(cè)，變換…可逆壓縮(LosslessCompression)冗余度壓縮：去除或減少那些可能是后來(lái)插入數(shù)據(jù)中的冗余度，是一個(gè)可逆過(guò)程。香農(nóng)（C.E.Shannon）信息論：數(shù)據(jù)=信息+冗余度其他術(shù)語(yǔ)：無(wú)損壓縮、無(wú)失真、無(wú)差錯(cuò)編碼（ErrorFreeCoding）、無(wú)噪聲（Noiseless）編碼、冗余度壓縮(RedundaryReduction)、熵編碼(EntropyCoding)、數(shù)據(jù)緊縮(Datacompaction)、信息保持編碼（Lossless,Bit-preserving）。

例1-4計(jì)算不同采樣值間重復(fù)采樣的數(shù)目(游程)，然后將變化的采樣值與該重復(fù)數(shù)目一起發(fā)送。

Compression:

針對(duì)數(shù)據(jù)內(nèi)部的多余信息進(jìn)行壓縮；

例1-512位A/D變換，通常采用2字節(jié)來(lái)存一個(gè)采樣值，多出4位冗余度，改用3個(gè)字節(jié)存4個(gè)數(shù)據(jù)，可消除冗余度。Compaction

:針對(duì)數(shù)據(jù)外在冗余度進(jìn)行壓縮。

舉例不可逆壓縮(LossyCompression)又稱:有失真（Lossy）壓縮、熵壓縮（EntropyCompression）。

例1-6

對(duì)采樣值設(shè)置門限，當(dāng)采樣值超過(guò)該門限時(shí)才傳輸—原始采樣值不可能恢復(fù)，信息丟失；舉例：有失真壓縮（茶葉粉末無(wú)法恢復(fù)出茶葉）例1-7

茶葉壓縮的例子

，直觀理解冗余度壓縮——無(wú)失真壓縮（茶葉保持完整）

外在冗余度：空氣—數(shù)據(jù)緊縮

內(nèi)在冗余度：水份—冗余度壓縮

茶葉壓成粉末——鐵罐可以裝得更多茶葉（“數(shù)據(jù)”）放入鐵罐（“存儲(chǔ)器”）一般結(jié)論 ①有冗余度就可以壓縮 ②壓縮只能在一定程度內(nèi)可逆 ③超過(guò)一定限度，必然帶來(lái)失真 ④允許的失真越大，壓縮的比例也可以越大實(shí)用的數(shù)據(jù)壓縮技術(shù)

數(shù)

據(jù)

壓

縮

冗余度壓縮（熵編碼）

統(tǒng)計(jì)編碼霍夫曼編碼、游程編碼、二進(jìn)制信源編碼等算術(shù)編碼基于字典的編碼：LZW編碼等其他編碼完全可逆的小波分解+統(tǒng)計(jì)編碼等

熵壓縮特征抽取

分析/綜合編碼子帶、小波、分形、模型基等

量化其他無(wú)記憶量化均勻量化、Max量化、壓擴(kuò)量化

有記憶量化

序列量化預(yù)測(cè)編碼增量調(diào)制、線性/非線性/自適應(yīng)/運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)等其他方法序貫量化等

分組量化直接映射矢量量化、神經(jīng)網(wǎng)絡(luò)、方塊截尾等

變換編碼正交變換：KLT、DCT、DFT、WHT等非正交變換其他函數(shù)變換表1.2數(shù)據(jù)壓縮技術(shù)的簡(jiǎn)單分類

數(shù)據(jù)壓縮技術(shù)的分類

數(shù)據(jù)壓縮的必要性

數(shù)據(jù)壓縮的基本概念第一章緒論數(shù)據(jù)壓縮的標(biāo)準(zhǔn)與應(yīng)用數(shù)據(jù)壓縮技術(shù)的發(fā)展歷史早在1949年，貝爾實(shí)驗(yàn)室的ClaudeShannon

和MIT的R.M.Fano

幾乎同時(shí)提出了的對(duì)符號(hào)進(jìn)行有效編碼從而實(shí)現(xiàn)數(shù)據(jù)壓縮的Shannon-Fano編碼方法。Shannon-Fano編碼大多數(shù)信息的表達(dá)都存在著一定的冗余度，通過(guò)采用一定的模型和編碼方法，可以降低這種冗余度。60年代、70年代乃至80年代的早期，數(shù)據(jù)壓縮領(lǐng)域幾乎一直被Huffman編碼及其分支所壟斷。UNIX系統(tǒng)上一個(gè)壓縮程序COMPACT就是Huffman0階自適應(yīng)編碼的具體實(shí)現(xiàn)。80年代初，Huffman編碼又在DOS系統(tǒng)中實(shí)現(xiàn)，其代表程序叫SQ。1952年D.A.Huffman第一次發(fā)表了他的論文“最小冗余度代碼的構(gòu)造方法”(AMethodfortheConstructionofMinimumRedundancyCodes)。Huffman編碼80年代，數(shù)學(xué)家們從新的角度入手，遵循Huffman編碼的主導(dǎo)思想，設(shè)計(jì)出另一種更為精確，更能接近信息論中“熵”極限的編碼方法—算術(shù)編碼。

算術(shù)編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號(hào)精確表達(dá)原始信息內(nèi)容。算術(shù)編碼雖然可以得到最好的壓縮效果，但卻要消耗也許幾十倍的計(jì)算時(shí)間。算術(shù)編碼能不能既在壓縮效果上超越

Huffman，又不增加程序?qū)ο到y(tǒng)資源和時(shí)間的需求呢？

1977年之前，數(shù)據(jù)壓縮的研究工作主要集中于熵、字符和單詞頻率以及統(tǒng)計(jì)模型等方面，1977年，以色列人JacobZiv和AbrahamLempel發(fā)表了論文“順序數(shù)據(jù)壓縮的一個(gè)通用算法”(AUniversalAlogrithemforSequentialDataCompression)。字典式編碼字典式編碼不但在壓縮效果上大大超過(guò)了Huffman，而且，對(duì)于算法的實(shí)現(xiàn)，其壓縮和解壓縮的速度也異常驚人。

1978年，他們發(fā)表了該論文的續(xù)篇“通過(guò)可變比率編碼的獨(dú)立序列的壓縮”(CompressionofIndividualSequencesviaVariable-RateCoding)。在這兩篇論文中提出的兩個(gè)壓縮技術(shù)被稱為L(zhǎng)Z77和LZ78?；谶@一思路的編碼方法被稱作“字典”式編碼。1984年，TerryWelch發(fā)表了名為“高性能數(shù)據(jù)壓縮技術(shù)”(ATechniqueforHigh-PerformanceDataCompression)的論文，實(shí)現(xiàn)了LZ78算法的一個(gè)變種—LZW。LZW繼承了LZ77和LZ78壓縮效果好、速度快的優(yōu)點(diǎn)，而且在算法描述上更容易被人們接受，實(shí)現(xiàn)也比較簡(jiǎn)單。不久，UNIX上出現(xiàn)了使用LZW算法的Compress程序，很快成為了UNIX世界的壓縮程序標(biāo)準(zhǔn)。緊隨其后的是MS-DOS環(huán)境下的ARC程序，還有象PKWare、PKARC等仿制品。LZ78和LZW一時(shí)間統(tǒng)治了UNIX和DOS兩大平臺(tái)。另外對(duì)于

GIF格式，GIF格式可以把原始圖形文件以非常小數(shù)據(jù)量存儲(chǔ)，可以在同一個(gè)文件中存儲(chǔ)多幅圖像從而實(shí)現(xiàn)動(dòng)畫效果。知道

GIF中的圖像使用什么方法壓縮的嗎？LZW!GIF精確地保留了原始圖像的每一個(gè)像素信息，是無(wú)損圖像壓縮的代表。當(dāng)然，GIF文件中除了經(jīng)過(guò)

LZW壓縮的像素信息以外，還保存有圖像的各種屬性信息以及圖像所使用的調(diào)色板信息等。80年代中期以后，人們對(duì)LZ77進(jìn)行了改進(jìn)，隨之誕生了一批我們今天還在大量使用的壓縮程序。LZ77得以和LZ78、LZW一起壟斷當(dāng)今的通用數(shù)據(jù)壓縮領(lǐng)域。目前，基于字典方式的壓縮已經(jīng)有了一個(gè)被廣泛認(rèn)可的標(biāo)準(zhǔn)，從古老的PKZip到現(xiàn)在的WinZip，特別是隨著Internet上文件傳輸?shù)牧餍校琙IP格式成為了事實(shí)上的標(biāo)準(zhǔn)，沒有哪一種通用的文件壓縮、歸檔系統(tǒng)敢于不支持ZIP格式?，F(xiàn)在對(duì)聲音、圖像、視頻等多媒體信息的壓縮有兩條思路：要么采用成熟的通用數(shù)據(jù)壓縮技術(shù)進(jìn)行壓縮；要么根據(jù)媒體信息的特性設(shè)計(jì)新的壓縮方法。根據(jù)媒體特性量身定制的壓縮方法中，游程編碼(RLE:Run-LengthEncoding)是最為簡(jiǎn)單、最容易被想到的一種。大多數(shù)計(jì)算機(jī)中產(chǎn)生的圖像(和現(xiàn)實(shí)世界的圖像例如照片不同)都具有著大面積重復(fù)的顏色塊，完全可以用一個(gè)顏色值加一個(gè)重復(fù)次數(shù)來(lái)表示這一塊圖像，冗余度由此減小了，這就是RLE方法的基本思路。顯然，它不適于用來(lái)壓縮照片、聲音等很少連續(xù)重復(fù)信息的數(shù)據(jù)。游程編碼70年代末80年代初，人們逐漸意識(shí)到，對(duì)到多數(shù)灰度或是彩色圖像乃至聲音文件，沒有必要忠實(shí)地保留其所有信息，在允許一定的精度損失的情況下，可以實(shí)現(xiàn)更為有效的壓縮方法。到80年代末，許多人已經(jīng)在這一領(lǐng)域取得了不小的收獲，設(shè)計(jì)出了一批在壓縮效果上讓人驚訝不已的聲音和圖像壓縮算法。在此基礎(chǔ)上，國(guó)際標(biāo)準(zhǔn)化組織(ISO)和CCITT聯(lián)合組成了兩個(gè)委員會(huì)：

靜態(tài)圖像聯(lián)合專家小組(JPEG)JPEG的壓縮目標(biāo)是靜止圖像(灰度的和彩色的)，

動(dòng)態(tài)圖像聯(lián)合專家小組(MPEG)MPEG的目標(biāo)則是聲音和視頻他們的基本思路是完全一樣的，即保留媒體信息中最有規(guī)律、最能體現(xiàn)信息主要特征的數(shù)據(jù)，而略去其他不重要的數(shù)據(jù)。主要數(shù)據(jù)壓縮標(biāo)準(zhǔn)和應(yīng)用標(biāo)準(zhǔn)化組織

國(guó)際標(biāo)準(zhǔn)化組織（InternationalOrganization

forStandardization,簡(jiǎn)稱ISO）

是目前世界上最大、最具權(quán)威性的國(guó)際標(biāo)準(zhǔn)化專

門機(jī)構(gòu)。國(guó)際電工委員會(huì)(InternationalElectrotechnical

Commission，簡(jiǎn)稱IEC）是世界上最早的國(guó)際性電工標(biāo)準(zhǔn)化機(jī)構(gòu)。國(guó)際電信聯(lián)盟的電子標(biāo)準(zhǔn)部(InternationalTelecommunicationUnion，簡(jiǎn)稱ITU）是聯(lián)合國(guó)的一個(gè)專門機(jī)構(gòu)，國(guó)際電信界最權(quán)威的標(biāo)準(zhǔn)修訂組織。1972年12月,電信標(biāo)準(zhǔn)化部、無(wú)線電通信部和電信發(fā)展部承擔(dān)著ITU的實(shí)質(zhì)性標(biāo)準(zhǔn)制訂工作。其中，電信標(biāo)準(zhǔn)化部門由原來(lái)的國(guó)際電報(bào)電話咨詢委員會(huì)（CCITT）和國(guó)際無(wú)線電咨詢委員會(huì)（CCIR）的標(biāo)準(zhǔn)化部門合并而成，其主要職責(zé)是實(shí)現(xiàn)國(guó)際電信聯(lián)盟有關(guān)電信標(biāo)準(zhǔn)化的目標(biāo)，使全世界的電信標(biāo)準(zhǔn)化。表1.3主要的數(shù)據(jù)壓縮標(biāo)準(zhǔn)及其典型應(yīng)用標(biāo)準(zhǔn)號(hào)俗稱適用信源典型應(yīng)用ITU-TT.82|ISO/IEC11544JBIG-1二值圖像、圖形G4傳真機(jī)、計(jì)算機(jī)圖形ISO/IEC14492JBIG-2二值圖像、圖形傳真、WWW圖形庫(kù)、PDA等ITU-TT.81|ISO/IEC10918JPEG連續(xù)色調(diào)靜止圖像圖像庫(kù)、傳真、彩色印刷、數(shù)碼相機(jī)等ITU-TT.87|ISO/IEC14495JPEG-LS連續(xù)色調(diào)靜止圖像醫(yī)學(xué)、遙感圖像資料的無(wú)損