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

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

As the rapid development of communications and information technology, data compression technology has become a powerful tool for people to work or do the scientific research on this information age. As a study of important issues on information research, data compression technology has been pay much attention to. Vector Quantization Technology, as an important branch in the field of data compression, with its excellent characteristics: high compression, encoding speed, clear and simple algorithm, has become powerful tools and methodologies in the area of image compression.
Aimed to the application with the way to Vector Quantization in the Static image of research goals, this thesis show you the detailed explanation of the basic Vector Quantization principle, related concepts and development status, the discussion the three technology key of Vector Quantization — code book design algorithm, code searching and code distribution. In detail elaborated LBG algorithm and most greatly drops which we can called MD algorithm in the code book design algorithm, based on inequality quick code-search in quick code-search and BAS algorithm and Prohibition search symbol index distribution algorithm in symbol index distribution. Finally, I analyzed the existing typical algorithm and improving algorithm, come up with my own realization based on the method of Vector Quantization and achieve good results.
KEYWORDS：data compression Vector Quantization LBG

目 錄

摘 要 I
ABSTRACT II
第一章 緒論 1
1．1 課題的研究背景及意義 1
1．2課題研究現(xiàn)狀 2
1．3 課題研究?jī)?nèi)容 3
第二章 矢量量化技術(shù)簡(jiǎn)介 4
2．1 數(shù)據(jù)壓縮技術(shù) 4
2．2 矢量量化的定義及理論基礎(chǔ) 8
2．3 矢量量化的相關(guān)概念 10
2．4 矢量量化的關(guān)鍵技術(shù)及技術(shù)指標(biāo) 13
第三章 矢量量化的算法研究 16
3．1 矢量量化碼書(shū)設(shè)計(jì)算法的研究 16
3．1．1 經(jīng)典的LBG算法 16
3．1．2 MD算法 18
3．1．3 碼書(shū)設(shè)計(jì)算法比較 19
3．2 碼字搜索算法 20
3．2．1 基于不等式的快速碼字搜索算法 20
3．2．2 等均值等方差最近鄰搜索算法 21
3．3 碼字索引分配算法 23
3．3．1 BSA算法 23
3．3．2 禁止搜索碼字索引算法 25
第四章 矢量量化算法的實(shí)現(xiàn) 26
4．1 需求分析與整體設(shè)計(jì) 26
4．1．1需求分析 26
4．1．2 整體設(shè)計(jì) 26
4．2 矢量量化算法的實(shí)現(xiàn)過(guò)程及說(shuō)明 27
4．2．1 初始碼書(shū)的生成 27
4．2．2 LBG矢量量化 28
4．2．3 矢量量化碼字索引與恢復(fù) 31
4．3 實(shí)驗(yàn)結(jié)果及評(píng)價(jià) 31
第五章 結(jié)論與展望 34
參考文獻(xiàn) 35
致 謝 36
附錄 37

摘 要

伴隨著通訊與信息科技的迅猛發(fā)展，數(shù)據(jù)壓縮技術(shù)己經(jīng)成為信息時(shí)代人們工作與科研的有力工具。數(shù)據(jù)壓縮技術(shù)，作為信息論研究中的一個(gè)重要課題，一直受到人們的廣泛關(guān)注。矢量量化技術(shù)作為數(shù)據(jù)壓縮領(lǐng)域里的一個(gè)重要分支，以它壓縮比高、編碼速度快、算法簡(jiǎn)單清晰等良好的特性，在圖像壓縮等領(lǐng)域都已成為有力的手段和方法。
本文以矢量量化在靜止圖像方面的應(yīng)用為研究目標(biāo)，介紹了矢量量化的定義，基本理論、相關(guān)概念及發(fā)展現(xiàn)狀，重點(diǎn)討論研究了矢量量化的三大關(guān)鍵技術(shù)–碼書(shū)生成和碼字搜索和碼字索引分配。詳細(xì)闡述了碼書(shū)設(shè)計(jì)算法中的LBG算法和最大下降MD算法；快速碼字搜索中的基于不等式快速碼字搜所和碼字索引分配中的BAS算法和禁止搜索碼字索引算法等。
最后總結(jié)分析了現(xiàn)有典型的算法和改進(jìn)算法并提出了自己的基于矢量量化算法的實(shí)現(xiàn)方法，編程實(shí)現(xiàn)了一個(gè)完整的數(shù)據(jù)壓縮軟件，取得了較好的效果。

關(guān)鍵詞： 數(shù)據(jù)壓縮，矢量量化，LBG
ABSTRACT
第一章 緒論
1．1 課題的研究背景及意義
1．1．1 研究背景
隨著計(jì)算機(jī)和大規(guī)模集成電路的飛速發(fā)展，數(shù)字信號(hào)分析和處理技術(shù)得到很大發(fā)展，并已經(jīng)廣泛應(yīng)用于通信、雷達(dá)和自動(dòng)化等領(lǐng)域。數(shù)字信號(hào)的突出優(yōu)點(diǎn)是便于傳輸、存儲(chǔ)、交換、加密和處理等。一個(gè)模擬信號(hào)f(t)，只要它的頻帶有限并允許一定的失真，往往可以經(jīng)過(guò)采樣變成時(shí)間離散但幅值連續(xù)的采樣信號(hào)f(n)。對(duì)于數(shù)字系統(tǒng)來(lái)說(shuō)，f(n)還需經(jīng)過(guò)量化變成時(shí)間和幅值均離散的數(shù)字信號(hào)x(n)。
通信系統(tǒng)有兩大類(lèi)：一類(lèi)是傳輸模擬信號(hào)f(t)的模擬通信系統(tǒng)；另一類(lèi)是傳輸數(shù)字信號(hào)x(n)的數(shù)字通信系統(tǒng)。在任何數(shù)據(jù)傳輸系統(tǒng)中，人們總希望只傳輸所需要的信息并以最小失真或者零失真來(lái)接收這些信息。人們常用有效性（傳輸效率）和可靠性（抗干擾能力）來(lái)描述傳輸系統(tǒng)的性能。與模擬通信系統(tǒng)相比，數(shù)字通信系統(tǒng)具有抗干擾能力強(qiáng)，保密性好，可靠性高，便于傳輸、存儲(chǔ)、交換和處理等優(yōu)點(diǎn)。在數(shù)字通信中，碼速率高不僅影響傳輸效率，而且增加了存儲(chǔ)和處理的負(fù)擔(dān)。
上個(gè)世紀(jì)八、九十年代，計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)取得了飛速的發(fā)展，人類(lèi)社會(huì)進(jìn)入到了前所未有的信息化時(shí)代。隨著信息時(shí)代的來(lái)臨人們對(duì)通信業(yè)務(wù)的要求不斷增長(zhǎng)，在日常生活中，大量的信息數(shù)據(jù)需要傳輸、存儲(chǔ)和處理?？茖W(xué)實(shí)驗(yàn)表明，人類(lèi)從外界獲取的知識(shí)之中，有80%以上都是通過(guò)視覺(jué)感知獲取的【1】。眼睛獲取的是圖像信息，和語(yǔ)音、文字等信息相比，圖像包含的信息量更大、更直觀、更確切，因而具有更高的使用效率和更廣泛的適應(yīng)性，一幅圖勝過(guò)千言萬(wàn)語(yǔ)， 圖像信息是人類(lèi)認(rèn)識(shí)世界、自身的重要源泉。所以在信息數(shù)據(jù)中，絕大部分?jǐn)?shù)據(jù)都是圖像數(shù)據(jù)，而圖像數(shù)據(jù)的傳輸常常要占用很大的帶寬，需要很大的存儲(chǔ)空間，因而怎樣對(duì)圖像數(shù)據(jù)進(jìn)行行之有效地傳輸是一個(gè)極具挑戰(zhàn)性的課題。
數(shù)字圖像中包含的數(shù)據(jù)量十分巨大，例如，800 x 600分辯率的真彩色圖像，其數(shù)據(jù)量為800 x 600 x 3=1440000字節(jié)，約1.4MB；而一分鐘CD音質(zhì)的音頻文件一般需要l OMB左右的存儲(chǔ)空間。在視頻傳輸中PAL制式(25幀/秒)下，畫(huà)面分辨率為640 x 480下，真彩色(24位)的圖像序列，播放1秒鐘的視頻畫(huà)面數(shù)據(jù)量為：640 x 480 x 3 x 25 = 23,040,000字節(jié)，相當(dāng)于存貯一千多萬(wàn)個(gè)漢字所占用的空間。如此龐大的數(shù)據(jù)量，給圖像的傳輸、存貯、傳輸線的傳輸率(帶寬)以及計(jì)算機(jī)的處理速度等增加巨大的壓力。由此可見(jiàn)，對(duì)降低傳輸成本，增加數(shù)據(jù)傳輸?shù)目煽啃?，不斷滿(mǎn)足人們對(duì)信息傳輸?shù)男枨?，圖像壓縮都具有十分重要的作用。為了解決好這個(gè)問(wèn)題，我們就必須對(duì)圖像進(jìn)行編碼壓縮，在保證一定圖像質(zhì)量的前提下，有效地減少傳輸時(shí)所需的數(shù)據(jù)量和占用的頻帶。
1．1．2 研究意義
圖像壓縮就是在沒(méi)有明顯失真的前提下，將圖像的位圖信息轉(zhuǎn)變成另外一種能將數(shù)據(jù)量縮減的表達(dá)形式，即去處冗余信息。首先，盡管圖像中數(shù)據(jù)量很大，但其行、列以及幀間都具有極強(qiáng)的相關(guān)性或冗余信息。即一個(gè)象素的灰度值，總是和它周?chē)南笏氐幕叶戎涤兄撤N關(guān)系，可以由它們推算表示出來(lái)，應(yīng)用某種方法提取或減少它們之間的這種相關(guān)性，即可實(shí)現(xiàn)圖像壓縮。其次，大部分圖像視頻信號(hào)的最終接收者都是人眼，而人類(lèi)的視覺(jué)系統(tǒng)是一種高度復(fù)雜的系統(tǒng)，它能從極為雜亂的圖像中抽象出有意義的信息，并以非常精練的形式反映給大腦。人眼對(duì)圖像中的不同部分的敏感程度是不同的，如果去除圖像中對(duì)人眼不敏感或意義不大的部分，對(duì)圖像的主觀質(zhì)量是不會(huì)有很大影響的，也實(shí)現(xiàn)了圖像壓縮。正由于圖像壓縮的必要性和可能性，圖像壓縮編碼研究成為一個(gè)越來(lái)越活躍的領(lǐng)域。在諸如基于Internet的多媒體通信、可視電話、數(shù)字電視，多媒體計(jì)算機(jī)等領(lǐng)域得到了廣泛的應(yīng)用。
1．2課題研究現(xiàn)狀
矢量量化的基本理論早在二十世紀(jì)六七十年代已有人關(guān)注，而在二十世紀(jì)八十年代開(kāi)始逐步完善起來(lái)。矢量量化是分組量化的一種，受到廣泛注意和使用的分組量化方法是由黃和舒爾泰斯于1963年首先提出來(lái)的【2】，他們指出分組量化的實(shí)現(xiàn)方法:首先與正交矩陣相乘將相關(guān)的采樣變換為不相關(guān)的采樣，然后再在每組固定的總比特?cái)?shù)限制下，將不同的量化比特?cái)?shù)目分配給每個(gè)不相關(guān)的采樣值。1979年，格爾肖在他的論文【3】中詳細(xì)闡述了分組量化的一般性理論，它將貝內(nèi)特早年關(guān)于均方誤差準(zhǔn)則的量化模型推廣到分組量化中。
將矢量量化技術(shù)推向研究高潮和推廣應(yīng)用應(yīng)歸功于1980年由Linde. Buzo和Gray提出來(lái)的一種有效的LBG矢量量化碼書(shū)設(shè)計(jì)方法【4】，該文獻(xiàn)己經(jīng)成為矢量量化的經(jīng)典文獻(xiàn)，是矢量量化技術(shù)發(fā)展的基石。
在20多年歷程中，學(xué)者們?cè)谝韵挛鍌€(gè)方面對(duì)矢量量化技術(shù)展開(kāi)研究：
1. 針對(duì)基本矢量量化器復(fù)雜度大和比特率固定的缺點(diǎn)，開(kāi)發(fā)其它類(lèi)型的矢量量化器；
2. 針對(duì)基本矢量量化器的LBG碼書(shū)設(shè)計(jì)算法容易陷入局部極小、初始碼書(shū)影響優(yōu)化結(jié)果和計(jì)算量大的缺點(diǎn)，學(xué)者們引入了神經(jīng)網(wǎng)絡(luò)、優(yōu)化理論、模糊集合等技術(shù)，提出了各種各樣的碼書(shū)設(shè)計(jì)算法；
3.在矢量量化編碼場(chǎng)合中，針對(duì)基本矢量量化器的窮盡搜索編碼算法的計(jì)算量大和比特率固定的缺點(diǎn)，提出各種各樣的快速碼字搜索算法和變比特率碼字搜索算法；
4. 矢量量化技術(shù)的應(yīng)用；
5. 考慮到信道噪聲將會(huì)在矢量量化解碼端引入額外失真，學(xué)者們開(kāi)始研究碼字索引分配算法以減少由于信道噪聲引起的失真。
1．3 課題研究?jī)?nèi)容
1. 研究?jī)?nèi)容
1）對(duì)數(shù)據(jù)壓縮的基本理論、技術(shù)標(biāo)準(zhǔn)、評(píng)價(jià)方法進(jìn)行研究和分析
2）對(duì)基于矢量量化的數(shù)據(jù)壓縮算法及其衍生算法進(jìn)行邏輯上的分析和比較
3）選擇矢量量化算法中的一種算法進(jìn)行實(shí)現(xiàn)，完成一個(gè)完整的數(shù)據(jù)壓縮軟件
2. 本文結(jié)構(gòu)安排
第一章為緒論，主要介紹了課題的研究背景，簡(jiǎn)要地闡述課題的研究意義最后，總結(jié)了本論文的研究?jī)?nèi)容。
第二章中，首先對(duì)數(shù)據(jù)壓縮作了簡(jiǎn)要的綜述；然后介紹了矢量量化數(shù)據(jù)壓縮算法的起源，發(fā)展和相關(guān)的數(shù)學(xué)模型及理論基礎(chǔ)；最后寫(xiě)了矢量量化的關(guān)鍵技術(shù)和矢量量化技術(shù)指標(biāo)。
第三章是對(duì)矢量量化算法的研究，首先分別論述了矢量量化的三大關(guān)鍵技術(shù)的算法，介紹了碼書(shū)設(shè)計(jì)中的LBG算法和最大下降算法；碼字搜索算法中的基于不等式的快速碼字搜索算法和等均值等方差最近鄰搜索算法；碼字索引分配算法中的BSA算法和禁止搜索碼字索引算法。
第四章是矢量量化算法的實(shí)現(xiàn)。詳細(xì)介紹了矢量量化算法的實(shí)現(xiàn)過(guò)程，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析和評(píng)價(jià)。

第二章 矢量量化技術(shù)簡(jiǎn)介
2．1 數(shù)據(jù)壓縮技術(shù)
2．1．1數(shù)據(jù)壓縮技術(shù)的發(fā)展
數(shù)據(jù)壓縮的研究過(guò)程一直有兩個(gè)發(fā)展方向【5】：一個(gè)是許多數(shù)學(xué)家所致力于的建立信源和數(shù)據(jù)壓縮的數(shù)學(xué)模型，并從中找出衡量數(shù)據(jù)壓縮質(zhì)量的技術(shù)指標(biāo)及最優(yōu)壓縮性能指標(biāo)；另一個(gè)則是眾多的工程技術(shù)人員所進(jìn)行的工作，他們的研究重點(diǎn)為建立一個(gè)能實(shí)現(xiàn)數(shù)據(jù)壓縮功能的系統(tǒng)，以服務(wù)于工程應(yīng)用，或者對(duì)這些數(shù)據(jù)壓縮系統(tǒng)進(jìn)行分析或模擬，以確定它們的性能指標(biāo)。
不論是理論研究還是工程實(shí)踐，1977年以前，數(shù)據(jù)壓縮作為信息論研究中的一項(xiàng)內(nèi)容，主要是有關(guān)信息嫡，數(shù)據(jù)壓縮比和各種編碼方法的研究，即按某種方法對(duì)源數(shù)據(jù)流進(jìn)行編碼，使得經(jīng)過(guò)編碼的數(shù)據(jù)流比原數(shù)據(jù)流占用較少的空間。其中基于符號(hào)頻率統(tǒng)計(jì)的霍夫曼編碼具有良好的壓縮性能，一直占據(jù)重要的地位，不斷有基于霍夫曼編碼的改進(jìn)算法提出。
隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，數(shù)據(jù)壓縮作為解決海量信息存儲(chǔ)和傳輸?shù)闹渭夹g(shù)受到人們的極大關(guān)注。1977年，兩位以色列科學(xué)家Jacob Ziv和Abraham Lempel發(fā)表了論文”A universal algorithm for sequential data compression”，提出了不同于以往的基于字典的壓縮算法LZ77【5】。1978年，又推出了改進(jìn)算法LZ78。他們的研究把無(wú)失真壓縮的研究推向了一個(gè)全新的階段。
隨著信號(hào)處理研究的不斷的發(fā)展，數(shù)字圖像信號(hào)、語(yǔ)音信號(hào)等都被大量的引入到有關(guān)的領(lǐng)域中。由于圖像信息占用較多的存儲(chǔ)空間，而圖像通信又是目前非話業(yè)務(wù)的主流，因此數(shù)據(jù)壓縮技術(shù)在圖像通信中得到了最廣泛的應(yīng)用。
在圖像編碼中，最早研究的是預(yù)測(cè)編碼，曾作為經(jīng)典理論而登載于各種專(zhuān)著，并得到廣泛的應(yīng)用。近年來(lái)，隨著神經(jīng)網(wǎng)絡(luò)理論的興起，有人采用BP網(wǎng)進(jìn)行非線性預(yù)測(cè)的嘗試，并取得了較好的效果。
1969年，在美國(guó)舉行首屆”圖形編碼會(huì)議”，表明圖像編碼以獨(dú)立的學(xué)科擠身于學(xué)術(shù)界。而變換編碼在五年左右的時(shí)間內(nèi)成為研究熱點(diǎn)。變換編碼中的DCT編碼由于編碼效果較好，運(yùn)算復(fù)雜度適中等優(yōu)點(diǎn)，已經(jīng)發(fā)展成為目前國(guó)際圖像編碼標(biāo)準(zhǔn)的核心算法。
80年代中后期，眾多研究者相繼提出了在多個(gè)分辨率下表示圖像的方案，主要的方法有：子代編碼，金字塔編碼，小波變換編碼等?；谛〔ㄗ儞Q的方法具有較高的壓縮性能，己發(fā)展為JPEG 2000的核心算法。在近年來(lái)的甚低碼率的編碼研究中，有一種稱(chēng)之為模型基的編碼方法頗引人注意，這種方法壓縮比高，但適用于場(chǎng)景比較簡(jiǎn)單的特定場(chǎng)合。
在1988年左右，有人提出了一種分形圖像編碼的壓縮方案。這種方案思路新穎、壓縮潛力大、并具有解碼分辨率無(wú)關(guān)性等優(yōu)點(diǎn)，是一種很有潛力的編碼方法。
盡管用軟件壓縮方法可以較好地實(shí)現(xiàn)數(shù)據(jù)壓縮的目的，但由于壓縮算法的運(yùn)算量較大，需要很高的運(yùn)算速度和存儲(chǔ)空間，這對(duì)現(xiàn)有系統(tǒng)來(lái)說(shuō)是很大的負(fù)擔(dān)。為了解決這個(gè)問(wèn)題，人們?cè)诶^續(xù)探索數(shù)據(jù)壓縮技術(shù)的同時(shí)，著手研制生產(chǎn)高性能的芯片和系統(tǒng)。一般在對(duì)時(shí)間要求不高的場(chǎng)合采用軟件壓縮，而對(duì)運(yùn)行速度有特殊要求的情況下，可使用硬件壓縮。不過(guò)，目前硬件壓縮的開(kāi)銷(xiāo)遠(yuǎn)遠(yuǎn)大于軟件壓縮的開(kāi)銷(xiāo)。
2．1．2 數(shù)據(jù)壓縮技術(shù)的分類(lèi)
數(shù)據(jù)壓縮的研究已有幾十年的歷史，其間，人們提出了各種各樣的壓縮算法。在分類(lèi)上，也存在幾種不同的方法，有人按編碼失真程度或者說(shuō)按壓縮過(guò)程的可逆性將數(shù)據(jù)壓縮編碼分為兩種類(lèi)型:無(wú)失真壓縮編碼 (Noiseless Coding)與有失真壓縮編碼 (Noise Coding)；有人按編碼基建模的不同將數(shù)據(jù)壓縮分成模型基編碼和波形基編碼；又有人將它分為第一代壓縮編碼和第二代壓縮編碼；還可按壓縮技術(shù)所使用的方法進(jìn)行分類(lèi)，可分為預(yù)測(cè)編碼(Predictive Coding)、變換編碼(Transform Coding)和統(tǒng)計(jì)編碼(Statistical Coding)三大類(lèi)。目前，較為認(rèn)可的是第一種分類(lèi)方法【6】。
1．無(wú)失真壓縮
無(wú)失真壓縮也可稱(chēng)之為冗余度壓縮(Redundancy Compression)，在數(shù)字圖象壓縮中，有3種基本的數(shù)據(jù)冗余：編碼冗余、像素間冗余以及心理視覺(jué)冗余。而無(wú)失真壓縮就是利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，除去或盡量除去數(shù)據(jù)中重復(fù)和冗余部分，而不丟失其中的任何信息，可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為2:1到5: 1這類(lèi)方法廣泛用于文本數(shù)據(jù)、程序和特殊應(yīng)用場(chǎng)合的圖像數(shù)據(jù)(如醫(yī)學(xué)圖像等)的壓縮.由于壓縮比的限制，僅使用無(wú)損壓縮方法不可能解決圖像和數(shù)字視頻的存儲(chǔ)和傳輸問(wèn)題。
常用的無(wú)失真壓縮技術(shù)有：哈夫曼編碼，算術(shù)編碼，游程編碼，LZ編碼等。
1）行程長(zhǎng)度編碼（RLE）
行程長(zhǎng)度編碼（run-length encoding）是壓縮一個(gè)文件最簡(jiǎn)單的方法之一。它的做法就是把一系列的重復(fù)值（例如圖象像素的灰度值）用一個(gè)單獨(dú)的值再加上一個(gè)計(jì)數(shù)值來(lái)取代。比如有這樣一個(gè)字母序列aabbbccccccccdddddd它的行程長(zhǎng)度編碼就是2a3b8c6d。這種方法實(shí)現(xiàn)起來(lái)很容易，而且對(duì)于具有長(zhǎng)重復(fù)值的串的壓縮編碼很有效。例如對(duì)于有大面積的連續(xù)陰影或者顏色相同的圖象，使用這種方法壓縮效果很好。很多位圖文件格式都用行程長(zhǎng)度編碼，例如TIFF，PCX，GEM等。
2）LZW編碼
這是三個(gè)發(fā)明人名字的縮寫(xiě)（Lempel，Ziv，Welch），其原理是將每一個(gè)字節(jié)的值都要與下一個(gè)字節(jié)的值配成一個(gè)字符對(duì)，并為每個(gè)字符對(duì)設(shè)定一個(gè)代碼。當(dāng)同樣的一個(gè)字符對(duì)再度出現(xiàn)時(shí)，就用代號(hào)代替這一字符對(duì)，然后再以這個(gè)代號(hào)與下個(gè)字符配對(duì)。LZW編碼原理的一個(gè)重要特征是，代碼不僅僅能取代一串同值的數(shù)據(jù)，也能夠代替一串不同值的數(shù)據(jù)。在圖像數(shù)據(jù)中若有某些不同值的數(shù)據(jù)經(jīng)常重復(fù)出現(xiàn)，也能找到一個(gè)代號(hào)來(lái)取代這些數(shù)據(jù)串。在此方面，LZW壓縮原理是優(yōu)于RLE的。
3）霍夫曼編碼
霍夫曼編碼（Huffman encoding）是通過(guò)用不固定長(zhǎng)度的編碼代替原始數(shù)據(jù)來(lái)實(shí)現(xiàn)的?；舴蚵幋a最初是為了對(duì)文本文件進(jìn)行壓縮而建立的，迄今已經(jīng)有很多變體。它的基本思路是出現(xiàn)頻率越高的值，其對(duì)應(yīng)的編碼長(zhǎng)度越短，反之出現(xiàn)頻率越低的值，其對(duì)應(yīng)的編碼長(zhǎng)度越長(zhǎng)。
2．有失真壓縮
有失真壓縮也可稱(chēng)為嫡壓縮(Entropy Compression)，這是一種不可逆壓縮。他利用了人類(lèi)視覺(jué)對(duì)圖像中的某些頻率成分不敏感的特性，在壓縮過(guò)程中會(huì)損失掉一部分信息，這樣，其原始數(shù)據(jù)不能由壓縮數(shù)據(jù)完全恢復(fù)出來(lái)。他是以丟失部分信息為代價(jià)而獲得較高的壓縮率。當(dāng)然，為了確?；謴?fù)后的數(shù)據(jù)能基本保持原數(shù)據(jù)的特征，這種失真應(yīng)該限制在某個(gè)規(guī)定的范圍之內(nèi)。無(wú)失真壓縮主要有兩大類(lèi)型：特征抽取和量化方法，特征抽取的典型例子如指紋、漢字的模式識(shí)別，一旦抽取出足以有效表征與區(qū)分不同模式的特征參數(shù)，便可用它取代原始的圖像數(shù)據(jù)，這一類(lèi)方法一般是用于特定的環(huán)境。量化則是更為通用的熵壓縮技術(shù)，除了直接對(duì)無(wú)記憶信源的單個(gè)樣本做所謂的零記憶量化外，還可以對(duì)有記憶信源的多個(gè)相關(guān)樣本映射到不同的空間，去除了原始數(shù)據(jù)中相關(guān)性后再做量化處理，由此又引出了預(yù)測(cè)編碼和變換編碼。
1）矢量量化編碼
矢量量化編碼利用相鄰圖象數(shù)據(jù)間的高度相關(guān)性，將輸入圖象數(shù)據(jù)序列分組，每一組m個(gè)數(shù)據(jù)構(gòu)成一個(gè)m維矢量，一起進(jìn)行編碼，即一次量化多個(gè)點(diǎn)。根據(jù)仙農(nóng)率失真理論，對(duì)于無(wú)記憶信源，矢量量化編碼總是優(yōu)于標(biāo)量量化編碼。
2）預(yù)測(cè)及內(nèi)插編碼
一般在圖象中局部區(qū)域的象素是高度相關(guān)的，因此可以用先前的象素的有關(guān)灰度知識(shí)來(lái)對(duì)當(dāng)前象素的灰度進(jìn)行預(yù)計(jì)，這就是預(yù)測(cè)。而所謂內(nèi)插就是根據(jù)先前的和后來(lái)的象素的灰度知識(shí)來(lái)推斷當(dāng)前象素的灰度情況。如果預(yù)測(cè)和內(nèi)插是正確的，則不必對(duì)每一個(gè)象素的灰度都進(jìn)行壓縮，而是把預(yù)測(cè)值與實(shí)際象素值之間的差值經(jīng)過(guò)熵編碼后發(fā)送到接收端。在接收端通過(guò)預(yù)測(cè)值加差值信號(hào)來(lái)重建原象素。
3）變換編碼
變換編碼就是將圖象光強(qiáng)矩陣（時(shí)域信號(hào)）變換到系數(shù)空間（頻域信號(hào)）上進(jìn)行處理的方法。在空間上具有強(qiáng)相關(guān)的信號(hào)，反映在頻域上是某些特定的區(qū)域內(nèi)能量常常被集中在一起，或者是系數(shù)矩陣的分布具有某些規(guī)律。我們可以利用這些規(guī)律在頻域上減少量化比特?cái)?shù)，達(dá)到壓縮的目的。由于正交變換的變換矩陣是可逆的且逆矩陣與轉(zhuǎn)置矩陣相等，這就使解碼運(yùn)算是有解的且運(yùn)算方便，因此運(yùn)算矩陣總是選用正交變換來(lái)做。

圖2.1 數(shù)據(jù)壓縮技術(shù)的分類(lèi)
2．1．3 數(shù)據(jù)壓縮算法的度量標(biāo)準(zhǔn)
對(duì)于一種數(shù)據(jù)壓縮算法的性能，有一定的衡量標(biāo)準(zhǔn)，為了后面幾章描述的方便，也為不至于產(chǎn)生歧義，對(duì)這些標(biāo)準(zhǔn)作以簡(jiǎn)單的介紹【7】。
1．算法性能評(píng)價(jià)
1）壓縮比（CR：Compression Ratio）：
壓縮比定義為原始數(shù)據(jù)量與壓縮后量的比值，即
壓縮比 = 原始數(shù)據(jù)量/壓縮后量
2）計(jì)算復(fù)雜度：
計(jì)算復(fù)雜度可以用算法處理一定量數(shù)據(jù)所需的基本運(yùn)算次數(shù)來(lái)度量。如處理一幀有確定的分辨率和顏色數(shù)的圖像所需的加法次數(shù)和乘法次數(shù)。
壓縮算法分為編碼部分和解碼部分，如果兩者的計(jì)算復(fù)雜度大至相當(dāng)，則算法稱(chēng)為對(duì)稱(chēng)的，反之稱(chēng)為非對(duì)稱(chēng)的。
2．圖像質(zhì)量評(píng)價(jià)
1）均方誤差（MSE）
對(duì)于模擬信號(hào)，設(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， 又稱(chēng)為均方誤差（Mean Squared Error）。
2）信噪比（SNR）：
對(duì)于離散信號(hào)，設(shè)原始數(shù)據(jù)為 ，編碼、解碼后的數(shù)據(jù)為 ，它們的差值為 的均方誤差為 ，信噪比（Signal to Noise Ratio）定義為原始數(shù)據(jù)方差 與重建數(shù)據(jù)誤差方差 的比值如公式2.2所示：
（2.2）
3）峰值信噪比（PSNR）：
對(duì)于離散圖像數(shù)據(jù)，在信噪比的計(jì)算中常用圖像數(shù)據(jù)中的最大值xmax來(lái)代替均方根值бx，得到峰值信噪比如公式2.3所示
（2.3）
2．2 矢量量化的定義及理論基礎(chǔ)
2．2．1 矢量量化的起源及發(fā)展
矢量量化基本理論早在20世紀(jì)六七十年代己有人關(guān)注，八十年代開(kāi)始逐步發(fā)展完善起來(lái)。1956年，Steinhaus第一次系統(tǒng)闡述了最佳矢量量化問(wèn)題【8】；1978年，Buzo第一個(gè)提出實(shí)際的矢量量化器。1980年，Linde, Buzo和Gray將Loyd-Max算法推廣，提出了一種有效的矢量量化碼書(shū)設(shè)計(jì)算法一一LBG【4】算法，將矢量量化技術(shù)的研究和推廣應(yīng)用推向了高潮，成為矢量量化技術(shù)發(fā)展的里程碑。
在20多年的發(fā)展歷程中，人們?nèi)嫜芯苛耸噶苛炕睦碚摵蛻?yīng)用，開(kāi)發(fā)了多種類(lèi)型的矢量量化器。雖然矢量量化技術(shù)研究已經(jīng)日趨成熟，但仍存在很多有待解決的問(wèn)題，如矢量量化碼書(shū)標(biāo)準(zhǔn)與編碼對(duì)象密切相關(guān)，不同應(yīng)用場(chǎng)合下碼書(shū)結(jié)構(gòu)、尺寸以及矢量維數(shù)都不相同。矢量量化的壓縮標(biāo)準(zhǔn)也一直沒(méi)有提出。目前的研究大多停留在理論方面，各種優(yōu)化的矢量量化器的硬件實(shí)現(xiàn)還有待于進(jìn)一步的研究。因此，有關(guān)矢量量化技術(shù)的研究還有很多工作要做。
矢量量化在20多年的發(fā)展歷程中，主要是從以下幾方面得到了發(fā)展：
(1) 矢量量化器的研究，對(duì)基本矢量量化器復(fù)雜度大和比特率固定的缺點(diǎn)，開(kāi)發(fā)其它類(lèi)型的矢量量化器；
(2) 矢量量化碼書(shū)設(shè)計(jì)算法研究：針對(duì)基本矢量量化器的LBG碼書(shū)設(shè)計(jì)算法 容易陷入局部極小、初始碼書(shū)影響優(yōu)化結(jié)果和計(jì)算量大的缺點(diǎn)，學(xué)者們引入神經(jīng) 網(wǎng)絡(luò)、優(yōu)化理論、模糊集合等技術(shù)，提出了各種各樣的碼書(shū)設(shè)計(jì)算法；
(3) 矢量量化碼字搜索算法研究：在矢量量化編碼場(chǎng)合中，針對(duì)基木矢量量 化器的窮盡搜索編碼算法的計(jì)算量大和比特率固定的缺點(diǎn)提出各種各樣的快速 碼字搜索算法和變化特率碼字搜索算法；
(4) 矢量量化碼字索引分配算法研究：考慮到信道噪聲將會(huì)在矢量量化解碼端引入額外失真，學(xué)者們開(kāi)始研究碼字索引分配算法以減少信道引起的失真。
2．2．2 矢量量化的定義及理論基礎(chǔ)
1. 定義
一個(gè)維數(shù)為k，尺寸為N的矢量量化器可以定義為從k維歐兒里得空間 到一個(gè)包含N個(gè)輸出(重構(gòu))點(diǎn)的有限集合C的映射Q【9】，表示為公式（2.4）：
（2.4）
其中， 。
C是重構(gòu)碼字矢量集合，稱(chēng)為碼書(shū)，其尺寸(大小)為N。碼書(shū)的N個(gè)元素Yi稱(chēng)為碼字或者碼矢量，它們均為k維歐幾里得空間 中的矢量。輸入矢量空間 通過(guò)尺寸為N的矢量量化器Q后，被分割成N個(gè)互不重疊的區(qū)域又稱(chēng)為胞腔，這個(gè)過(guò)程稱(chēng)為輸入矢量空間的劃分。對(duì) 胞腔 定義為公式（2.5）：
（2.5）
2. 理論基礎(chǔ)
矢量量化的理論基礎(chǔ)是香農(nóng)的率失真理論。1948年，香農(nóng)定義了信道容量，并證明只要編碼速率不超過(guò)信道容量，符號(hào)就能以任意小的差錯(cuò)概率在該信道中傳輸。1959年，香農(nóng)定義了率失真函數(shù)R(D)，并證明只要R(D)不超過(guò)信道容量就能保證接收端的失真不超過(guò)給定閾值D。在數(shù)學(xué)上，R (D)定義為在給定失真D的條件下，系統(tǒng)所能夠達(dá)到的最小碼速率。對(duì)于幅值離散的信源， R(D)定義如下公式（2.6）所示:
（2.6）
其中， ，平均失真滿(mǎn)足公式2.7：
（2.7）
式中d(X,Y)是失真測(cè)度，它表示輸出采樣值Y再現(xiàn)原始采樣值X所引入的失真， P(Y/X)表示在己發(fā)送X的情況下接收到Y(jié)的概率。R(D)的單位為比特/采樣。同樣，也可以定義失真率函數(shù)D(R)，它是率失真函數(shù)的逆函數(shù)，其含義為在定速率不超過(guò)R的條件下，系統(tǒng)所能夠達(dá)到的最小失真，它是在維數(shù)k趨向無(wú)窮大時(shí)Dk(R)的極限，即 。
香農(nóng)理論表明在速率受限的條件下或在平均失真受限的情況下，通信系統(tǒng)所能達(dá)到的最優(yōu)性能。率失真函數(shù)通常又被作為理論最優(yōu)值，如果一個(gè)系統(tǒng)的性能低于理論最優(yōu)值，則一定可用更好的編碼技術(shù)獲得系統(tǒng)性能的改善；如果一個(gè)系統(tǒng)的性能接近理論最優(yōu)值，則此系統(tǒng)已接近最優(yōu)，無(wú)法再做太多改善；一個(gè)系統(tǒng)的性能不可能優(yōu)于理論最優(yōu)值。由香農(nóng)理淪可知，理論上，矢量量化技術(shù)只要不斷的增加矢量的維數(shù)k，編碼的性能就可任意接近率失真函數(shù)，使系統(tǒng)性能達(dá)到最優(yōu)。因此，香農(nóng)的率失真理論指出了矢量量化技術(shù)的優(yōu)越性，是矢量量化技術(shù)的理論基礎(chǔ)。
2．3 矢量量化的相關(guān)概念
2．3．1 數(shù)學(xué)模型
設(shè)有一個(gè)信源采樣數(shù)據(jù)序列，我們把每K個(gè)數(shù)據(jù)分成一組，每組數(shù)據(jù)都記錄成矢量形式 (i =1,2 ,…,N )，稱(chēng)x為輸入矢量。設(shè) 為一個(gè)K維輸入矢量的集合。
再把T劃分成M( (2.8)
通常，我們把這M個(gè)子空間稱(chēng)為Voronoi胞腔(Cells)，或者簡(jiǎn)稱(chēng)胞腔，有時(shí)也把它稱(chēng)為一個(gè)分類(lèi)或分區(qū)。在每個(gè)胞腔R，中我們?cè)僬业揭粋€(gè)代表元Yi,我們稱(chēng)所有這些代表元組成的集合C=( )為碼書(shū)(Codebook)。這些代表元也稱(chēng)為碼字(Codeword)集合1= (1,2,…, M}稱(chēng)為碼字的索引集合。一個(gè)矢量量化器包括編碼器和解碼器兩部分。編碼器主要包括一個(gè)碼書(shū)和一個(gè)量化器。
量化器Q(X)定義如式(2.9)：
Q: T C；
當(dāng)X 時(shí)，Q (X)= Yi (i=1 ,2,…,M). (2.9)
其中，Q(X)是一個(gè)多對(duì)一的函數(shù)，因此它是不可逆的。解碼器主要包括一個(gè)與編碼器相同的碼書(shū)和一個(gè)碼字檢索器 (i)。
碼字檢索器 (i)定義如式（2.10）：
: I C；
(i) = Yi，i=1,2,…,M. (2.10)
矢量量化的模型如下圖2.2所示：
編碼時(shí)：對(duì)任意一個(gè)輸入的K維矢量X，計(jì)算Q(X)的值Yi，通過(guò)傳輸信道發(fā)送碼字Yi的索引i到解碼器端。
解碼時(shí)：對(duì)輸入的一個(gè)索引號(hào)i，查找碼書(shū)中對(duì)應(yīng)的碼字Yi，輸出Yi作為整個(gè)系統(tǒng)對(duì)矢量X的壓縮恢復(fù)值。
圖2.2矢量量化器結(jié)構(gòu)示意圖
2．3．2 量化器Q(x)相關(guān)問(wèn)題
我們可以看出矢量量化可以等價(jià)于一個(gè)聚類(lèi)問(wèn)題。但如何聚類(lèi)卻有很多種方法。在上文我們說(shuō)當(dāng) 時(shí)，Q(X)= Yi；(i=1 ,2,…,M)。這是用胞腔來(lái)定義Q(X)。反過(guò)來(lái)，也可以用Q(X)和碼字Yi來(lái)定義胞腔Ri，如式（2.11）所示:
（2.11）
當(dāng)然，最初必須有一個(gè)明確的Q{X〕的定義。
如何判斷 昵？通常定義一個(gè)失真測(cè)度函數(shù) (實(shí)數(shù)域)，d (X,Yi)表示用Yi來(lái)代表X時(shí)產(chǎn)生的誤差。我們用它來(lái)判斷一個(gè)矢量X到底屬于那個(gè)胞腔:
當(dāng)d (X,Y
因此，在這里量化器的主要工作就是利用失真測(cè)度函數(shù)d進(jìn)行最近鄰碼字收索。有時(shí)候我們也把d(X,Yi)稱(chēng)作X與Yi之NJ的距離。
2．3．3 失真測(cè)度函數(shù)
我們要求失真測(cè)度函數(shù)滿(mǎn)足以下兩個(gè)條件：
(1)正定性： 當(dāng)且僅當(dāng) X=Y時(shí)d( X,Y)=0；
(2)對(duì)稱(chēng)性： ；
有時(shí)候我們也加上第三個(gè)條件：
(3)三角不等式： ；
失真測(cè)度函數(shù)通常選擇線性賦范空間中的范數(shù)，根據(jù)范數(shù)的定義，它們都滿(mǎn)足上面三個(gè)條件。在本文中若無(wú)特殊聲明，我們的d(X,Y)就取最常用的2范數(shù)的平方，即K維歐幾里德空間中的距離的平方： ，我們把這個(gè)測(cè)度又稱(chēng)為平方誤差測(cè)度。它雖然不滿(mǎn)足三角不等式但是 卻是滿(mǎn)足全部這三個(gè)條件的。
事實(shí)上，判斷一個(gè)矢量X屬于哪個(gè)胞腔可以有很多種標(biāo)準(zhǔn)，在本文中，我們僅僅依據(jù)最近鄰(NN: Nearest Neighbor)準(zhǔn)則為判斷標(biāo)準(zhǔn)。利用矢量失真函數(shù)d，我們?cè)俣x一個(gè)胞腔失真函數(shù)：
D: Voronoi Cells R (實(shí)數(shù)域)；
X為處理矢量。
因?yàn)槲覀兺ǔＬ幚淼臄?shù)據(jù)量都是有限的，所以有限個(gè)實(shí)數(shù)之和也是有限的，從而D(Ri)是有限的。那么我們系統(tǒng)的總失真就如式（2.12）所示：
（2.12）
有時(shí)為方便起見(jiàn)，我們也把Er記為Er(C)，C為碼書(shū)，把D(Ri)記為D(Ri, Yi), Yi為Ri的代表元。顯而易見(jiàn)的，Er是越小越好。
2．4 矢量量化的關(guān)鍵技術(shù)及技術(shù)指標(biāo)
2．4．1 矢量量化的關(guān)鍵技術(shù)
矢量量化的三大關(guān)鍵技術(shù)是【8】：碼書(shū)設(shè)計(jì)、碼字搜索和碼字索引分配。其中前兩項(xiàng)最關(guān)鍵。
1. 碼書(shū)設(shè)計(jì)
矢量量化的首要問(wèn)題是設(shè)計(jì)出性能好的碼書(shū)。如果沒(méi)有碼書(shū)，那么編碼將成為無(wú)米之炊。假設(shè)采用平方誤差測(cè)度作為失真測(cè)度，訓(xùn)練矢量數(shù)為M，目的是生成含N (N< M)個(gè)碼字的碼書(shū)，則碼書(shū)設(shè)計(jì)過(guò)程就是尋求把M個(gè)訓(xùn)練矢量分成N類(lèi)的一種最佳方案(如:使得均方誤差最小)，而把各類(lèi)的質(zhì)心矢量作為碼書(shū)的碼字?？梢宰C明在這種條件下各種可能的碼書(shū)個(gè)數(shù)為Num C，Num C滿(mǎn)足公式2.13：
（2.13） 其中C為組合數(shù)。通過(guò)測(cè)試所有碼書(shū)的性能可以得到全局最優(yōu)碼書(shū)。
然而，在N和M比較大的情況下，搜索全部碼書(shū)是根本不可能的。為了克服這個(gè)困難，文獻(xiàn)中各種碼書(shū)設(shè)計(jì)方法都采取搜索部分碼書(shū)的方法得到局部最優(yōu)或接近全局最優(yōu)的碼書(shū)。所以研究碼書(shū)設(shè)計(jì)算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼書(shū)以提高碼書(shū)的性能，并且盡可能減少計(jì)算復(fù)雜度。
2. 碼字搜索
矢量量化碼字搜索算法是指在碼書(shū)已經(jīng)存在的情況下，對(duì)于給定的輸入矢量，在碼書(shū)中搜索與輸入矢量之間失真最小的碼字。給定大小為N的碼書(shū)C，如果矢量x與碼字A之間的失真測(cè)度為d(x,y)，則碼字搜索算法的目的就是找到碼字Y，使得失真測(cè)度滿(mǎn)足公式2.14:
（2.14）
如果采用平方誤差測(cè)度，對(duì)于k維矢量，每次失真計(jì)算需要k次乘法，2k一1次加法，從而為了對(duì)矢量x進(jìn)行窮盡搜索編碼需要Nk次乘法，N(2k -1)次加法和N-1次比較?？梢钥闯觯?jì)算復(fù)雜度由碼書(shū)尺寸和矢量維數(shù)決定。對(duì)于大尺寸碼書(shū)和高維矢量，計(jì)算復(fù)雜程度將很大。研究碼字搜索算法的主要目的就是尋求快速有效的算法以減少計(jì)算復(fù)雜程度，并且盡量使得算法易于用硬件實(shí)現(xiàn)。
3. 碼字索引分配
在圖示的矢量量化編碼和解碼系統(tǒng)中，如果信道有噪聲，則信道左端的索引i經(jīng)過(guò)信道傳輸可能輸出索引J而不是索引i，從而將在解碼端引入額外失真。為了減少這種失真，可以對(duì)碼字的索引進(jìn)行重新分配。如果書(shū)大小為N，則碼字索引分配方案一共有N!種。碼字索引分配算法就是在N!種碼字索引分配方案中尋求一種最佳的碼字索引分配使由信道噪聲引起的失真最小。然而，當(dāng)N較大時(shí)，測(cè)試N!種碼字索引分配方案是不可能的。為了克服這個(gè)困難，各種碼字索引分配方法都采用局部搜索算法，往往只能得到局部最優(yōu)解。所以研究碼字索引分配算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼字索引分配方案以減少由信道噪聲引起的失真，并盡可能減少計(jì)算復(fù)雜度和搜索時(shí)間。
2．4．2 矢量量化技術(shù)指標(biāo)
1. 矢量量化壓縮率
從矢量量化器的工作原理我們看出，碼書(shū)確定之后，傳輸或者存儲(chǔ)的壓縮數(shù)據(jù)只是一系列碼字的索引，這些索引本身并不包含原始數(shù)據(jù)的任何信息。因此矢量量化的壓縮率很大，其比特率 bit/采樣，也就是說(shuō)壓縮倍數(shù)為 B為原始采樣數(shù)據(jù)所用比特(bit)數(shù)。
舉例來(lái)說(shuō)，當(dāng)E=8, M= 256, K=64時(shí)，壓縮率r=0.015625 bits/采樣。壓縮倍數(shù)為64。這樣的壓縮倍數(shù)顯然很可觀了從壓 縮 率 與壓縮倍數(shù)的計(jì)算公式我們看出，M一般是2的冪次。再例如，碼書(shū)大小為150,碼字索引要用8bits碼書(shū)大小為256，碼字索引也要用8bits.兩種碼書(shū)大小得到的數(shù)據(jù)壓縮率相同，但后者壓縮性能顯然更好，所以一般我們用256而非150個(gè)碼字，大小為2a的碼書(shū)又稱(chēng)為q比特碼書(shū)。
2. 信號(hào)恢復(fù)性能指標(biāo)
通常信號(hào)質(zhì)量有均方誤差(MSE)，信噪比(SNR)，峰值信噪比(PSNR) 【11】等。在本文的討論中，我們主要是灰度圖像作為測(cè)試數(shù)據(jù)來(lái)源。我們的矢量量化技術(shù)的應(yīng)用也主要是針對(duì)灰度圖像的，因此以L級(jí)灰度圖像為例，我們給出個(gè)指標(biāo)的定義：設(shè)一副L級(jí)灰度圖像有WXH個(gè)像親，Xij為原始圖像像素值，Yij為恢復(fù)圖像像素值，那么
結(jié)過(guò)如下公式所示：
（2.15）
（2.16）
（2.17）
第三章 矢量量化的算法研究
3．1 矢量量化碼書(shū)設(shè)計(jì)算法的研究
3．1．1 經(jīng)典的LBG算法
如前所述，在矢量量化器的構(gòu)造過(guò)程中，碼本設(shè)計(jì)是最初的也是最重要的部分，根據(jù)各種碼本設(shè)計(jì)算法的思想和迭代過(guò)程，我們可以將碼本設(shè)計(jì)問(wèn)題歸結(jié)為L(zhǎng)loyd算法的兩條基本準(zhǔn)則【12】：
1. 最佳劃分準(zhǔn)則(Optimal Partition)
對(duì)于給定的碼本 利用最近鄰條件對(duì)訓(xùn)練矢量集進(jìn)行重新劃分。將每個(gè)訓(xùn)練矢量映射到與它之間失真最小的碼字，最后形成一組以現(xiàn)有碼本中的碼字為中心的最佳劃分。設(shè)訓(xùn)練矢量集為：
則訓(xùn)練矢量集的最佳分類(lèi) 滿(mǎn)足公式（3.1）：
式中，i,j= 1,2,…,N （3.1）
如果存在D(x,yi )= D (x,yj ), 則將訓(xùn)練矢量歸入碼字yi的集合。
通常把這種最佳劃分稱(chēng)為Voronoi劃分，對(duì)應(yīng)的子集凡稱(chēng)為Voronoi胞腔。設(shè)訓(xùn)練矢量x為k維的 ，如果用平方誤差測(cè)度用來(lái)表征訓(xùn)練矢量x和碼字yi之間的失真，即：
（3.2）

2. 質(zhì)心條件 (CentroidC ondition)
利用由上面步驟得到的訓(xùn)練矢量劃分集 重新計(jì)算它們各自的質(zhì)心，得到新的碼本：
（3.3）
（3.4）
式中， 代表子集Si中訓(xùn)練矢量的個(gè)數(shù)。
各種矢量量化碼本設(shè)計(jì)算法基本都是上面兩個(gè)步驟的交替迭代的基礎(chǔ)上得到最后的碼本。不難看出，碼本生成過(guò)程中的計(jì)算量是隨著碼本矢量的維數(shù)k和碼本尺寸N的增大而急劇增長(zhǎng)的，對(duì)于需要高維大碼本的矢量量化器來(lái)說(shuō)，測(cè)試所有可能的碼本來(lái)尋求全局最優(yōu)碼本將是十分困難的。為了克服這個(gè)困難，Linde . Buzo和Gray提出了經(jīng)典的LBG算法。
1980年Linde，Buzo和Gray將Lloyd算法推廣到矢量空間【8】， 算法的步驟簡(jiǎn)單描述如下：
Step 1 ：給定初始碼本 ，令迭代次數(shù)m=0，平均失真初始值為 ，給定失真下降閾值 ；
Step 2：用碼本 中的碼字作為質(zhì)心，根據(jù)最佳劃分原則將訓(xùn)練矢量集x劃分為對(duì)應(yīng)于每個(gè)碼字的N個(gè)聚類(lèi)，
滿(mǎn)足： ；
Step 3：計(jì)算本次迭代的平均失真 判斷相對(duì)誤差是否滿(mǎn)足 ，若滿(mǎn)足，則停止算法，碼本C(m)就是所求的碼本;
否則，轉(zhuǎn)Step 4；
Step 4：根據(jù)質(zhì)心條件，計(jì)算各聚類(lèi)的質(zhì)心，即公式（3.5）：
（3.5）
產(chǎn)生新碼本 并置m=m+1，轉(zhuǎn)Step 2
END：算法結(jié)束。

對(duì)于 LBG算法來(lái)說(shuō)，初始碼本選擇的好壞將直接影響到后面的迭代計(jì)算結(jié)果，一個(gè)不好的初始碼本會(huì)降低算法的收斂速度和最終碼本的性能。因此在LBG算法中要對(duì)初始碼本的選擇作一定的處理。如果初始碼本隨機(jī)產(chǎn)生，即直接從訓(xùn)練序列中隨機(jī)選擇N個(gè)訓(xùn)練矢量作為初始碼字，構(gòu)成初始碼本，可能會(huì)選到一些非典型的訓(xùn)練矢量作碼字，因而該胞腔可能含有少數(shù)幾個(gè)矢量甚至只有1個(gè)。另外，有可能把某些空間分得過(guò)疏。這可能會(huì)導(dǎo)致碼本中的有些碼字得不到充分利用，設(shè)計(jì)出來(lái)的碼本性能就可能較差。
3．1．2 MD算法
最大下降（MD）【13】碼本設(shè)計(jì)算法與經(jīng)典的LBG算法不同，它是一種分裂算法，而沒(méi)有初始碼本。在MD算法中，首先將訓(xùn)練矢量集 作為一個(gè)原始包腔，然后該包腔被它的最優(yōu)分割超平面分成兩個(gè)子包腔。依此類(lèi)推，每次分裂產(chǎn)生一個(gè)包腔，直到生成最后的N個(gè)包腔，計(jì)算它們的質(zhì)心，就可以得到設(shè)計(jì)的碼本C={y}i=1,2,…,N)。與LBG算法相比，MD算法的計(jì)算量少并且所產(chǎn)生的碼本性能好。另一方面，MD算法傾向于分割元素較多的胞腔，而不會(huì)去分割只有一個(gè)元素的胞腔，避免了非典型碼字的形成，提高了碼本的整體性能。在MD算法中，從L個(gè)包腔向(L+ l )個(gè)包腔擴(kuò)展時(shí)，先要找出每個(gè)現(xiàn)有包腔的最優(yōu)分割超平面，并計(jì)算它們各自帶來(lái)的失真下降幅度，然后依據(jù)失真下降最大準(zhǔn)則來(lái)選擇究竟對(duì)哪一個(gè)包腔進(jìn)行分裂。這在k維空間里是比較困難的事，需要大量的計(jì)算和比較。圖3.2所示為MD算法的分裂過(guò)程示意圖，圖中每一步驟中有陰影的包腔 是當(dāng)前符合失真下降最大準(zhǔn)則的包腔，它被最優(yōu)分割超平面分成下面的兩個(gè)子包腔 和 。從L個(gè)包腔生成(L+ 1)個(gè)包腔的具體實(shí)現(xiàn)描述如下：
設(shè)超平面 將某胞腔 分成兩個(gè)非空胞腔如式（3.6）所示：

（3.6）
式中 ， ， ， T表示轉(zhuǎn)置。
當(dāng) 中的矢量被質(zhì)心 量化時(shí)，胞腔的失真D(Si)定義為公式（3.7）： （3.7）
則由分割超平面H,劃分胞腔S,所引起的失真下降可表示為式（3.8）：
（3.8）
若采用平方誤差測(cè)度，則式(3.8)可以化簡(jiǎn)為式（3.9）：
或 （3.9）
式中， 分別為 的元素個(gè)數(shù)， 。分別為 的質(zhì)心。
從式(3.9)中可以看出，若胞腔 、 非空，則失真下降函數(shù)滿(mǎn)足 。
我們將胞腔Si的最優(yōu)分割超平面 定義為使胞腔 具有最大失真下降 的超平面。MD算法先計(jì)算出所有胞腔的最大失真下降值 ， ，然后找出最大的最大失真下降值 ，即 ，最后將胞腔Sp分割成兩個(gè)新胞腔。所以，L+l個(gè)胞腔是通過(guò)劃分L個(gè)胞腔中具有最大失真下降的胞腔并保持其余胞腔不變而得到的。值得注意的是，每次分裂包腔時(shí)，并不需要重新計(jì)算所有包腔的失真函數(shù)，而只需找到新增加的兩個(gè)包腔的最優(yōu)分割超平面，計(jì)算它們各自的失真函數(shù)，再與其它包腔的失真函數(shù)值進(jìn)行比較即可找出新的滿(mǎn)足失真下降最大準(zhǔn)則的包腔。產(chǎn)生最后的N個(gè)胞腔，一共需計(jì)算(2N-3)次最大失真下降函數(shù)。
3．1．3 碼書(shū)設(shè)計(jì)算法比較
LBG算法是一種迭代算法，其迭代操作是標(biāo)量量化勞埃德迭代操作的直接推廣。LBG算法他具有如下的優(yōu)點(diǎn)：
1. 不用初始化計(jì)算，可大大減少計(jì)算時(shí)間
2. 初始碼字選自訓(xùn)練序列，無(wú)空胞腔問(wèn)題
LBG算法在具有如上的優(yōu)點(diǎn)的同時(shí)也有一些缺點(diǎn)和不足:
1. 在每次迭代的最佳劃分階段，從碼書(shū)中搜索訓(xùn)練矢量的最近碼字需要大量的存儲(chǔ)空間和繁瑣的計(jì)算；
2. 初始碼書(shū)的選擇影響碼書(shū)訓(xùn)練的收斂速度和最終碼書(shū)的性能；
碼書(shū)設(shè)計(jì)的第一個(gè)缺點(diǎn)可采用各種快速碼字搜索算法來(lái)解決，但這些算法無(wú)法改善碼書(shū)的性能，第2個(gè)缺點(diǎn)產(chǎn)生的原因是:LBG算法是一種下降算法，每次迭代總能減少(至少保持不變)平均失真，而且每次迭代通常只能產(chǎn)生碼書(shū)的局部變化，即每次迭代后，與舊碼書(shū)相比，新碼書(shū)不可能有非常大的變化。因此，一旦選定初始碼書(shū)，該算法只能得到局部最優(yōu)的碼書(shū)，即LBG算法一般不能得到全局最優(yōu)的碼書(shū)。
與LBG算法相比，MD算法的計(jì)算量少且所產(chǎn)生的碼書(shū)性能好。另一方面， MD算法傾向于分割元素較多的胞腔，而不會(huì)去分割只有一個(gè)元素的胞腔，而這種情況在LBG算法中卻常常出現(xiàn)。然而，在MD算法中，多維胞腔的最優(yōu)分割超平面的搜索是一個(gè)非常困難的問(wèn)題。為減少計(jì)算量，這些算法的搜索范圍被限制在與矢量空間的基本矢量正交的超平面上，這個(gè)矢量空間可由離散余弦變換(DCT)得到。但是，在這種限制條件下，算法常常搜索不到最優(yōu)超平面。
3．2 碼字搜索算法
3．2．1 基于不等式的快速碼字搜索算法
1. 部分失真不等式排除法
部分失真搜索(Partial Distortion Search，PDS)算法【12】是一種較簡(jiǎn)單有效的最近鄰搜索算法。它的基本思想是：在計(jì)算某個(gè)碼字與輸入矢量之間失真測(cè)度的過(guò)程中，始終判斷累加的部分失真是否已經(jīng)超過(guò)目前的最小失真，如果一旦超出則終止該碼字與輸入矢量之間的失真計(jì)算，轉(zhuǎn)而開(kāi)始計(jì)算另一個(gè)碼字與輸入矢量的失真測(cè)度。PDS常被用來(lái)與其他快速搜索算法結(jié)合起來(lái)運(yùn)用，來(lái)排除其它快速算法最后無(wú)法排除的碼字。
在編碼過(guò)程中計(jì)算前面部分維數(shù)的失真距離，若其超出當(dāng)前最小距離，則排除此碼字為最匹配碼字，否則繼續(xù)搜索其它碼字。
據(jù)如下（3.10）所示的柯西一許瓦爾茲不等式【14】：
（3.10）
可得一個(gè)不等式判據(jù) 若 ，則能保證 ，yi可被排除。因?yàn)閨yi|可離線計(jì)算，所以節(jié)省了計(jì)算量。
首先判斷 是否成立，若成立，則排除碼字Yi否則，再判斷是否滿(mǎn)足 ，若滿(mǎn)足，yi也可被排除。這縮小了搜索范圍，他們還融入部分距離失真法節(jié)省計(jì)算量。雙測(cè)試法的缺陷在于要求矢量的所有分量都為正值，而圖像變換域編碼中產(chǎn)生的變換系數(shù)有正有負(fù)，必須對(duì)這些系數(shù)進(jìn)行正補(bǔ)償，使所有矢量分量均大于零。
2. 整數(shù)投影法
整數(shù)投影法是一種適用于圖像矢量量化的快速碼字搜索算法。他們?yōu)槊總€(gè)m×m圖像塊 ，定義三種整數(shù)投影【14】，如下公式（3.11）（3.12）（3.13）所示：
塊狀投影： （3.11）
垂直投影： （3.12）
水平投影： （3.13）
在這三種投影的基礎(chǔ)上定義了三個(gè)不等式條件，公式（3.14）（3.15）（3.16）所示：
（3.14）
（3.15）
（3.16）
可以證明，只要不滿(mǎn)足上述任何一個(gè)條件，可排除yi是最匹配碼字。
3. 三角不等式法
基于三角不等式d(Y i,yj) < d (x ,Yi)+ d (x ,yj)提出三種改進(jìn)算法【14】。第一種算法先計(jì)算碼書(shū)中每?jī)蓚€(gè)碼字之間的距離，以當(dāng)前匹配碼字yi為中心，2hi(h i為輸入矢量與當(dāng)前匹配碼字之間的歐氏距離)為半徑劃定搜索范圍，即只搜索滿(mǎn)足d(yj,yi)< 2hi的碼字yj,j= 1,2,…,N；
第二種算法是將搜索范圍定為滿(mǎn)足：x-hi其中rx為輸入矢量的范數(shù)，rk為碼字的范數(shù)，hi為輸入矢量與當(dāng)前匹配碼字之間的歐氏距離，此種算法不同于第一種算法，無(wú)須計(jì)算碼字之間的距離；
第三種算法取前兩種算法搜索區(qū)域的交集作為搜索區(qū)域。
這三種算法都涉及如何確定初始匹配碼字的問(wèn)題，一般取范數(shù)與輸入矢量范數(shù)最相近的碼字。第一、三種算法比第二種算法要多耗費(fèi)存儲(chǔ)空間來(lái)存儲(chǔ)碼字之間的距離。最小均方誤差編碼算法，取一長(zhǎng)訓(xùn)練矢量序列，計(jì)算每個(gè)Voronoi區(qū)域內(nèi)的訓(xùn)練矢量與該區(qū)域質(zhì)心矢量(碼字) 的最大距離di，求平方根后得ri，按其升序排列。編碼時(shí)，從最小的ri開(kāi)始，排除對(duì)任意 ，滿(mǎn)足 .的碼字；那些對(duì)所有j，滿(mǎn)足 的碼字，則采用部分失真排除判定法，確定此碼字為最佳匹配碼字或者在以該碼字為開(kāi)始的剩余碼字中搜索最佳匹配碼字。
3．2．2 等均值等方差最近鄰搜索算法
均值等方差最近鄰碼字搜索算法是將均值不等式判據(jù)和用方差不等式判據(jù)相結(jié)合，進(jìn)一步縮小了碼字搜索范圍。k維輸入矢量x的方差定義公式（3.17）【9】為
（3.17）
其中：Mx為輸入矢量x的均值。
等均值等方差最近鄰搜索算法所用到的方差判別準(zhǔn)則為：
設(shè)碼字 為輸入矢量x的當(dāng)前最近鄰碼字， ，輸入矢量x和碼字Y，的方差分別為Vx和Vyi，如果公式（3.18）成立，
（3.18）
則有d(x,yi) >d( x,yp)，碼字yi，可以被排除是輸入矢量x的最近鄰碼字。對(duì)式(3.12)作適當(dāng)變形，可得公式（3.19）和（3.20）
(3.19)
(3.20)
即碼字Yi的方差滿(mǎn)足以上兩式時(shí)，碼字Yi可以被排除是輸入矢量x的最近鄰碼字。
由幾何知識(shí)可知，在歐幾里得空間 中以空間中心線L為軸心的超圓柱面上，各點(diǎn)的方差相等，該超圓柱面稱(chēng)為等方差超圓柱面。由式(3.13)和(3.14)可知，等方差判別準(zhǔn)則將碼字搜索范圍限制在方差分別為Vmax和V min的兩個(gè)超圓柱面內(nèi)。則等均值判別準(zhǔn)則與等方差判別準(zhǔn)則相結(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ù)處理：計(jì)算并存儲(chǔ)碼書(shū)C中的均值和方差，按均值的大小對(duì)碼書(shū)進(jìn)行排序。
(B)在線處理：
Step l：計(jì)算輸入矢量x的均值Mx和方差Vx，在已排序碼書(shū)中找到均值與Mx 最 接近的碼字 作為輸入矢量X的初始匹配碼字。計(jì)算當(dāng)前最小失真 d min = d (x ,yp )。使集合
Step 2：如果集合G為空，轉(zhuǎn)Step 7；
Step 3：往返搜索法搜索初始匹配碼字yp兩側(cè)的碼字yj；
Step 4：如果碼字滿(mǎn)足 或者 ，則執(zhí)行
下列步驟的(a)或者(b)。否則，轉(zhuǎn)步驟5；
(C)如果Myj> Mx，則從集合G中刪除所有碼字yi，i(D)否則，則從集合G中刪除所有碼字yi i>j，轉(zhuǎn)Step2。
Step 5：判斷碼字Yi的方差是否滿(mǎn)足 或者 如果 滿(mǎn)足， 則從刪除集合G中刪除碼字Yi，否則，轉(zhuǎn)Step6；
Step 6：用部分失真排除算法搜索碼字Yi，如果d(x, Yi)Step7：確定輸入矢量x的最匹配碼字為Yp。
3．3 碼字索引分配算法
3．3．1 BSA算法
BSA算法是在1990年提出基于二元對(duì)稱(chēng)信道模型的碼字索引分配算法【16】。該算法對(duì)于任何索引映射函數(shù) ，選擇碼字y，作為輸入矢量x的最近碼字后將產(chǎn)生索引 的傳輸，該過(guò)程與首先將碼書(shū)中的碼字進(jìn)行位置交換等價(jià)，即對(duì)每一索i，碼字y最終移動(dòng)到碼書(shū)中索引為 的位置。
基于這個(gè)事實(shí)，很自然地想到一種最簡(jiǎn)單的碼字索引分配方法：首先在給定碼書(shū)基礎(chǔ)上隨機(jī)產(chǎn)生一個(gè)初始碼字排列，然后將所有碼字的排列位置以特定方式進(jìn)行交換，使信道失真不斷減少。因此，這種算法的輸入是一個(gè)碼書(shū)，輸出仍是一個(gè)碼書(shū)，只不過(guò)碼字存放在不同的位置。這帶來(lái)一個(gè)附加優(yōu)點(diǎn):除了存儲(chǔ)碼書(shū)所需的空間以外，不需要任何額外信息來(lái)詳細(xì)描述索引映射函數(shù)n，從而不需要信道編碼和信道解碼。
BSA算法的主要思想是通過(guò)不斷交換碼字的位置，使得信道噪聲失真的目標(biāo)函數(shù)場(chǎng)獲得局部最優(yōu)值.隨著交換的進(jìn)行 不斷下降，而且索引映射函數(shù) 也跟著不斷變化。在每次迭代中，碼字的交換對(duì)是按一定的順序選擇的。所有的碼字y，都對(duì)應(yīng)一個(gè)函數(shù) ，用來(lái)描述當(dāng)該碼字的索引(在當(dāng)前碼書(shū)中)在噪聲信道中傳輸時(shí)可能產(chǎn)生的失真，其定義為公式（3.21）：
（3.21）
BSA算法每次按 從大到小的順序?qū)Υa字進(jìn)行排序。擁有最大函數(shù)值 的碼字被選為首先交換的候選對(duì)象。首先進(jìn)行試驗(yàn)性的交換， 與其他每一個(gè)碼字分別進(jìn)行交換，并計(jì)算每次交換后 的下降值。選擇能使 出現(xiàn)最大下降的那一個(gè)碼字與 進(jìn)行真正地交換，然后進(jìn)入下一次迭代。如果不存在這樣的碼字，則對(duì)yi作相同的交換試驗(yàn)。如果每一個(gè)碼字按這種方法與其他碼字進(jìn)行交換后。不再下降，則終止算法，從而獲得一個(gè)局部最優(yōu)的碼字索引分配方案。算法的具體步驟如下：
Step 1：初始化。隨機(jī)打亂碼字的排序；
Step 2：整理排序。根據(jù) 從大到小的順序?qū)Υa字yi進(jìn)行排序。令n=－1；
Step 3：試驗(yàn)性交換。令n＝n＋1從j＝n＋1到N一1，分別計(jì)算索引n和索弓!j交換后所能引起的失真減少量，比較這些失真減少量，獲得最大的失真下降量 ；
Step 4：如果 >0，則交換索引n和引起最大失真下降的索引j，并轉(zhuǎn)Step 2；
Step 5：終止算法。如果n=N一1，則終止算法，否則，轉(zhuǎn)Step 3。
可以看出，BSA算法根據(jù)函數(shù)值 將碼字進(jìn)行排列而選擇出哪一個(gè)碼字最先進(jìn)行交換，從而在運(yùn)算上給出了一個(gè)方向性引導(dǎo)。如果由于程序運(yùn)行時(shí)間的限制而使算法的迭代次數(shù)有限，則這種方向性引導(dǎo)將顯得尤為重要。每一次成功交換的完成，代表一次迭代的結(jié)束。若一次迭代中的所有試驗(yàn)性交換產(chǎn)生的失真下降都不大于O，則說(shuō)明算法已經(jīng)達(dá)到一個(gè)局部最優(yōu)解.應(yīng)該指出的是:從不同的初始碼字排序出發(fā)，可獲得不同的局部最優(yōu)解，從而保證BSA算法對(duì)于碼字交換的限制不會(huì)影響它獲得全局最優(yōu)碼字索引分配方案的可能性。實(shí)驗(yàn)證明，該算法獲得的碼字索引分配方案的失真比隨機(jī)碼字索引分配方案的失真有較大改進(jìn)。
3．3．2 禁止搜索碼字索引算法
禁止搜索的基本思想是通過(guò)一系列移動(dòng)來(lái)搜尋所有可行解的搜索空間，并且在當(dāng)前迭代中禁止某些搜索方向以避免死循環(huán)和跳入局部極小。由當(dāng)前解到其鄰域解的移動(dòng)被部分地或完全地記錄在禁止表中，目的是為了禁止以后迭代中的重復(fù)操作。
令 為測(cè)試解的集合，其中元素si可以被表示為式【8】（3.22）：
（3.22）
其中，N為碼書(shū)的尺寸，Si(j)表示在解si中分配給碼字Yj的索引， 令 和 分別表示當(dāng)前解和最優(yōu)解。中碼字Yj的索引，Sb(j)仍表示分配給解Sb中碼字Yi的索引。
令 ， 和 分別代表測(cè)試解組的目標(biāo)函數(shù)值集合，當(dāng)前解的目標(biāo)函數(shù)值和最優(yōu)解的目標(biāo)函數(shù)值，其中 是測(cè)試解 的目標(biāo)函數(shù)值，0Step 1：設(shè)置禁止表大小Ts測(cè)試解個(gè)數(shù)N，以及迭代次數(shù)Im。令迭代計(jì)數(shù)器i=1，禁止表插入點(diǎn)t=1。隨機(jī)產(chǎn)生當(dāng)前解 ，計(jì)算其相應(yīng)的目標(biāo)函數(shù)值V}。令Sb=Sc以及Vb=Vc
Step 2：把當(dāng)前解Sc拷貝給每一個(gè)測(cè)試解si, 0Step 3：如果最優(yōu)測(cè)試解的目標(biāo)函數(shù)值比最優(yōu)解的目標(biāo)函數(shù)值Vb還小，則把它作為新的當(dāng)前解，并令其目標(biāo)函數(shù)值作為當(dāng)前解的目標(biāo)函數(shù)值Vc，轉(zhuǎn)Step 3。否則，選出測(cè)試解中最好的非禁止解。如果能選到，則把它作為新的當(dāng)前解Sc并令其目標(biāo)函數(shù)值作為當(dāng)前解的目標(biāo)函數(shù)值Vc，轉(zhuǎn)Step 3；否則，轉(zhuǎn)Step 1。
Step 4： 如果vb>vc，令Sb=Sc，Vb＝Vc，把從舊當(dāng)前解到新當(dāng)前解所交換過(guò)的索引插入禁止表中。禁止表的插入點(diǎn)設(shè)為ti=ti+1;如果ti>Ts，令ti＝l，如果i

第四章 矢量量化算法的實(shí)現(xiàn)
4．1 需求分析與整體設(shè)計(jì)
4．1．1需求分析
隨著數(shù)字技術(shù)的飛速發(fā)展，越來(lái)越多的信息(文本、圖形、圖像、動(dòng)畫(huà)、音頻及視頻影像等)采用數(shù)字化的形式存儲(chǔ)、傳輸和檢索。由于網(wǎng)絡(luò)上的數(shù)據(jù)流量飛速增長(zhǎng)，而且網(wǎng)絡(luò)的帶寬總是滿(mǎn)足不了需求，數(shù)據(jù)壓縮編碼技術(shù)的迅猛發(fā)展，要求在盡量不損傷多媒體質(zhì)量的情況下壓縮數(shù)據(jù)量。
正是由于這種需求的存在，要求開(kāi)發(fā)一套完整的數(shù)據(jù)壓縮軟件，利用矢量量化的數(shù)據(jù)壓縮算法，能夠調(diào)用BMP格式的圖像，對(duì)載入的圖像進(jìn)行壓縮并顯示解壓后的圖像效果，能夠選擇路徑保存解壓后的圖像實(shí)現(xiàn)SNR信噪比的計(jì)算，便于對(duì)壓縮軟件性能的評(píng)價(jià)。
4．1．2 整體設(shè)計(jì)
軟件的設(shè)計(jì)在Eclipse開(kāi)發(fā)工具下編譯Java應(yīng)用程序。利用Java語(yǔ)言的面向?qū)ο蟮奶攸c(diǎn)，充分利用他的可封裝性，重用性和多態(tài)性等特點(diǎn)，開(kāi)發(fā)一整套完整的基于矢量量化數(shù)據(jù)壓縮算法的壓縮軟件。
將這個(gè)數(shù)據(jù)壓縮軟件從整體上分五個(gè)模塊來(lái)實(shí)現(xiàn)的。Bmp格式圖像的調(diào)入和保存模塊，圖像矢量塊的劃分模塊，初始碼書(shū)生成模塊，LBG量化模塊，圖像解壓模塊。如圖4.1所示：

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

圖4.2程序運(yùn)行初始界面
4．2 矢量量化算法的實(shí)現(xiàn)過(guò)程及說(shuō)明
4．2．1 初始碼書(shū)的生成
這個(gè)程序利用了隨機(jī)編碼生成碼書(shū)的方法，即根據(jù)輸入信源分布直接從訓(xùn)練序列中隨機(jī)選擇N個(gè)訓(xùn)練矢量作為初始碼字以構(gòu)成初始碼書(shū)。該方法的優(yōu)點(diǎn)是計(jì)算量低，初始碼書(shū)的生成較為容易。雖然可能出現(xiàn)碼書(shū)的分布不均勻的現(xiàn)象，但是配合LBG算法的多次迭代可以得到補(bǔ)償。需要注意，這里所說(shuō)的隨機(jī)編碼是說(shuō)初始碼書(shū)的選擇方式是隨機(jī)的，而一旦碼書(shū)選定，編碼器的工作方式則是按著最近鄰方式進(jìn)行的。隨機(jī)碼書(shū)的生成代碼如下：
codebook=new MyBlock[N];
for(int i=0;i{ codebook[i]=new MyBlock();
} codebook[0]=tv.randomselect();
for(int j=1;jint t=0;
do{ t++;
n=0;
codebook[j]=tv.randomselect();
for(int l=0;l{ if(codebook[j].vcmp(codebook[l])==0)
{ n=1; break; }
}
}while(n!=0&&t<100);}

4．2．2 LBG矢量量化
圖4.2 LBG碼書(shū)設(shè)計(jì)流程圖

如圖4.2所示的流程圖，對(duì)隨機(jī)生成初始碼書(shū)，碼書(shū)大小N，訓(xùn)練矢量序列，停止計(jì)算門(mén)限和起始平均失真的初始碼書(shū)進(jìn)行勞埃德迭代。用初始碼書(shū)為已知的心形，把訓(xùn)練序列重新劃分為N個(gè)胞腔。計(jì)算新的平均失真和相對(duì)失真，判斷新的失真是否滿(mǎn)足門(mén)限條件，如果滿(mǎn)足則退出勞埃德迭代否則繼續(xù)進(jìn)行勞埃德迭代直到滿(mǎn)足門(mén)限條件，生成碼書(shū)。LBG算法的關(guān)鍵代碼如下：
flag=0;//循環(huán)標(biāo)識(shí)
tcb(s,tv);//訓(xùn)練集和碼本建立關(guān)系
for(int i=0;i{ for(int j=0;j{if(s[j]==i) n++;
yn[i]=n;
} }dsum=0;
for(int i=0;i{dsum=dsum+(long)min1(tv.train[i],1);
}d1=(double)(dsum/tv.M);
d=Math.abs(((double)(d0-d1)/(double)d1));
if(d1e)
{for(int i=0;i{if(yn[i]!=0)
{o=core(tv,i,s);
codebook[i].vcopy(o);
}d0=d1;
flag=1;
}while(flag==1);
在這段代碼中，首先建立碼本與訓(xùn)練矢量的關(guān)系，并經(jīng)過(guò)多次的勞埃德迭代直到滿(mǎn)足門(mén)限條件，生成新的碼書(shū)。這里應(yīng)用了LBG算法他具有如下的優(yōu)點(diǎn)：
1.不用初始化計(jì)算，可大大減少計(jì)算時(shí)間
2.初始碼字選自訓(xùn)練序列，無(wú)空胞腔問(wèn)題
雖然LBG算法有如上的優(yōu)點(diǎn)，但是他本身也存在一些缺點(diǎn)和不足的地方，比如在計(jì)算的過(guò)程中可能會(huì)選到一些非典型矢量作碼字，因而該胞腔中只有很少矢量，甚至只有一個(gè)初始碼字，而且每次迭代又都保留了這些非典型矢量的形心；還可能會(huì)造成在某些空間把胞腔分得過(guò)細(xì)，而有些空間分得太大。這些缺點(diǎn)都會(huì)導(dǎo)致碼書(shū)中有限個(gè)碼字得不到充分利用，還需要進(jìn)一步的改進(jìn)算法。
程序整體流程圖如圖4.3所示：

圖4.3 軟件流程圖
4．2．3 矢量量化碼字索引與恢復(fù)
在這個(gè)程序中沒(méi)有考慮快速碼字搜索的算法，應(yīng)用了最佳碼字搜索的方法，使輸入矢量與所有的碼字進(jìn)行比較，選出距離最小的那個(gè)碼字成為匹配碼字，生成索引。這種算法雖然增加了計(jì)算量，但是減少了圖像數(shù)據(jù)壓縮過(guò)程中的失真。
在輸出端，將編碼過(guò)后生成的索引對(duì)照碼書(shū)，將圖像數(shù)據(jù)進(jìn)行還原。
4．3 實(shí)驗(yàn)結(jié)果及評(píng)價(jià)
在初始界面點(diǎn)擊瀏覽按鈕調(diào)入.BMP圖像。圖像就會(huì)顯示在程序運(yùn)行初始界面的左側(cè)，如圖4.3所示：

圖4.4 壓縮前的程序界面
點(diǎn)擊”壓縮”按鈕，程序就會(huì)自動(dòng)進(jìn)行矢量量化的壓縮，下面的進(jìn)度條會(huì)顯示壓縮的百分比，當(dāng)進(jìn)度達(dá)到100％時(shí)，程序就會(huì)將解壓好的圖像顯示在程序界面的左側(cè)。并顯示一系列的壓縮信息，包括壓縮源文件的大小，壓縮后的碼本大小，壓縮比，壓縮過(guò)程所需要的時(shí)間以及峰信噪比PSNR等信息。壓縮后的界面如圖4.5所示：

圖4.5 恢復(fù)后的程序界面
程序顯示的壓縮結(jié)果的壓縮比和壓縮時(shí)間上可以看出，這個(gè)利用矢量量化編碼算法的壓縮軟件可以達(dá)到16：1的高壓縮比，并且壓縮時(shí)間比較短。所以矢量量化壓縮編碼是一種非常有效的壓縮算法。
從壓縮圖像的效果來(lái)看，實(shí)驗(yàn)測(cè)試的圖像均采用的512×512，8比特/象素的women圖像作為訓(xùn)練圖像產(chǎn)生各種大小的碼書(shū)，矢量維數(shù)均為16，對(duì)壓縮程序進(jìn)行測(cè)試。通過(guò)變換碼書(shū)的大小，運(yùn)行程序得到不同的信噪比。測(cè)試結(jié)果如下表4.1所示：
表4.1 不同碼書(shū)的信噪比
序號(hào) 碼書(shū)大小 PSNR
1 64 27.36
2 128 27.74
3 256 28.54
4 512 29.28

如上表所示，隨著碼書(shū)的加大，系統(tǒng)的信噪比在升高，當(dāng)碼書(shū)大小為512時(shí)，PSNR可以達(dá)到29.28。圖像雖然有一定程度上的失真，但是并不是十分明顯，基本上保持了圖像原有的圖像質(zhì)量。
這個(gè)程序采用的是矢量量化碼書(shū)生成算法中的LBG算法，通過(guò)運(yùn)行程序以及對(duì)運(yùn)行結(jié)果的分析可以看出這種從標(biāo)量量化勞埃德迭代操作推廣出來(lái)的迭代算法具有以下兩個(gè)優(yōu)點(diǎn)：
1．不用初始化計(jì)算，可大大減少計(jì)算時(shí)間
2．初始碼字選自訓(xùn)練序列，無(wú)空胞腔問(wèn)題
雖然LBG算法在具有如上的優(yōu)點(diǎn)，但是因?yàn)長(zhǎng)BG算法是一種下降算法，每次迭代總能減少(至少保持不變)平均失真，而且每次迭代通常只能產(chǎn)生碼書(shū)的局部變化，即每次迭代后，與舊碼書(shū)相比，新碼書(shū)不可能有非常大的變化。所以初始碼書(shū)的選擇影響碼書(shū)訓(xùn)練的收斂速度和最終碼書(shū)的性能，一旦選定初始碼書(shū)，該算法只能得到局部最優(yōu)的碼書(shū)，即LBG算法一般不能得到全局最優(yōu)的碼書(shū)。
在每次迭代的最佳劃分階段，從碼書(shū)中搜索訓(xùn)練矢量的最近碼字需要大量的存儲(chǔ)空間和繁瑣的計(jì)算；這對(duì)軟件大的運(yùn)行要求比較高的運(yùn)行環(huán)境。這個(gè)可以通過(guò)快速碼字搜索的算法來(lái)解決這個(gè)問(wèn)題。

第五章 結(jié)論與展望
本文主要針對(duì)矢量量化的算法和實(shí)現(xiàn)研究與探討，本章主要對(duì)本文內(nèi)容與研究工作進(jìn)行一下總結(jié)。最后對(duì)矢量量化技術(shù)在今后發(fā)展方向上作了一些展望。
矢量量化技術(shù)作為數(shù)據(jù)壓縮領(lǐng)域里的一個(gè)分支，主要優(yōu)點(diǎn)是壓縮比大以及解碼簡(jiǎn)單，在圖像壓縮方面已經(jīng)得到成功地應(yīng)用。目前， 矢量量化技術(shù)的研究主要集中在三個(gè)方面：矢量量化器的碼本設(shè)計(jì)，矢量量化碼字快速搜索算法設(shè)計(jì)，矢量量化碼字索引分配問(wèn)題。本文主要研究了矢量量化碼本設(shè)計(jì)算法和碼字快速搜索算法，并討論了矢量量化技術(shù)的應(yīng)用問(wèn)題。全文主要工作可以總結(jié)如下:
首先，介紹了數(shù)據(jù)壓縮算法的基本理論和發(fā)展現(xiàn)狀，討論了數(shù)據(jù)壓縮算法的分類(lèi)體系和發(fā)展歷程。
其次，介紹了矢量量化技術(shù)的來(lái)源和發(fā)展歷程，重點(diǎn)介紹了關(guān)于矢量量化技術(shù)的技術(shù)基礎(chǔ)和矢量量化算法中的關(guān)鍵技術(shù)。
再次，研究了經(jīng)典的矢量量化的設(shè)計(jì)算法，分別研究討論了矢量量化中的LBG算法，最大下降算法；快速搜索算法中的基于不等式的快速搜索算法和碼字索引分配中的BSA算法等，并討論了現(xiàn)有各種矢量量化算法。
最后，介紹了一種LBG矢量量化算法的實(shí)現(xiàn)方法，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了性能評(píng)價(jià)。
以上是本文內(nèi)容的總結(jié)。還有許多問(wèn)題沒(méi)有涉足或研究的深度不夠。矢量量化技術(shù)領(lǐng)域雖然已經(jīng)取得了長(zhǎng)足的進(jìn)步，但總體上來(lái)說(shuō)還有許多問(wèn)題需要進(jìn)一步研究。下面對(duì)矢量量化未來(lái)發(fā)展的展望：
(1) 矢量量化是一種信源編碼技術(shù)，在矢量量化器設(shè)計(jì)的過(guò)程中，考慮如何降低信道傳輸中可能造成的噪聲干擾的影響，可以提高矢量量化系統(tǒng)的整體性能。歸結(jié)起來(lái)，可以用矢量量化碼書(shū)索引分配問(wèn)題來(lái)描繪，即研究如何合理的安排碼書(shū)中碼字的排序，使得編碼系統(tǒng)在信道傳輸中的容錯(cuò)能力增強(qiáng)。
(2) 矢量量化作為一種數(shù)據(jù)壓縮技術(shù)，如何更好地應(yīng)用到實(shí)際的數(shù)據(jù)壓縮和傳輸系統(tǒng)中去，在實(shí)際應(yīng)用中體現(xiàn)編碼算法的優(yōu)越性，是一個(gè)很實(shí)際的問(wèn)題，在設(shè)計(jì)算法的同時(shí)，要考慮應(yīng)用的實(shí)際情況。
(3) 本文中在圖像的編碼方面對(duì)矢量量化進(jìn)行研究，矢量量化技術(shù)并不僅僅用在圖像編碼中，可以根據(jù)實(shí)際需要，可以深入對(duì)其進(jìn)行深入研究，如可以在語(yǔ)音壓縮編解碼、音視頻壓縮和遠(yuǎn)程會(huì)議等方面，還可以將這些成果應(yīng)用到其方面一數(shù)字水印、語(yǔ)音識(shí)別、語(yǔ)音合成以及文字合成以及文字的識(shí)別等。