摘 要

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

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

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

圖2.1 數據壓縮技術的分類
2．1．3 數據壓縮算法的度量標準
對于一種數據壓縮算法的性能，有一定的衡量標準，為了后面幾章描述的方便，也為不至于產生歧義，對這些標準作以簡單的介紹【7】。
1．算法性能評價
1）壓縮比（CR：Compression Ratio）：
壓縮比定義為原始數據量與壓縮后量的比值，即
壓縮比 = 原始數據量/壓縮后量
2）計算復雜度：
計算復雜度可以用算法處理一定量數據所需的基本運算次數來度量。如處理一幀有確定的分辨率和顏色數的圖像所需的加法次數和乘法次數。
壓縮算法分為編碼部分和解碼部分，如果兩者的計算復雜度大至相當，則算法稱為對稱的，反之稱為非對稱的。
2．圖像質量評價
1）均方誤差（MSE）
對于模擬信號，設原始數據為x(t)，編碼、解碼后的數據為y(t)，二者之差為e(t)，即e(t) = x(t) - y(t)。則e(t)的方差如公式2.1所示：
（2.1）
通常誤差均值μe=0， 又稱為均方誤差（Mean Squared Error）。
2）信噪比（SNR）：
對于離散信號，設原始數據為 ，編碼、解碼后的數據為 ，它們的差值為 的均方誤差為 ，信噪比（Signal to Noise Ratio）定義為原始數據方差 與重建數據誤差方差 的比值如公式2.2所示：
（2.2）
3）峰值信噪比（PSNR）：
對于離散圖像數據，在信噪比的計算中常用圖像數據中的最大值xmax來代替均方根值бx，得到峰值信噪比如公式2.3所示
（2.3）
2．2 矢量量化的定義及理論基礎
2．2．1 矢量量化的起源及發展
矢量量化基本理論早在20世紀六七十年代己有人關注，八十年代開始逐步發展完善起來。1956年，Steinhaus第一次系統闡述了最佳矢量量化問題【8】；1978年，Buzo第一個提出實際的矢量量化器。1980年，Linde, Buzo和Gray將Loyd-Max算法推廣，提出了一種有效的矢量量化碼書設計算法一一LBG【4】算法，將矢量量化技術的研究和推廣應用推向了高潮，成為矢量量化技術發展的里程碑。
在20多年的發展歷程中，人們全面研究了矢量量化的理論和應用，開發了多種類型的矢量量化器。雖然矢量量化技術研究已經日趨成熟，但仍存在很多有待解決的問題，如矢量量化碼書標準與編碼對象密切相關，不同應用場合下碼書結構、尺寸以及矢量維數都不相同。矢量量化的壓縮標準也一直沒有提出。目前的研究大多停留在理論方面，各種優化的矢量量化器的硬件實現還有待于進一步的研究。因此，有關矢量量化技術的研究還有很多工作要做。
矢量量化在20多年的發展歷程中，主要是從以下幾方面得到了發展：
(1) 矢量量化器的研究，對基本矢量量化器復雜度大和比特率固定的缺點，開發其它類型的矢量量化器；
(2) 矢量量化碼書設計算法研究：針對基本矢量量化器的LBG碼書設計算法 容易陷入局部極小、初始碼書影響優化結果和計算量大的缺點，學者們引入神經 網絡、優化理論、模糊集合等技術，提出了各種各樣的碼書設計算法；
(3) 矢量量化碼字搜索算法研究：在矢量量化編碼場合中，針對基木矢量量 化器的窮盡搜索編碼算法的計算量大和比特率固定的缺點提出各種各樣的快速 碼字搜索算法和變化特率碼字搜索算法；
(4) 矢量量化碼字索引分配算法研究：考慮到信道噪聲將會在矢量量化解碼端引入額外失真，學者們開始研究碼字索引分配算法以減少信道引起的失真。
2．2．2 矢量量化的定義及理論基礎
1. 定義
一個維數為k，尺寸為N的矢量量化器可以定義為從k維歐兒里得空間 到一個包含N個輸出(重構)點的有限集合C的映射Q【9】，表示為公式（2.4）：
（2.4）
其中， 。
C是重構碼字矢量集合，稱為碼書，其尺寸(大小)為N。碼書的N個元素Yi稱為碼字或者碼矢量，它們均為k維歐幾里得空間 中的矢量。輸入矢量空間 通過尺寸為N的矢量量化器Q后，被分割成N個互不重疊的區域又稱為胞腔，這個過程稱為輸入矢量空間的劃分。對 胞腔 定義為公式（2.5）：
（2.5）
2. 理論基礎
矢量量化的理論基礎是香農的率失真理論。1948年，香農定義了信道容量，并證明只要編碼速率不超過信道容量，符號就能以任意小的差錯概率在該信道中傳輸。1959年，香農定義了率失真函數R(D)，并證明只要R(D)不超過信道容量就能保證接收端的失真不超過給定閾值D。在數學上，R (D)定義為在給定失真D的條件下，系統所能夠達到的最小碼速率。對于幅值離散的信源， R(D)定義如下公式（2.6）所示:
（2.6）
其中， ，平均失真滿足公式2.7：
（2.7）
式中d(X,Y)是失真測度，它表示輸出采樣值Y再現原始采樣值X所引入的失真， P(Y/X)表示在己發送X的情況下接收到Y的概率。R(D)的單位為比特/采樣。同樣，也可以定義失真率函數D(R)，它是率失真函數的逆函數，其含義為在定速率不超過R的條件下，系統所能夠達到的最小失真，它是在維數k趨向無窮大時Dk(R)的極限，即 。
香農理論表明在速率受限的條件下或在平均失真受限的情況下，通信系統所能達到的最優性能。率失真函數通常又被作為理論最優值，如果一個系統的性能低于理論最優值，則一定可用更好的編碼技術獲得系統性能的改善；如果一個系統的性能接近理論最優值，則此系統已接近最優，無法再做太多改善；一個系統的性能不可能優于理論最優值。由香農理淪可知，理論上，矢量量化技術只要不斷的增加矢量的維數k，編碼的性能就可任意接近率失真函數，使系統性能達到最優。因此，香農的率失真理論指出了矢量量化技術的優越性，是矢量量化技術的理論基礎。
2．3 矢量量化的相關概念
2．3．1 數學模型
設有一個信源采樣數據序列，我們把每K個數據分成一組，每組數據都記錄成矢量形式 (i =1,2 ,…,N )，稱x為輸入矢量。設 為一個K維輸入矢量的集合。
再把T劃分成M( N)個子空間 ，即各子空間滿足公式(2.8)：
(2.8)
通常，我們把這M個子空間稱為Voronoi胞腔(Cells)，或者簡稱胞腔，有時也把它稱為一個分類或分區。在每個胞腔R，中我們再找到一個代表元Yi,我們稱所有這些代表元組成的集合C=( )為碼書(Codebook)。這些代表元也稱為碼字(Codeword)集合1= (1,2,…, M}稱為碼字的索引集合。一個矢量量化器包括編碼器和解碼器兩部分。編碼器主要包括一個碼書和一個量化器。
量化器Q(X)定義如式(2.9)：
Q: T C；
當X 時，Q (X)= Yi (i=1 ,2,…,M). (2.9)
其中，Q(X)是一個多對一的函數，因此它是不可逆的。解碼器主要包括一個與編碼器相同的碼書和一個碼字檢索器 (i)。