數(shù)字媒體技術(shù)專業(yè)之“數(shù)據(jù)壓縮”課程建設(shè)

付　慧　黃心淵

文章編號(hào)：1672-5913(2009)06-0071-03

摘要：隨著數(shù)字媒體技術(shù)的不斷發(fā)展，數(shù)據(jù)壓縮技術(shù)在多媒體領(lǐng)域發(fā)揮著越來越重要的作用。針對(duì)目前很多數(shù)據(jù)壓縮的教材是針對(duì)計(jì)算機(jī)專業(yè)和信息專業(yè)所編著的，在數(shù)字媒體技術(shù)專業(yè)講授這門課程時(shí)需要進(jìn)行適當(dāng)調(diào)整和更新。現(xiàn)將我所在學(xué)校的數(shù)字媒體專業(yè)講授數(shù)據(jù)壓縮這門課程的大綱、授課重點(diǎn)內(nèi)容和實(shí)驗(yàn)設(shè)計(jì)介紹如下，希望能夠有助于該門課程的建設(shè)。

關(guān)鍵詞: 數(shù)據(jù)壓縮；課程大綱；實(shí)驗(yàn)設(shè)計(jì)

中圖分類號(hào)：G642

文獻(xiàn)標(biāo)識(shí)碼：B

1數(shù)據(jù)壓縮課程大綱

我們?cè)谠O(shè)定大綱時(shí)考慮到要結(jié)合本科生強(qiáng)調(diào)基礎(chǔ)理論知識(shí)的特點(diǎn)選擇了小部分學(xué)時(shí)用于介紹數(shù)據(jù)壓縮的基礎(chǔ)理論，這部分要涉及信息論中的一些內(nèi)容。數(shù)據(jù)壓縮算法的介紹占據(jù)主要的學(xué)時(shí)，我們選擇從單純的數(shù)據(jù)領(lǐng)域和多媒體(以圖像為例)領(lǐng)域兩個(gè)方面來介紹壓縮算法。分別選取有代表意義的經(jīng)典的算法進(jìn)行介紹，同時(shí)輔助以實(shí)驗(yàn)進(jìn)行鞏固和練習(xí)。最后的學(xué)時(shí)用于介紹國(guó)際上和我國(guó)的各種數(shù)據(jù)壓縮標(biāo)準(zhǔn)，以及數(shù)據(jù)壓縮方法在視音頻領(lǐng)域的應(yīng)用。

我校數(shù)字媒體專業(yè)的數(shù)據(jù)壓縮課程目前作為選修課，40學(xué)時(shí)，講授20學(xué)時(shí)，實(shí)驗(yàn)20學(xué)時(shí)。相對(duì)于別的專業(yè)的數(shù)據(jù)壓縮課程，學(xué)時(shí)數(shù)不多。但是在有限的學(xué)時(shí)內(nèi)我們要盡量將該講的知識(shí)傳授給學(xué)生，因此我們?cè)O(shè)計(jì)了上述范圍的內(nèi)容。對(duì)于學(xué)時(shí)更充分的學(xué)校來說，以上的每個(gè)部分都可以進(jìn)行內(nèi)容擴(kuò)展，便于進(jìn)行更深入的講授?，F(xiàn)將課程大綱介紹如下：

第一部分：數(shù)據(jù)壓縮基礎(chǔ)理論

第一章數(shù)據(jù)壓縮概述(2學(xué)時(shí))

1.1為什么需要數(shù)據(jù)壓縮

1.2早期的數(shù)據(jù)壓縮思想

1.3數(shù)據(jù)壓縮的原理及實(shí)現(xiàn)

1.4數(shù)據(jù)壓縮的發(fā)展歷史

第二章數(shù)據(jù)壓縮基本概念(2學(xué)時(shí))

2.1熵與信息量

2.2模型和編碼

2.3多媒體信息的壓縮

2.4有損壓縮

2.5無損壓縮

第二部分：數(shù)據(jù)壓縮算法介紹

第三章統(tǒng)計(jì)壓縮方法(4學(xué)時(shí))

3.1Shannon-Fano編碼方法

3.2Huffman編碼方法

3.3算術(shù)編碼方法

第四章字典壓縮方法(4學(xué)時(shí))

4.1符號(hào)串的壓縮

4.2什么是字典壓縮方法

4.3LZ77算法

4.4LZ78算法

4.5LZW算法

第五章多媒體數(shù)據(jù)壓縮之圖像數(shù)據(jù)的壓縮(4學(xué)時(shí))

5.1彩色數(shù)字圖像基礎(chǔ)

5.2圖像文件壓縮格式

5.3GIF壓縮編碼

5.4JPEG壓縮編碼

第三部分：國(guó)際和國(guó)內(nèi)的數(shù)據(jù)壓縮標(biāo)準(zhǔn)和數(shù)據(jù)壓縮在視音頻領(lǐng)域的應(yīng)用

第六章視音頻數(shù)據(jù)壓縮及國(guó)際國(guó)內(nèi)壓縮標(biāo)準(zhǔn)(4學(xué)時(shí))

6.1視音頻壓縮的必要性

6.2視頻壓縮的國(guó)際標(biāo)準(zhǔn)

6.3視頻壓縮技術(shù)

6.4音頻壓縮的國(guó)際標(biāo)準(zhǔn)

6.5音頻壓縮技術(shù)

6.6我國(guó)視音頻壓縮標(biāo)準(zhǔn)——AVS(Audio Video Coding Standard)介紹

2數(shù)據(jù)壓縮課程重點(diǎn)內(nèi)容介紹

在選擇教材時(shí)，我選擇了國(guó)外作者David Salomon所著的Data Compression第三版，該書較為全面地介紹了數(shù)據(jù)壓縮的知識(shí)，包括大量的數(shù)據(jù)壓縮算法和實(shí)例。該書中除了介紹上述的大綱中的部分內(nèi)容，還詳細(xì)介紹了數(shù)據(jù)壓縮中的小波方法，視頻壓縮方法以及數(shù)據(jù)壓縮中用到的實(shí)用算法。但是由于這本著作的介紹較為詳盡，而我們授課學(xué)時(shí)有限，因此有很多內(nèi)容只能放棄。但是我把這門書的電子版提供給學(xué)生們，指導(dǎo)他們?cè)谡n下如果感興趣的話可以自行閱讀。

針對(duì)第一部分，我們的重點(diǎn)放在介紹數(shù)據(jù)壓縮基礎(chǔ)理論的基本概念上。包括信息量、熵、模型和編碼等概念。由于熵的概念較為抽象，因此我們首先需要介紹信息量的概念。將信息量解釋為“量化了的信息，是對(duì)數(shù)據(jù)中包含信息內(nèi)容的觀察，它等于在這條數(shù)據(jù)中令你吃驚的數(shù)目?！边@樣就將抽象的概念具體化了。而熵的概念就是度量信息量的一種方法。熵定義為“一條數(shù)據(jù)中有多少信息進(jìn)行編碼的度量”，即消息的熵越高則包含的信息量越多，也即消息中令人吃驚的信息數(shù)目越多。因?yàn)橄⒅行畔⒘坎煌耆韧谙⒈旧?，因此可知消息?shù)據(jù)中存在冗余，而這些數(shù)據(jù)中的冗余信息與數(shù)據(jù)所表達(dá)的信息量無關(guān)，可以去除，因此數(shù)據(jù)壓縮才進(jìn)入信息領(lǐng)域。數(shù)據(jù)壓縮的實(shí)現(xiàn)由兩部分組成，即“數(shù)據(jù)壓縮=模型+編碼”。因此要設(shè)計(jì)一個(gè)數(shù)據(jù)壓縮算法都會(huì)涉及到這兩方面的內(nèi)容。清楚了這些基本概念后，就可以針對(duì)各個(gè)具體的數(shù)據(jù)壓縮算法進(jìn)行介紹了。

針對(duì)第二部分，重點(diǎn)在于對(duì)壓縮算法的理解和實(shí)現(xiàn)。統(tǒng)計(jì)壓縮方法、字典壓縮方法和多媒體壓縮方法的原理和實(shí)現(xiàn)是這部分的重點(diǎn)內(nèi)容。介紹每個(gè)算法時(shí)都要包括以下幾個(gè)方面：

① 基本思想：介紹算法實(shí)現(xiàn)的基本思想，從總體上先了解算法。

② 數(shù)據(jù)結(jié)構(gòu)：算法的具體實(shí)現(xiàn)中會(huì)涉及到的一些固定的數(shù)據(jù)結(jié)構(gòu)的介紹。

③ 算法實(shí)例：以一個(gè)具體的實(shí)例來具體說明算法的實(shí)現(xiàn)。

④ 算法描述：以流程圖或步驟總結(jié)的形式表述算法的實(shí)現(xiàn)過程。

⑤ 算法實(shí)現(xiàn)：介紹算法在實(shí)現(xiàn)過程中的關(guān)鍵步驟和問題，同時(shí)以程序的形式來描述算法。

⑥ 算法中的問題：強(qiáng)調(diào)在算法實(shí)現(xiàn)中容易出錯(cuò)的問題，找出算法中可以改進(jìn)的地方和改進(jìn)方法。

將上述每個(gè)方面都講清楚了，算法就會(huì)非常容易理解。同時(shí)還要可以對(duì)同類算法之間進(jìn)行一些比較，以便于同學(xué)們記憶和區(qū)分不同的算法。在逐個(gè)介紹這些算法的過程中，介紹算法中問題主要目的是要啟發(fā)式的引導(dǎo)同學(xué)們思考如何改進(jìn)這些已有的壓縮算法。

例如在講到字典壓縮的LZ77算法時(shí)，算法要求輸出的必須都是三元組(偏移量，長(zhǎng)度，下一個(gè)字符)。對(duì)于沒有匹配上的字符仍然要輸出一個(gè)三元組(0,0,字符)，這樣本來一個(gè)字符所需的存儲(chǔ)空間就要用一個(gè)三元組來代替，這個(gè)字符壓縮后反而變長(zhǎng)了，那么如何解決這個(gè)問題呢？這實(shí)際上是數(shù)據(jù)壓縮在實(shí)現(xiàn)中的編碼問題。匹配不上的字符如何改進(jìn)其編碼，使其不出現(xiàn)上述問題。一種解決方法是：將匹配串和不能匹配的單個(gè)字符分別編碼、分別輸出，輸出匹配串時(shí)不同時(shí)輸出后續(xù)字符。這種輸出方式的優(yōu)點(diǎn)是輸出單個(gè)字符的時(shí)候比較節(jié)省空間。另外，因?yàn)椴粡?qiáng)求每次都外帶一個(gè)后續(xù)字符，可以適應(yīng)一些較長(zhǎng)匹配的情況。通過將這種改進(jìn)算法的思想教授給學(xué)生，可以引導(dǎo)他們?cè)趯W(xué)習(xí)壓縮算法時(shí)多注意思考，能夠舉一反三的對(duì)算法進(jìn)行修改和設(shè)計(jì)。

針對(duì)第三部分，重點(diǎn)在于了解目前已有的視音頻國(guó)際國(guó)內(nèi)標(biāo)準(zhǔn)，同時(shí)概括了解一下當(dāng)前的熱點(diǎn)視音頻技術(shù)。

介紹視音頻標(biāo)準(zhǔn)時(shí)重點(diǎn)介紹一下我國(guó)的AVS (Audio Video Coding Standard)標(biāo)準(zhǔn)。AVS是我國(guó)具備自主知識(shí)產(chǎn)權(quán)的第二代信源編碼標(biāo)準(zhǔn)。AVS標(biāo)準(zhǔn)是《信息技術(shù) 先進(jìn)音視頻編碼》系列標(biāo)準(zhǔn)的簡(jiǎn)稱，AVS標(biāo)準(zhǔn)包括系統(tǒng)、視頻、音頻、數(shù)字版權(quán)管理等四個(gè)主要技術(shù)標(biāo)準(zhǔn)和一致性測(cè)試等支撐標(biāo)準(zhǔn)。

AVS最直接的產(chǎn)業(yè)化成果是未來10年我國(guó)需要的3～5億顆解碼芯片，最直接效益是節(jié)省超過10億美元的專利費(fèi)。在多媒體領(lǐng)域開創(chuàng)新的數(shù)據(jù)壓縮標(biāo)準(zhǔn)和方法無疑有著巨大的前景和效益。數(shù)字媒體專業(yè)的學(xué)生需要了解社會(huì)和技術(shù)發(fā)展對(duì)多媒體數(shù)據(jù)壓縮技術(shù)的巨大需求，可以以此作為將來工作的一個(gè)領(lǐng)域。

3數(shù)據(jù)壓縮課程的實(shí)驗(yàn)設(shè)計(jì)

課程算法的介紹是從易到難，實(shí)驗(yàn)的完成也是循序漸進(jìn)的。每次實(shí)驗(yàn)同學(xué)們能夠鞏固學(xué)習(xí)到的算法，同時(shí)還可以為下一個(gè)算法的設(shè)計(jì)打好基礎(chǔ)。針對(duì)我們講授的算法和實(shí)驗(yàn)學(xué)時(shí)數(shù)，我們共設(shè)計(jì)了4個(gè)實(shí)驗(yàn)，實(shí)驗(yàn)軟件采用VC++或Java。

實(shí)驗(yàn)一：建立統(tǒng)計(jì)壓縮方法理論模型

實(shí)驗(yàn)內(nèi)容：采用C/C++/Java編寫程序，根據(jù)Shannon-Fano編碼及Huffman編碼方法的原理，實(shí)現(xiàn)建立Shannon-Fano樹或建立Huffman樹。并自定義簡(jiǎn)單輸入數(shù)據(jù)，檢驗(yàn)結(jié)果。

實(shí)驗(yàn)要求：

模型分別采用：

① 靜態(tài)的概率表

② 對(duì)每個(gè)輸入流建立概率表

輸入：鍵盤輸入的任意字符流。

輸出：每個(gè)字符的編碼，整個(gè)串的壓縮編碼，計(jì)算壓縮比(輸出流的大小/輸入流的大小)。

實(shí)驗(yàn)?zāi)康模和ㄟ^逐步實(shí)現(xiàn)算法，深入理解利用統(tǒng)計(jì)的方法進(jìn)行數(shù)據(jù)壓縮的原理。實(shí)驗(yàn)要求采用兩種不同的模型方法，目的是使同學(xué)們體會(huì)選取的模型不同會(huì)對(duì)數(shù)據(jù)壓縮算法產(chǎn)生不同的影響。

實(shí)驗(yàn)二：統(tǒng)計(jì)壓縮方法的具體實(shí)現(xiàn)

實(shí)驗(yàn)內(nèi)容：在實(shí)驗(yàn)一中完成的統(tǒng)計(jì)數(shù)據(jù)壓縮方法理論模型的基礎(chǔ)上實(shí)現(xiàn)對(duì)數(shù)據(jù)文件的壓縮和解壓縮。

實(shí)驗(yàn)要求：

輸入：字符串文件

功能1：將文件中的字符串進(jìn)行Shannon-Fano編碼或Huffman編碼。

輸出：字符的編碼結(jié)果，并將字符串的編碼結(jié)果寫成2進(jìn)制文件保存。

功能2：將2進(jìn)制文件讀入，進(jìn)行解碼。

輸出：解碼后的結(jié)果。

實(shí)驗(yàn)?zāi)康模?/p>

本實(shí)驗(yàn)要求輸入和輸出均為實(shí)際應(yīng)用中的數(shù)據(jù)文件，使得數(shù)據(jù)壓縮算法成為真正能用的工具。本實(shí)驗(yàn)通過解決壓縮算法在實(shí)際應(yīng)用出現(xiàn)的一系列問題真正實(shí)現(xiàn)數(shù)據(jù)壓縮算法從理論到實(shí)踐的轉(zhuǎn)換。

實(shí)驗(yàn)三：字典壓縮方法實(shí)現(xiàn)壓縮和解壓縮

實(shí)驗(yàn)內(nèi)容：

基于給定程序(略)，用C/C++ /Java編寫程序，根據(jù)LZ77或者LZ78字典壓縮算法的原理實(shí)現(xiàn)文件的壓縮及解壓縮，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

實(shí)驗(yàn)要求：

輸入：字符串文件

輸出：輸出壓縮/解壓縮文件。

實(shí)驗(yàn)?zāi)康模?/p>

學(xué)習(xí)已有的一個(gè)實(shí)現(xiàn)LZW算法的具體的程序，根據(jù)LZW算法和LZ77、LZ78算法的差別自己設(shè)計(jì)實(shí)現(xiàn)LZ77/LZ78字典壓縮算法，完成對(duì)數(shù)據(jù)文件的壓縮和解壓縮。本實(shí)驗(yàn)?zāi)軌蝈憻拰W(xué)生的讀程序的能力，同時(shí)啟發(fā)他們學(xué)習(xí)已有程序的設(shè)計(jì)思想，進(jìn)行部分改造來實(shí)現(xiàn)自己的算法。

實(shí)驗(yàn)四：圖像數(shù)據(jù)壓縮

實(shí)驗(yàn)內(nèi)容：

基于給定程序(略)，用C/C++/Java編寫程序，根據(jù)LZW字典壓縮算法的原理將圖像文件壓縮成GIF格式，用現(xiàn)有軟件檢驗(yàn)生成GIF圖像文件的正確性，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

實(shí)驗(yàn)要求：

1 輸入：給定的Bmp格式圖像。

2 輸出：壓縮成GIF格式圖像。

實(shí)驗(yàn)?zāi)康模?/p>

學(xué)習(xí)在已有程序的基礎(chǔ)上添加一些內(nèi)容來實(shí)現(xiàn)新的功能。在掌握?qǐng)D像GIF壓縮編碼原理的基礎(chǔ)上，在給定的LZW程序上添加針對(duì)圖像數(shù)據(jù)文件的一些功能，實(shí)現(xiàn)圖像GIF壓縮。

本實(shí)驗(yàn)使學(xué)生了解圖像數(shù)據(jù)壓縮方法，深入理解基于字典的方法進(jìn)行數(shù)據(jù)壓縮的原理。

4總結(jié)

以上是我對(duì)“數(shù)據(jù)壓縮”這門課程的一些心得和總結(jié)。主要從課程的大綱、授課重點(diǎn)內(nèi)容和實(shí)驗(yàn)設(shè)計(jì)進(jìn)行了介紹。通過四次授課顯示，同學(xué)們對(duì)這樣的課程內(nèi)容掌握的較好，同時(shí)學(xué)習(xí)到的數(shù)據(jù)壓縮的思想對(duì)他們思考問題的方式也有很大的啟發(fā)作用。同學(xué)們?cè)谡n程實(shí)驗(yàn)中極大地鍛煉了編程能力，同時(shí)也通過實(shí)驗(yàn)對(duì)算法的原理有了深入的理解，對(duì)算法的很多細(xì)節(jié)問題能夠提出自己的改造方法，進(jìn)行了創(chuàng)造性的設(shè)計(jì)工作。衷心希望以上總結(jié)的內(nèi)容能夠?qū)@門課程的建設(shè)有所幫助。

參考文獻(xiàn)：

[1] David Salomon. Data Compression. 3rd Edition,SPRINGER-VERLAG NEW YORK INC,2004.

[2] 笨笨數(shù)據(jù)壓縮教程[EB/OL]. http://www.contextfree.net/wangyg/a/tutorial/benben.html.

[3] 林福宗. 多媒體技術(shù)基礎(chǔ)(第二版)[M]. 北京:清華大學(xué)出版社,2002,9.

[4] David Salomon著,吳樂南等譯. 數(shù)據(jù)壓縮原理與應(yīng)用(第二版)[M]. 北京:電子工業(yè)出版社,1999.