采用分量均值正交分割法設(shè)計(jì)矢量量化初始碼書(shū)

鄧宏貴，郭晟偉

(中南大學(xué) 物理科學(xué)與技術(shù)學(xué)院，湖南 長(zhǎng)沙，410083)

矢量量化(Vector quantization, VQ)[1]技術(shù)是一種高效的數(shù)據(jù)壓縮技術(shù)，由于其可以獲得比標(biāo)量量化更高的壓縮比，故廣泛應(yīng)用于語(yǔ)音、圖像和視頻壓縮系統(tǒng)。碼書(shū)設(shè)計(jì)是矢量量化最關(guān)鍵的技術(shù)，直接影響到量化系統(tǒng)的性能。Linde等[2]提出的LBG算法物理含義清晰，數(shù)學(xué)推理嚴(yán)密，易于實(shí)現(xiàn)。但是，LBG算法嚴(yán)重依賴初始碼書(shū)的選擇，直接影響訓(xùn)練算法的收斂速度和碼書(shū)質(zhì)量。目前，初始碼書(shū)有3種生成方法，即隨機(jī)法、分裂法(Splitting algorithm, SA)[3-5]和乘積碼書(shū)法。隨機(jī)法就是從N個(gè)訓(xùn)練矢量中隨機(jī)抽取M個(gè)作為初始碼書(shū)。這種方法簡(jiǎn)單易行，且不會(huì)出現(xiàn)空胞腔，但結(jié)果具有較大偶然性。分裂法是首先把整個(gè)訓(xùn)練樣本看成1個(gè)胞腔，再用最優(yōu)分割超平面將胞腔一分為二，二分為四，直到形成M個(gè)胞腔，以這些胞腔的質(zhì)心得到M個(gè)碼字。采用該法量化失真小，但是，多維最優(yōu)分割超平面的選擇是一個(gè)非常復(fù)雜的問(wèn)題[6]。乘積碼書(shū)法以若干低維的碼書(shū)作為乘積碼，再求得高維碼書(shū)，計(jì)算量小，但性能差。不同的初始碼書(shū)會(huì)使LBG迭代算法陷入不同的局部最優(yōu)解。目前，雖然人們對(duì)全局最優(yōu)解進(jìn)行了研究[7-9]，但計(jì)算量均很大。事實(shí)上，使初始碼字根據(jù)樣本分布規(guī)律盡量散開(kāi)可以得到更好的迭代解[10-11]。在此，本文作者利用矢量在各個(gè)維度上的分量均值這一統(tǒng)計(jì)特性，將碼書(shū)盡量散開(kāi)得到充分利用，以便得到比以往算法更優(yōu)的碼書(shū)。

1 傳統(tǒng)LBG算法

將N個(gè)輸入矢量用M個(gè)碼字矢量來(lái)量化，實(shí)際上是一個(gè)聚類問(wèn)題，目前，沒(méi)有多項(xiàng)式法求全局最優(yōu)碼書(shū)(均方量化誤差最小的碼書(shū))。經(jīng)典的LBG算法是基于最佳劃分和最佳碼字[12]這2個(gè)必要條件提出來(lái)的，采用迭代方法求得局部最優(yōu)解。其算法步驟如下。

步驟 1：初始化，給定訓(xùn)練矢量集 T={xi|xi∈Rk,1≤i≤N}，碼書(shū)大小為M，迭代門限ε＞0，初始碼書(shū)為C(0)，置迭代次數(shù)t=0，初始失真D(-1)=∞。

步驟 2：依據(jù)最近鄰法則[13]將 T劃分為 M 個(gè)Voronoi胞腔。步驟 3：計(jì)算平均量化失真若失真下降率為(D(t-1)-D(t))/D(t)≤ε，則停止算法，碼書(shū)C(t)就是所求的碼書(shū)，否則轉(zhuǎn)下一步。

步驟4：將M個(gè)胞腔的質(zhì)心作為新碼書(shū)，t=t+1，返回步驟2。

從以上步驟可以看出：LBG算法初始碼書(shū)的選擇至關(guān)重要，它影響到算法的收斂速度和最終碼書(shū)的性能。傳統(tǒng)初始碼書(shū)生成方法一般采用隨機(jī)法和分裂法，其中：隨機(jī)法性能差，分裂法計(jì)算量大且性能有待提高[5]。本文從分量均值這一特征值出發(fā)，提出一種新的初始碼書(shū)生成算法即分量均值正交分割法(Component mean orthogonal segmentation algorithm, CMOSA)。

2 分量均值正交分割法

2.1 基本思想

先引出2個(gè)與本文算法密切相關(guān)的概念——矢量均值和分量均值。

設(shè)x為Rk空間的k維矢量，xj(1≤j≤k)表示x在第j個(gè)維度的投影，矢量x的均值μx定義為：

本文將其簡(jiǎn)記為矢量均值。

設(shè)xi(1≤i≤N)為Rk空間N個(gè)k維矢量，這N個(gè)矢量組成1個(gè)矢量組，xij(1≤i≤N, 1≤j≤k)表示矢量xi在第j個(gè)維度的投影。矢量組第j維分量的均值定義為：

本文簡(jiǎn)記為分量均值。

引入如下定義：設(shè)L為Rk空間的1條直線，若L上任意點(diǎn)p=(p1, p2, …, pk)都滿足p1=p2=…= pk，則稱L為Rk的中心線[14]。

從物理意義上看，矢量x的矢量均值相當(dāng)于矢量x在冗余維度xL=(x1+x1+…+xk)/k上的投影。x?∈Rk，x 在 L 上的投影點(diǎn)為 px=(μx, μx, …, μx)。因此，與 L 正交的超平面上的所有點(diǎn)矢量均值相等，稱為等均值超平面。

碼書(shū)通常是以矢量均值劃分樣本空間，這樣會(huì)出現(xiàn)1個(gè)問(wèn)題：即使劃分非常細(xì)，胞腔空間也是由2個(gè)無(wú)限寬的平行等均值超平面包裹，仍然存在歐式距離很大的碼字同屬一個(gè)胞腔的問(wèn)題，而且矢量均值計(jì)算量大。該矢量均值僅僅是xL維度上的投影所致。這種方法只利用了訓(xùn)練樣本在xL維度上的分布特點(diǎn)，而沒(méi)有利用在其他維度上的分布特點(diǎn)，因而，不如直接依次用各分量空間的均值分割。這種在各個(gè)維度上都對(duì)訓(xùn)練樣本空間進(jìn)行分割的方法，使分割平面相互正交，由于每次分割只涉及1個(gè)相異的獨(dú)立維度，計(jì)算量小，且同一胞腔內(nèi)碼字之間歐式距離小。根據(jù)這種情況，本文提出了基于分量均值分割的初始碼書(shū)設(shè)計(jì)新算法。

2.2 實(shí)現(xiàn)步驟

假設(shè)有N個(gè)k維訓(xùn)練樣本，碼書(shū)大小為M，本文算法先計(jì)算N個(gè)訓(xùn)練樣本在x1維度的均值μ1，利用該均值將樣本空間一分為二，再將失真大的區(qū)域在 x2維度作正交分割共得到3個(gè)區(qū)域，依此類推，最終得到M個(gè)區(qū)域。以這些區(qū)域的質(zhì)心作為初始碼書(shū)，可以保證碼字盡量散開(kāi)，得到充分利用。新算法的實(shí)現(xiàn)步驟如下。

步驟 1：初始化。給定訓(xùn)練矢量集 T={xi|xi∈Rk,1≤i≤N}，最終碼書(shū)大小為M，開(kāi)始時(shí)所有訓(xùn)練矢量組成一個(gè)區(qū)域S1，置初始維度j=1，初始碼字個(gè)數(shù)m=1，初始最大失真區(qū)域序號(hào)v=1。

步驟 2：按照式(2)計(jì)算最大失真區(qū)域 Sv在維度 j上的分量均值μj。使用μj將區(qū)域Sv一分為二，即Sm+1和 Sm+2。

去掉Sv，以Sm+2代替Sv，保證區(qū)域個(gè)數(shù)增加1。若j=k，則j=1，否則j=j+1，m=m+1；若m=M，則結(jié)束分割，轉(zhuǎn)步驟4。

步驟3：分別計(jì)算m個(gè)區(qū)域的平均量化失真Dt，找出失真最大的區(qū)域，即

式中：p為區(qū)域St內(nèi)樣本個(gè)數(shù)。找出其中平均量化失真最大的區(qū)域序號(hào)v

步驟4：分別計(jì)算M個(gè)區(qū)域的質(zhì)心，作為初始碼書(shū)賦給LBG算法進(jìn)行迭代。

該算法利用分量均值正交分割平均失真最大的區(qū)域，直至形成需要的M個(gè)初始胞腔，以分割后的區(qū)域質(zhì)心作為初始碼書(shū)放到 LBG算法迭代。需要說(shuō)明的是：按照這些步驟獲得的初始碼書(shū)不是最優(yōu)碼書(shū)。本方法的目的只是為 LBG算法提供大致按照訓(xùn)練樣本規(guī)律分布的初始碼字，使初始碼字得到充分利用。

2.3 非均勻分布樣本改進(jìn)措施

從上述基本思想和實(shí)現(xiàn)步驟可以看出：分量均值正交分割設(shè)計(jì)法對(duì)于均勻分布的樣本特別有效。實(shí)際上，大多數(shù)圖像樣本都不是完全地均勻分布，這樣，對(duì)某一區(qū)域分割時(shí)，若少數(shù)幾個(gè)樣本在維度xj上與其他樣本差別很大，則可能出現(xiàn)非典型碼字(映射到該碼字的樣本數(shù)目很少)，這些碼字利用率不高。由于該算法以分量均值分割，每個(gè)新區(qū)域至少包含1個(gè)樣本，因此，不可能出現(xiàn)空胞腔，至多出現(xiàn)非典型碼字。為了解決該算法的非典型碼字問(wèn)題，需要對(duì)步驟2略加改進(jìn)，具體方法如下。

對(duì)于分割得到的2個(gè)新胞腔，統(tǒng)計(jì)其中樣本數(shù)pi(i為m+1和m+2)。若pi小于預(yù)先設(shè)定的非典型碼字門限Ns，則認(rèn)定該碼字為非典型碼字，去掉區(qū)域Si，將其中樣本劃分給其他最臨近的碼字所屬胞腔。這樣，本次操作相當(dāng)于只對(duì)離中心碼字較遠(yuǎn)的部分樣本進(jìn)行調(diào)整，而不增加胞腔個(gè)數(shù)。參數(shù)Ns一般是訓(xùn)練樣本規(guī)模N的弱函數(shù)，Ns隨著N增大而略增大，經(jīng)驗(yàn)值取3～5為宜。

經(jīng)過(guò)改進(jìn)之后，本文的分量均值正交分割法對(duì)于非均勻分布樣本同樣適用，應(yīng)用范圍擴(kuò)大。

3 算法仿真及結(jié)果討論

實(shí)驗(yàn)硬件環(huán)境：CPU(P4 2.93 G)，內(nèi)存為512 M，DDR；實(shí)驗(yàn)軟件環(huán)境：Visual C++ 6.0。

從標(biāo)準(zhǔn)測(cè)試圖像庫(kù)中選取10幅大小為256×256和256色的灰度圖像進(jìn)行測(cè)試。將圖像劃為4×4的小塊，因此，矢量維數(shù)k=16，樣本數(shù)N=4 096，碼書(shū)大小 M∈{8，16，32，64，128，256，512，1 024}，失真下降門限ε取0.001。分別用LBG算法[2]、SA+LBG算法[15]、本文算法進(jìn)行碼書(shū)設(shè)計(jì)，把各種方法在不同碼書(shū)下的失真度和訓(xùn)練時(shí)間這2個(gè)最重要的參數(shù)進(jìn)行對(duì)比。其中，訓(xùn)練時(shí)間包括初始碼書(shū)設(shè)計(jì)時(shí)間和迭代優(yōu)化時(shí)間，失真度用峰值信噪比RPSN度量。

設(shè)原始像素為xij，量化值為qij，均方誤差EMS、峰值信噪比RPSN定義為：

選取最典型的Lena和Barb 2幅圖像，在碼書(shū)大小為128時(shí)進(jìn)行對(duì)比，結(jié)果見(jiàn)表1。圖1所示為3種算法在不同碼書(shū)大小下失真度的對(duì)比結(jié)果；圖2所示為不同碼書(shū)大小下訓(xùn)練時(shí)間對(duì)比結(jié)果。實(shí)驗(yàn)結(jié)果表明：本文提出的分量均值正交分割法與經(jīng)典 LBG算法相比，峰值信噪比RPSN提高超過(guò)1 dB，訓(xùn)練時(shí)間增加不超過(guò)30%；相對(duì)于SA+LBG法，RPSN相差不超過(guò)0.1 dB，但訓(xùn)練速度提高了 1.0～1.5倍。其原因是：以隨機(jī)方式產(chǎn)生初始碼書(shū)的LBG算法，不需要附加計(jì)算，耗時(shí)最少。但是，由于初始碼字不能自適應(yīng)于訓(xùn)練樣本的統(tǒng)計(jì)特性，最終收斂到RPSN較低的局部最優(yōu)解。用SA產(chǎn)生初始碼書(shū)，可以使初始胞腔沿著失真下降最大的方向分裂，產(chǎn)生較好碼書(shū)，但是，在分裂過(guò)程中，尋找最優(yōu)分割超平面需進(jìn)行繁瑣的運(yùn)算，算法應(yīng)用受到限制。本文提出的CMOSA算法，充分利用了正交分割平均失真最大的胞腔，使初始碼字盡量散開(kāi)，再在LBG算法中迭代，最終碼書(shū)質(zhì)量比隨機(jī)LBG的質(zhì)量高得多，與SA和LBG聯(lián)合算法相比碼書(shū)質(zhì)量相差很小。由于CMOSA算法只需M次分量均值的計(jì)算，相對(duì)于分裂法M次分裂[6]少得多，故比SA和LBG聯(lián)合算法的運(yùn)算速率快得多。

表1 Lena和Barb圖像在3種算法下的性能對(duì)比(M=128)Table 1 Performance comparison of three algorithms for Lena and Barb images (M=128)

圖1 3種算法的RPSN對(duì)比Fig.1 Comparison of peak signal to noise ratio of three algorithms

圖2 3種算法訓(xùn)練時(shí)間對(duì)比Fig.2 Training time comparison of three algorithms

4 結(jié)論

(1) 基于分量均值正交分割平均失真最大的胞腔，提出了一種矢量量化初始碼書(shū)設(shè)計(jì)算法即CMOSA算法。

(2) CMOSA算法量化誤差小。與經(jīng)典LBG算法相比，CMOSA算法峰值信噪比提高超過(guò)1 dB；與SA和LBG聯(lián)合算法相比，峰值信噪比相差低于0.1 dB。

(3) CMOSA算法運(yùn)算量小。CMOSA算法與經(jīng)典LBG算法相比，訓(xùn)練時(shí)間增加不超過(guò)30%；與SA和

LBG聯(lián)合算法相比，訓(xùn)練速度提高1.0～1.5倍。

[1] Gersho A, Gray R M. Vector quantization and signal compression[M]. Boston: Kluwer Academic Publishers, 1992.

[2] Linde Y, Buzo A, Gray R M. An algorithm for vector quantizer design[J]. IEEE Transactions on Communications, 1980, 28(1):84-95.

[3] Lee W F, Chan C K. Two-dimensional split and merge algorithm for differential vector quantization of images[J]. Image Communication, 1998, 13(1): 1-14.

[4] Stephen S, Kuldip K P. Efficient product code vector quantisation using the switched split vector quantiser[J]. Digital Signal Processing, 2007, 17(1): 138-171.

[5] Ahmed M E. Fast methods for split codebooks[J]. Signal Processing, 2000, 80(12): 2553-2565.

[6] Chan C K, Ma C K. A fast method of designing better codebooks for image vector quantization[J]. IEEE Transactions on Communications, 1994, 42(234): 237-242.

[7] Franti P. Genetic algorithm with deterministic crossover for vector quantization[J]. Pattern Recognition Letters, 2000, 21:61-68.

[8] 李霞, 羅雪暉, 張基宏. 基于人工蟻群優(yōu)化的矢量量化碼書(shū)設(shè)計(jì)算法[J]. 電子學(xué)報(bào), 2004, 32(7): 1082-1085.LI Xia, LUO Xue-hui, ZHANG Ji-hong. Codebook design for image vector quantization with ant colony optimization[J]. Acta Electronica Sinica, 2004, 32(7): 1082-1085.

[9] 陸哲明, 潘正祥, 孫圣和. 基于改進(jìn)禁止搜索算法的矢量量化碼書(shū)設(shè)計(jì)[J]. 電子學(xué)報(bào), 2000, 28(9): 108-110.LU Zhe-ming, PAN Zheng-xiang, SUN Sheng-he. VQ codebook design based on the modified tabu search algorithms[J]. Acta Electronica Sinica, 2000, 28(9): 108-110.

[10] Villmann T, Schleif F, Hammer B. Comparison of relevance learning vector quantization with other metric adaptive classification methods[J]. Neural Networks, 2006, 19(5):610-622.

[11] Shen F, Hasegawa O. An adaptive incremental LBG for vector quantization[J]. Neural Networks, 2006, 19(5): 694-704.

[12] Lloyd S. Least squares quantization in PCM[J]. IEEE Transactions on Information Theory, 1982, 28(2): 129-137.

[13] Garey M R, Johnson D S, Witsenhausen H S. The complexity of the generalized Loyd-Max problem[J]. IEEE Transactions on Information Theory, 1982, 28(2): 255-256.

[14] Ra S W, Kim J K. Fast mean-distance-ordered partial codebook search algorithm for image vector quantization[J]. IEEE Transactions on Circuits and Systems-II, 1993, 40(9): 576-579.

[15] 李弼程, 文超, 平西建. 兩個(gè)優(yōu)于分裂法的初始碼書(shū)設(shè)計(jì)算法[J]. 中國(guó)圖像圖形學(xué)報(bào), 2000, 5(1): 48-51.LI Bi-cheng, WEN Chao, PING Xi-jian. On the design of original codebooks with two algorithms better than the splitting algorithm[J]. Journal of Image and Graphics, 2000, 5(1): 48-51.