矢量量化

矢量量化是七十年代發展起來的一種數據壓縮技術, 其理論基礎是信息論中的“速率—失真理論”。對一定的碼率R, 最小量化失真D (用量化信號與原始信號之間的誤差均方值和原信號均方值之比來衡量) 是一定的,即D可表示為R的函數D (R) 。無論對於何種信源, 矢量量化總優於標量量化, 且矢量維數越大, 優越性越高。由此可知, 對於一個特定的信息源, 若給定碼率R, 那麼任何量化器都不可能獲得低於“速率—失真理論”給出的下限D (R) 的量化失真。矢量量化的研究目的, 在於針對特定的信息源和矢量維數, 找到一種最優的矢量量化器, 能夠在R一定時給出最小的失真。 ^[3] 

矢量量化是標量量化的拓廣和延伸。可以這樣描述矢量量化的基本原理。 ^[4]  設有N個K維矢量{X1, X2, …, XN}, 其中第i個矢量可記為Xi={xi1, xi2, …, xik}, i=1, 2…, N。把K維空間RK無遺漏的劃分為J個互不相交的子空間R1, R2, …RJ, 即滿足:R1∪R2∪…∪RJ=RK;Ri∩Rj=!, i≠j。這些子空間R1, R2, …RJ稱為胞腔 (cell) 。在每一個子空間中找出一個代表矢量Yi={yi1, yi2, …, yik}, i=1, 2…, J。令矢量集Y=[Y1, Y2, …, YJ], Y叫作碼書或碼本, Yi叫碼字 (code word) 或碼矢 (code vector) , 碼書Y中的矢量個數J叫作碼書長度。矢量量化的過程就是對任意輸入矢量X∈RK, 在Y中找到一個與X最接近的Yi代替X, Yi就是X的量化值。矢量量化的過程可以看成是從K維歐氏空間RK到其中一個有限子集Y的映射。這個映射可以記為:Q:RK→Y={Y1, Y2, …, YJ}。 ^[5] 

矢量量化是標量量化思想的一種自然推廣。標量量化利用了數據間的線性依賴性和概率密度函數的形狀來消除冗餘度。香農的速率-失真理論表明，即使信源是無記憶的，利用矢量編碼代替標量編碼總能在理論上得到更好的性能。實際上，是兩種各分量間存在4種相互關聯的性質：線性依賴性、非線性依賴性、概率密度函數的形狀以及矢量維度。為了去掉數據之間的這些冗餘，作為標量量化的一種推廣，矢量量化就能夠更好地壓縮數據。 ^[6] 

矢量量化的三大關鍵技術,即碼書設計、碼字搜索和碼字索引分配。 ^[7] 

矢量量化設計的首要問題和核心問題是碼書的設計。如果沒有碼書的設計, 那麼整個矢量量化系統就無法實現。碼書的質量直接影響到壓縮效率和復原信號的質量。 ^[7] 

1980年, Linde, Buzo和Gray提出了一種有效的矢量量化碼書設計算法, 也就是在矢量量化技術的發展中具有里程碑意義的LBG算法。LBG算法是碼書設計的一種經典算法, 其優點為物理概念清晰、算法理論嚴密及算法容易實現。但是, LBG算法並不完美, 它的主要缺點是:對初始碼書的依賴性強, 易收斂於局部最優。學者們主要針對LBG算法易陷入局部最小失真和對初始碼書的依賴性強這兩個方面對其進行改進, 提出了多種改進算法。a.基於神經網絡的碼書設計, 如自組織特徵映射算法 (SOFM)， ^[8]  它的收斂特性受初始碼書的影響較小, 對初始碼書和訓練矢量的要求較低, 且可以很方便的修改已有的碼書。它的缺點是計算量大。b.遺傳算法。針對LBG易陷入局部最優的問題進行的改進, 能得到全局最優解。 ^[7] 

碼字搜索是矢量量化的一項關鍵技術。碼字搜索是指在碼書已經存在的情況下, 對於給定的輸入矢量, 在碼書中搜索與輸入矢量之間失真最小的碼字。研究碼字搜索算法的主要目的就是尋求快速有效的算法以減少計算複雜程度, 且儘量使算法易於硬件實現。 ^[7] 

針對窮盡搜索算法的缺點, 許多文獻提出了各種各樣的快速算法, 這些碼字搜索算法可以分為兩大類:一類是基於特殊碼書結構的快速算法, 這類算法依賴於碼書結構而在編碼時只搜索較小的子碼書, 如分類矢量量化和基於樹結構的矢量量化 ^[9]  等, 第二類算法不依賴於碼書, 這類算法通常採用一些碼字排除準則以減少計算量。這些算法有:a.部分失真搜索算法 (Partial Distortion Search, PDS) 。部分失真搜索算法的思想是:在計算某個碼字與輸入矢量之間的失真測度的過程中始終判斷累計的部分失真是否已經超過目前的最小失真, 一旦超出則終止該碼字與輸入矢量間的失真計算。部分失真搜索算法是一種簡單有效的算法, 但是其效率是有限的。b.基於Hadamard變換的搜索算法 ^[10]  。這類算法利用了變換域的特點, 一是在變換域內搜索最匹配碼字和在空間域內搜索最匹配碼字是等價的, 另一個是變換域具有能量集中的特點。利用變換域的特點和其他搜索算法相結合能夠產生的較高效率的算法。 ^[7] 

在矢量量化編碼和解碼系統中，如果信道有噪聲，則信道輸入端的索引i經過信道傳輸可能輸出索引j而不是索引i，從而在解碼端引入額外失真。為了減少這種失真，可對碼字索引進行重新分配。碼字索引分配就是在N！種分配方案中尋求一種最佳方法使得由信道噪聲引起的失真最小。然而當N！較大時，測試所有方案是不可能的。因此，研究碼字索引分配算法的目的就是尋求有效的算法儘可能找到全局最優或接近全局最優的方案以減少由信道噪聲引起的失真，並儘可能減少計算複雜度和搜索時間。 ^[7] 

矢量量化(VQ)作為一種有效的有損壓縮技術,其突出優點是壓縮比大以及解碼算法簡單,因此它已經成為圖像壓縮編碼的重要技術之一。矢量量化壓縮技術的應用領域非常廣闊,如軍事部門和氣象部門的衞星(或航天飛機)遙感照片的壓縮編碼和實時傳輸、雷達圖像和軍用地圖的存儲與傳輸、數字電視和DVD的視頻壓縮、醫學圖像的壓縮與存儲、網絡化測試數據的壓縮和傳輸、語音編碼、圖像識別和語音識別等等。矢量量化技術的研究涉及多學科領域的理論和技術,無論從理論角度還是從應用角度來看,開展對矢量量化技術的研究,不但具有重要的學術意義,還有極為重要的國防意義和經濟意義。 ^[11]