【文章內(nèi)容簡介】 重構矢量與輸入矢量之間的差異的度量。假設一個輸入矢量X的重構矢量為Y都定義在k維歐幾里德空間上，因量化過程會產(chǎn)生失真，那么設該失真為d(X，Y)，且滿足以下三個性質(zhì)：正定性，對稱性，三角不等式。以下是幾種常見的失真測度方法。(a)平方誤差測度。通過輸入矢量X與其對應的重構矢量Y=Q(X))的平方歐幾里德距離可導出為均方誤差，其公式為， （公式3）(b)Minkowshi測度矢量。X和Y的之間的p階Minkowshi測度為， （公式4）三種常見的特殊測度為：當p=1時，L1(絕對誤差)測度；當p=2時，L2(歐幾里德)測度；當p為無窮大時，L (切比雪夫)測度。(c)假設有一幅MN的L級灰度圖像，其原始圖像像素值為，而重構圖像像素值為，則有： 均方誤差 （公式5） 信噪比 （公式6） 峰值信噪比 （公式 7） 矢量量化的實現(xiàn)復雜度矢量量化的復雜度分為時間復雜度和空間復雜度，且復雜度隨矢量維數(shù)的增加而呈指數(shù)形式增加，這成為了高維矢量量化的實現(xiàn)障礙之一。時間復雜度，一般有兩種衡量方法，假設碼書大小為N，矢量維數(shù)為k。第一種，考慮到每個輸入矢量所用到的乘法、加法和比較次數(shù)，則其復雜度為kN次乘法加(2k1)N次加法再加(N1)次比較。第二種，僅用乘法運算次數(shù)來度量量化一個輸入矢量的復雜度，則復雜度為kN。至于空間復雜度，基本的窮盡搜索矢量量化器的空間復雜度為kN。雖然存儲器的容量在不斷增長，價格也在下降，但假如數(shù)據(jù)量很大，則讀取數(shù)據(jù)的時間也將耗費很多，故空間復雜度也不能忽視。 矢量量化的關鍵技術介紹在上文中提過，矢量量化器的設計有幾個關鍵的環(huán)節(jié)，矢量量化器設計的成敗和好壞基本取決于這幾個關鍵環(huán)節(jié)的設計是否有效，這些環(huán)節(jié)也正是矢量量化技術研究的關鍵點。這些關鍵技術包括碼書設計、碼字搜索和碼字索引分配，其中碼字索引分配是比較新的研究方向，文章將著重論述碼書設計和碼字搜索。 碼書設計矢量量化設計的首要問題和核心問題就是設計出性能好的碼書。如果碼書設計效果差，那么不僅是碼書質(zhì)量差，而且還導致整個設計系統(tǒng)的壓縮效率和編碼質(zhì)量受到重大影響。碼書設計的過程就是找到一種最佳方案，把M個訓練矢量分成N類，并將各類的質(zhì)心矢量作為碼書的碼字。然而當訓練矢量數(shù)較大和分類較多的時候，搜索全部碼書將會耗費巨大處理時間，這直接影響到矢量量化器的實用性，因而碼書設計的目的就是尋求有效的算法的找到或接近全局最優(yōu)的碼書，使失真最小，以提高碼書的實用性，并降低計算復雜度。LBG算法是基于最佳矢量量化器的最佳劃分和最佳碼書的生成這兩個條件的，該算法物理概念清晰、算法理論嚴謹、實現(xiàn)容易。但LBG算法存在著不足，首先是對初始碼書的依賴性強，初始碼書選取的好壞直接影響碼書訓練的收斂速度和碼書最終的性能。其二由于LBG是基于聚類方法的，需要不斷迭代，而每次迭代，需要從碼書中查找到最近鄰碼字，這將耗費大量的存儲空間和繁瑣的計算時間。還有，就是碼書的自適應力不強，無法自適應地跟蹤圖像信源的特性。而且最終碼書只能收斂到基于訓練矢量的局部最優(yōu)，碼書的生成速度也比較慢。LBG算法是無記憶的窮盡搜索矢量量化方法，雖然可以獲得質(zhì)量較優(yōu)的碼書，但是碼書形成的復雜度比較高，使得使用該碼書的矢量量化編碼的復雜度也高。針對以上這些問題，專家學者們提出了許多改進算法。這些改進算法主要是基于初始碼書的選取，即改進碼書的初始化技術，還有就是引進快速碼字搜索算法和采用其他技術提高碼書性能或加快設計速度的技術。這些算法都旨在提高矢量量化碼書的質(zhì)量和降低計算復雜度。 碼字搜索矢量量化設計的另一個關鍵技術，就是碼字搜索技術。碼字搜索，是指在已經(jīng)給定碼書的情況下，對于當前輸入矢量，采用某種度量方法，在碼書中搜索出與輸入矢量之間失真最小的碼字。在一般常規(guī)的全搜索編碼矢量量化器中，假如碼書長度為N，碼字維數(shù)為k，那么當要為一個輸入矢量進行編碼時，就必須進行N次距離計算和N1次比較。上文中已經(jīng)論述了，在采用平方誤差測度時，矢量量化的時間和空間復雜度，如果碼書較長，碼字的維數(shù)也大的話，計算的復雜度將會變得很大。因此碼字搜索算法研究的目的就是尋求快速有效的算法以減少計算復雜度，讓搜索算法便于硬件的實現(xiàn)。根據(jù)窮盡搜索算法的缺點，專家提出了許多改進的快速搜索算法，算法有：基于不等式判據(jù)的快速碼字搜索算法；基于變換域的快速碼字搜索算法；基于金字塔結(jié)構的快速碼字搜索算法等。矢量量化的快速碼字搜索算法，是解決編碼時計算復雜度高的方法之一，這些算法都在力求待量化矢量和碼字之間距離與它們的一些低維特征量的不等式關系，以排除大量不可能的碼字，不過這得以增加較少的存儲量為代價，但它們在很大程度上降低了計算復雜度，提高了搜索效率。 矢量量化的碼書設計方法一般情況下，基于窮盡搜索方法的矢量量化碼書設計，能夠得到較好的量化質(zhì)量，因此很多改進的矢量量化器的設計都是以基于窮盡搜索方法矢量量化碼書設計算法為基礎，而該算法就是經(jīng)典的LBG算法。研究碼書的設計方法，目的就是為了尋求一個最優(yōu)碼書設計方法，以提高碼書的質(zhì)量，降低計算復雜度。 矢量量化碼書設計的最優(yōu)條件矢量量化器的設計目的就是為了尋求一個K維矢量量化器Q(X)，使得待編碼矢量序列的總體失真D最小，總體失真一般可以采用某種失真測度的統(tǒng)計平均值來描述，比如平方誤差測度的統(tǒng)計平均值。實際上，矢量量化器的工作原理，就是先找到一個碼書和一個輸入矢量空間的劃分方法，碼書是用于解碼，矢量空間的劃分則是為了編碼，而最優(yōu)矢量量化器就是指擁有最佳碼書和最優(yōu)劃分的量化器，那么最優(yōu)矢量量化器該滿足怎樣的條件呢。假設有一個矢量量化器，其輸入矢量空間RK的N個劃分為Ri={R1,R2,…RN}，其碼書尺寸為N，碼書為Y={Y1,Y2,…YN}，則可以按照給定碼書的最優(yōu)劃分和給定劃分的最優(yōu)碼書條件，來刻畫最優(yōu)矢量量化器需要滿足的條件。最近鄰條件：給定碼書的最優(yōu)劃分條件，即給定了解碼器的最優(yōu)編碼器條件。假如給定了碼書，那么輸入矢量空間的最優(yōu)劃分應該滿足最近鄰條件，即每個輸入矢量應該劃分到離它最近的碼字，或者是以離它最近的碼字來重構該輸入矢量。最近鄰條件為：，它表明了在給定碼書的條件下，輸入矢量的最優(yōu)空間劃分是一個最小失真的映射，通常把該最優(yōu)劃分稱為Voronoi劃分，對應的子集Ri稱為Voronoi胞腔。質(zhì)心條件：給定劃分的最優(yōu)碼書條件，即給定了編碼器的最優(yōu)解碼器條件。假如給定了輸入矢量空間的最優(yōu)劃分，那么在確定每個胞腔最優(yōu)的量化點，即確定碼書時，應該滿足質(zhì)心條件，由所有胞腔的質(zhì)心構成最優(yōu)碼書。質(zhì)心條件為：當給定了空間的劃分后，最優(yōu)碼字Yi是對應胞腔Ri的質(zhì)心，Yi=cent(Ri) 。零邊界概率條件：是為了防止邊界點的出現(xiàn)，所謂的邊界點就是指一個輸入矢量沒有固定的最近鄰碼字，可能同時與幾個碼字的距離相等。 LBG算法及其初始碼書生成算法LBG算法是基于最優(yōu)矢量量化器最近鄰條件和質(zhì)心條件的實現(xiàn)碼書設計的一種迭代算法。它通常是從按照某種方法生成的初始碼書開始的，然后根據(jù)最近鄰條件把每個輸入訓練矢量劃分到離它最近的胞腔中，再根據(jù)質(zhì)心條件，重新計算每個胞腔的質(zhì)心，得出新一輪的碼書，按照這種形式不斷迭代，直到滿足給定的限制條件后停止迭代，并得到最終的碼書。而每次迭代總可以將平均失真降低一些，使碼書的性能逐漸提高。假設給定矢量訓練集X={X1,X2,…,XM}，LBG算法的一般實現(xiàn)步驟如下:(a)給定初始參數(shù)和迭代停止條件。給定最大迭代次數(shù)T的值，當前迭代次數(shù)t=0，平均失真D趨于無窮大，并給定相對誤差值TermTh。(b)生成初始碼書Y0。根據(jù)某種生成算法，得到初始碼書，初始碼書的選取很關鍵，直接影響到收斂速度和最終碼書的質(zhì)量。(c)按照某種距離測度方法，把當前碼書的碼字作為胞腔的質(zhì)心，將當前的矢量訓練集劃分到離它們最近鄰的胞腔中，得到新的胞腔劃分。(d)計算當前胞腔劃分的平均失真，公式為：，若前后兩次平均失真的相對誤差滿足，或達到限制的迭代次數(shù)T，則停止算法，而當前碼書就是所求的最終碼書，否則轉(zhuǎn)到下一個步驟，繼續(xù)執(zhí)行。(e)由當前的劃分，根據(jù)質(zhì)心條件，重新計算每個胞腔的質(zhì)心，并將所有質(zhì)心組成當前的碼書。每個胞腔的質(zhì)心為：，從而獲得新的碼書Y，并另迭代次數(shù)t加1，重復步驟 (c)。LBG算法在實現(xiàn)時存在以下幾個不足：在每次迭代時，訓練矢量在碼書中搜索與其最近鄰的碼字的過程中，占用大量的存儲空間并耗費大量的繁瑣計算；對初始碼書依賴性太強，初始碼書的好壞制約著碼書訓練的收斂速度和最終碼書的性能；碼書的自適應力不強。好的初始碼書能較好地提高迭代生成的最終碼書的性能，若初始碼書的性能足夠好，那么就能在很大程度上減少后面碼書在迭代過程中所耗費的時間和空間占用。鑒于初始碼書的選取對矢量量化器的性能有重大影響，專家學者們對此也提出了許多初始碼書生成算法，以改進LBG算法的整體性能。包括隨機編碼、刪除算法、成對最近鄰算法、