一種改進的基于Hadamard 域的碼書設計算法*

王佳果，陳善學，張 艷，尹雪嬌

(重慶郵電大學移動通信安全技術實驗室 重慶400065)

1 引言

矢量量化（vector quantization,VQ）[1,2]是一種高效的有損數據壓縮技術，因其具有壓縮比高、編解碼速度快的特點，被廣泛地應用于話音編碼和圖像的壓縮系統中。碼書設計[3]是矢量量化研究的一個關鍵技術，研究碼書設計算法的根本目的是尋求一種有效的算法來盡可能地找到全局最優或者接近全局最優的碼書以提高碼書的性能，碼書設計的好壞關系到整個矢量量化器設計的成功與否，是決定矢量量化器性能的主要因素。

矢量量化的基本思想[4]是：把圖像看成是一串數據，設這一串數據大小為m，把它截成M段(一般每段相等，例如為k)，即把m個數據變成了M個矢量，再把這M個矢量分成N組，對每個組挑選一個數據矢量作為這個組的代表，例如第 j個組的代表為 yj(j=0,1,…,N-1)。集合{yj|j＝0,1,…,N-1}稱為碼書。其中N稱為碼書長度或碼書大小。一個k維、尺寸為N的矢量量化器可以定義為從k維歐幾里德空間Rk到其一個有限子集C的一個映射，即Q:Rk→C,C={y1,y2,y3,…,yN}。通常將集合C稱為碼書，N為碼書長度。該映射滿足：Q(x|x∈Rk)=yp，其中 x=(x0,x1,…,xk-1),yp=(yp0,yp1,…,yp(k-1))，并且滿足：

其中d(x,yp)為矢量x與碼字yj的失真測度，通常采用的失真測度是歐式距離的平方，其表達式為：

LBG算法[4]是關于碼書設計的經典算法，其為矢量量化技術的發展奠定了基礎。LBG算法主要依據兩個準則：一是最佳劃分準則，即對于給定碼書，訓練矢量集的最佳劃分可通過把每個訓練矢量映射為離它最近的碼字得到。二是最佳碼書準則，即對于給定訓練矢量劃分，最佳碼書的各碼字為各胞腔的質心。傳統的碼書設計算法LBG算法，主要存在3個缺點[5]:對初始碼書非常敏感；碼書自適應能力不強；運算量大，這些缺點也就限制了LBG算法的應用。LBG算法的步驟如下[6]。

（1）初始化碼書。即采用訓練矢量隨機抽取法選定初始碼書YN(0)={Yj|j=1,…,N}，設置迭代次數n=0，平均失真D-1→∞，給定相關門限 ε(0<ε<1)。

（2）聚類過程。根據最近鄰原則，把訓練集X={xm|m=1,2,…,M}中的矢量xm劃入到N個不同的子區間Si(n)(i=1,2,…,N)中，其中，Si={xj:d(xj,yi)=min d(xj,yl)}，對于任意 l∈i{1,2,…,N}成立。

LBG算法初始碼書中采用的訓練矢量集是隨機抽取法，即將M個訓練矢量平分成N組，在每組中選取一個訓練矢量作為初始碼字。參考文獻[7]是Chen的一種LBG改進算法，Chen的算法主要是引進范數，對訓練矢量采用按矢量和值進行排序生成碼書。

但Chen的算法也存在著初始碼書隨機性較強和搜索獲勝碼字計算量較大的缺點。為此改進算法使用了新的初始碼書生成方法使得編碼性能得到了改善，同時還引入了一種搜索獲勝碼字的快速算法降低了搜索碼字過程中的計算量，并且獲得的初始碼書首先經過Hadamard變化，使算法簡單，計算量小。

2 改進算法

2.1 Hadamard變換的定義和性質

令Hn為 2n×2n的 Hadamard[8,9]矩陣，其元素屬于集合{-1,1}，假定以下所有矢量為k維矢量，k=2n(n>0)，則可得到以下基本定義和性質。

矢量x的Hadamard變換矢量X可定義為：

X1=Sx，這里X1是矢量X的第一維分量，Sx為空域中輸入矢量x的和值。

D(X,Yj)=kd(x,yj)，Yj為碼字 yj的 Hadamard 變換。

由此可以看出Hadamard變換前后的能量成倍數關系，在Hadamard域和空域中搜索最近鄰碼字是等價的。

2.2 算法步驟

在 k 維適量空間中[10]，訓練矢量 X=（x1,x2,…,xk）和初始碼書Y=(Yj,j=1,…,N)，碼書大小為N。矢量X和Y的矢量和、方差和二范數分別為（Sx,Vx,Lx）和(Sj,Vj,Lj)，則：

H(k)為 k×k維 Hadamard矩陣，矢量 X和碼書 Yj經Hadamard變換為 hx和hyj，并且有 hx=XH(k)和hyj=YjH(k)，則hx和hyj的方差和二范數為：

本算法首先對訓練矢量進行Hadamard變化，計算其范數，并按照范數大小進行排序，然后按照碼書大小進行平均分組，選擇每組第一個訓練矢量作為初始碼書。假設當前最小失真為Dmin，hx1和hyj1分別是hx和hyj第一維分量，則有以下3步排除準則。

在N個碼字中尋找與Dmin相等的碼字，即當前獲勝碼字Yp，此時將訓練矢量X劃分到第P個胞腔，計算其質心替代當前獲勝碼字Yp，輸入下一個訓練矢量，直到所有訓練矢量被訓練完為止，此時令迭代次數t→t+1，直到達到所要的迭代次數。本算法結合LBG算法優點，利用統計特征量的分類平均法生成初始碼書，同時引入快速搜索算法，克服LBG算法的兩個缺點，而在每個訓練矢量找到匹配碼字后，利用求質心的方法調整碼字，更能夠匹配整個胞腔，而且加速了碼書的收斂速度，提升了碼書的性能。

表1 改進算法的編碼效果（PSNR）比較

表2 計算復雜度的比較

3 實驗仿真結果

仿真實驗采用 512×512×8 bit的灰度 Lena圖像和Peppers圖像作為測試圖像，經Hadamard變換后按第一維升序排列生成初始碼書，碼書大小分別為128、256、512、1 024。首先比較改進算法和參考文獻[7]的算法在迭代次數為1和20的情況，如表1所示，因為算法的運算時間與電腦性能以及編程技術有關，所以本算法不進行運算時間的比較，而是只比較算法壓縮后圖像的恢復效果和計算復雜度。表1比較了改進算法和Chen算法的峰值信噪比（PSNR）；圖1比較了改進算法和Chen算法在不同迭代次數下的峰值信噪比，其中碼書大小為512；表2比較了改進算法和Chen算法的計算復雜度。

圖1 兩種算法在不同迭代次數下的峰值信噪比（PSNR）

從表1可以看出，本算法相比Chen的算法有很大的提高，尤其在迭代次數較小的情況下，算法的提升非常明顯，PSNR的提升最大達到0.9 dB。圖1表示的是兩種算法在碼書大小為512的情況下，不同迭代次數下的PSNR，可以看到，本算法在較低迭代次數就能達到較好的效果，并且快速達到穩定，說明本算法碼字排查效率很高。從表2可以看出，本改進算法在計算復雜度上并沒有明顯增加，從而說明本算法在沒有增加計算復雜度的情況下，對圖像的恢復效果，即PSNR，有較好的提高。

4 結束語

本文結合Hadamard變換和K-means理論，在對Chen的算法研究基礎上，針對初始隨機性強和排除碼字效率不高的特點進行以下改進：對初始碼書按Hadamard變換后計算其二范數，并按其范數大小進行升序排列，按碼書大小進行選取，利用統計特征量的分類平均法生成初始碼書，然后提高求質心的頻率，每當一個訓練矢量被分類到胞腔時，就求出相應胞腔的質心來代替原有的碼字。從實驗數據上可以看出，在迭代次數較小時改進算法的PSNR相比Chen的算法提高了0.5～0.9 dB，在迭代次數較小時說明改進后的初始碼書更能代表輸入矢量的數據分布情況，更易快速收斂。而在迭代次數較大時，本算法也較Chen的算法有0.2～0.3 dB的提高，體現了本算法的優勢。相比Chen的算法，調整后的碼字代表了整個胞腔的特性，更能夠匹配整個胞腔。引入3步快速排除準則，可以較高效率排除不必要的碼字，加速了碼書的收斂速度，提升了碼書的性能。

1 Nasrabadi N M，King R A．Image coding using vector quantization：a review．IEEE Trans Commun,l988，36(8)：957～971

2 Linde Y,Buzo A,Gray R M.An algorithm for vector quantizer design.IEEE Trans Commun,1980,28(1):84～95

3 陳善學，李方偉.矢量量化與圖像處理.北京：科學出版社，2009

4 孫圣和，陸哲明.矢量量化技術及應用.北京：科學出版社，2002

5 Rui Xiayi,Yu Yibiao.A new codebook design method based on genetic algorithm for text-independent speaker identification.Signal Processing,2005,21(3):289～292

6 劉麗娟，鄒雪城，沈緒榜.一種新的矢量量化編碼算法.小型微型計算機系統,2004,25(10)

7 Chen Shanxue,Li Fangwei,Zhu Weile,et al.Initial codebook algorithm of vector quantization.IEICE Trans Inf&Syst 2008,E91-D(8):2 189～2 191

8 Lu Z M,Chu S C,Huang K C.Equal-average equal-variance equal-norm nearest neighbor codeword search algorithm based on ordered hadamard transform.International Journal of Innovative Computing,Information and Control,2005,1(1):35～41

9 Chu S C,Lu Z M,Pan J S.Hadamard transform based fast codeword search algorithm for high-dimensional VQ encoding.Information Sciences,2007,177(3):734～746

10 Lai J Z C,Liaw Y C.Fast-searching algorithm for vector quantization using projection and triangular inequality.IEEE Trans Image Process,2004,13(12):1 554～1 558