矢量量化ＬＢＧ算法的研究

矢量量化（VQVectorQuantization）是70年代后期發(fā)展起來的一種數(shù)據(jù)壓縮技術(shù)，是一種高效的有損數(shù)據(jù)壓縮技術(shù)，它具有壓縮比大、解碼簡單和失真較小等優(yōu)點。其基本思想是：將若干個標量數(shù)據(jù)組構(gòu)成一個矢量，然后在矢量空間給以整體量化，從而壓縮了數(shù)據(jù)而不損失多少信息。矢量量化是仙農(nóng)信息論在信源編碼理論方面的發(fā)展，它的理論基礎(chǔ)是仙農(nóng)的率失真理論，率失真理論是一個存在性定理，并非是一個構(gòu)造性定理，它未給出如何構(gòu)造矢量量化器的方法，矢量量化總是優(yōu)于標量量化，這是因為矢量量化能有效地應(yīng)用矢量中各分量之間的4種相互關(guān)聯(lián)性質(zhì)來消除數(shù)據(jù)中的冗余度。自從1980年提出矢量量化器（VectorQuantizater）碼書設(shè)計的LBG算法以來，矢量量化（VectorQuantization）技術(shù)[Gray（1984）]已經(jīng)成功地應(yīng)用到圖像壓縮和語音編碼中[1]。 二、LBG算法中最佳量化器的設(shè)計 LBG算法中的最佳矢量量化器設(shè)計的關(guān)鍵是最佳劃分和最佳碼書的設(shè)計[2]。 一是給定碼書條件下，尋找信源空間的最佳劃分，使平均失真最小，由碼書和NNR得最佳劃分。信源空間中的任一點矢量，，如果它和碼字的失真小于它和其它碼字的失真， 二是在給定劃分條件下，尋找最佳碼書，使平均失真最小 給定了劃分后為了使碼書的平均失真最小，碼字必須為相應(yīng)劃分的形心（質(zhì)心），即： 式中表示選取的Y是使平均失真為最小的Y，對于一般的失真測度和信源分布，很難找到形心的計算方法。對于訓(xùn)練序列分布和常用的均方失真測度，形心可由下式給出： 式中表示集合中元素的個數(shù)，即集中有個X。 三、矢量量化器的設(shè)計算法 經(jīng)典的碼書設(shè)計算法是LBG算法[2]，它是Y.Linde，A.Buzo與R.M.Gray在1980年推出的，其思想是對于一個訓(xùn)練序列，先找出其中心，再用分裂法產(chǎn)生一個初始碼書A^0，最后把訓(xùn)練序列按碼書A^0中的元素分組，找出每組的中心，得到新的碼書，轉(zhuǎn)而把新碼書作為初始碼書再進行上述過程，直到滿意為止。設(shè)計矢量量化器的主要任務(wù)是設(shè)計碼書，在給定碼書大小N的情況下，由最佳劃分和最佳碼書兩個必要條件得到矢量量化器的設(shè)計算法，LBG算法既可用于已知信源分布特性情況，又可用于未知信源分布特性情況： LBG算法流程描述如下： 此算法基于最佳矢量量化器設(shè)計的最佳劃分和最佳碼書這兩個必要條件，是勞埃德算法在矢量空間的推廣，其特點為物理概念清晰、算法理論嚴密及算法實現(xiàn)容易。但是，它有3個主要缺點: （1）在每次迭代的最佳劃分階段，從碼書中搜索訓(xùn)練矢量的最近碼字需要大量的存儲空間和繁瑣的計算。 （2）初始碼書的選擇影響碼書訓(xùn)練的收斂速度和最終碼書的性能。 （3）碼書的自適應(yīng)能力不強。 四、改進的算法 由上所述，LBG算法是一個不斷迭代、不斷調(diào)整聚類中心的過程，聚類速度慢，初始點的選取對聚類結(jié)果的影響大。因此，針對LBG算法的不足和圖像壓縮的特征，提出了另一種新算法，此算法的基本思想是求出一組領(lǐng)域，將相似度大的樣本聚合在一起，將相似度小的樣本分隔開來，達到聚類的效果。即給定一輸入集 （K是n維歐式空間的點集），設(shè)K分為s個子集} 每個子集就是一個覆蓋。對于領(lǐng)域覆蓋比較少的樣本點采用最短距離法（這里采用歐式距離）進行聚類，這樣形成橢球形覆蓋領(lǐng)域，即選擇圓心距離最近的一對覆蓋合并成一個新覆蓋。計算新覆蓋和其他覆蓋的圓心的距離，再將距離最近的兩個覆蓋合并。根據(jù)實際需要，重復(fù)以上合并步驟，每次減少一個覆蓋，最終得到合理的覆蓋劃分，且所有相似點分布在一個領(lǐng)域（球形或者橢球形）[4]。 按照上面的聚類準則和歐式距離函數(shù)，并根據(jù)圖像壓縮特點和實際處理圖像的情況，歸納出如下的新算法: （1）求所有矢量的重心，矢量重心用該矢量中所含像素點灰度值的平均值來表示。 （2）取一個矢量，求此矢量重心與其它未聚類矢量重心的距離，找出最小距離對應(yīng)的矢量作為類覆蓋的圓心。 （3）以這個最小距離的1.02倍作為半徑r，形成一個球覆蓋，即根據(jù)各矢量重心將相應(yīng)的矢量歸于此類，同時記錄類中的個數(shù)。 （4）求這個類的質(zhì)心，以此得到一個碼矢量和其對應(yīng)的矢量。 （5）找離當(dāng)前覆蓋的圓心最遠的矢量作為下一步覆蓋的圓心。 （6）重復(fù)（2）-（6）直到所有的樣本全部覆蓋結(jié)束。 （7）對于包含點比較少的覆蓋采用最短距離法合并，具體步驟如下: ①對于要用最短距離法合并的覆蓋，計算出兩覆蓋的圓心的距離。 ②將離得最近的兩個覆蓋合并為一個新覆蓋。 ③更新其它覆蓋與新覆蓋的最短距離。 ④根據(jù)實際需要，重復(fù)②、③步，確定最后的聚類數(shù)。 （8）結(jié)束。 五、測試結(jié)果與分析 實驗條件:矢量維數(shù)為4，以“mandrill”作為產(chǎn)生碼書的圖像，對“Lena”進行處理。 實驗環(huán)境:微型計算機:IntelP4處理器，512MB的內(nèi)存；系統(tǒng):MicrosoftWindowsXPProfes-sional，版本2002。 編譯平臺:VisualC++.NET2003。 結(jié)果分析：通過反復(fù)實驗測量，程序運行時間有明顯的差異，采用LBG算法需要的時間為38.26s，而采用剛才提出的新算法只需2.28s，大約快了18倍?？朔薒BG算法因迭代次數(shù)過大而導(dǎo)致程序運行時間長的缺點，大大地縮短了程序運行時間。這是由于此算法是在覆蓋和最短距離相結(jié)合的基礎(chǔ)上進行的，另外該算法的初始點選取對系統(tǒng)影響不大，具有一定的抗干擾能力。此種新算法主要解決了經(jīng)典算法LBG算法難以解決的問題:初值的選取對系統(tǒng)的影響和聚類速度慢等問題。該算法是覆蓋后求重心，再對覆蓋做調(diào)整，得到新覆蓋。因此，初值的選擇對系統(tǒng)性能影響小于LBG算法對系統(tǒng)產(chǎn)生的影響；覆蓋聚類大量減少了迭代次數(shù)，且只用最短距離法處理少量樣本，聚類速度有較大提高。另外，覆蓋聚類算法還可在事先不需知道聚類數(shù)目的情況下，根據(jù)實際需要確定聚類數(shù)目。 但通過新算法產(chǎn)生的碼書解碼出來的圖像質(zhì)量有明顯的下降。這是主要是因為雖然覆蓋聚類算法可以用較快的速度獲得較合理的聚類結(jié)果，但該算法覆蓋半徑的確定、下一個覆蓋中心的選擇等問題，因此我們應(yīng)該進一步對此算法的研究，以便既能縮短運行的時間，同時又能提高解碼出來后圖形的質(zhì)量。