基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實現(xiàn)

基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實現(xiàn)基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實現(xiàn)Astherapiddevelopmentofcommunicationsandinformationtechnology,datacompressiontechnologyhasbecomeapowerfultoolforpeopletoworkordothescientificresearchonthisinformationage.Asastudyofimportantissuesoninformationresearch,datacompressiontechnologyhasbeenpaymuchattentionto.VectorQuantizationTechnology,asanimportantbranchinthefieldofdatacompression,withitsexcellentcharacteristics:highcompression,encodingspeed,clearandsimplealgorithm,hasbecomepowerfultoolsandmethodologiesintheareaofimagecompression.

AimedtotheapplicationwiththewaytoVectorQuantizationintheStaticimageofresearchgoals,thisthesisshowyouthedetailedexplanationofthebasicVectorQuantizationprinciple,relatedconceptsanddevelopmentstatus,thediscussionthethreetechnologykeyofVectorQuantization—codebookdesignalgorithm,codesearchingandcodedistribution.IndetailelaboratedLBGalgorithmandmostgreatlydropswhichwecancalledMDalgorithminthecodebookdesignalgorithm,basedoninequalityquickcode-searchinquickcode-searchandBASalgorithmandProhibitionsearchsymbolindexdistributionalgorithminsymbolindexdistribution.Finally,Ianalyzedtheexistingtypicalalgorithmandimprovingalgorithm,comeupwithmyownrealizationbasedonthemethodofVectorQuantizationandachievegoodresults.

KEYWORDS：datacompressionVectorQuantizationLBG

目錄摘要I

ABSTRACTII

第一章緒論1

1．1課題的研究背景及意義1

1．2課題研究現(xiàn)狀2

1．3課題研究內(nèi)容3

第二章矢量量化技術(shù)簡介4

2．1數(shù)據(jù)壓縮技術(shù)4

2．2矢量量化的定義及理論基礎(chǔ)8

2．3矢量量化的相關(guān)概念10

2．4矢量量化的關(guān)鍵技術(shù)及技術(shù)指標13

第三章矢量量化的算法研究16

3．1矢量量化碼書設(shè)計算法的研究16

3．1．1經(jīng)典的LBG算法16

3．1．2MD算法18

3．1．3碼書設(shè)計算法比較19

3．2碼字搜索算法20

3．2．1基于不等式的快速碼字搜索算法20

3．2．2等均值等方差最近鄰搜索算法21

3．3碼字索引分配算法23

3．3．1BSA算法23

3．3．2禁止搜索碼字索引算法25

第四章矢量量化算法的實現(xiàn)26

4．1需求分析與整體設(shè)計26

4．1．1需求分析26

4．1．2整體設(shè)計26

4．2矢量量化算法的實現(xiàn)過程及說明27

4．2．1初始碼書的生成27

4．2．2LBG矢量量化28

4．2．3矢量量化碼字索引與恢復(fù)31

4．3實驗結(jié)果及評價31

第五章結(jié)論與展望34

參考文獻35

致謝36

附錄37摘要伴隨著通訊與信息科技的迅猛發(fā)展，數(shù)據(jù)壓縮技術(shù)己經(jīng)成為信息時代人們工作與科研的有力工具。數(shù)據(jù)壓縮技術(shù)，作為信息論研究中的一個重要課題，一直受到人們的廣泛關(guān)注。矢量量化技術(shù)作為數(shù)據(jù)壓縮領(lǐng)域里的一個重要分支，以它壓縮比高、編碼速度快、算法簡單清晰等良好的特性，在圖像壓縮等領(lǐng)域都已成為有力的手段和方法。

本文以矢量量化在靜止圖像方面的應(yīng)用為研究目標，介紹了矢量量化的定義，基本理論、相關(guān)概念及發(fā)展現(xiàn)狀，重點討論研究了矢量量化的三大關(guān)鍵技術(shù)–碼書生成和碼字搜索和碼字索引分配。詳細闡述了碼書設(shè)計算法中的LBG算法和最大下降MD算法；快速碼字搜索中的基于不等式快速碼字搜所和碼字索引分配中的BAS算法和禁止搜索碼字索引算法等。

最后總結(jié)分析了現(xiàn)有典型的算法和改進算法并提出了自己的基于矢量量化算法的實現(xiàn)方法，編程實現(xiàn)了一個完整的數(shù)據(jù)壓縮軟件，取得了較好的效果。關(guān)鍵詞：數(shù)據(jù)壓縮，矢量量化，LBG

ABSTRACT

第一章緒論

1．1課題的研究背景及意義

1．1．1研究背景

隨著計算機和大規(guī)模集成電路的飛速發(fā)展，數(shù)字信號分析和處理技術(shù)得到很大發(fā)展，并已經(jīng)廣泛應(yīng)用于通信、雷達和自動化等領(lǐng)域。數(shù)字信號的突出優(yōu)點是便于傳輸、存儲、交換、加密和處理等。一個模擬信號f(t)，只要它的頻帶有限并允許一定的失真，往往可以經(jīng)過采樣變成時間離散但幅值連續(xù)的采樣信號f(n)。對于數(shù)字系統(tǒng)來說，f(n)還需經(jīng)過量化變成時間和幅值均離散的數(shù)字信號x(n)。

通信系統(tǒng)有兩大類：一類是傳輸模擬信號f(t)的模擬通信系統(tǒng)；另一類是傳輸數(shù)字信號x(n)的數(shù)字通信系統(tǒng)。在任何數(shù)據(jù)傳輸系統(tǒng)中，人們總希望只傳輸所需要的信息并以最小失真或者零失真來接收這些信息。人們常用有效性（傳輸效率）和可靠性（抗干擾能力）來描述傳輸系統(tǒng)的性能。與模擬通信系統(tǒng)相比，數(shù)字通信系統(tǒng)具有抗干擾能力強，保密性好，可靠性高，便于傳輸、存儲、交換和處理等優(yōu)點。在數(shù)字通信中，碼速率高不僅影響傳輸效率，而且增加了存儲和處理的負擔(dān)。

上個世紀八、九十年代，計算機技術(shù)和網(wǎng)絡(luò)技術(shù)取得了飛速的發(fā)展，人類社會進入到了前所未有的信息化時代。隨著信息時代的來臨人們對通信業(yè)務(wù)的要求不斷增長，在日常生活中，大量的信息數(shù)據(jù)需要傳輸、存儲和處理?？茖W(xué)實驗表明，人類從外界獲取的知識之中，有80%以上都是通過視覺感知獲取的【1】。眼睛獲取的是圖像信息，和語音、文字等信息相比，圖像包含的信息量更大、更直觀、更確切，因而具有更高的使用效率和更廣泛的適應(yīng)性，一幅圖勝過千言萬語，圖像信息是人類認識世界、自身的重要源泉。所以在信息數(shù)據(jù)中，絕大部分數(shù)據(jù)都是圖像數(shù)據(jù)，而圖像數(shù)據(jù)的傳輸常常要占用很大的帶寬，需要很大的存儲空間，因而怎樣對圖像數(shù)據(jù)進行行之有效地傳輸是一個極具挑戰(zhàn)性的課題。

數(shù)字圖像中包含的數(shù)據(jù)量十分巨大，例如，800x600分辯率的真彩色圖像，其數(shù)據(jù)量為800x600x3=1440000字節(jié)，約1.4MB；而一分鐘CD音質(zhì)的音頻文件一般需要lOMB左右的存儲空間。在視頻傳輸中PAL制式(25幀/秒)下，畫面分辨率為640x480下，真彩色(24位)的圖像序列，播放1秒鐘的視頻畫面數(shù)據(jù)量為：640x480x3x25=23,040,000字節(jié)，相當(dāng)于存貯一千多萬個漢字所占用的空間。如此龐大的數(shù)據(jù)量，給圖像的傳輸、存貯、傳輸線的傳輸率(帶寬)以及計算機的處理速度等增加巨大的壓力。由此可見，對降低傳輸成本，增加數(shù)據(jù)傳輸?shù)目煽啃裕粩酀M足人們對信息傳輸?shù)男枨?，圖像壓縮都具有十分重要的作用。為了解決好這個問題，我們就必須對圖像進行編碼壓縮，在保證一定圖像質(zhì)量的前提下，有效地減少傳輸時所需的數(shù)據(jù)量和占用的頻帶。

1．1．2研究意義

圖像壓縮就是在沒有明顯失真的前提下，將圖像的位圖信息轉(zhuǎn)變成另外一種能將數(shù)據(jù)量縮減的表達形式，即去處冗余信息。首先，盡管圖像中數(shù)據(jù)量很大，但其行、列以及幀間都具有極強的相關(guān)性或冗余信息。即一個象素的灰度值，總是和它周圍的象素的灰度值有著某種關(guān)系，可以由它們推算表示出來，應(yīng)用某種方法提取或減少它們之間的這種相關(guān)性，即可實現(xiàn)圖像壓縮。其次，大部分圖像視頻信號的最終接收者都是人眼，而人類的視覺系統(tǒng)是一種高度復(fù)雜的系統(tǒng)，它能從極為雜亂的圖像中抽象出有意義的信息，并以非常精練的形式反映給大腦。人眼對圖像中的不同部分的敏感程度是不同的，如果去除圖像中對人眼不敏感或意義不大的部分，對圖像的主觀質(zhì)量是不會有很大影響的，也實現(xiàn)了圖像壓縮。正由于圖像壓縮的必要性和可能性，圖像壓縮編碼研究成為一個越來越活躍的領(lǐng)域。在諸如基于Internet的多媒體通信、可視電話、數(shù)字電視，多媒體計算機等領(lǐng)域得到了廣泛的應(yīng)用。

1．2課題研究現(xiàn)狀

矢量量化的基本理論早在二十世紀六七十年代已有人關(guān)注，而在二十世紀八十年代開始逐步完善起來。矢量量化是分組量化的一種，受到廣泛注意和使用的分組量化方法是由黃和舒爾泰斯于1963年首先提出來的【2】，他們指出分組量化的實現(xiàn)方法:首先與正交矩陣相乘將相關(guān)的采樣變換為不相關(guān)的采樣，然后再在每組固定的總比特數(shù)限制下，將不同的量化比特數(shù)目分配給每個不相關(guān)的采樣值。1979年，格爾肖在他的論文【3】中詳細闡述了分組量化的一般性理論，它將貝內(nèi)特早年關(guān)于均方誤差準則的量化模型推廣到分組量化中。

將矢量量化技術(shù)推向研究高潮和推廣應(yīng)用應(yīng)歸功于1980年由Linde.Buzo和Gray提出來的一種有效的LBG矢量量化碼書設(shè)計方法【4】，該文獻己經(jīng)成為矢量量化的經(jīng)典文獻，是矢量量化技術(shù)發(fā)展的基石。

在20多年歷程中，學(xué)者們在以下五個方面對矢量量化技術(shù)展開研究：

1.針對基本矢量量化器復(fù)雜度大和比特率固定的缺點，開發(fā)其它類型的矢量量化器；

2.針對基本矢量量化器的LBG碼書設(shè)計算法容易陷入局部極小、初始碼書影響優(yōu)化結(jié)果和計算量大的缺點，學(xué)者們引入了神經(jīng)網(wǎng)絡(luò)、優(yōu)化理論、模糊集合等技術(shù)，提出了各種各樣的碼書設(shè)計算法；

3.在矢量量化編碼場合中，針對基本矢量量化器的窮盡搜索編碼算法的計算量大和比特率固定的缺點，提出各種各樣的快速碼字搜索算法和變比特率碼字搜索算法；

4.矢量量化技術(shù)的應(yīng)用；

5.考慮到信道噪聲將會在矢量量化解碼端引入額外失真，學(xué)者們開始研究碼字索引分配算法以減少由于信道噪聲引起的失真。

1．3課題研究內(nèi)容

1.研究內(nèi)容

1）對數(shù)據(jù)壓縮的基本理論、技術(shù)標準、評價方法進行研究和分析

2）對基于矢量量化的數(shù)據(jù)壓縮算法及其衍生算法進行邏輯上的分析和比較

3）選擇矢量量化算法中的一種算法進行實現(xiàn)，完成一個完整的數(shù)據(jù)壓縮軟件

2.本文結(jié)構(gòu)安排

第一章為緒論，主要介紹了課題的研究背景，簡要地闡述課題的研究意義最后，總結(jié)了本論文的研究內(nèi)容。

第二章中，首先對數(shù)據(jù)壓縮作了簡要的綜述；然后介紹了矢量量化數(shù)據(jù)壓縮算法的起源，發(fā)展和相關(guān)的數(shù)學(xué)模型及理論基礎(chǔ)；最后寫了矢量量化的關(guān)鍵技術(shù)和矢量量化技術(shù)指標。

第三章是對矢量量化算法的研究，首先分別論述了矢量量化的三大關(guān)鍵技術(shù)的算法，介紹了碼書設(shè)計中的LBG算法和最大下降算法；碼字搜索算法中的基于不等式的快速碼字搜索算法和等均值等方差最近鄰搜索算法；碼字索引分配算法中的BSA算法和禁止搜索碼字索引算法。

第四章是矢量量化算法的實現(xiàn)。詳細介紹了矢量量化算法的實現(xiàn)過程，并對實驗結(jié)果進行了分析和評價。第二章矢量量化技術(shù)簡介

2．1數(shù)據(jù)壓縮技術(shù)

2．1．1數(shù)據(jù)壓縮技術(shù)的發(fā)展

數(shù)據(jù)壓縮的研究過程一直有兩個發(fā)展方向【5】：一個是許多數(shù)學(xué)家所致力于的建立信源和數(shù)據(jù)壓縮的數(shù)學(xué)模型，并從中找出衡量數(shù)據(jù)壓縮質(zhì)量的技術(shù)指標及最優(yōu)壓縮性能指標；另一個則是眾多的工程技術(shù)人員所進行的工作，他們的研究重點為建立一個能實現(xiàn)數(shù)據(jù)壓縮功能的系統(tǒng)，以服務(wù)于工程應(yīng)用，或者對這些數(shù)據(jù)壓縮系統(tǒng)進行分析或模擬，以確定它們的性能指標。

不論是理論研究還是工程實踐，1977年以前，數(shù)據(jù)壓縮作為信息論研究中的一項內(nèi)容，主要是有關(guān)信息嫡，數(shù)據(jù)壓縮比和各種編碼方法的研究，即按某種方法對源數(shù)據(jù)流進行編碼，使得經(jīng)過編碼的數(shù)據(jù)流比原數(shù)據(jù)流占用較少的空間。其中基于符號頻率統(tǒng)計的霍夫曼編碼具有良好的壓縮性能，一直占據(jù)重要的地位，不斷有基于霍夫曼編碼的改進算法提出。

隨著計算機技術(shù)的飛速發(fā)展，數(shù)據(jù)壓縮作為解決海量信息存儲和傳輸?shù)闹渭夹g(shù)受到人們的極大關(guān)注。1977年，兩位以色列科學(xué)家JacobZiv和AbrahamLempel發(fā)表了論文”Auniversalalgorithmforsequentialdatacompression”，提出了不同于以往的基于字典的壓縮算法LZ77【5】。1978年，又推出了改進算法LZ78。他們的研究把無失真壓縮的研究推向了一個全新的階段。

隨著信號處理研究的不斷的發(fā)展，數(shù)字圖像信號、語音信號等都被大量的引入到有關(guān)的領(lǐng)域中。由于圖像信息占用較多的存儲空間，而圖像通信又是目前非話業(yè)務(wù)的主流，因此數(shù)據(jù)壓縮技術(shù)在圖像通信中得到了最廣泛的應(yīng)用。

在圖像編碼中，最早研究的是預(yù)測編碼，曾作為經(jīng)典理論而登載于各種專著，并得到廣泛的應(yīng)用。近年來，隨著神經(jīng)網(wǎng)絡(luò)理論的興起，有人采用BP網(wǎng)進行非線性預(yù)測的嘗試，并取得了較好的效果。

1969年，在美國舉行首屆”圖形編碼會議”，表明圖像編碼以獨立的學(xué)科擠身于學(xué)術(shù)界。而變換編碼在五年左右的時間內(nèi)成為研究熱點。變換編碼中的DCT編碼由于編碼效果較好，運算復(fù)雜度適中等優(yōu)點，已經(jīng)發(fā)展成為目前國際圖像編碼標準的核心算法。

80年代中后期，眾多研究者相繼提出了在多個分辨率下表示圖像的方案，主要的方法有：子代編碼，金字塔編碼，小波變換編碼等。基于小波變換的方法具有較高的壓縮性能，己發(fā)展為JPEG2000的核心算法。在近年來的甚低碼率的編碼研究中，有一種稱之為模型基的編碼方法頗引人注意，這種方法壓縮比高，但適用于場景比較簡單的特定場合。

在1988年左右，有人提出了一種分形圖像編碼的壓縮方案。這種方案思路新穎、壓縮潛力大、并具有解碼分辨率無關(guān)性等優(yōu)點，是一種很有潛力的編碼方法。

盡管用軟件壓縮方法可以較好地實現(xiàn)數(shù)據(jù)壓縮的目的，但由于壓縮算法的運算量較大，需要很高的運算速度和存儲空間，這對現(xiàn)有系統(tǒng)來說是很大的負擔(dān)。為了解決這個問題，人們在繼續(xù)探索數(shù)據(jù)壓縮技術(shù)的同時，著手研制生產(chǎn)高性能的芯片和系統(tǒng)。一般在對時間要求不高的場合采用軟件壓縮，而對運行速度有特殊要求的情況下，可使用硬件壓縮。不過，目前硬件壓縮的開銷遠遠大于軟件壓縮的開銷。

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

數(shù)據(jù)壓縮的研究已有幾十年的歷史，其間，人們提出了各種各樣的壓縮算法。在分類上，也存在幾種不同的方法，有人按編碼失真程度或者說按壓縮過程的可逆性將數(shù)據(jù)壓縮編碼分為兩種類型:無失真壓縮編碼(NoiselessCoding)與有失真壓縮編碼(NoiseCoding)；有人按編碼基建模的不同將數(shù)據(jù)壓縮分成模型基編碼和波形基編碼；又有人將它分為第一代壓縮編碼和第二代壓縮編碼；還可按壓縮技術(shù)所使用的方法進行分類，可分為預(yù)測編碼(PredictiveCoding)、變換編碼(TransformCoding)和統(tǒng)計編碼(StatisticalCoding)三大類。目前，較為認可的是第一種分類方法【6】。

1．無失真壓縮

無失真壓縮也可稱之為冗余度壓縮(RedundancyCompression)，在數(shù)字圖象壓縮中，有3種基本的數(shù)據(jù)冗余：編碼冗余、像素間冗余以及心理視覺冗余。而無失真壓縮就是利用數(shù)據(jù)的統(tǒng)計冗余進行壓縮，除去或盡量除去數(shù)據(jù)中重復(fù)和冗余部分，而不丟失其中的任何信息，可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但壓縮率受到數(shù)據(jù)統(tǒng)計冗余度的理論限制，一般為2:1到5:1這類方法廣泛用于文本數(shù)據(jù)、程序和特殊應(yīng)用場合的圖像數(shù)據(jù)(如醫(yī)學(xué)圖像等)的壓縮.由于壓縮比的限制，僅使用無損壓縮方法不可能解決圖像和數(shù)字視頻的存儲和傳輸問題。

常用的無失真壓縮技術(shù)有：哈夫曼編碼，算術(shù)編碼，游程編碼，LZ編碼等。

1）行程長度編碼（RLE）

行程長度編碼（run-lengthencoding）是壓縮一個文件最簡單的方法之一。它的做法就是把一系列的重復(fù)值（例如圖象像素的灰度值）用一個單獨的值再加上一個計數(shù)值來取代。比如有這樣一個字母序列aabbbccccccccdddddd它的行程長度編碼就是2a3b8c6d。這種方法實現(xiàn)起來很容易，而且對于具有長重復(fù)值的串的壓縮編碼很有效。例如對于有大面積的連續(xù)陰影或者顏色相同的圖象，使用這種方法壓縮效果很好。很多位圖文件格式都用行程長度編碼，例如TIFF，PCX，GEM等。

2）LZW編碼

這是三個發(fā)明人名字的縮寫（Lempel，Ziv，Welch），其原理是將每一個字節(jié)的值都要與下一個字節(jié)的值配成一個字符對，并為每個字符對設(shè)定一個代碼。當(dāng)同樣的一個字符對再度出現(xiàn)時，就用代號代替這一字符對，然后再以這個代號與下個字符配對。LZW編碼原理的一個重要特征是，代碼不僅僅能取代一串同值的數(shù)據(jù)，也能夠代替一串不同值的數(shù)據(jù)。在圖像數(shù)據(jù)中若有某些不同值的數(shù)據(jù)經(jīng)常重復(fù)出現(xiàn)，也能找到一個代號來取代這些數(shù)據(jù)串。在此方面，LZW壓縮原理是優(yōu)于RLE的。

3）霍夫曼編碼

霍夫曼編碼（Huffmanencoding）是通過用不固定長度的編碼代替原始數(shù)據(jù)來實現(xiàn)的?；舴蚵幋a最初是為了對文本文件進行壓縮而建立的，迄今已經(jīng)有很多變體。它的基本思路是出現(xiàn)頻率越高的值，其對應(yīng)的編碼長度越短，反之出現(xiàn)頻率越低的值，其對應(yīng)的編碼長度越長。

2．有失真壓縮

有失真壓縮也可稱為嫡壓縮(EntropyCompression)，這是一種不可逆壓縮。他利用了人類視覺對圖像中的某些頻率成分不敏感的特性，在壓縮過程中會損失掉一部分信息，這樣，其原始數(shù)據(jù)不能由壓縮數(shù)據(jù)完全恢復(fù)出來。他是以丟失部分信息為代價而獲得較高的壓縮率。當(dāng)然，為了確保恢復(fù)后的數(shù)據(jù)能基本保持原數(shù)據(jù)的特征，這種失真應(yīng)該限制在某個規(guī)定的范圍之內(nèi)。無失真壓縮主要有兩大類型：特征抽取和量化方法，特征抽取的典型例子如指紋、漢字的模式識別，一旦抽取出足以有效表征與區(qū)分不同模式的特征參數(shù)，便可用它取代原始的圖像數(shù)據(jù)，這一類方法一般是用于特定的環(huán)境。量化則是更為通用的熵壓縮技術(shù)，除了直接對無記憶信源的單個樣本做所謂的零記憶量化外，還可以對有記憶信源的多個相關(guān)樣本映射到不同的空間，去除了原始數(shù)據(jù)中相關(guān)性后再做量化處理，由此又引出了預(yù)測編碼和變換編碼。

1）矢量量化編碼

矢量量化編碼利用相鄰圖象數(shù)據(jù)間的高度相關(guān)性，將輸入圖象數(shù)據(jù)序列分組，每一組m個數(shù)據(jù)構(gòu)成一個m維矢量，一起進行編碼，即一次量化多個點。根據(jù)仙農(nóng)率失真理論，對于無記憶信源，矢量量化編碼總是優(yōu)于標量量化編碼。

2）預(yù)測及內(nèi)插編碼

一般在圖象中局部區(qū)域的象素是高度相關(guān)的，因此可以用先前的象素的有關(guān)灰度知識來對當(dāng)前象素的灰度進行預(yù)計，這就是預(yù)測。而所謂內(nèi)插就是根據(jù)先前的和后來的象素的灰度知識來推斷當(dāng)前象素的灰度情況。如果預(yù)測和內(nèi)插是正確的，則不必對每一個象素的灰度都進行壓縮，而是把預(yù)測值與實際象素值之間的差值經(jīng)過熵編碼后發(fā)送到接收端。在接收端通過預(yù)測值加差值信號來重建原象素。

3）變換編碼

變換編碼就是將圖象光強矩陣（時域信號）變換到系數(shù)空間（頻域信號）上進行處理的方法。在空間上具有強相關(guān)的信號，反映在頻域上是某些特定的區(qū)域內(nèi)能量常常被集中在一起，或者是系數(shù)矩陣的分布具有某些規(guī)律。我們可以利用這些規(guī)律在頻域上減少量化比特數(shù)，達到壓縮的目的。由于正交變換的變換矩陣是可逆的且逆矩陣與轉(zhuǎn)置矩陣相等，這就使解碼運算是有解的且運算方便，因此運算矩陣總是選用正交變換來做。圖2.1數(shù)據(jù)壓縮技術(shù)的分類

2．1．3數(shù)據(jù)壓縮算法的度量標準

對于一種數(shù)據(jù)壓縮算法的性能，有一定的衡量標準，為了后面幾章描述的方便，也為不至于產(chǎn)生歧義，對這些標準作以簡單的介紹【7】。

1．算法性能評價

1）壓縮比（CR：CompressionRatio）：

壓縮比定義為原始數(shù)據(jù)量與壓縮后量的比值，即

壓縮比=原始數(shù)據(jù)量/壓縮后量

2）計算復(fù)雜度：

計算復(fù)雜度可以用算法處理一定量數(shù)據(jù)所需的基本運算次數(shù)來度量。如處理一幀有確定的分辨率和顏色數(shù)的圖像所需的加法次數(shù)和乘法次數(shù)。

壓縮算法分為編碼部分和解碼部分，如果兩者的計算復(fù)雜度大至相當(dāng)，則算法稱為對稱的，反之稱為非對稱的。

2．圖像質(zhì)量評價

1）均方誤差（MSE）

對于模擬信號，設(shè)原始數(shù)據(jù)為x(t)，編碼、解碼后的數(shù)據(jù)為y(t)，二者之差為e(t)，即e(t)=x(t)-y(t)。則e(t)的方差如公式2.1所示：

（2.1）

通常誤差均值μe=0，又稱為均方誤差（MeanSquaredError）。

2）信噪比（SNR）：

對于離散信號，設(shè)原始數(shù)據(jù)為，編碼、解碼后的數(shù)據(jù)為，它們的差值為的均方誤差為，信噪比（SignaltoNoiseRatio）定義為原始數(shù)據(jù)方差與重建數(shù)據(jù)誤差方差的比值如公式2.2所示：

（2.2）

3）峰值信噪比（PSNR）：

對于離散圖像數(shù)據(jù)，在信噪比的計算中常用圖像數(shù)據(jù)中的最大值xmax來代替均方根值бx，得到峰值信噪比如公式2.3所示

（2.3）

2．2矢量量化的定義及理論基礎(chǔ)

2．2．1矢量量化的起源及發(fā)展

矢量量化基本理論早在20世紀六七十年代己有人關(guān)注，八十年代開始逐步發(fā)展完善起來。1956年，Steinhaus第一次系統(tǒng)闡述了最佳矢量量化問題【8】；1978年，Buzo第一個提出實際的矢量量化器。1980年，Linde,Buzo和Gray將Loyd-Max算法推廣，提出了一種有效的矢量量化碼書設(shè)計算法一一LBG【4】算法，將矢量量化技術(shù)的研究和推廣應(yīng)用推向了高潮，成為矢量量化技術(shù)發(fā)展的里程碑。

在20多年的發(fā)展歷程中，人們?nèi)嫜芯苛耸噶苛炕睦碚摵蛻?yīng)用，開發(fā)了多種類型的矢量量化器。雖然矢量量化技術(shù)研究已經(jīng)日趨成熟，但仍存在很多有待解決的問題，如矢量量化碼書標準與編碼對象密切相關(guān)，不同應(yīng)用場合下碼書結(jié)構(gòu)、尺寸以及矢量維數(shù)都不相同。矢量量化的壓縮標準也一直沒有提出。目前的研究大多停留在理論方面，各種優(yōu)化的矢量量化器的硬件實現(xiàn)還有待于進一步的研究。因此，有關(guān)矢量量化技術(shù)的研究還有很多工作要做。

矢量量化在20多年的發(fā)展歷程中，主要是從以下幾方面得到了發(fā)展：

(1)矢量量化器的研究，對基本矢量量化器復(fù)雜度大和比特率固定的缺點，開發(fā)其它類型的矢量量化器；

(2)矢量量化碼書設(shè)計算法研究：針對基本矢量量化器的LBG碼書設(shè)計算法容易陷入局部極小、初始碼書影響優(yōu)化結(jié)果和計算量大的缺點，學(xué)者們引入神經(jīng)網(wǎng)絡(luò)、優(yōu)化理論、模糊集合等技術(shù)，提出了各種各樣的碼書設(shè)計算法；

(3)矢量量化碼字搜索算法研究：在矢量量化編碼場合中，針對基木矢量量化器的窮盡搜索編碼算法的計算量大和比特率固定的缺點提出各種各樣的快速碼字搜索算法和變化特率碼字搜索算法；

(4)矢量量化碼字索引分配算法研究：考慮到信道噪聲將會在矢量量化解碼端引入額外失真，學(xué)者們開始研究碼字索引分配算法以減少信道引起的失真。

2．2．2矢量量化的定義及理論基礎(chǔ)

1.定義

一個維數(shù)為k，尺寸為N的矢量量化器可以定義為從k維歐兒里得空間到一個包含N個輸出(重構(gòu))點的有限集合C的映射Q【9】，表示為公式（2.4）：

（2.4）

其中，。

C是重構(gòu)碼字矢量集合，稱為碼書，其尺寸(大小)為N。碼書的N個元素Yi稱為碼字或者碼矢量，它們均為k維歐幾里得空間中的矢量。輸入矢量空間通過尺寸為N的矢量量化器Q后，被分割成N個互不重疊的區(qū)域又稱為胞腔，這個過程稱為輸入矢量空間的劃分。對胞腔定義為公式（2.5）：

（2.5）

2.理論基礎(chǔ)

矢量量化的理論基礎(chǔ)是香農(nóng)的率失真理論。1948年，香農(nóng)定義了信道容量，并證明只要編碼速率不超過信道容量，符號就能以任意小的差錯概率在該信道中傳輸。1959年，香農(nóng)定義了率失真函數(shù)R(D)，并證明只要R(D)不超過信道容量就能保證接收端的失真不超過給定閾值D。在數(shù)學(xué)上，R(D)定義為在給定失真D的條件下，系統(tǒng)所能夠達到的最小碼速率。對于幅值離散的信源，R(D)定義如下公式（2.6）所示:

（2.6）

其中，，平均失真滿足公式2.7：

（2.7）

式中d(X,Y)是失真測度，它表示輸出采樣值Y再現(xiàn)原始采樣值X所引入的失真，P(Y/X)表示在己發(fā)送X的情況下接收到Y(jié)的概率。R(D)的單位為比特/采樣。同樣，也可以定義失真率函數(shù)D(R)，它是率失真函數(shù)的逆函數(shù)，其含義為在定速率不超過R的條件下，系統(tǒng)所能夠達到的最小失真，它是在維數(shù)k趨向無窮大時Dk(R)的極限，即。

香農(nóng)理論表明在速率受限的條件下或在平均失真受限的情況下，通信系統(tǒng)所能達到的最優(yōu)性能。率失真函數(shù)通常又被作為理論最優(yōu)值，如果一個系統(tǒng)的性能低于理論最優(yōu)值，則一定可用更好的編碼技術(shù)獲得系統(tǒng)性能的改善；如果一個系統(tǒng)的性能接近理論最優(yōu)值，則此系統(tǒng)已接近最優(yōu)，無法再做太多改善；一個系統(tǒng)的性能不可能優(yōu)于理論最優(yōu)值。由香農(nóng)理淪可知，理論上，矢量量化技術(shù)只要不斷的增加矢量的維數(shù)k，編碼的性能就可任意接近率失真函數(shù)，使系統(tǒng)性能達到最優(yōu)。因此，香農(nóng)的率失真理論指出了矢量量化技術(shù)的優(yōu)越性，是矢量量化技術(shù)的理論基礎(chǔ)。

2．3矢量量化的相關(guān)概念

2．3．1數(shù)學(xué)模型

設(shè)有一個信源采樣數(shù)據(jù)序列，我們把每K個數(shù)據(jù)分成一組，每組數(shù)據(jù)都記錄成矢量形式(i=1,2,…,N)，稱x為輸入矢量。設(shè)為一個K維輸入矢量的集合。

再把T劃分成M(<N)個子空間，即各子空間滿足公式(2.8)：

(2.8)

通常，我們把這M個子空間稱為Voronoi胞腔(Cells)，或者簡稱胞腔，有時也把它稱為一個分類或分區(qū)。在每個胞腔R，中我們再找到一個代表元Yi,我們稱所有這些代表元組成的集合C=()為碼書(Codebook)。這些代表元也稱為碼字(Codeword)集合1=(1,2,…,M}稱為碼字的索引集合。一個矢量量化器包括編碼器和解碼器兩部分。編碼器主要包括一個碼書和一個量化器。

量化器Q(X)定義如式(2.9)：

Q:TC；

當(dāng)X時，Q(X)=Yi(i=1,2,…,M).(2.9)

其中，Q(X)是一個多對一的函數(shù)，因此它是不可逆的。解碼器主要包括一個與編碼器相同的碼書和一個碼字檢索器(i)。

碼字檢索器(i)定義如式（2.10）：

:IC；

(i)=Yi，i=1,2,…,M.(2.10)

矢量量化的模型如下圖2.2所示：

編碼時：對任意一個輸入的K維矢量X，計算Q(X)的值Yi，通過傳輸信道發(fā)送碼字Yi的索引i到解碼器端。

解碼時：對輸入的一個索引號i，查找碼書中對應(yīng)的碼字Yi，輸出Yi作為整個系統(tǒng)對矢量X的壓縮恢復(fù)值。

圖2.2矢量量化器結(jié)構(gòu)示意圖

2．3．2量化器Q(x)相關(guān)問題

我們可以看出矢量量化可以等價于一個聚類問題。但如何聚類卻有很多種方法。在上文我們說當(dāng)時，Q(X)=Yi；(i=1,2,…,M)。這是用胞腔來定義Q(X)。反過來，也可以用Q(X)和碼字Yi來定義胞腔Ri，如式（2.11）所示:

（2.11）

當(dāng)然，最初必須有一個明確的Q{X〕的定義。

如何判斷昵？通常定義一個失真測度函數(shù)(實數(shù)域)，d(X,Yi)表示用Yi來代表X時產(chǎn)生的誤差。我們用它來判斷一個矢量X到底屬于那個胞腔:

當(dāng)d(X,Y

因此，在這里量化器的主要工作就是利用失真測度函數(shù)d進行最近鄰碼字收索。有時候我們也把d(X,Yi)稱作X與Yi之NJ的距離。

2．3．3失真測度函數(shù)

我們要求失真測度函數(shù)滿足以下兩個條件：

(1)正定性：當(dāng)且僅當(dāng)X=Y時d(X,Y)=0；

(2)對稱性：；

有時候我們也加上第三個條件：

(3)三角不等式：；

失真測度函數(shù)通常選擇線性賦范空間中的范數(shù)，根據(jù)范數(shù)的定義，它們都滿足上面三個條件。在本文中若無特殊聲明，我們的d(X,Y)就取最常用的2范數(shù)的平方，即K維歐幾里德空間中的距離的平方：，我們把這個測度又稱為平方誤差測度。它雖然不滿足三角不等式但是卻是滿足全部這三個條件的。

事實上，判斷一個矢量X屬于哪個胞腔可以有很多種標準，在本文中，我們僅僅依據(jù)最近鄰(NN:NearestNeighbor)準則為判斷標準。利用矢量失真函數(shù)d，我們再定義一個胞腔失真函數(shù)：

D:VoronoiCellsR(實數(shù)域)；

X為處理矢量。

因為我們通常處理的數(shù)據(jù)量都是有限的，所以有限個實數(shù)之和也是有限的，從而D(Ri)是有限的。那么我們系統(tǒng)的總失真就如式（2.12）所示：

（2.12）

有時為方便起見，我們也把Er記為Er(C)，C為碼書，把D(Ri)記為D(Ri,Yi),Yi為Ri的代表元。顯而易見的，Er是越小越好。

2．4矢量量化的關(guān)鍵技術(shù)及技術(shù)指標

2．4．1矢量量化的關(guān)鍵技術(shù)

矢量量化的三大關(guān)鍵技術(shù)是【8】：碼書設(shè)計、碼字搜索和碼字索引分配。其中前兩項最關(guān)鍵。

1.碼書設(shè)計

矢量量化的首要問題是設(shè)計出性能好的碼書。如果沒有碼書，那么編碼將成為無米之炊。假設(shè)采用平方誤差測度作為失真測度，訓(xùn)練矢量數(shù)為M，目的是生成含N(N<M)個碼字的碼書，則碼書設(shè)計過程就是尋求把M個訓(xùn)練矢量分成N類的一種最佳方案(如:使得均方誤差最小)，而把各類的質(zhì)心矢量作為碼書的碼字。可以證明在這種條件下各種可能的碼書個數(shù)為NumC，NumC滿足公式2.13：

（2.13）其中C為組合數(shù)。通過測試所有碼書的性能可以得到全局最優(yōu)碼書。

然而，在N和M比較大的情況下，搜索全部碼書是根本不可能的。為了克服這個困難，文獻中各種碼書設(shè)計方法都采取搜索部分碼書的方法得到局部最優(yōu)或接近全局最優(yōu)的碼書。所以研究碼書設(shè)計算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼書以提高碼書的性能，并且盡可能減少計算復(fù)雜度。

2.碼字搜索

矢量量化碼字搜索算法是指在碼書已經(jīng)存在的情況下，對于給定的輸入矢量，在碼書中搜索與輸入矢量之間失真最小的碼字。給定大小為N的碼書C，如果矢量x與碼字A之間的失真測度為d(x,y)，則碼字搜索算法的目的就是找到碼字Y，使得失真測度滿足公式2.14:

（2.14）

如果采用平方誤差測度，對于k維矢量，每次失真計算需要k次乘法，2k一1次加法，從而為了對矢量x進行窮盡搜索編碼需要Nk次乘法，N(2k-1)次加法和N-1次比較?？梢钥闯?，計算復(fù)雜度由碼書尺寸和矢量維數(shù)決定。對于大尺寸碼書和高維矢量，計算復(fù)雜程度將很大。研究碼字搜索算法的主要目的就是尋求快速有效的算法以減少計算復(fù)雜程度，并且盡量使得算法易于用硬件實現(xiàn)。

3.碼字索引分配

在圖示的矢量量化編碼和解碼系統(tǒng)中，如果信道有噪聲，則信道左端的索引i經(jīng)過信道傳輸可能輸出索引J而不是索引i，從而將在解碼端引入額外失真。為了減少這種失真，可以對碼字的索引進行重新分配。如果書大小為N，則碼字索引分配方案一共有N!種。碼字索引分配算法就是在N!種碼字索引分配方案中尋求一種最佳的碼字索引分配使由信道噪聲引起的失真最小。然而，當(dāng)N較大時，測試N!種碼字索引分配方案是不可能的。為了克服這個困難，各種碼字索引分配方法都采用局部搜索算法，往往只能得到局部最優(yōu)解。所以研究碼字索引分配算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼字索引分配方案以減少由信道噪聲引起的失真，并盡可能減少計算復(fù)雜度和搜索時間。

2．4．2矢量量化技術(shù)指標

1.矢量量化壓縮率

從矢量量化器的工作原理我們看出，碼書確定之后，傳輸或者存儲的壓縮數(shù)據(jù)只是一系列碼字的索引，這些索引本身并不包含原始數(shù)據(jù)的任何信息。因此矢量量化的壓縮率很大，其比特率bit/采樣，也就是說壓縮倍數(shù)為B為原始采樣數(shù)據(jù)所用比特(bit)數(shù)。

舉例來說，當(dāng)E=8,M=256,K=64時，壓縮率r=0.015625bits/采樣。壓縮倍數(shù)為64。這樣的壓縮倍數(shù)顯然很可觀了從壓縮率與壓縮倍數(shù)的計算公式我們看出，M一般是2的冪次。再例如，碼書大小為150,碼字索引要用8bits碼書大小為256，碼字索引也要用8bits.兩種碼書大小得到的數(shù)據(jù)壓縮率相同，但后者壓縮性能顯然更好，所以一般我們用256而非150個碼字，大小為2a的碼書又稱為q比特碼書。

2.信號恢復(fù)性能指標

通常信號質(zhì)量有均方誤差(MSE)，信噪比(SNR)，峰值信噪比(PSNR)【11】等。在本文的討論中，我們主要是灰度圖像作為測試數(shù)據(jù)來源。我們的矢量量化技術(shù)的應(yīng)用也主要是針對灰度圖像的，因此以L級灰度圖像為例，我們給出個指標的定義：設(shè)一副L級灰度圖像有WXH個像親，Xij為原始圖像像素值，Yij為恢復(fù)圖像像素值，那么

結(jié)過如下公式所示：

（2.15）

（2.16）

（2.17）

第三章矢量量化的算法研究

3．1矢量量化碼書設(shè)計算法的研究

3．1．1經(jīng)典的LBG算法

如前所述，在矢量量化器的構(gòu)造過程中，碼本設(shè)計是最初的也是最重要的部分，根據(jù)各種碼本設(shè)計算法的思想和迭代過程，我們可以將碼本設(shè)計問題歸結(jié)為Lloyd算法的兩條基本準則【12】：

1.最佳劃分準則(OptimalPartition)

對于給定的碼本利用最近鄰條件對訓(xùn)練矢量集進行重新劃分。將每個訓(xùn)練矢量映射到與它之間失真最小的碼字，最后形成一組以現(xiàn)有碼本中的碼字為中心的最佳劃分。設(shè)訓(xùn)練矢量集為：

則訓(xùn)練矢量集的最佳分類滿足公式（3.1）：

式中，i,j=1,2,…,N（3.1）

如果存在D(x,yi)=D(x,yj),則將訓(xùn)練矢量歸入碼字yi的集合。

通常把這種最佳劃分稱為Voronoi劃分，對應(yīng)的子集凡稱為Voronoi胞腔。設(shè)訓(xùn)練矢量x為k維的，如果用平方誤差測度用來表征訓(xùn)練矢量x和碼字yi之間的失真，即：

（3.2）2.質(zhì)心條件(CentroidCondition)

利用由上面步驟得到的訓(xùn)練矢量劃分集重新計算它們各自的質(zhì)心，得到新的碼本：

（3.3）

（3.4）

式中，代表子集Si中訓(xùn)練矢量的個數(shù)。

各種矢量量化碼本設(shè)計算法基本都是上面兩個步驟的交替迭代的基礎(chǔ)上得到最后的碼本。不難看出，碼本生成過程中的計算量是隨著碼本矢量的維數(shù)k和碼本尺寸N的增大而急劇增長的，對于需要高維大碼本的矢量量化器來說，測試所有可能的碼本來尋求全局最優(yōu)碼本將是十分困難的。為了克服這個困難，Linde.Buzo和Gray提出了經(jīng)典的LBG算法。

1980年Linde，Buzo和Gray將Lloyd算法推廣到矢量空間【8】，算法的步驟簡單描述如下：

Step1：給定初始碼本，令迭代次數(shù)m=0，平均失真初始值為，給定失真下降閾值；

Step2：用碼本中的碼字作為質(zhì)心，根據(jù)最佳劃分原則將訓(xùn)練矢量集x劃分為對應(yīng)于每個碼字的N個聚類，

滿足：；

Step3：計算本次迭代的平均失真判斷相對誤差是否滿足，若滿足，則停止算法，碼本C(m)就是所求的碼本;

否則，轉(zhuǎn)Step4；

Step4：根據(jù)質(zhì)心條件，計算各聚類的質(zhì)心，即公式（3.5）：

（3.5）

產(chǎn)生新碼本并置m=m+1，轉(zhuǎn)Step2

END：算法結(jié)束。對于LBG算法來說，初始碼本選擇的好壞將直接影響到后面的迭代計算結(jié)果，一個不好的初始碼本會降低算法的收斂速度和最終碼本的性能。因此在LBG算法中要對初始碼本的選擇作一定的處理。如果初始碼本隨機產(chǎn)生，即直接從訓(xùn)練序列中隨機選擇N個訓(xùn)練矢量作為初始碼字，構(gòu)成初始碼本，可能會選到一些非典型的訓(xùn)練矢量作碼字，因而該胞腔可能含有少數(shù)幾個矢量甚至只有1個。另外，有可能把某些空間分得過疏。這可能會導(dǎo)致碼本中的有些碼字得不到充分利用，設(shè)計出來的碼本性能就可能較差。

3．1．2MD算法

最大下降（MD）【13】碼本設(shè)計算法與經(jīng)典的LBG算法不同，它是一種分裂算法，而沒有初始碼本。在MD算法中，首先將訓(xùn)練矢量集作為一個原始包腔，然后該包腔被它的最優(yōu)分割超平面分成兩個子包腔。依此類推，每次分裂產(chǎn)生一個包腔，直到生成最后的N個包腔，計算它們的質(zhì)心，就可以得到設(shè)計的碼本C={y}i=1,2,…,N)。與LBG算法相比，MD算法的計算量少并且所產(chǎn)生的碼本性能好。另一方面，MD算法傾向于分割元素較多的胞腔，而不會去分割只有一個元素的胞腔，避免了非典型碼字的形成，提高了碼本的整體性能。在MD算法中，從L個包腔向(L+l)個包腔擴展時，先要找出每個現(xiàn)有包腔的最優(yōu)分割超平面，并計算它們各自帶來的失真下降幅度，然后依據(jù)失真下降最大準則來選擇究竟對哪一個包腔進行分裂。這在k維空間里是比較困難的事，需要大量的計算和比較。圖3.2所示為MD算法的分裂過程示意圖，圖中每一步驟中有陰影的包腔是當(dāng)前符合失真下降最大準則的包腔，它被最優(yōu)分割超平面分成下面的兩個子包腔和。從L個包腔生成(L+1)個包腔的具體實現(xiàn)描述如下：

設(shè)超平面將某胞腔分成兩個非空胞腔如式（3.6）所示：（3.6）

式中，，，T表示轉(zhuǎn)置。

當(dāng)中的矢量被質(zhì)心量化時，胞腔的失真D(Si)定義為公式（3.7）：（3.7）

則由分割超平面H,劃分胞腔S,所引起的失真下降可表示為式（3.8）：

（3.8）

若采用平方誤差測度，則式(3.8)可以化簡為式（3.9）：

或（3.9）

式中，分別為的元素個數(shù)，。分別為的質(zhì)心。

從式(3.9)中可以看出，若胞腔、非空，則失真下降函數(shù)滿足。

我們將胞腔Si的最優(yōu)分割超平面定義為使胞腔具有最大失真下降的超平面。MD算法先計算出所有胞腔的最大失真下降值，，然后找出最大的最大失真下降值，即，最后將胞腔Sp分割成兩個新胞腔。所以，L+l個胞腔是通過劃分L個胞腔中具有最大失真下降的胞腔并保持其余胞腔不變而得到的。值得注意的是，每次分裂包腔時，并不需要重新計算所有包腔的失真函數(shù)，而只需找到新增加的兩個包腔的最優(yōu)分割超平面，計算它們各自的失真函數(shù)，再與其它包腔的失真函數(shù)值進行比較即可找出新的滿足失真下降最大準則的包腔。產(chǎn)生最后的N個胞腔，一共需計算(2N-3)次最大失真下降函數(shù)。

3．1．3碼書設(shè)計算法比較

LBG算法是一種迭代算法，其迭代操作是標量量化勞埃德迭代操作的直接推廣。LBG算法他具有如下的優(yōu)點：

1.不用初始化計算，可大大減少計算時間

2.初始碼字選自訓(xùn)練序列，無空胞腔問題

LBG算法在具有如上的優(yōu)點的同時也有一些缺點和不足:

1.在每次迭代的最佳劃分階段，從碼書中搜索訓(xùn)練矢量的最近碼字需要大量的存儲空間和繁瑣的計算；

2.初始碼書的選擇影響碼書訓(xùn)練的收斂速度和最終碼書的性能；

碼書設(shè)計的第一個缺點可采用各種快速碼字搜索算法來解決，但這些算法無法改善碼書的性能，第2個缺點產(chǎn)生的原因是:LBG算法是一種下降算法，每次迭代總能減少(至少保持不變)平均失真，而且每次迭代通常只能產(chǎn)生碼書的局部變化，即每次迭代后，與舊碼書相比，新碼書不可能有非常大的變化。因此，一旦選定初始碼書，該算法只能得到局部最優(yōu)的碼書，即LBG算法一般不能得到全局最優(yōu)的碼書。

與LBG算法相比，MD算法的計算量少且所產(chǎn)生的碼書性能好。另一方面，MD算法傾向于分割元素較多的胞腔，而不會去分割只有一個元素的胞腔，而這種情況在LBG算法中卻常常出現(xiàn)。然而，在MD算法中，多維胞腔的最優(yōu)分割超平面的搜索是一個非常困難的問題。為減少計算量，這些算法的搜索范圍被限制在與矢量空間的基本矢量正交的超平面上，這個矢量空間可由離散余弦變換(DCT)得到。但是，在這種限制條件下，算法常常搜索不到最優(yōu)超平面。

3．2碼字搜索算法

3．2．1基于不等式的快速碼字搜索算法

1.部分失真不等式排除法

部分失真搜索(PartialDistortionSearch，PDS)算法【12】是一種較簡單有效的最近鄰搜索算法。它的基本思想是：在計算某個碼字與輸入矢量之間失真測度的過程中，始終判斷累加的部分失真是否已經(jīng)超過目前的最小失真，如果一旦超出則終止該碼字與輸入矢量之間的失真計算，轉(zhuǎn)而開始計算另一個碼字與輸入矢量的失真測度。PDS常被用來與其他快速搜索算法結(jié)合起來運用，來排除其它快速算法最后無法排除的碼字。

在編碼過程中計算前面部分維數(shù)的失真距離，若其超出當(dāng)前最小距離，則排除此碼字為最匹配碼字，否則繼續(xù)搜索其它碼字。

據(jù)如下（3.10）所示的柯西一許瓦爾茲不等式【14】：

（3.10）

可得一個不等式判據(jù)若，則能保證，yi可被排除。因為|yi|可離線計算，所以節(jié)省了計算量。

首先判斷是否成立，若成立，則排除碼字Yi否則，再判斷是否滿足，若滿足，yi也可被排除。這縮小了搜索范圍，他們還融入部分距離失真法節(jié)省計算量。雙測試法的缺陷在于要求矢量的所有分量都為正值，而圖像變換域編碼中產(chǎn)生的變換系數(shù)有正有負，必須對這些系數(shù)進行正補償，使所有矢量分量均大于零。

2.整數(shù)投影法

整數(shù)投影法是一種適用于圖像矢量量化的快速碼字搜索算法。他們?yōu)槊總€m×m圖像塊，定義三種整數(shù)投影【14】，如下公式（3.11）（3.12）（3.13）所示：

塊狀投影：（3.11）

垂直投影：（3.12）

水平投影：（3.13）

在這三種投影的基礎(chǔ)上定義了三個不等式條件，公式（3.14）（3.15）（3.16）所示：

（3.14）

（3.15）

（3.16）

可以證明，只要不滿足上述任何一個條件，可排除yi是最匹配碼字。

3.三角不等式法

基于三角不等式d(Yi,yj)<d(x,Yi)+d(x,yj)提出三種改進算法【14】。第一種算法先計算碼書中每兩個碼字之間的距離，以當(dāng)前匹配碼字yi為中心，2hi(hi為輸入矢量與當(dāng)前匹配碼字之間的歐氏距離)為半徑劃定搜索范圍，即只搜索滿足d(yj,yi)<2hi的碼字yj,j=1,2,…,N；

第二種算法是將搜索范圍定為滿足：x-hi<rk<rx+hi，

其中rx為輸入矢量的范數(shù)，rk為碼字的范數(shù)，hi為輸入矢量與當(dāng)前匹配碼字之間的歐氏距離，此種算法不同于第一種算法，無須計算碼字之間的距離；

第三種算法取前兩種算法搜索區(qū)域的交集作為搜索區(qū)域。

這三種算法都涉及如何確定初始匹配碼字的問題，一般取范數(shù)與輸入矢量范數(shù)最相近的碼字。第一、三種算法比第二種算法要多耗費存儲空間來存儲碼字之間的距離。最小均方誤差編碼算法，取一長訓(xùn)練矢量序列，計算每個Voronoi區(qū)域內(nèi)的訓(xùn)練矢量與該區(qū)域質(zhì)心矢量(碼字)的最大距離di，求平方根后得ri，按其升序排列。編碼時，從最小的ri開始，排除對任意，滿足.的碼字；那些對所有j，滿足的碼字，則采用部分失真排除判定法，確定此碼字為最佳匹配碼字或者在以該碼字為開始的剩余碼字中搜索最佳匹配碼字。

3．2．2等均值等方差最近鄰搜索算法

均值等方差最近鄰碼字搜索算法是將均值不等式判據(jù)和用方差不等式判據(jù)相結(jié)合，進一步縮小了碼字搜索范圍。k維輸入矢量x的方差定義公式（3.17）【9】為

（3.17）

其中：Mx為輸入矢量x的均值。

等均值等方差最近鄰搜索算法所用到的方差判別準則為：

設(shè)碼字為輸入矢量x的當(dāng)前最近鄰碼字，，輸入矢量x和碼字Y，的方差分別為Vx和Vyi，如果公式（3.18）成立，

（3.18）

則有d(x,yi)>d(x,yp)，碼字yi，可以被排除是輸入矢量x的最近鄰碼字。對式(3.12)作適當(dāng)變形，可得公式（3.19）和（3.20）

(3.19)

(3.20)

即碼字Yi的方差滿足以上兩式時，碼字Yi可以被排除是輸入矢量x的最近鄰碼字。

由幾何知識可知，在歐幾里得空間中以空間中心線L為軸心的超圓柱面上，各點的方差相等，該超圓柱面稱為等方差超圓柱面。由式(3.13)和(3.14)可知，等方差判別準則將碼字搜索范圍限制在方差分別為Vmax和Vmin的兩個超圓柱面內(nèi)。則等均值判別準則與等方差判別準則相結(jié)合的等均值等方差最近鄰搜索算法將碼字的搜索范圍限制在了如圖3.2所示的陰影部分內(nèi)。

圖3.1等均值等方差最近鄰搜索算法搜索范圍二維示意圖圖3.1所示是EENNS算法搜索范圍的二維示意圖，圖中以中心線L為軸心的超圓柱面分別是方差為Vmin和Vmax的等方差超圓柱面，與中心線L垂直的超平面分別是均值為Mmax和Mmin的等均值超圓柱面。等均值等方差最近鄰搜索算法將碼字的搜索范圍限制在超圓柱面V1,V2和超平面Ll，L2所夾的范圍內(nèi)，即圖中的陰影區(qū)域。EENNS算法減少了碼字搜索范圍，從而可以提高碼字搜索速度。EENNS算法具體步驟如下：

(A)預(yù)處理：計算并存儲碼書C中的均值和方差，按均值的大小對碼書進行排序。

(B)在線處理：

Stepl：計算輸入矢量x的均值Mx和方差Vx，在已排序碼書中找到均值與Mx最接近的碼字作為輸入矢量X的初始匹配碼字。計算當(dāng)前最小失真dmin=d(x,yp)。使集合

Step2：如果集合G為空，轉(zhuǎn)Step7；

Step3：往返搜索法搜索初始匹配碼字yp兩側(cè)的碼字yj；

Step4：如果碼字滿足或者，則執(zhí)行

下列步驟的(a)或者(b)。否則，轉(zhuǎn)步驟5；

(C)如果Myj>Mx，則從集合G中刪除所有碼字yi，i<j，轉(zhuǎn)Step2。

(D)否則，則從集合G中刪除所有碼字yii>j，轉(zhuǎn)Step2。

Step5：判斷碼字Yi的方差是否滿足或者如果滿足，則從刪除集合G中刪除碼字Yi，否則，轉(zhuǎn)Step6；

Step6：用部分失真排除算法搜索碼字Yi，如果d(x,Yi)<dmin,.則更新p=J，從集合G中刪除碼字Yi轉(zhuǎn)Step2；

Step7：確定輸入矢量x的最匹配碼字為Yp。

3．3碼字索引分配算法

3．3．1BSA算法

BSA算法是在1990年提出基于二元對稱信道模型的碼字索引分配算法【16】。該算法對于任何索引映射函數(shù)，選擇碼字y，作為輸入矢量x的最近碼字后將產(chǎn)生索引的傳輸，該過程與首先將碼書中的碼字進行位置交換等價，即對每一索i，碼字y最終移動到碼書中索引為的位置。

基于這個事實，很自然地想到一種最簡單的碼字索引分配方法：首先在給定碼書基礎(chǔ)上隨機產(chǎn)生一個初始碼字排列，然后將所有碼字的排列位置以特定方式進行交換，使信道失真不斷減少。因此，這種算法的輸入是一個碼書，輸出仍是一個碼書，只不過碼字存放在不同的位置。這帶來一個附加優(yōu)點:除了存儲碼書所需的空間以外，不需要任何額外信息來詳細描述索引映射函數(shù)n，從而不需要信道編碼和信道解碼。

BSA算法的主要思想是通過不斷交換碼字的位置，使得信道噪聲失真的目標函數(shù)場獲得局部最優(yōu)值.隨著交換的進行不斷下降，而且索引映射函數(shù)也跟著不斷變化。在每次迭代中，碼字的交換對是按一定的順序選擇的。所有的碼字y，都對應(yīng)一個函數(shù)，用來描述當(dāng)該碼字的索引(在當(dāng)前碼書中)在噪聲信道中傳輸時可能產(chǎn)生的失真，其定義為公式（3.21）：

（3.21）

BSA算法每次按從大到小的順序?qū)Υa字進行排序。擁有最大函數(shù)值的碼字被選為首先交換的候選對象。首先進行試驗性的交換，與其他每一個碼字分別進行交換，并計算每次交換后的下降值。選擇能使出現(xiàn)最大下降的那一個碼字與進行真正地交換，然后進入下一次迭代。如果不存在這樣的碼字，則對yi作相同的交換試驗。如果每一個碼字按這種方法與其他碼字進行交換后。不再下降，則終止算法，從而獲得一個局部最優(yōu)的碼字索引分配方案。算法的具體步驟如下：

Step1：初始化。隨機打亂碼字的排序；

Step2：整理排序。根據(jù)從大到小的順序?qū)Υa字yi進行排序。令n=－1；

Step3：試驗性交換。令n＝n＋1從j＝n＋1到N一1，分別計算索引n和索弓!j交換后所能引起的失真減少量，比較這些失真減少量，獲得最大的失真下降量；

Step4：如果>0，則交換索引n和引起最大失真下降的索引j，并轉(zhuǎn)Step2；

Step5：終止算法。如果n=N一1，則終止算法，否則，轉(zhuǎn)Step3。

可以看出，BSA算法根據(jù)函數(shù)值將碼字進行排列而選擇出哪一個碼字最先進行交換，從而在運算上給出了一個方向性引導(dǎo)。如果由于程序運行時間的限制而使算法的迭代次數(shù)有限，則這種方向性引導(dǎo)將顯得尤為重要。每一次成功交換的完成，代表一次迭代的結(jié)束。若一次迭代中的所有試驗性交換產(chǎn)生的失真下降都不大于O，則說明算法已經(jīng)達到一個局部最優(yōu)解.應(yīng)該指出的是:從不同的初始碼字排序出發(fā)，可獲得不同的局部最優(yōu)解，從而保證BSA算法對于碼字交換的限制不會影響它獲得全局最優(yōu)碼字索引分配方案的可能性。實驗證明，該算法獲得的碼字索引分配方案的失真比隨機碼字索引分配方案的失真有較大改進。

3．3．2禁止搜索碼字索引算法

禁止搜索的基本思想是通過一系列移動來搜尋所有可行解的搜索空間，并且在當(dāng)前迭代中禁止某些搜索方向以避免死循環(huán)和跳入局部極小。由當(dāng)前解到其鄰域解的移動被部分地或完全地記錄在禁止表中，目的是為了禁止以后迭代中的重復(fù)操作。

令為測試解的集合，其中元素si可以被表示為式【8】（3.22）：

（3.22）

其中，N為碼書的尺寸，Si(j)表示在解si中分配給碼字Yj的索引，令和分別表示當(dāng)前解和最優(yōu)解。中碼字Yj的索引，Sb(j)仍表示分配給解Sb中碼字Yi的索引。

令，和分別代表測試解組的目標函數(shù)值集合，當(dāng)前解的目標函數(shù)值和最優(yōu)解的目標函數(shù)值，其中是測試解的目標函數(shù)值，0<i<Ns-1。初始的當(dāng)前解是隨機產(chǎn)生的，通過隨機交換當(dāng)前解中的兩個索引來產(chǎn)生測試解。禁止表中只存儲交換的索引。如果從當(dāng)前解中產(chǎn)生測試解的交換索引與禁止表中任何記錄相同，則稱該測試解為禁止解。該算法的具體步驟如下:

Step1：設(shè)置禁止表大小Ts測試解個數(shù)N，以及迭代次數(shù)Im。令迭代計數(shù)器i=1，禁止表插入點t=1。隨機產(chǎn)生當(dāng)前解，計算其相應(yīng)的目標函數(shù)值V}。令Sb=Sc以及Vb=Vc

Step2：把當(dāng)前解Sc拷貝給每一個測試解si,0<i<Ns-1。對每一個測試解si，0<i<Ns-1，產(chǎn)生兩個隨機整數(shù)r1和r2，，，。N為碼字個數(shù)，然后通過交換索引和產(chǎn)生新測試解組。計算測試解的函數(shù)值。

Step3：如果最優(yōu)測試解的目標函數(shù)值比最優(yōu)解的目標函數(shù)值Vb還小，則把它作為新的當(dāng)前解，并令其目標函數(shù)值作為當(dāng)前解的目標函數(shù)值Vc，轉(zhuǎn)Step3。否則，選出測試解中最好的非禁止解。如果能選到，則把它作為新的當(dāng)前解Sc并令其目標函數(shù)值作為當(dāng)前解的目標函數(shù)值Vc，轉(zhuǎn)Step3；否則，轉(zhuǎn)Step1。

Step4：如果vb>vc，令Sb=Sc，Vb＝Vc，把從舊當(dāng)前解到新當(dāng)前解所交換過的索引插入禁止表中。禁止表的插入點設(shè)為ti=ti+1;如果ti>Ts，令ti＝l，如果i<Im，令i=i+1轉(zhuǎn)Step1；否則，算法結(jié)束。第四章矢量量化算法的實現(xiàn)

4．1需求分析與整體設(shè)計

4．1．1需求分析

隨著數(shù)字技術(shù)的飛速發(fā)展，越來越多的信息(文本、圖形、圖像、動畫、音頻及視頻影像等)采用數(shù)字化的形式存儲、傳輸和檢索。由于網(wǎng)絡(luò)上的數(shù)據(jù)流量飛速增長，而且網(wǎng)絡(luò)的帶寬總是滿足不了需求，數(shù)據(jù)壓縮編碼技術(shù)的迅猛發(fā)展，要求在盡量不損傷多媒體質(zhì)量的情況下壓縮數(shù)據(jù)量。

正是由于這種需求的存在，要求開發(fā)一套完整的數(shù)據(jù)壓縮軟件，利用矢量量化的數(shù)據(jù)壓縮算法，能夠調(diào)用BMP格式的圖像，對載入的圖像進行壓縮并顯示解壓后的圖像效果，能夠選擇路徑保存解壓后的圖像實現(xiàn)SNR信噪比的計算，便于對壓縮軟件性能的評價。

4．1．2整體設(shè)計

軟件的設(shè)計在Eclipse開發(fā)工具下編譯Java應(yīng)用程序。利用Java語言的面向?qū)ο蟮奶攸c，充分利用他的可封裝性，重用性和多態(tài)性等特點，開發(fā)一整套完整的基于矢量量化數(shù)據(jù)壓縮算法的壓縮軟件。

將這個數(shù)據(jù)壓縮軟件從整體上分五個模塊來實現(xiàn)的。Bmp格式圖像的調(diào)入和保存模塊，圖像矢量塊的劃分模塊，初始碼書生成模塊，LBG量化模塊，圖像解壓模塊。如圖4.1所示：圖4.1程序模塊框圖

軟件界面的設(shè)計。在JAVA的運行環(huán)境下要實現(xiàn)基于矢量量化數(shù)據(jù)壓縮算法對BMP格式的靜止圖像進行壓縮與解壓。軟件界面的設(shè)計，在圖像界面的左側(cè)可以顯示調(diào)入的圖像，右側(cè)顯示圖像信息。在瀏覽按鈕上可以調(diào)入待壓縮的圖像，并且可以選擇解壓后的圖像的保存位置。選擇好解壓圖像后點擊壓縮按鈕即可開始對圖像進行矢量量化的壓縮。最后顯示壓縮的結(jié)果，包括原始圖像的大小，壓縮后的大小，壓縮比，壓縮時間及PSNR值等信息。軟件運行的初始界面如圖4.2所示：圖4.2程序運行初始界面

4．2矢量量化算法的實現(xiàn)過程及說明

4．2．1初始碼書的生成

這個程序利用了隨機編碼生成碼書的方法，即根據(jù)輸入信源分布直接從訓(xùn)練序列中隨機選擇N個訓(xùn)練矢量作為初始碼字以構(gòu)成初始碼書。該方法的優(yōu)點是計算量低，初始碼書的生成較為容易。雖然可能出現(xiàn)碼書的分布不均勻的現(xiàn)象，但是配合LBG算法的多次迭代可以得到補償。需要注意，這里所說的隨機編碼是說初始碼書的選擇方式是隨機的，而一旦碼書選定，編碼器的工作方式則是按著最近鄰方式進行的。隨機碼書的生成代碼如下：

codebook=newMyBlock[N];

for(inti=0;i<N;i++)

{codebook[i]=newMyBlock();

}codebook[0]=tv.randomselect();

for(intj=1;j<N;j++){

intt=0;

do{t++;

n=0;

codebook[j]=tv.randomselect();

for(intl=0;l<j;l++)

{if(codebook[j].vcmp(codebook[l])==0)

{n=1;break;}

}

}while(n!=0&&t<100);}4．2．2LBG矢量量化

圖4.2LBG碼書設(shè)計流程圖如圖4.2所示的流程圖，對隨機生成初始碼書，碼書大小N，訓(xùn)練矢量序列，停止計算門限和起始平均失真的初始碼書進行勞埃德迭代。用初始碼書為已知的心形，把訓(xùn)練序列重新劃分為N個胞腔。計算新的平均失真和相對失真，判斷新的失真是否滿足門限條件，如果滿足則退出勞埃德迭代否則繼續(xù)進行勞埃德迭代直到滿足門限條件，生成碼書。LBG算法的關(guān)鍵代碼如下：

flag=0;//循環(huán)標識

tcb(s,tv);//訓(xùn)練集和碼本建立關(guān)系

for(inti=0;i<N;i++)

{for(intj=0;j<tv.M;j++)

{if(s[j]==i)n++;

yn[i]=n;

}}dsum=0;

for(inti=0;i<tv.M;i++)

{dsum=dsum+(long)min1(tv.train[i],1);

}d1=(do