壓縮編碼緒論(2015)

1、1 1壓縮編碼技術壓縮編碼技術 21、課堂出勤。、課堂出勤。課程每學分不得超過一次缺勤課程每學分不得超過一次缺勤，每缺勤，每缺勤一次，期末總成績扣五分；若缺勤次數超過課程學分數，一次，期末總成績扣五分；若缺勤次數超過課程學分數，則取消該門課程的期末考試資格。則取消該門課程的期末考試資格。2、作業(yè)。課程作業(yè)缺交量超過作業(yè)總量、作業(yè)。課程作業(yè)缺交量超過作業(yè)總量30%及以上的，及以上的，取消該門課程的期末考試資格。辦理課程免聽的學生亦取消該門課程的期末考試資格。辦理課程免聽的學生亦參照此規(guī)定執(zhí)行，教學辦在學生辦理免聽手續(xù)時，須向參照此規(guī)定執(zhí)行，教學辦在學生辦理免聽手續(xù)時，須向學生聲明強調此規(guī)定。學生

2、聲明強調此規(guī)定。 學院的有關規(guī)定學院的有關規(guī)定3考核方式考核方式 開卷考試開卷考試 考試內容：考試內容： 基礎知識和基本原理基礎知識和基本原理 壓縮編碼方法壓縮編碼方法 4教材及參考書目教材及參考書目 1.吳樂南.數據壓縮（第三版）.北京:電子工業(yè)出版社，2012.8 （主要教材）（主要教材）2.吳家安.數據壓縮技術及應用.北京:科學出版社，2009.13.戴善榮.數據壓縮.西安:西安電子科學技術出版社,2005.54.Khalid Sayood著.數據壓縮導論.北京:人民郵電出版社,20095.David Salomon著.數據壓縮原理與應用.北京:電子工業(yè)出版社,2003.9 5參考書目參

3、考書目 6參考書目參考書目 7其他參考書目其他參考書目 8其他參考書目其他參考書目 9教學內容教學內容 第一章第一章 緒論緒論 第二章第二章 信源的數字化與壓縮系統(tǒng)評價信源的數字化與壓縮系統(tǒng)評價 第三章第三章 數據壓縮的信息論基礎數據壓縮的信息論基礎 第四章第四章 統(tǒng)計編碼統(tǒng)計編碼 第五章第五章 預測編碼預測編碼 第六章第六章 變換編碼變換編碼 第七章第七章 子帶編碼與小波變換子帶編碼與小波變換 第八章第八章 圖像圖像/視頻壓縮編碼的國際標準視頻壓縮編碼的國際標準10第一章第一章 緒緒 論論1.1 什么是數據壓縮？什么是數據壓縮？1.2 數據壓縮的必要性數據壓縮的必要性1.3 數據壓縮技術的分

4、類數據壓縮技術的分類1.4 數據壓縮技術的歷史發(fā)展數據壓縮技術的歷史發(fā)展111.1 什么是數據壓縮？什么是數據壓縮？u數據壓縮數據壓縮：用緊致的方式表示信息的技術或科學。：用緊致的方式表示信息的技術或科學。探求任何信源的探求任何信源的“精純精純”表述，而又不致帶來重表述，而又不致帶來重大的失真，這就是數據壓縮要解決的命題。大的失真，這就是數據壓縮要解決的命題。121.1 什么是數據壓縮？什么是數據壓縮？u信息：抽象的，要表達的特定意思；信息：抽象的，要表達的特定意思；u消息：可以把信息表達出來的文字、語言或消息：可以把信息表達出來的文字、語言或圖像等，具體的；圖像等，具體的；u信號：消息的物理

5、體現，可在通信系統(tǒng)中傳信號：消息的物理體現，可在通信系統(tǒng)中傳輸，如光信號、電信號；輸，如光信號、電信號；l通信最基本、最重要的功能就是通信最基本、最重要的功能就是傳遞傳遞信信息，獲取信息、處理信息、和利用信息。息，獲取信息、處理信息、和利用信息。131.1 什么是數據壓縮？什么是數據壓縮？141.1 什么是數據壓縮？什么是數據壓縮？u信源編碼：壓縮與解壓縮、加密與解密信源編碼：壓縮與解壓縮、加密與解密 主要解決傳輸的主要解決傳輸的有效性有效性問題問題 用最少的數碼傳遞最大的信息量。用最少的數碼傳遞最大的信息量。u信道編碼：盡量克服傳輸過程中的差錯信道編碼：盡量克服傳輸過程中的差錯 主要解決傳輸

6、的主要解決傳輸的可靠性可靠性問題問題 151.1 什么是數據壓縮？什么是數據壓縮？161.1 什么是數據壓縮？什么是數據壓縮？u信源編碼：壓縮與解壓縮、加密與解密信源編碼：壓縮與解壓縮、加密與解密 主要解決傳輸的主要解決傳輸的有效性有效性問題問題l數據壓縮：以最少的平均信息位來表示信源所發(fā)出數據壓縮：以最少的平均信息位來表示信源所發(fā)出的信息，減少容納給定消息集合或數據采樣集合的的信息，減少容納給定消息集合或數據采樣集合的信號空間（數據存儲介質、時間、帶寬，即空域、信號空間（數據存儲介質、時間、帶寬，即空域、時域和頻域等）。時域和頻域等）。17 Winzip、RAR、ARJ、UNIX下的壓縮程序

7、等：下的壓縮程序等： JPEG、GIF： AVI、MPEG2、MPEG4： PostScript： 基于字典模型的壓縮技術（基于字典模型的壓縮技術（LZ77、LZ78、LZW）灰度、彩色圖像的壓縮灰度、彩色圖像的壓縮矢量圖像壓縮矢量圖像壓縮聲音視頻信號的壓縮聲音視頻信號的壓縮實實 際際 應應 用用18第一章第一章 緒緒 論論1.1 什么是數據壓縮？什么是數據壓縮？1.2 數據壓縮的必要性數據壓縮的必要性1.3 數據壓縮技術的分類數據壓縮技術的分類1.4 數據壓縮技術的歷史發(fā)展數據壓縮技術的歷史發(fā)展191.2 數據壓縮的必要性數據壓縮的必要性數字傳輸系統(tǒng)的優(yōu)點：數字傳輸系統(tǒng)的優(yōu)點： 數字傳輸質量

8、高于模擬傳輸質量，經多次中繼不引數字傳輸質量高于模擬傳輸質量，經多次中繼不引起嚴重的噪聲累積，不受系統(tǒng)非線性影響起嚴重的噪聲累積，不受系統(tǒng)非線性影響 易于采用信道編碼技術提高傳輸的可靠性易于采用信道編碼技術提高傳輸的可靠性 便于利用時分復用技術與其他通信業(yè)務相結合便于利用時分復用技術與其他通信業(yè)務相結合 易于數字加密，提高信息安全性易于數字加密，提高信息安全性 數字電路易于大規(guī)模集成數字電路易于大規(guī)模集成 數字設備可靠性高，維護簡便數字設備可靠性高，維護簡便20采用數字技術（或系統(tǒng)）具有許多優(yōu)越性，但也使采用數字技術（或系統(tǒng)）具有許多優(yōu)越性，但也使數據量大增數據量大增。數字信號的傳輸速率或比特

9、率。數字信號的傳輸速率或比特率 I 為：為： (bit/s or b/s)sIfR其中：數字化信號的取樣頻率其中：數字化信號的取樣頻率 ，每個取樣幅度值，每個取樣幅度值用用R 位二進制編碼（位二進制編碼（R bit）?？衫斫鉃椋涸撔盘栐冢？衫斫鉃椋涸撔盘栐谕ㄐ啪€路上每秒鐘應通信線路上每秒鐘應傳送的位數傳送的位數，或著保存一秒鐘，或著保存一秒鐘信號樣值所需要占用的信號樣值所需要占用的存儲容量存儲容量。當取樣速率一定時，比特率當取樣速率一定時，比特率(或數碼率、碼率、速或數碼率、碼率、速率、數據率率、數據率)也可簡單地用也可簡單地用R表示表示，意為每個樣值，意為每個樣值R bit。一般傳輸時多用

10、。一般傳輸時多用I ，存儲時只用，存儲時只用R 。sf1.2 數據壓縮的必要性數據壓縮的必要性211.2 數據壓縮的必要性數據壓縮的必要性幾種常見視頻圖像源未壓縮的原始數據率幾種常見視頻圖像源未壓縮的原始數據率視頻源視頻源每秒每秒 幀率幀率分辨率（幀分辨率（幀內像素數）內像素數）未壓縮數據率未壓縮數據率 / / MbpsMbpsNTSCNTSC3030720720 480480125125PALPAL2525720720 576576125125VCRVCR2525352352 2882883131HDTVHDTV303019201920 1080108010001000221.2 數據壓縮的

11、必要性數據壓縮的必要性表表1.1 數字化音、視頻格式數字化音、視頻格式數字音頻格式數字音頻格式頻帶范圍頻帶范圍（Hz）取樣頻率取樣頻率（kHz）樣本精度樣本精度（bit）聲道數聲道數原始碼率原始碼率（Kb/s）電話電話300340088164調幅（調幅（AM）廣播）廣播50700011.025161176.4調頻（調頻（FM）廣播）廣播201500022.03162705.6激光唱盤（激光唱盤（CD）202000044.11621411.2數字錄音帶（數字錄音帶（DAT）2020000481621536數字視頻格式數字視頻格式每秒幀數每秒幀數圖像分辨率圖像分辨率（像素）（像素）樣本精度樣本精度

12、（bit）亮度信號原始碼率亮度信號原始碼率（Mb/s）CIF格式的亮度信號格式的亮度信號30352 x 288824.33CCIR 601的亮度信號的亮度信號30/25720 x 576882.944HDTV亮度信號亮度信號601920 x 10808995.323數字音頻、視頻信號數據傳輸速率計算數字音頻、視頻信號數據傳輸速率計算 從傳輸角度：從傳輸角度： 數字電話數字電話 一路廣播級的彩色數字電視一路廣播級的彩色數字電視(若按若按4:2:2（亮度（亮度/色差色差/色差）色差）的分量編碼標準格式，用的分量編碼標準格式，用13.5/6.75/6.75 MHz頻率采樣，每頻率采樣，每像素（像素（

13、pixel: picture element, 簡寫為簡寫為pel）用）用8位編碼：位編碼： 8864 kb/s(kbps)I 亦寫作64等于等于3375路數字話路；路數字話路； Mb/s 2168)75. 675. 65 .13(I24從存儲角度：從存儲角度： 512512像素、像素、8bit/pel黑白圖像：黑白圖像： 512512像素、每分量像素、每分量8bit/pel的彩色圖像：的彩色圖像： 一幅一幅223022308bit的氣象衛(wèi)星紅外云圖的氣象衛(wèi)星紅外云圖37.94MB： kB 2568512512RkB 7683kB 256RMB 37.948MB 74. 4822302230R

14、數字音頻、視頻信號數據傳輸速率計算數字音頻、視頻信號數據傳輸速率計算 25 海洋地球物理勘探遙測數據海洋地球物理勘探遙測數據： 60路傳感器，每路信號按路傳感器，每路信號按1KHz頻率采樣、頻率采樣、16位位模模-數轉換器（數轉換器（A/D）量化而得，每）量化而得，每1km就需記錄就需記錄1盤盤0.5英寸的計算機磁帶，而僅僅一條測量船每英寸的計算機磁帶，而僅僅一條測量船每年可勘測年可勘測15000km 。 一顆衛(wèi)星每半個小時即可發(fā)回一次全波段數據（一顆衛(wèi)星每半個小時即可發(fā)回一次全波段數據（5個個波段），每天的數據率高達波段），每天的數據率高達1.1GB 數字音頻、視頻信號數據傳輸速率計算數字音

15、頻、視頻信號數據傳輸速率計算 261.2 數據壓縮的必要性數據壓縮的必要性u數據壓縮的目的數據壓縮的目的1. 在現有系統(tǒng)特性限制下，通過數據壓縮來滿足在現有系統(tǒng)特性限制下，通過數據壓縮來滿足工作要求。工作要求。2. 在新系統(tǒng)設計時，通過數據壓縮，節(jié)省成本。在新系統(tǒng)設計時，通過數據壓縮，節(jié)省成本。3. 在某些情況下，由于客觀條件限制，即使不惜在某些情況下，由于客觀條件限制，即使不惜成本也無法滿足設計要求，數據壓縮就是唯成本也無法滿足設計要求，數據壓縮就是唯一的途徑。一的途徑。27為什么可以壓縮？為什么可以壓縮？u自然界中的大多數數據都是冗余的：任何非隨機選擇自然界中的大多數數據都是冗余的：任何非

16、隨機選擇的數據都有一定結構，可利用這種結構得到數據的更的數據都有一定結構，可利用這種結構得到數據的更緊致表示緊致表示 統(tǒng)計冗余：大多數常見的壓縮算法都利用了該冗余統(tǒng)計冗余：大多數常見的壓縮算法都利用了該冗余 字母冗余：英文中字母字母冗余：英文中字母E最常出現，而最常出現，而Z很少出現很少出現 文本冗余：字母文本冗余：字母Q后常跟有字母后常跟有字母U 圖像冗余：自然圖像中相鄰像素的顏色往往比較相近圖像冗余：自然圖像中相鄰像素的顏色往往比較相近 數據的物理產生過程數據的物理產生過程 如利用人類的發(fā)聲系統(tǒng)，設計語音壓縮算法如利用人類的發(fā)聲系統(tǒng)，設計語音壓縮算法 可用在軍事、移動通信和玩具中的語音合成

17、中可用在軍事、移動通信和玩具中的語音合成中 數據的應用：感知冗余數據的應用：感知冗余 聽覺冗余：如聽覺冗余：如mp3音頻編碼音頻編碼 視覺冗余視覺冗余28例：空間冗余例：空間冗余u圖像中存在大面積部分相似或完全一樣的像素圖像中存在大面積部分相似或完全一樣的像素 水平相鄰像素的聯合直方圖水平相鄰像素的聯合直方圖pmf29例：時間冗余例：時間冗余u視頻圖像前后幾幀的內容變化不大（位置可能不視頻圖像前后幾幀的內容變化不大（位置可能不同，可用運動估計方法找到對應位置）同，可用運動估計方法找到對應位置）30例：結構冗余例：結構冗余u圖像中物體表面紋理等結構存在冗余圖像中物體表面紋理等結構存在冗余311.

18、2 數據壓縮的必要性數據壓縮的必要性u不進行數據壓縮，無論傳輸或存儲都很難實用化，不進行數據壓縮，無論傳輸或存儲都很難實用化，數據壓縮的好處就在于：數據壓縮的好處就在于：1. 較快地傳輸各種信源，降低信道占用的費用；較快地傳輸各種信源，降低信道占用的費用；（時間域上的壓縮）（時間域上的壓縮）2. 在有限帶寬上能開展更多的并行業(yè)務。在有限帶寬上能開展更多的并行業(yè)務。 （頻率域上的壓縮）（頻率域上的壓縮）3. 對移動設備而言，能夠降低發(fā)射功率。對移動設備而言，能夠降低發(fā)射功率。 （能量域上的壓縮）（能量域上的壓縮）4. 減少數據存儲的容量。（空間域上的壓縮）減少數據存儲的容量。（空間域上的壓縮）3

19、2第一章第一章 緒緒 論論1.1 什么是數據壓縮？什么是數據壓縮？1.2 數據壓縮的必要性數據壓縮的必要性1.3 數據壓縮技術的分類數據壓縮技術的分類1.4 數據壓縮技術的歷史發(fā)展數據壓縮技術的歷史發(fā)展33可逆壓縮可逆壓縮 (Lossless Compression) 冗余度壓縮：去除或減少那些可能是后來插入數據中的冗余冗余度壓縮：去除或減少那些可能是后來插入數據中的冗余度，是一個可逆過程。度，是一個可逆過程。香農（香農（C.E.ShannonC.E.Shannon）信息論：）信息論：數據數據= =信息信息+ +冗余度冗余度其他術語：無損壓縮、無失真、無差錯編碼（其他術語：無損壓縮、無失真、無

20、差錯編碼（Error Free Coding）、無噪聲（）、無噪聲（Noiseless）編碼、冗余度壓縮）編碼、冗余度壓縮(Redundancy Reduction)、熵編碼、熵編碼 (Entropy Coding)、數、數據緊縮據緊縮 (Data compaction)、信息保持編碼（、信息保持編碼（Lossless, Bit-preserving）。）。 34例例1-4 計算不同采樣值間重復采樣的數目計算不同采樣值間重復采樣的數目(游程游程)，然，然后將變化的采樣值與該重復數目一起發(fā)送。后將變化的采樣值與該重復數目一起發(fā)送。 Compression（壓縮）（壓縮） : 針對數據內部的多余信

21、息進行壓縮；針對數據內部的多余信息進行壓縮； 例例1-5 12位位A/D變換，通常采用變換，通常采用1字字(2Byte)來存一個采來存一個采樣值，這樣每個樣值就額外增加了樣值，這樣每個樣值就額外增加了4位冗余度，但是位冗余度，但是如果改用如果改用3個字（個字（48bit）來存）來存4個數據，可消除冗余度。個數據，可消除冗余度。Compaction（緊縮）（緊縮） : 針對數據外在冗余度進行壓縮。針對數據外在冗余度進行壓縮。 舉舉 例例35不可逆壓縮不可逆壓縮(Lossy Compression) 又稱又稱: : 有失真（有失真（Lossy）壓縮、熵壓縮（）壓縮、熵壓縮（Entropy Comp

22、ression）。）。 例例1-61-6 對采樣值設置門限，當采樣值超過該門限對采樣值設置門限，當采樣值超過該門限時才傳輸時才傳輸原始采樣值不可能恢復，信息丟失；原始采樣值不可能恢復，信息丟失；舉例：舉例：36 有失真壓縮（茶葉粉末無法恢復出茶葉）有失真壓縮（茶葉粉末無法恢復出茶葉）例例1-71-7 茶葉壓縮的例子茶葉壓縮的例子 ，直觀理解，直觀理解 冗余度壓縮冗余度壓縮無失真壓縮（茶葉保持完整）無失真壓縮（茶葉保持完整） 外在冗余度：空氣外在冗余度：空氣數據緊縮數據緊縮 內在冗余度：水份內在冗余度：水份冗余度壓縮冗余度壓縮 茶葉壓成粉末茶葉壓成粉末鐵罐可以裝得更多鐵罐可以裝得更多茶葉（茶葉（

23、“數據數據”）放入鐵罐（）放入鐵罐（“存儲器存儲器”）37一般結論一般結論 有冗余度就可以壓縮有冗余度就可以壓縮 壓縮只能在一定程度內可逆壓縮只能在一定程度內可逆 超過一定限度，必然帶來失真超過一定限度，必然帶來失真 允許的失真越大，壓縮的比例也可以越大允許的失真越大，壓縮的比例也可以越大381.3 數據壓縮技術分類數據壓縮技術分類u按照信息論基本概念進行分類按照信息論基本概念進行分類冗余度壓縮：僅對數據源中的冗余度進行壓縮，冗余度壓縮：僅對數據源中的冗余度進行壓縮，去除冗余信息，又稱無失真壓縮、無噪壓縮或去除冗余信息，又稱無失真壓縮、無噪壓縮或可逆壓縮?？赡鎵嚎s。熵壓縮：不僅對數據源中的冗余

24、信息進行壓縮，熵壓縮：不僅對數據源中的冗余信息進行壓縮，還要對數據源所含的信息本身進行壓縮，又稱還要對數據源所含的信息本身進行壓縮，又稱有失真壓縮、有損壓縮或不可逆壓縮。有失真壓縮、有損壓縮或不可逆壓縮。391.3 數據壓縮技術分類數據壓縮技術分類u按照壓縮所依據的信源輸出分布特性分按照壓縮所依據的信源輸出分布特性分類類統(tǒng)計編碼：根據信源輸出符號的統(tǒng)計特性進行統(tǒng)計編碼：根據信源輸出符號的統(tǒng)計特性進行編碼，以便最大限度去除壓縮數據之間的統(tǒng)計編碼，以便最大限度去除壓縮數據之間的統(tǒng)計相關性，實現壓縮目的。統(tǒng)計編碼屬于冗余度相關性，實現壓縮目的。統(tǒng)計編碼屬于冗余度壓縮，是經典的數據壓縮方法。壓縮，是經

25、典的數據壓縮方法。字典編碼：又稱為字典編碼：又稱為LZ編碼，是從信源輸出的數編碼，是從信源輸出的數據中選擇字符串，并把字符串編碼為一個標識據中選擇字符串，并把字符串編碼為一個標識加以保存，利用查字典的原理對字符串編碼，加以保存，利用查字典的原理對字符串編碼，實現壓縮的目的。實現壓縮的目的。401.3 數據壓縮技術分類數據壓縮技術分類u按照數據編碼所使用的編碼技術分類按照數據編碼所使用的編碼技術分類預測編碼、變換編碼、基于模型的編碼、基于預測編碼、變換編碼、基于模型的編碼、基于小波方法的編碼、分形編碼等。小波方法的編碼、分形編碼等。u按照被壓縮數據的頻率范圍分類按照被壓縮數據的頻率范圍分類音頻壓

26、縮：語音壓縮、聲頻壓縮音頻壓縮：語音壓縮、聲頻壓縮視頻壓縮視頻壓縮411.3 數據壓縮技術分類數據壓縮技術分類u按照被壓縮數據的屬性分類按照被壓縮數據的屬性分類語音壓縮、文本壓縮語音壓縮、文本壓縮 、圖形和圖像壓縮。、圖形和圖像壓縮。u按照壓縮算法的實現手段分類按照壓縮算法的實現手段分類硬件壓縮：通過硬件實現數據壓縮硬件壓縮：通過硬件實現數據壓縮軟件壓縮：通過軟件實現數據壓縮軟件壓縮：通過軟件實現數據壓縮421.3 數據壓縮技術分類數據壓縮技術分類u按照數據壓縮系統(tǒng)自適應能力分類按照數據壓縮系統(tǒng)自適應能力分類自適應數據壓縮：能夠隨著數據源的變化而自適應數據壓縮：能夠隨著數據源的變化而相應調整壓

27、縮編碼器的特性以適應數據變化。相應調整壓縮編碼器的特性以適應數據變化。非自適應數據壓縮：不能隨著數據源的變化非自適應數據壓縮：不能隨著數據源的變化而相應調整壓縮編碼器特性的壓縮方法。而相應調整壓縮編碼器特性的壓縮方法。431.3 數據壓縮技術分類數據壓縮技術分類u按照壓縮器和解壓器的復雜度分類按照壓縮器和解壓器的復雜度分類對稱壓縮：壓縮編碼器和解壓縮譯碼器的復對稱壓縮：壓縮編碼器和解壓縮譯碼器的復雜度及工作量相同或基本相同。（多媒體通雜度及工作量相同或基本相同。（多媒體通信系統(tǒng)中的數據壓縮多為對稱壓縮）信系統(tǒng)中的數據壓縮多為對稱壓縮）非對稱壓縮：壓縮編碼器和解壓縮譯碼器的非對稱壓縮：壓縮編碼器

28、和解壓縮譯碼器的復雜度及工作量不同。（多媒體錄放系統(tǒng)中復雜度及工作量不同。（多媒體錄放系統(tǒng)中的數據壓縮多為非對稱壓縮）的數據壓縮多為非對稱壓縮）441.3 數據壓縮技術分類數據壓縮技術分類u按照數據壓縮的應用領域分類按照數據壓縮的應用領域分類遙測數據壓縮、地震數據壓縮、醫(yī)學信息壓遙測數據壓縮、地震數據壓縮、醫(yī)學信息壓縮、報紙壓縮、數據庫壓縮等縮、報紙壓縮、數據庫壓縮等u按照數據壓縮使用的量化技術分類按照數據壓縮使用的量化技術分類標量量化數據壓縮標量量化數據壓縮矢量量化數據壓縮矢量量化數據壓縮45數數據據壓壓縮縮冗余度冗余度壓縮壓縮（熵編（熵編碼）碼）統(tǒng)計編碼統(tǒng)計編碼霍夫曼編碼、游程編碼、二進制

29、信源編碼等霍夫曼編碼、游程編碼、二進制信源編碼等算術編碼算術編碼基于字典的編碼：基于字典的編碼：LZWLZW編碼等編碼等其他編碼其他編碼完全可逆的小波分解完全可逆的小波分解+ +統(tǒng)計編碼等統(tǒng)計編碼等熵壓縮熵壓縮特征抽取特征抽取分析分析/ /綜合編碼綜合編碼子帶、小波、分形等子帶、小波、分形等量化量化其他其他無記憶量化無記憶量化均勻量化、壓擴量化均勻量化、壓擴量化有有記記憶憶量量化化序列序列量化量化預測預測 編碼編碼增量調制、線性增量調制、線性/ /非線非線性性/ /自適應預測等自適應預測等其他其他 方法方法序貫量化等序貫量化等分組分組量化量化直接直接 映射映射矢量量化、神經網等矢量量化、神經網

30、等變換變換編碼編碼正交變換正交變換 KLTKLT、DCTDCT等等非正交變換非正交變換其他函數變換其他函數變換表表1.2 1.2 數據壓縮技術的簡單分類數據壓縮技術的簡單分類46編碼實例：盲文編碼實例：盲文 u由路易由路易布萊爾（布萊爾（Louis Braille）發(fā)明：）發(fā)明：3 x 2凸印點陣凸印點陣u26個盲文字母個盲文字母u一些盲文字和字符串一些盲文字和字符串u例：例：“to others”47編碼實例：編碼實例：Morse碼碼u19世紀中葉，由世紀中葉，由 Samuel Morse發(fā)明發(fā)明 每個字符用每個字符用“ . ” 表示表示48編碼實例：編碼實例：Morse碼碼 (2)uMor

31、se碼與字母頻率碼與字母頻率：u基本原則：基本原則：用較短的碼字表示出現頻率高的字符，較長的碼字表示用較短的碼字表示出現頻率高的字符，較長的碼字表示出現頻率低的字符出現頻率低的字符 但也不是但也不是100% 滿足（如滿足（如l vs. m ）u這就是利用統(tǒng)計冗余編碼的基本思想這就是利用統(tǒng)計冗余編碼的基本思想49圖像壓縮實例圖像壓縮實例u圖象圖象 丟失高頻部分細節(jié)丟失高頻部分細節(jié) 50第一章第一章 緒緒 論論1.1 什么是數據壓縮？什么是數據壓縮？1.2 數據壓縮的必要性數據壓縮的必要性1.3 數據壓縮技術的分類數據壓縮技術的分類1.4 數據壓縮技術的歷史發(fā)展數據壓縮技術的歷史發(fā)展51n 早在早

32、在1949年年，貝爾實驗室的，貝爾實驗室的 Claude Shannon 和和 MIT 的的 R.M.Fano 幾乎同時提出了的對符號進行有效幾乎同時提出了的對符號進行有效編碼從而實現數據壓縮的編碼從而實現數據壓縮的 Shannon-Fano 編碼編碼方法方法 。Shannon-FanoShannon-Fano 編碼編碼大多數信息的表達都存在著一定的冗余度，通過采用一定大多數信息的表達都存在著一定的冗余度，通過采用一定的模型和編碼方法，可以降低這種冗余度。的模型和編碼方法，可以降低這種冗余度。1.4 數據壓縮技術的歷史發(fā)展數據壓縮技術的歷史發(fā)展52n 60 年代、年代、70 年代乃至年代乃至

33、80 年代的早期，數據壓縮領年代的早期，數據壓縮領域幾乎一直被域幾乎一直被 Huffman 編碼及其分支所壟斷。編碼及其分支所壟斷。 n UNIX 系統(tǒng)上一個壓縮程序系統(tǒng)上一個壓縮程序 COMPACT 就是就是 Huffman 0 階自適應編碼的具體實現。階自適應編碼的具體實現。80 年代初，年代初，Huffman 編碼編碼又在又在 DOS 系統(tǒng)中實現，其代表程序叫系統(tǒng)中實現，其代表程序叫 SQ。 n 1952年年D.A.Huffman 第一次發(fā)表了他的論文第一次發(fā)表了他的論文“最小冗余度代碼的構造方法最小冗余度代碼的構造方法”(A Method for the Construction of

34、 Minimum Redundancy Codes)。 Huffman Huffman 編碼編碼53n 80年代，數學家們從新的角度入手，遵循年代，數學家們從新的角度入手，遵循 Huffman 編碼的主導思想，設計出另一種更為精確，更能接近信編碼的主導思想，設計出另一種更為精確，更能接近信息論中息論中“熵熵”極限的編碼方法極限的編碼方法算術編碼。算術編碼。 算術編碼得到的壓縮效果可以最大地減小信息的冗余算術編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號精確表達原始信息內容。算術編度，用最少量的符號精確表達原始信息內容。算術編碼雖然可以得到最好的壓縮效果，但卻要消耗也許幾碼雖然可以

35、得到最好的壓縮效果，但卻要消耗也許幾十倍的計算時間。十倍的計算時間。 算術算術編碼編碼54能不能既在壓縮效果上超越能不能既在壓縮效果上超越 Huffman，又不增加，又不增加程序對系統(tǒng)資源和時間的需求呢？程序對系統(tǒng)資源和時間的需求呢？ n 1977年之前，數據壓縮的研究工作主要集中于熵、年之前，數據壓縮的研究工作主要集中于熵、字符和單詞頻率以及統(tǒng)計模型等方面，字符和單詞頻率以及統(tǒng)計模型等方面， n 1977年，以色列人年，以色列人 Jacob Ziv 和和 Abraham Lempel 發(fā)表了論文發(fā)表了論文“順序數據壓縮的一個通用算法順序數據壓縮的一個通用算法”(A Universal Alg

36、orithm for Sequential Data Compression)。字典式字典式編碼編碼55字典式編碼不但在壓縮效果上大大超過了字典式編碼不但在壓縮效果上大大超過了Huffman，而且，對于算法的實現，其壓縮和解壓縮的速度也異而且，對于算法的實現，其壓縮和解壓縮的速度也異常驚人。常驚人。 n 1978年，他們發(fā)表了該論文的續(xù)篇年，他們發(fā)表了該論文的續(xù)篇“通過可變通過可變比率編碼的獨立序列的壓縮比率編碼的獨立序列的壓縮”(Compression of Individual Sequences via Variable-Rate Coding)。在這兩篇論文中提出的兩個壓縮技術。在這兩

37、篇論文中提出的兩個壓縮技術被稱為被稱為 LZ77 和和 LZ78 ?；谶@一思路的編碼方?；谶@一思路的編碼方法被稱作法被稱作“字典字典”式編碼。式編碼。字典式字典式編碼編碼56n 1984年，年，Terry Welch 發(fā)表了名為發(fā)表了名為“高性能數據高性能數據壓縮技術壓縮技術”(A Technique for High-Performance Data Compression)的論文，實現了的論文，實現了 LZ78 算法的一算法的一個變種個變種LZW。LZW 繼承了繼承了 LZ77 和和 LZ78 壓縮壓縮效果好、速度快的優(yōu)點，而且在算法描述上更容易效果好、速度快的優(yōu)點，而且在算法描述上更

38、容易被人們接受，實現也比較簡單。被人們接受，實現也比較簡單。n 不久，不久，UNIX上出現了使用上出現了使用 LZW 算法的算法的 Compress 程序，很快成為了程序，很快成為了 UNIX 世界的壓縮程序世界的壓縮程序標準。緊隨其后的是標準。緊隨其后的是 MS-DOS環(huán)境下的環(huán)境下的ARC 程序，程序，還有象還有象 PKWare、PKARC 等仿制品。等仿制品。LZ78 和和 LZW 一時間統(tǒng)治了一時間統(tǒng)治了 UNIX 和和 DOS 兩大平臺。兩大平臺。字典式字典式編碼編碼57另外對于另外對于 GIF 格式，格式，GIF 格式格式可以把原始圖形文件可以把原始圖形文件以非常小數據量存儲，可以

39、在同一個文件中存儲多以非常小數據量存儲，可以在同一個文件中存儲多幅圖像從而實現動畫效果。知道幅圖像從而實現動畫效果。知道 GIF 中的圖像使用中的圖像使用什么方法壓縮的嗎？什么方法壓縮的嗎？LZW! GIF 精確地保留了原始圖像的每一個精確地保留了原始圖像的每一個像素信息，是無損圖像壓縮的代表。像素信息，是無損圖像壓縮的代表。當然，當然，GIF 文件中除了經過文件中除了經過 LZW 壓縮的像素信息以壓縮的像素信息以外，還保存有圖像的各種屬性信息以及圖像所使用外，還保存有圖像的各種屬性信息以及圖像所使用的調色板信息等。的調色板信息等。字典式字典式編碼編碼58n 80年代中期以后，人們對年代中期以

40、后，人們對 LZ77 進行了改進，隨進行了改進，隨之誕生了一批我們今天還在大量使用的壓縮程序。之誕生了一批我們今天還在大量使用的壓縮程序。 ARJ 是其中著名的例子。是其中著名的例子。LZ77 得以和得以和 LZ78、LZW 一起壟斷當今的通用數據壓縮領域。一起壟斷當今的通用數據壓縮領域。n 目前，基于字典方式的壓縮已經有了一個被廣泛目前，基于字典方式的壓縮已經有了一個被廣泛認可的標準，從古老的認可的標準，從古老的 PKZip 到現在的到現在的 WinZip，特，特別是隨著別是隨著 Internet 上文件傳輸的流行，上文件傳輸的流行，ZIP 格式成為格式成為了事實上的標準，沒有哪一種通用的文

41、件壓縮、歸檔了事實上的標準，沒有哪一種通用的文件壓縮、歸檔系統(tǒng)敢于不支持系統(tǒng)敢于不支持 ZIP 格式。格式。 字典式字典式編碼編碼59現在對聲音、圖像、視頻等多媒體信息的壓縮有兩條現在對聲音、圖像、視頻等多媒體信息的壓縮有兩條思路：思路： 要么采用成熟的通用數據壓縮技術進行壓縮；要么采用成熟的通用數據壓縮技術進行壓縮； 要么根據媒體信息的特性設計新的壓縮方法。要么根據媒體信息的特性設計新的壓縮方法。60根據媒體特性量身定制的壓縮方法中，根據媒體特性量身定制的壓縮方法中，游程編碼游程編碼(RLE: Run-Length Encoding)是最為簡單、最容易被想到的一是最為簡單、最容易被想到的一種

42、。大多數種。大多數計算機中產生的圖像計算機中產生的圖像(和現實世界的圖像例如和現實世界的圖像例如照片不同照片不同)都具有著大面積重復的顏色塊，完全可以用一都具有著大面積重復的顏色塊，完全可以用一個顏色值加一個重復次數來表示這一塊圖像，冗余度由個顏色值加一個重復次數來表示這一塊圖像，冗余度由此減小了，這就是此減小了，這就是 RLE 方法的基本思路。方法的基本思路。顯然，它不適于用來壓縮照片、聲音等很少連續(xù)重復信息顯然，它不適于用來壓縮照片、聲音等很少連續(xù)重復信息的數據。的數據。RLE RLE 方法最有代表性的實現有方法最有代表性的實現有 PCX PCX 和和 TargaTarga 圖圖形格式。形

43、格式。游程游程編碼編碼61只有黑白兩種顏色的只有黑白兩種顏色的二值圖像二值圖像以及只有以及只有 256 256 級灰度級灰度變化的圖像變化的圖像具有一些獨特的地方，可以被壓縮算法加具有一些獨特的地方，可以被壓縮算法加以利用。以利用。對于對于灰度圖像灰度圖像，除了著名的，除了著名的 JPEG JPEG 標準以外，一種叫標準以外，一種叫 FELICSFELICS 的算法可以實現效果非常好的無損壓縮。的算法可以實現效果非常好的無損壓縮。627070年代末年代末8080年代初年代初，人們逐漸意識到，對到多數灰度，人們逐漸意識到，對到多數灰度或是彩色圖像乃至聲音文件，沒有必要忠實地保留其或是彩色圖像乃至

44、聲音文件，沒有必要忠實地保留其所有信息，所有信息，在允許一定的精度損失的情況下，可以實在允許一定的精度損失的情況下，可以實現更為有效的壓縮方法?，F更為有效的壓縮方法。到到8080年代末年代末，許多人已經在這一領域取得了不小的，許多人已經在這一領域取得了不小的收獲，設計出了一批在壓縮效果上讓人驚訝不已的收獲，設計出了一批在壓縮效果上讓人驚訝不已的聲音和圖像壓縮算法。聲音和圖像壓縮算法。63在此基礎上，國際標準化組織在此基礎上，國際標準化組織(ISO)(ISO)和和CCITTCCITT聯合組成聯合組成了兩個委員會：了兩個委員會： 靜態(tài)圖像聯合專家小組靜態(tài)圖像聯合專家小組( JPEG )( JPEG

45、 ) JPEG JPEG 的壓縮目標是靜止圖像的壓縮目標是靜止圖像( (灰度的和彩色的灰度的和彩色的) )， 動態(tài)圖像聯合專家小組動態(tài)圖像聯合專家小組( MPEG ) ( MPEG ) MPEG MPEG 的目標則是聲音和視頻的目標則是聲音和視頻他們的基本思路是完全一樣的，即保留媒體信息中最有他們的基本思路是完全一樣的，即保留媒體信息中最有規(guī)律、最能體現信息主要特征的數據，而略去其他不重規(guī)律、最能體現信息主要特征的數據，而略去其他不重要的數據。要的數據。64主要數據壓縮標準和應用主要數據壓縮標準和應用 標準化組織標準化組織 國際標準化組織（國際標準化組織（International Organ

46、ization International Organization for Standardization, for Standardization, 簡稱簡稱ISO） 是目前世界上最大、最具權威性的國際標準化專 門機構。 國際電工委員會國際電工委員會(International ElectrotechnicalInternational Electrotechnical Commission Commission，簡稱，簡稱IECIEC） 是世界上最早的國際性電工標準化機構。65 國際電信聯盟的電子標準部國際電信聯盟的電子標準部(International International Te

47、lecommunication UnionTelecommunication Union，簡稱，簡稱ITUITU）是聯合國的一個專門機構，國際電信界最權威的標準修訂組織。1972年12月, 電信標準化部、無線電通信部和電信發(fā)展部承擔著ITU的實質性標準制訂工作。其中，電信標準化部門由原來的國際電報電話咨詢委員會（CCITT）和國際無線電咨詢委員會（CCIR）的標準化部門合并而成，其主要職責是實現國際電信聯盟有關電信標準化的目標，使全世界的電信標準化。66標準標準發(fā)發(fā) 布布日日 期期標標 題題應用場合應用場合H.2611990.12p 64 kbits/s的音視的音視頻業(yè)務的編譯碼頻業(yè)務的編譯碼

48、綜合業(yè)務數字網綜合業(yè)務數字網(ISDN)中的視頻中的視頻會議會議H.2631996.3低比特率的視頻壓低比特率的視頻壓縮編碼縮編碼桌面可視電話移桌面可視電話移動視頻通信等動視頻通信等H.263+1998.1H.263+2000.11H.264/AVC2003.5H.264/AVC視頻壓視頻壓縮標準縮標準有線電視、無線有線電視、無線視頻通信、分組視頻通信、分組網絡視頻傳輸、網絡視頻傳輸、IP視頻會議等視頻會議等H.264/AVC2004.7H.264補充擴展高補充擴展高保真壓縮保真壓縮JBIG1991.9二值圖像的漸進壓二值圖像的漸進壓縮編碼縮編碼傳真等傳真等67標準標準發(fā)布日期發(fā)布日期標標 題

49、題應用場合應用場合JPEG1992.10靜止圖像的靜止圖像的數字壓縮編碼數字壓縮編碼數字照相、數字照相、圖像圖像/視頻編輯視頻編輯JPEG20002000.12新一代靜止新一代靜止圖像編碼標準圖像編碼標準IP網、傳真、電子商網、傳真、電子商務、遙感圖像編碼務、遙感圖像編碼MPEG-11992.11面向數字存儲的運動面向數字存儲的運動圖像及伴音的編碼圖像及伴音的編碼光盤存儲、家用視頻、光盤存儲、家用視頻、視頻監(jiān)控視頻監(jiān)控MPEG-21994.11活動圖像及伴音活動圖像及伴音的通用編碼的通用編碼數字電視、數字電視、DVD、高、高清晰度電視、衛(wèi)星清晰度電視、衛(wèi)星電視、視頻點播等電視、視頻點播等MPEG-41995.5音視頻對象的音視頻對象的通用編碼通用編碼IP網、交互視頻、移網、交互視頻、移動通信、專業(yè)視頻、動通信、專業(yè)視頻、視頻會議等視頻會議等68ITU-GITU-G系列標準技術參數系列標準技術參數標標 準準算算 法法 類類 型型碼碼 率率(