【正文】 第四章 多媒體數(shù)據(jù)壓縮編碼技術(shù) 計(jì)算機(jī)系 李知菲 本章要點(diǎn) ? 多媒體數(shù)據(jù)壓縮編碼的重要性及分類 ? 常用壓縮編碼的基本原理及實(shí)現(xiàn)技術(shù)，預(yù)測(cè)編碼，變換編碼（ KL變換， DCT變換），統(tǒng)計(jì)編碼（ Huffman編碼，算術(shù)編碼）。 ? 量化的基本原理及量化器的設(shè)計(jì)思想 ? 靜態(tài)圖像壓縮編碼的國(guó)際標(biāo)準(zhǔn) （ JPEG） 原理 ， 實(shí)現(xiàn)技術(shù) ， 以及動(dòng)態(tài)圖像壓縮編碼國(guó)際標(biāo)準(zhǔn) （ MPEG） 的基本原理 。 進(jìn)入信息時(shí)代，人們將越來(lái)越依靠計(jì)算機(jī)獲取和利用信息，而數(shù)字化后的視頻和音頻等媒體信息具有數(shù)據(jù)海量性，與當(dāng)前硬件技術(shù)所提供的計(jì)算機(jī)存儲(chǔ)資源和網(wǎng)絡(luò)帶寬之間具有很大的差距性。這樣，就對(duì)多媒體信息的存儲(chǔ)和傳輸造成很大的困難。成為阻礙人們有效獲取和利用信息的障礙。一段時(shí)間內(nèi)，數(shù)字化的媒體信息數(shù)據(jù)的壓縮形式存儲(chǔ)和傳輸仍然是唯一的選擇。 4． 1 多媒體數(shù)據(jù)壓縮編碼的重要性和分類 ? 多媒體數(shù)據(jù)壓縮編碼的重要性 信息時(shí)代的重要特征是信息的數(shù)字化，數(shù)字化的信息帶來(lái)了 “信息爆炸 ”。多媒體計(jì)算機(jī)系統(tǒng)技術(shù)是面向三維圖形，立體聲和彩色全屏幕運(yùn)動(dòng)畫(huà)面的處理技術(shù)。數(shù)字計(jì)算機(jī)面臨的是數(shù)值，文字，語(yǔ)言，音樂(lè)，圖形，動(dòng)畫(huà)，靜圖像，電視視頻圖像等多種媒體承載的用模擬量轉(zhuǎn)化成數(shù)字量信息的吞吐，存儲(chǔ)和傳輸?shù)膯?wèn)題。數(shù)字化了的視頻和音頻信號(hào)數(shù)據(jù)量之大是非常驚人的，下面列舉兩例未經(jīng)壓縮的數(shù)字化信息的例子： ? 一頁(yè)印在 B5（約 18*25。 5cm）紙上的文件，若以中等分辨率（ 300d/I約 12像素點(diǎn) /mm）的掃描儀進(jìn)行采樣，其數(shù)據(jù)量約 6。 61MB/頁(yè)。一片650MB的 CDROM可存 98頁(yè)。 ? 一個(gè)陸地衛(wèi)星（ Land Sat3）的例子（其水平。垂直分辨率分別為 2340和 3240， 4波段，采樣精度 7位），它的一幅圖像的數(shù)據(jù)量為2340*3240*7*4=212M，按每天 30幅計(jì)，每天數(shù)據(jù)量為 212*30=6。 36GB，每年的數(shù)據(jù)量高達(dá)2300GB。 從以上列舉的數(shù)據(jù)例子，可以看出數(shù)字化信息的數(shù)據(jù)量是何等龐大，這樣大的數(shù)據(jù)量，無(wú)疑給存儲(chǔ)器的存儲(chǔ)容量，通信干線的信道傳輸率以及計(jì)算機(jī)的速度都增加了極大的壓力。 彩色視頻數(shù)據(jù)量分析 ? 對(duì)于電視畫(huà)面的分辨率 640*480的彩色圖像，每秒 30幀，則一秒鐘的數(shù)據(jù)量為： 640*480*24*30= ? 播放時(shí)，需要 221Mbps的通信回路。 彩色視頻數(shù)據(jù)量分析 ? 實(shí)時(shí)傳輸： 在 10M帶寬網(wǎng)上實(shí)時(shí)傳輸?shù)脑?，需要壓縮到原來(lái)數(shù)據(jù)量的 ， 即 。 ? 存儲(chǔ)： （按 1張光盤(pán)可存 640M計(jì)算） 如果不進(jìn)行壓縮， 1張 CD則僅可以存放 據(jù)。存 2小時(shí)的信息則需要壓縮到原來(lái)數(shù)據(jù)量的，即： 。 傳真數(shù)據(jù)量分析 ? 如果只傳送 2值圖像，以 200dpi的分辨率傳輸，一張 A4稿紙的數(shù)據(jù)量為： 1654*2337*1=3888768bit =390K ? 按目前 ，需要傳送的時(shí)間是： 270秒（ ） 這個(gè)問(wèn)題是多媒體技術(shù)發(fā)展中的一個(gè)非常棘手的瓶頸問(wèn)題。解決這一問(wèn)題，數(shù)據(jù)壓縮是行之有效的方法。通過(guò)數(shù)據(jù)壓縮手段把信息數(shù)據(jù)壓下來(lái)，以壓縮形式存儲(chǔ)和傳輸，即緊縮了存儲(chǔ)空間，又提高了通信干線的傳輸效率，同時(shí)也使計(jì)算機(jī)實(shí)時(shí)處理音頻，視頻信息，以保證播放出高質(zhì)量的視頻，音頻節(jié)目成為可能。 ?數(shù)據(jù)壓縮技術(shù)經(jīng)歷了漫長(zhǎng)的 50余年的發(fā)展過(guò)程。 ?早在 1948 年 ， Oliver提出了 PCM編碼理論（ PCM編碼全名是 Pulse Code Modulation “脈沖碼調(diào)制”編碼）。該編碼理論的提出，標(biāo)志著數(shù)據(jù)壓縮技術(shù)的誕生。 ? 1948年香農(nóng)（ Shannon）在他的經(jīng)典論文“通信的數(shù)學(xué)原理”中首次提出并建立了信息率失真函數(shù)概念，1959年他又進(jìn)一步確立了碼率失真理論，從而奠定了信息編碼的理論基礎(chǔ) (第一代 ) 。此后，圖像壓縮編碼理論和方法都有很大發(fā)展。 數(shù)據(jù)壓縮技術(shù)的歷史及理論基礎(chǔ) ?主要的編碼方法有預(yù)測(cè)編碼、變換編碼和統(tǒng)計(jì)編碼，也稱為三大經(jīng)典編碼方法。 ? ： 1952 年第一次發(fā)表了 (A Method for the Construction of Minimum Redundancy Codes)論文。從此，數(shù)據(jù)壓縮在商業(yè)程序中實(shí)現(xiàn)并被應(yīng)用在許多技術(shù)領(lǐng)域。 ?UNIX 系統(tǒng)上一個(gè)壓縮程序 COMPACT 就是 采用的Huffman 0 階自適應(yīng)編碼。 ? 80 年代初， Huffman 編碼又在 CP/M 和 DOS 系統(tǒng)中實(shí)現(xiàn)，其代表程序叫 SQ。在數(shù)據(jù)壓縮領(lǐng)域， Huffman 的這一論文事實(shí)上開(kāi)創(chuàng)了數(shù)據(jù)壓縮技術(shù)新紀(jì)元。 ? 60 年代、 70 年代乃至 80 年代的早期，數(shù)據(jù)壓縮領(lǐng)域幾乎一直被 Huffman 編碼及其分支所壟斷。如果不是后面將要提到的那兩個(gè)以色列人，也許我們今天還要在 Huffman 編碼的 0 和 1 的組合中流連忘返。 ? 80 年代，數(shù)學(xué)家們不滿足于 Huffman 編碼中的某些致命弱點(diǎn)，他們從新的角度入手，遵循 Huffman 編碼的主導(dǎo)思想，設(shè)計(jì)出另一種更為精確，更能接近信息論中“熵”極限的編碼方法 ——算術(shù)編碼?？梢宰C明，算術(shù)編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號(hào)精確表達(dá)原始信息內(nèi)容。當(dāng)然，在同樣的計(jì)算機(jī)系統(tǒng)上，算術(shù)編碼雖然可以得到最好的壓縮效果，但卻要消耗也許幾十倍的計(jì)算時(shí)間。所以算術(shù)編碼沒(méi)有使用的軟件。 ? 1984 年， Terry Welch 發(fā)表了名為“高性能數(shù)據(jù)壓縮技術(shù)” (A Technique for HighPerformance Data Compression)的論文，描述了他在 Sperry Research Center(現(xiàn)在是 Unisys 的一部分 )的研究成果。他實(shí)現(xiàn)了 LZ78 算法的一個(gè)變種 —— LZW。 LZW 繼承了 LZ77 和 LZ78 壓縮效果好、速度快的優(yōu)點(diǎn)，而且在算法描述上更容易被人們接受 ,實(shí)現(xiàn)也比較簡(jiǎn)單。 ? “第一代”圖像編碼技術(shù)是指以信息論和數(shù)字信號(hào)處理技術(shù)為理論基礎(chǔ)， 旨在去除圖像數(shù)據(jù)中的線性相關(guān)性的一類編碼技術(shù)。這類技術(shù)去除客觀和視覺(jué)冗余信息的能力已接近極限，其壓縮比不高，大約在 10:1左右。 ? 80 年代中期以后，人們對(duì) LZ77 進(jìn)行了改進(jìn)，隨之誕生了一批我們今天還在大量使用的壓縮程序。Haruyasu Yoshizaki(Yoshi) 的 LHarc 和 Robert Jung 的 ARJ 是其中兩個(gè)著名的例子。 LZ77 得以和 LZ7 LZW 一起壟斷當(dāng)今的通用數(shù)據(jù)壓縮領(lǐng)域。 ? 目前，基于字典方式的壓縮已經(jīng)有了一個(gè)被廣泛認(rèn)可的標(biāo)準(zhǔn)，從古老的 PKZip 到現(xiàn)在的 WinZip，特別是隨著 Inter 上文件傳輸?shù)牧餍校?ZIP 格式成為了事實(shí)上的標(biāo)準(zhǔn)，沒(méi)有哪一種通用的文件壓縮、歸檔系統(tǒng)敢于不支持 ZIP 格式。 ? 70 年代末 80 年代初，人們逐漸意識(shí)到，對(duì)多數(shù)灰度或是彩色圖像乃至聲音文件，沒(méi)有必要忠實(shí)地保留其所有信息， 在允許一定的精度損失的情況下，可以實(shí)現(xiàn)更為有效的壓縮方法。 到 80 年代末，設(shè)計(jì)出了一批在壓縮效果上讓人驚訝不已的聲音和圖像壓縮算法。 ? 第二代”圖像編碼技術(shù) 是 Kunt等人于 1985年提出的。 “第二代”并不局限于信息論的框架， 要求充分利用人的視覺(jué)、生理、心理和圖像信源的各種特征，能獲得高壓縮比的一類編碼技術(shù) ，其壓縮比多在 30∶ 1～ 70∶ 1之間，有的甚至高達(dá)100∶ 1。第二代編碼技術(shù)代表性的方法有子帶圖像編碼等。 ? “第三代”編碼技術(shù)是指標(biāo)準(zhǔn)化的編碼壓縮技術(shù)在此基礎(chǔ)上，國(guó)際標(biāo)準(zhǔn)化組織 ( ISO )和 CCITT 聯(lián)合組成了兩個(gè)委員會(huì)：靜態(tài)圖像聯(lián)合專家小組( JPEG )和動(dòng)態(tài)圖像聯(lián)合專家小組 ( MPEG )。JPEG 的壓縮目標(biāo)是靜止圖像（灰度的和彩色的）， MPEG 的目標(biāo)則是聲音和視頻。但他們的基本思路是完全一樣的，即保留媒體信息中最有規(guī)律、最能體現(xiàn)信息主要特征的數(shù)據(jù)，而略去其他不重要的數(shù)據(jù)。 ? 對(duì)聲音、圖像、視頻等多媒體信息的壓縮有兩條思路，要么采用成熟的通用數(shù)據(jù)壓縮技術(shù)進(jìn)行壓縮，要么根據(jù)媒體信息的特性設(shè)計(jì)新的壓縮方法。 ? GIF 壓縮比非常高，可以在同一個(gè)文件中存儲(chǔ)多幅圖像從而實(shí)現(xiàn)動(dòng)畫(huà)效果。知 GIF 中的圖像使用的是LZW! 。 GIF 大概是使用通用壓縮技術(shù)壓縮圖像信息的最成功的例子，當(dāng)然， GIF 文件中除了經(jīng)過(guò) LZW 壓縮的像素信息以外，還保存有圖像的各種屬性信息以及圖像所使用的調(diào)色板信息等。 GIF 精確地保留了原始圖像的每一個(gè)像素信息，是無(wú)損圖像壓縮的代表。 壓縮編碼的 理論基礎(chǔ) 是信息論 。信息論的主要奠基人香農(nóng) (C． E． Shannon)曾在他的論文中給出了信息的度量的公式，他把信息定義為熵的減少。 從信息論的角度來(lái)看，壓縮就是去掉信息中的冗余，即保留不確定的信息，去除確定的信息（可推知的），也就是用一種更接近信息本質(zhì)的描述來(lái)代替原有冗余的描述。所以，將香農(nóng)的信息論觀點(diǎn)運(yùn)用到圖像信息的壓縮，所要解決的問(wèn)題就是如何將圖像信息壓縮到最小，但仍攜有足夠信息以保證能復(fù)制出與原圖近似的圖像。 信息量和熵 壓縮編碼的理論基礎(chǔ)是 信息論。 從信息論的角度看 ,壓縮就是去掉信息中的冗余 ,即保留不確定的信息 ,去除確定的信息 (可推知的 ),也就是 用一種更接近信息本質(zhì)的描述來(lái)代替原有冗余的描述 。這個(gè)本質(zhì)的東西就是 信息量 (即不確定因素 )。 （ 1）信息量 信息量的大小和消息有一定的關(guān)系、在數(shù)學(xué)上，消息是其出現(xiàn)概率的單調(diào)下降函數(shù)。信息量越大．消息的可能性越小，反之亦然 . 信息量是指： 為了從 N個(gè)相等的可能事件中挑選出一個(gè)事件所需的信息度量和含量，所提問(wèn)“是或否”的次數(shù) .也就是說(shuō)，在 N個(gè)事件中辨識(shí)特定的一個(gè)事件要詢間“是或否”多少次． ? 例如 要從 256個(gè)數(shù)中選定某一個(gè)數(shù) 可以先提問(wèn) “ 是否大于 128？ ’ ， 不論回答是與否 ， 則半數(shù)的可能事件被取消 。 如果繼續(xù)詢問(wèn)下去 ， 每次詢問(wèn)將對(duì)應(yīng)一個(gè) lbit的信息量 。 隨著每次詢問(wèn) ， 都將有半數(shù)的可能事件被取消 ， 這個(gè)過(guò)程由下列公式表示： log2256＝ 8bit ? 從公式看出，對(duì)于 256個(gè)數(shù)的詢問(wèn)只要進(jìn)行 8次，即可確定一個(gè)具體的數(shù)。設(shè)從 N個(gè)數(shù)中選定任意一個(gè)數(shù) x的概率為產(chǎn) p（ x）．假定選定任意一個(gè)數(shù)的概率都相等，即 p（ x） =1/N，則信息量為： )]([)(/1)( logloglog 222 xpIxpNNxI ?????? （ 2） 熵的概念 ? 數(shù)據(jù)壓縮不僅起源于 40 年代由 Claude Shannon 首創(chuàng)的信息論，而且其基本原理即信息究竟能被壓縮到多小，至今依然遵循信息論中的一條定理，這條定理借用了 熱力學(xué)中的名詞“熵” ( Entropy )來(lái)表示一條信息中真正需要編碼的信息量。 En = log2( Pn ) （ 2） 熵的概念 ? 信息（熵）、熱力學(xué)熵和復(fù)雜程度是互相成正比例