矢量量化

矢量量化（ — ）展據壓縮技術基思：若干標量據組構矢量，矢量空整量化，壓縮據損息。矢量量化編碼圖、語號編碼技術研究較型量化編碼，僅僅量化器設計提，壓縮編碼研究。傳統預測換編碼，首號某映射換序列，標量量化編碼。而在矢量量化編碼中，則是把輸入數據幾個一組地分成許多組，成組地量化編碼，即將這些數看成一個k維矢量，然後以矢量為單位逐個矢量進行量化。矢量量化是一種限失真編碼，其原理仍可用資訊理論中的率失真函數理論來分析。而率失真理論指出，即使對無記憶信源，矢量量化編碼也總是優於標量量化。

矢量量化編碼，鍵碼建碼搜索算。

碼算類型，源布設計算；另未源布，源列具且足夠集合（即訓練序列）設計算。證，源矢量衡且遍歷，若訓練序列充則算價。

碼字搜索是矢量量化中的一個最基本問題，矢量量化過程本身實際上就是一個搜索過程，即搜索出與輸入最為匹配的碼矢。矢量量化中最常用的搜索方法是全搜索演演算法和樹搜索演演算法。全搜索演演算法與碼本生成演演算法是基本相同的，在給定速率下其複雜度隨矢量維數K以指數形式增長，全搜索矢量量化器性能好但設備較複雜。樹搜索演演算法又有二叉樹和多叉樹之分，它們的原理是相同的，但後者的計算量和存儲量都比前者大，性能比前者好。樹搜索的過程是逐步求近似的過程，中間的碼字是起指引路線的作用，其複雜度比全搜索演演算法顯著減少，搜索速度較快。由於樹搜索並不是從整個碼本中尋找最小失真的碼字，因此它的量化器並不是最佳的，其量化信噪比低於全搜索。

矢量量化的使用：

n如果一個2x2像素的小塊，每像素有8位表示，則所有的像素塊的可能取值有：232=4G種，可以選擇一個遠遠小於這個數的數n，作為碼書中碼的個數，然後對圖像中的每個塊（矢量），用一個碼書中的碼來近似，這樣只需用這個碼的編號來編碼這個圖像矢量即可，因此每一個小塊，最後都只需用log2n個位來表示，由此達到壓縮的目的。

圖像塊與碼書中碼的匹配：

n設圖像塊B=(b1, b2, …, bn)

碼矢量：C=(c1, c2, …, cn)

n圖像塊與碼矢量的匹配程度，由它們之間的“距離”來度量，一般d(B, C)可取如下之一：

nΣ|bi - ci|

nΣ(bi– ci)2

nMax|bi - ci|

nd(B, C) 可以看成失真程度的一種度量(B用C表示時)

LBG演演算法：

nLBG演演算法是由Linde, Buzo 和 Gray三位學者提出的方法。其主要的思想是：從一組碼矢量出發，將所有的圖像矢量進行劃分，然後再重新計算碼矢量，直到碼矢量的變化收斂時，即完成了碼書的選擇。

主要步驟：

1.隨意選取n個圖像塊作為碼矢量

2.由這n個碼矢量對所有的圖像塊進行劃分，即分成n個集合，使每個集合中的圖像塊，都是與各碼矢量距離中，與對應的碼矢量的距離最小的

3.由這n個集合的重心，得到n個新的碼矢量

4.如果這些個碼矢量與原來的碼矢量變化不大（收斂），就完成碼書的訓練，否則重新進行2、3步

例子：

n假設每像素8位，分成兩個像素的小塊。

n圖像共有24個像素，12個小塊：

B1=(32,32), B2=(60,32), B3=(32,50), B4=(60,50), B5=(60,150), B6=(70,140), B7=(200,210), B8=(200,32), B9=(200,40), B10=(200,50), B11=(215,50), B12=(215,35)

n初始碼書：C1=(70,40), C2=(60,120), C3=(210,200), C4=(225, 50)

矢量量化可以充分利用各分量間的統計依賴性，包括線性的和非線性的依賴關係，並可以充分利用信號概率分佈密度函數形狀中存在的剩餘度。它還可以充分利用信號空間維數增加所帶來的好處。在維數足夠高時，可以任意接近率失真理論所給出的極限，而這在標量量化時是做不到的。

對空間的毎一矢量x來說，矢量量化就是把x映射為L個離散矢量yi（1≤i≤L）中的一個。yi稱為碼矢，其集合稱為碼本。這一過程有時也被分為編碼和解碼兩個過程。在編碼時，空間中每一矢量都得到一個特定的地址γ（x），解碼時由地址轉換成碼矢yi=β[γ（x）]=f（x）。γ和β分別表示編碼和解碼完成的運算。量化帶來的失真稱為量化失真。對這一失真的量度可以有多種方法，如歐氏距、漢明距等。失真量度的選擇原則是：實用中有意義，數學上好處理、實現時便於計算。在一定約束條件下能使平均失真達到最小的量化稱為最詿t化，相應的量化器稱為最佳量化器。在矢量量化中初始碼本的選擇是一個重要問題。產生初始碼本的方法通常有兩種：第一種方法的碼本，指一開始就對其大小有要求的碼本，這種方法如隨機碼方法、乘積碼方法；第二種方法的碼本，在開始時只有很少幾個碼矢，在迭代訓練中逐步增加到所要求的大小，這種方法如碼分裂法等。特別是人工神經網路，為量化器的設計提供了新途徑，如自組織特徵映射法和模擬退火法，都是設計碼本的有效方法。象模擬退火法，它可以有效地避免局部最優解。

非全搜索的矢量量化器：基本的矢量量化器在量化時要對碼本中的碼矢進行全面搜索，被稱為全搜索式量化器。這種量化器在實現時需要很大的計算量和存儲量。所以在實用中有多種減少複雜性的量化器，它們的共同特點是使碼本具有某種結構。這樣，碼本的存儲和搜索就都可能結構化，從而減少計算量和存儲量。這種非全搜索的量化器主要有：樹狀搜索量化器或分層量化器；乘積碼本量化器或分類量化器；格子狀量化器。

有記憶的矢量量化器：矢量量化在原理上可以用很高的維數，但因複雜性的限制，維數又不能很高。這時，有記憶的量化器是解決矢量維數有限而信號有很長記憶這一矛盾的有效方法。有記憶的矢量量化器有多種具體的形式，如有限狀態量化器、矢量預測量化器、反饋式矢量量化器、自適量矢量預測器等。

矢量量化已得到廣泛應用。例如在語音編碼和圖像編碼以及各種模式識別中都有重要的應用。而且它在如何適應複雜的失真量度，如何適應信號的統計特性以及如何減少實現時的複雜性等幾個主要方面，也有很大的發展。