采用分量均值正交分割法設計矢量量化初始碼書

鄧宏貴，郭晟偉

(中南大學 物理科學與技術學院，湖南 長沙，410083)

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

1 傳統LBG算法

將N個輸入矢量用M個碼字矢量來量化，實際上是一個聚類問題，目前，沒有多項式法求全局最優碼書(均方量化誤差最小的碼書)。經典的LBG算法是基于最佳劃分和最佳碼字[12]這2個必要條件提出來的，采用迭代方法求得局部最優解。其算法步驟如下。

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

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

步驟4：將M個胞腔的質心作為新碼書，t=t+1，返回步驟2。

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

2 分量均值正交分割法

2.1 基本思想

先引出2個與本文算法密切相關的概念——矢量均值和分量均值。

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

本文將其簡記為矢量均值。

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

本文簡記為分量均值。

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

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

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

2.2 實現步驟

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

步驟 1：初始化。給定訓練矢量集 T={xi|xi∈Rk,1≤i≤N}，最終碼書大小為M，開始時所有訓練矢量組成一個區域S1，置初始維度j=1，初始碼字個數m=1，初始最大失真區域序號v=1。

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

去掉Sv，以Sm+2代替Sv，保證區域個數增加1。若j=k，則j=1，否則j=j+1，m=m+1；若m=M，則結束分割，轉步驟4。

步驟3：分別計算m個區域的平均量化失真Dt，找出失真最大的區域，即

式中：p為區域St內樣本個數。找出其中平均量化失真最大的區域序號v

步驟4：分別計算M個區域的質心，作為初始碼書賦給LBG算法進行迭代。

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

2.3 非均勻分布樣本改進措施

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

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

經過改進之后，本文的分量均值正交分割法對于非均勻分布樣本同樣適用，應用范圍擴大。

3 算法仿真及結果討論

實驗硬件環境：CPU(P4 2.93 G)，內存為512 M，DDR；實驗軟件環境：Visual C++ 6.0。

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

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

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

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

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

圖2 3種算法訓練時間對比Fig.2 Training time comparison of three algorithms

4 結論

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

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

(3) CMOSA算法運算量小。CMOSA算法與經典LBG算法相比，訓練時間增加不超過30%；與SA和

LBG聯合算法相比，訓練速度提高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] 李霞, 羅雪暉, 張基宏. 基于人工蟻群優化的矢量量化碼書設計算法[J]. 電子學報, 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]. 電子學報, 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] 李弼程, 文超, 平西建. 兩個優于分裂法的初始碼書設計算法[J]. 中國圖像圖形學報, 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.