【正文】 ................................. 23 改進(jìn)的覆蓋聚類算法 ........................................................................................ 23 改進(jìn)的 SALBG 算法 ........................................................................................ 24 第四章 軟件系統(tǒng)的整體設(shè)計(jì)與實(shí)現(xiàn) .............................................................................. 29 軟件系統(tǒng)的整體設(shè)計(jì)及模塊實(shí)現(xiàn)說明 .................................................................. 29 算法的 VC++實(shí)現(xiàn)的簡(jiǎn)單說明 ................................................................................ 36 矢量量化編碼的性能和復(fù)雜度 ............................................................................... 37 算法的結(jié)果 ............................................................................................................... 38 第五章 結(jié)束語(yǔ) .................................................................................................................. 39 參考文獻(xiàn) ............................................................................................................................ 40 致謝 .................................................................................................................................... 42 附 錄 .................................................................................................................................. 43 I 摘要 伴隨著科技的發(fā)展，社會(huì)的進(jìn)步，在多媒體壓縮范疇里，人們認(rèn)識(shí)到對(duì)信源的建模表達(dá)能使壓縮技術(shù)取得更大的進(jìn)展。于是產(chǎn)生了一系列的基于信源模型的圖像壓縮技術(shù)。 矢量量化一直是圖像編碼領(lǐng)域最常用的有損壓縮技術(shù)之一，具有信息理論概念上的最優(yōu)性和實(shí)際應(yīng)用的簡(jiǎn)易性。論文主要的研究工作體現(xiàn)在以下幾個(gè)方面： 系統(tǒng)地綜述了矢量量化的三大關(guān)鍵技術(shù)，即碼書設(shè)計(jì)、碼字搜索和碼字索引分配。 同時(shí)還介紹了分形圖像壓縮和模型基圖像壓縮的基本原理及算法，旨在深入了解信源模型圖像壓縮的技術(shù)。這些圖像包括文字、照片、圖表、插圖等，它使我們感到安適和生活情趣。隨著信息處理技術(shù)的發(fā)展，出現(xiàn)了文本、聲音、圖像、視頻等大量不同類型 的聽覺和視覺媒體數(shù)據(jù)。然而這些數(shù)據(jù)由于數(shù)據(jù)量龐大，在存儲(chǔ)空間和傳輸帶寬有限的情況下，這些數(shù)據(jù)的存儲(chǔ)和傳輸存在瓶頸。在保證聽覺和視覺質(zhì)量的前提下，人們往往希望能夠以盡量少的空間和盡量小的比特率來存儲(chǔ)和傳輸各種聲音、圖像數(shù)據(jù)。因此如何建立新的語(yǔ)音、圖像和視頻的分析模型，從而改進(jìn)壓縮編碼算法長(zhǎng)久 以來一直是信號(hào)處理領(lǐng)域的研究熱點(diǎn)。而在多媒體數(shù)據(jù)通信的發(fā)展趨勢(shì)下，圖像壓縮編碼技術(shù)的研究和應(yīng)用越來越引人矚目。最初在這一領(lǐng)域研究的焦點(diǎn)集中在如何建立一種模擬的方法以便減少視頻傳輸所需的帶寬。數(shù)字計(jì)算機(jī)的出現(xiàn)和后來先進(jìn)的集成電路的發(fā)展，導(dǎo)致了這方面研究的重點(diǎn)從模擬方式轉(zhuǎn)移到數(shù)字壓縮方法上來。當(dāng)前，圖像壓縮被認(rèn)為是一種“開 放技術(shù)”，已經(jīng)被廣泛用于現(xiàn)代通信業(yè)務(wù)、工程應(yīng)用、媒體傳播、醫(yī)療服務(wù)和商務(wù)應(yīng)用等諸多領(lǐng)域中。 然而在 通用數(shù)據(jù)壓縮領(lǐng)域 技術(shù)已經(jīng)相當(dāng)?shù)某墒欤茈y有大的突破，與此同時(shí)， 多媒體信息日益成為主流信息形態(tài)，數(shù)據(jù)壓縮技術(shù)特別是專用于圖像、音頻、視頻的數(shù)據(jù)壓縮技術(shù)還基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第一章 緒論 2 有相當(dāng)大的發(fā)展空間 —— 畢竟，人們對(duì)信息數(shù)量和信息質(zhì)量的追求是永無止境 。 今天，從事基于信源模型的圖像編碼 的數(shù)據(jù)壓縮課題的研究也正是在此思潮的引領(lǐng)之下開展的，希望通過筆者 的努力能為這一技術(shù)的發(fā)展做出應(yīng)有的貢獻(xiàn)。當(dāng)我們對(duì)文字信息進(jìn)行編碼時(shí)，如果為出現(xiàn)概率較高的字母賦予較短的編碼，為出現(xiàn)概率較低的字母賦予較長(zhǎng)的編碼，總的編碼長(zhǎng)度就能縮短不少。在 1948 年發(fā)表的論文 “ 通信的數(shù)學(xué)理論（ A Mathematical Theory of Communication ） [2]中， Shannon 指出，任何信息都存在冗余，冗余大小與信息中每個(gè)符號(hào)（數(shù)字、字母或單詞）的出現(xiàn)概率或者說不確定性有關(guān)。這篇偉大的論文后來被譽(yù)為信息論的開山之作，信息熵也奠定了所有數(shù)據(jù)壓縮算法的理論基礎(chǔ)。利用信息熵公式，人們可以計(jì)算出信息編碼的極限，即在一定的概率模型下，無損壓縮的編碼長(zhǎng)度不可能小于信息熵公式給出的結(jié)果。 隨著科學(xué)技術(shù)的不斷進(jìn)步，出現(xiàn)了 Huffman 編碼 [3]。 不過 ， Huffman 編碼所得的編碼長(zhǎng)度只是對(duì)信息熵計(jì)算結(jié)果的 一種近似，還無法真正逼近信息熵的極限。 1976 年， J. Rissanen 提出了一種可以成功地逼近信息熵極限的編碼方法 —— 算術(shù)編碼 [3]。 對(duì)于無損壓縮而言， PPM 模型與算術(shù)編碼相結(jié)合，已經(jīng)可以最大程度地逼近信息熵的極限。不幸的是，事情往往不像想象中的那樣簡(jiǎn)單：算術(shù)編碼雖然可以獲得最短的編碼長(zhǎng)度，但其本身的復(fù)雜性也使得算術(shù)編碼的任何具體實(shí)現(xiàn)在運(yùn)行時(shí)都慢如蝸牛。 后來又相繼出現(xiàn)了 LZ7 LZ78 及基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第一章 緒論 3 LZW。 伴隨著科技的發(fā)展，社會(huì)的進(jìn)步，人們逐漸認(rèn)識(shí)到多媒體的數(shù)據(jù)壓縮成為一項(xiàng)亟待解決的技術(shù)。到 80 年代末，許多人已經(jīng)在這一領(lǐng)域取得了不小的收獲，設(shè)計(jì)出了一批在壓縮效果上讓人驚訝不已的聲音和圖像壓縮算法。委員會(huì)的名字我們大概都已經(jīng)非常熟悉了：靜態(tài)圖像聯(lián)合專家小組 ( JPEG )和動(dòng)態(tài)圖像聯(lián)合專家小組 ( MPEG )。但他們的基本思路是完全一樣的，即保留媒體 信息中最有規(guī)律、最能體現(xiàn)信息主要特征的數(shù)據(jù)，而略去其他不重要的數(shù)據(jù)。 就在多媒體壓縮范疇里，人們認(rèn)識(shí)到對(duì)信源的建模表達(dá)能使壓縮技術(shù)取得更大的進(jìn)展。而接受端則借助于一定的規(guī)則或模型，按一定的算法將這些基元或參數(shù)再綜合成原信源的一個(gè)逼近。 原則上，壓縮編碼的極限結(jié)果 是通過那些能夠反映信號(hào)產(chǎn)生過程最早階段的模型而得到的，比較鮮明的例子就是人類發(fā)音的“清晰聲帶 聲道模型”，它把注意焦點(diǎn)從 LPC 分析擴(kuò)展到了聲道區(qū)分析，原則上為甚低碼率矢量化提供了強(qiáng)得多的 定義域，并允許更好的處理聲帶 聲道相互作用，而簡(jiǎn)化的激勵(lì)后濾波模型忽略了這一現(xiàn)象。僅就圖像編碼而言，對(duì)信源模型的描述正從波形參數(shù)向幾何特征發(fā) 展。 本課題要求完成如下工作： 1. 對(duì)數(shù)據(jù)壓縮的基本理論、技術(shù)標(biāo)準(zhǔn)、評(píng)價(jià)方法進(jìn)行研究和分析； 2. 對(duì)基于信源模型圖像編碼的數(shù)據(jù)壓縮算法及其衍生算法進(jìn)行邏輯上的分析和比較； 3. 對(duì)這些算法進(jìn)行編程實(shí)現(xiàn)，并在實(shí)踐中進(jìn)行分析比較 4. 從這些算法中選擇一個(gè)較優(yōu)算法，并以此算法實(shí)現(xiàn)一個(gè)完整的壓縮軟件。其中 冗余信息是指在圖像文件中多余或重復(fù)的信息 ； 不相干信息是指圖像信息中不重要，無關(guān)緊要的部分。圖像壓縮的對(duì)象就是這兩種信息。兩個(gè)文件的大小之比 (壓縮比 )確定了壓縮的程度。無損壓縮算法去除的僅僅是冗余信息，因而可以在解壓縮時(shí)精確地恢復(fù)原圖像。對(duì)于多數(shù)圖像來說，為達(dá)到較高的壓縮比，保真度的輕微損失是可以接受的，這時(shí)就需要采用有損壓縮算法。人們?cè)谶x擇或設(shè)計(jì)算法時(shí)，往往是在算法的復(fù)雜度 (易實(shí)現(xiàn)性，計(jì)算量等 )和解壓縮圖像的保真度之間進(jìn)行折衷，從而在保持較小的存儲(chǔ)空間和傳輸負(fù)擔(dān)的同時(shí)保持可接受的圖像質(zhì)量。香農(nóng)的信息論告訴人們，只要碼速率不超過信道容量，符 號(hào)就能以任意小的差錯(cuò)概率在該信道中傳輸。對(duì)于幅值離散的信源， R(D)[5]定義如下： ( ) ( / ) ( , )XY P X P Y X d X Y D??? （ 11） 其中 ( ) ( ) ( / )XQ Y P X P Y X? ? （ 12） 平均失真滿足條件 : ( ) ( / ) ( , )XY P X P Y X d X Y D??? （ 13） 其中 d(X,Y)是失真測(cè)度，它表示輸出采樣值 Y再現(xiàn)原始信源采樣值 X所引入的失真，P(Y/X)表示在己經(jīng)發(fā)送 X 的情況下接收到 Y 的概率。相基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第一章 緒論 5 應(yīng)地，速率 — — 失真函數(shù)的逆函數(shù) D(R)表示在給定速率不超過 R的條件下，系統(tǒng)所能夠達(dá)到的最小失真。在實(shí)際應(yīng)用中，速率失真函數(shù)常常作為一個(gè)理論下界與實(shí)際編碼速率相比較，分析系統(tǒng)還有多大的改進(jìn)余地。 圖像質(zhì)量的測(cè)度 對(duì)人類而言，圖像信息的接收和預(yù)處理都要通過人眼來完成，圖像質(zhì)量好壞的判斷自然和人眼的視覺特性密切相關(guān)。這種感官上的差異的大小可以反映圖像質(zhì)量退化的多少。人們把這種純粹主觀感覺上的圖像質(zhì)量稱作圖像的主觀視覺質(zhì)量，并提出了一些衡量圖像質(zhì)量的主觀評(píng)價(jià)標(biāo)準(zhǔn)。雖然客觀評(píng)價(jià)不如主觀評(píng)價(jià)更符合人眼感受特性，但它形式簡(jiǎn)單、計(jì)算方便，同時(shí)也能較好的反映圖 像信息的損失量。 0? i? P1 0? j? Q1。在實(shí)際應(yīng)用當(dāng)中，通?？紤]如下幾個(gè)評(píng)價(jià)標(biāo)準(zhǔn)： (1) 圖像壓縮比。 (2) 圖像質(zhì)量。 (3) 編碼復(fù)雜度。 一般來說，以上三個(gè)評(píng)價(jià)參數(shù)是互相矛盾的，不同的算法因不同的應(yīng)用要求會(huì)在這三個(gè)參數(shù)上有不同的偏重。對(duì)給定信源來說，用時(shí)間和存儲(chǔ)量來描述的復(fù)雜度通常會(huì)隨比特率的降低而增高。在對(duì)編碼算法的選取上，人們必須在系統(tǒng)復(fù)雜度和性能，成本和保真度之間尋求折衷。另 一個(gè)例子就是人臉的線框模型，它為壓縮可視電話這類以人臉為主要景物的序列圖像提供了一個(gè)強(qiáng)有力的手段。 為便于研究和加深理解，學(xué)者們嘗試按 表 [3]。其中第 3 類是第一代圖像編碼技術(shù)的典型代表，編碼效率較 高，時(shí)延短、技術(shù)成熟，被現(xiàn)有的多種視頻編碼標(biāo)準(zhǔn)所采納。 1987 年 ， 美國(guó)喬治亞工學(xué)院的數(shù)學(xué)家 在題為 “ Chaotic Compression” [6]的論文中 提出 了分形圖像編碼的概念 之后，在 1988 年 和 loan發(fā)表了一篇題為 “ A Better Way to Compress Images”[7]的文章，在此文中，他們首次將 提出的 IFS 理論應(yīng)用到圖像壓縮編碼中，并獲得了較好的壓縮效果，壓縮比高達(dá) 10000: 1。盡管如此，它的極有希望的壓縮效果和壓縮比使人們看到了用分形理論解決圖像壓縮問題的前景和希望。各國(guó)學(xué)者紛紛效仿 的壓縮方案提出各種各樣的改進(jìn)方案，從而掀起了分形圖像編碼的高潮。編碼的過程是依據(jù)拼貼定理，通過給定的圖像，尋找一組壓縮仿射變換，使其構(gòu)成的迭代函數(shù)系統(tǒng)逼近給定的吸引子，然后記錄下相應(yīng)參數(shù)，并且用這些參數(shù)作為圖像的編碼進(jìn)行存儲(chǔ)和傳輸。這就是分形圖像壓縮的基本原理和方法。 基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 二 章 基于信源模型圖像壓縮的綜述 9 圖 分形編解碼原理框圖 分形圖像壓縮的基本算法 1990 年， 發(fā)表了一種基于方塊劃分的分形圖像壓縮方案 [8]。該方案突破了 設(shè)計(jì)的方案，將圖像分割成兩種大小固定的方塊，然后去找這兩種方塊之間的相似性，由于不再與整幅圖像比較，而放寬為原始圖像的一部分，從而使該方案能夠自動(dòng)對(duì)任意圖像進(jìn)行編碼。以后其他學(xué)者提出的方案都是基于此方案的改進(jìn)，因此 的 方案 被公認(rèn)為最基本的分形圖像編碼 方案 [3]。 把 NN? 大小的待編碼圖像 I 分割成若干個(gè)不重疊的、大小為 BB? 的子塊，稱之為值域塊，記為 NRRR , 21 ? 。然后再把待編碼圖像分割成若干個(gè)可以重疊的、大小為 KK? 的子塊，稱之為定義域塊，記為 MDDD , 21 ? 。對(duì)原始圖像的劃分如圖 ： (a)值域塊 iR