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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

從存儲角度：

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

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

較快地傳輸各種信源—

時間域的壓縮；

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

頻率域的壓縮；

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

能量域的壓縮；

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

空間域的壓縮。

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

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

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

數(shù)據(jù)壓縮的基本概念第一章緒論數(shù)據(jù)壓縮的標準與應用圖1.2數(shù)據(jù)壓縮的一般步驟

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

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

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

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

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

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

Compression:

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

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

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

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

例1-6

對采樣值設置門限，當采樣值超過該門限時才傳輸—原始采樣值不可能恢復，信息丟失；舉例：有失真壓縮（茶葉粉末無法恢復出茶葉）例1-7

茶葉壓縮的例子

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

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

內在冗余度：水份—冗余度壓縮

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

數(shù)

據(jù)

壓

縮

冗余度壓縮（熵編碼）

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

熵壓縮特征抽取

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

量化其他無記憶量化均勻量化、Max量化、壓擴量化

有記憶量化

序列量化預測編碼增量調制、線性/非線性/自適應/運動補償預測等其他方法序貫量化等

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

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

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

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

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

和MIT的R.M.Fano

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

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

Huffman，又不增加程序對系統(tǒng)資源和時間的需求呢？

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

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

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

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

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

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

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

國際標準化組織（InternationalOrganization

forStandardization,簡稱ISO）

是目前世界上最大、最具權威性的國際標準化專

門機構。國際電工委員會(InternationalElectrotechnical

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