基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究分析

摘 要

伴隨著通訊與信息科技的迅猛發(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ù)–碼書生成和碼字搜索和碼字索引分配。詳細(xì)闡述了碼書設(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)有兩大類：一類是傳輸模擬信號(hào)f(t)的模擬通信系統(tǒng)；另一類是傳輸數(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ā)展，人類社會(huì)進(jìn)入到了前所未有的信息化時(shí)代。隨著信息時(shí)代的來(lái)臨人們對(duì)通信業(yè)務(wù)的要求不斷增長(zhǎng)，在日常生活中，大量的信息數(shù)據(jù)需要傳輸、存儲(chǔ)和處理?？茖W(xué)實(shí)驗(yàn)表明，人類從外界獲取的知識(shí)之中，有80%以上都是通過(guò)視覺感知獲取的【1】。眼睛獲取的是圖像信息，和語(yǔ)音、文字等信息相比，圖像包含的信息量更大、更直觀、更確切，因而具有更高的使用效率和更廣泛的適應(yīng)性，一幅圖勝過(guò)千言萬(wàn)語(yǔ)， 圖像信息是人類認(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幀/秒)下，畫面分辨率為640 x 480下，真彩色(24位)的圖像序列，播放1秒鐘的視頻畫面數(shù)據(jù)量為：640 x 480 x 3 x 25 = 23,040,000字節(jié)，相當(dāng)于存貯一千多萬(wàn)個(gè)漢字所占用的空間。如此龐大的數(shù)據(jù)量，給圖像的傳輸、存貯、傳輸線的傳輸率(帶寬)以及計(jì)算機(jī)的處理速度等增加巨大的壓力。由此可見，對(duì)降低傳輸成本，增加數(shù)據(jù)傳輸?shù)目煽啃裕粩酀M足人們對(duì)信息傳輸?shù)男枨?，圖像壓縮都具有十分重要的作用。為了解決好這個(gè)問題，我們就必須對(duì)圖像進(jìn)行編碼壓縮，在保證一定圖像質(zhì)量的前提下，有效地減少傳輸時(shí)所需的數(shù)據(jù)量和占用的頻帶。
1．1．2 研究意義
圖像壓縮就是在沒有明顯失真的前提下，將圖像的位圖信息轉(zhuǎn)變成另外一種能將數(shù)據(jù)量縮減的表達(dá)形式，即去處冗余信息。首先，盡管圖像中數(shù)據(jù)量很大，但其行、列以及幀間都具有極強(qiáng)的相關(guān)性或冗余信息。即一個(gè)象素的灰度值，總是和它周圍的象素的灰度值有著某種關(guān)系，可以由它們推算表示出來(lái)，應(yīng)用某種方法提取或減少它們之間的這種相關(guān)性，即可實(shí)現(xiàn)圖像壓縮。其次，大部分圖像視頻信號(hào)的最終接收者都是人眼，而人類的視覺系統(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ì)八十年代開始逐步完善起來(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è)計(jì)方法【4】，該文獻(xiàn)己經(jīng)成為矢量量化的經(jīng)典文獻(xiàn)，是矢量量化技術(shù)發(fā)展的基石。
在20多年歷程中，學(xué)者們?cè)谝韵挛鍌€(gè)方面對(duì)矢量量化技術(shù)展開研究：
1. 針對(duì)基本矢量量化器復(fù)雜度大和比特率固定的缺點(diǎn)，開發(fā)其它類型的矢量量化器；
2. 針對(duì)基本矢量量化器的LBG碼書設(shè)計(jì)算法容易陷入局部極小、初始碼書影響優(yōu)化結(jié)果和計(jì)算量大的缺點(diǎn)，學(xué)者們引入了神經(jīng)網(wǎng)絡(luò)、優(yōu)化理論、模糊集合等技術(shù)，提出了各種各樣的碼書設(shè)計(jì)算法；
3.在矢量量化編碼場(chǎng)合中，針對(duì)基本矢量量化器的窮盡搜索編碼算法的計(jì)算量大和比特率固定的缺點(diǎn)，提出各種各樣的快速碼字搜索算法和變比特率碼字搜索算法；
4. 矢量量化技術(shù)的應(yīng)用；
5. 考慮到信道噪聲將會(huì)在矢量量化解碼端引入額外失真，學(xué)者們開始研究碼字索引分配算法以減少由于信道噪聲引起的失真。
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ǔ)；最后寫了矢量量化的關(guān)鍵技術(shù)和矢量量化技術(shù)指標(biāo)。
第三章是對(duì)矢量量化算法的研究，首先分別論述了矢量量化的三大關(guān)鍵技術(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)典理論而登載于各種專著，并得到廣泛的應(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)景比較簡(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è)問題，人們?cè)诶^續(xù)探索數(shù)據(jù)壓縮技術(shù)的同時(shí)，著手研制生產(chǎn)高性能的芯片和系統(tǒng)。一般在對(duì)時(shí)間要求不高的場(chǎng)合采用軟件壓縮，而對(duì)運(yùn)行速度有特殊要求的情況下，可使用硬件壓縮。不過(guò)，目前硬件壓縮的開銷遠(yuǎn)遠(yuǎn)大于軟件壓縮的開銷。
2．1．2 數(shù)據(jù)壓縮技術(shù)的分類
數(shù)據(jù)壓縮的研究已有幾十年的歷史，其間，人們提出了各種各樣的壓縮算法。在分類上，也存在幾種不同的方法，有人按編碼失真程度或者說(shuō)按壓縮過(guò)程的可逆性將數(shù)據(jù)壓縮編碼分為兩種類型:無(wú)失真壓縮編碼 (Noiseless Coding)與有失真壓縮編碼 (Noise Coding)；有人按編碼基建模的不同將數(shù)據(jù)壓縮分成模型基編碼和波形基編碼；又有人將它分為第一代壓縮編碼和第二代壓縮編碼；還可按壓縮技術(shù)所使用的方法進(jìn)行分類，可分為預(yù)測(cè)編碼(Predictive Coding)、變換編碼(Transform Coding)和統(tǒng)計(jì)編碼(Statistical Coding)三大類。目前，較為認(rèn)可的是第一種分類方法【6】。
1．無(wú)失真壓縮
無(wú)失真壓縮也可稱之為冗余度壓縮(Redundancy Compression)，在數(shù)字圖象壓縮中，有3種基本的數(shù)據(jù)冗余：編碼冗余、像素間冗余以及心理視覺冗余。而無(wú)失真壓縮就是利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，除去或盡量除去數(shù)據(jù)中重復(fù)和冗余部分，而不丟失其中的任何信息，可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為2:1到5: 1這類方法廣泛用于文本數(shù)據(jù)、程序和特殊應(yīng)用場(chǎng)合的圖像數(shù)據(jù)(如醫(yī)學(xué)圖像等)的壓縮.由于壓縮比的限制，僅使用無(wú)損壓縮方法不可能解決圖像和數(shù)字視頻的存儲(chǔ)和傳輸問題。
常用的無(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ā)明人名字的縮寫（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．有失真壓縮
有失真壓縮也可稱為嫡壓縮(Entropy Compression)，這是一種不可逆壓縮。他利用了人類視覺對(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ú)失真壓縮主要有兩大類型：特征抽取和量化方法，特征抽取的典型例子如指紋、漢字的模式識(shí)別，一旦抽取出足以有效表征與區(qū)分不同模式的特征參數(shù)，便可用它取代原始的圖像數(shù)據(jù)，這一類方法一般是用于特定的環(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ù)的分類
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)，則算法稱為對(duì)稱的，反之稱為非對(duì)稱的。
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， 又稱為均方誤差（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)注，八十年代開始逐步發(fā)展完善起來(lái)。1956年，Steinhaus第一次系統(tǒng)闡述了最佳矢量量化問題【8】；1978年，Buzo第一個(gè)提出實(shí)際的矢量量化器。1980年，Linde, Buzo和Gray將Loyd-Max算法推廣，提出了一種有效的矢量量化碼書設(shè)計(jì)算法一一LBG【4】算法，將矢量量化技術(shù)的研究和推廣應(yīng)用推向了高潮，成為矢量量化技術(shù)發(fā)展的里程碑。
在20多年的發(fā)展歷程中，人們?nèi)嫜芯苛耸噶苛炕睦碚摵蛻?yīng)用，開發(fā)了多種類型的矢量量化器。雖然矢量量化技術(shù)研究已經(jīng)日趨成熟，但仍存在很多有待解決的問題，如矢量量化碼書標(biāo)準(zhǔn)與編碼對(duì)象密切相關(guān)，不同應(yīng)用場(chǎng)合下碼書結(jié)構(gòu)、尺寸以及矢量維數(shù)都不相同。矢量量化的壓縮標(biāo)準(zhǔn)也一直沒有提出。目前的研究大多停留在理論方面，各種優(yōu)化的矢量量化器的硬件實(shí)現(xiàn)還有待于進(jìn)一步的研究。因此，有關(guān)矢量量化技術(shù)的研究還有很多工作要做。
矢量量化在20多年的發(fā)展歷程中，主要是從以下幾方面得到了發(fā)展：
(1) 矢量量化器的研究，對(duì)基本矢量量化器復(fù)雜度大和比特率固定的缺點(diǎn)，開發(fā)其它類型的矢量量化器；
(2) 矢量量化碼書設(shè)計(jì)算法研究：針對(duì)基本矢量量化器的LBG碼書設(shè)計(jì)算法 容易陷入局部極小、初始碼書影響優(yōu)化結(jié)果和計(jì)算量大的缺點(diǎn)，學(xué)者們引入神經(jīng) 網(wǎng)絡(luò)、優(yōu)化理論、模糊集合等技術(shù)，提出了各種各樣的碼書設(shè)計(jì)算法；
(3) 矢量量化碼字搜索算法研究：在矢量量化編碼場(chǎng)合中，針對(duì)基木矢量量 化器的窮盡搜索編碼算法的計(jì)算量大和比特率固定的缺點(diǎn)提出各種各樣的快速 碼字搜索算法和變化特率碼字搜索算法；
(4) 矢量量化碼字索引分配算法研究：考慮到信道噪聲將會(huì)在矢量量化解碼端引入額外失真，學(xué)者們開始研究碼字索引分配算法以減少信道引起的失真。
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)碼字矢量集合，稱為碼書，其尺寸(大小)為N。碼書的N個(gè)元素Yi稱為碼字或者碼矢量，它們均為k維歐幾里得空間 中的矢量。輸入矢量空間 通過(guò)尺寸為N的矢量量化器Q后，被分割成N個(gè)互不重疊的區(qū)域又稱為胞腔，這個(gè)過(guò)程稱為輸入矢量空間的劃分。對(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）
其中， ，平均失真滿足公式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 )，稱x為輸入矢量。設(shè) 為一個(gè)K維輸入矢量的集合。
再把T劃分成M( N)個(gè)子空間 ，即各子空間滿足公式(2.8)：
(2.8)
通常，我們把這M個(gè)子空間稱為Voronoi胞腔(Cells)，或者簡(jiǎn)稱胞腔，有時(shí)也把它稱為一個(gè)分類或分區(qū)。在每個(gè)胞腔R，中我們?cè)僬业揭粋€(gè)代表元Yi,我們稱所有這些代表元組成的集合C=( )為碼書(Codebook)。這些代表元也稱為碼字(Codeword)集合1= (1,2,…, M}稱為碼字的索引集合。一個(gè)矢量量化器包括編碼器和解碼器兩部分。編碼器主要包括一個(gè)碼書和一個(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è)與編碼器相同的碼書和一個(gè)碼字檢索器 (i)。