一種改進(jìn)的基于Hadamard 域的碼書設(shè)計(jì)算法*

王佳果，陳善學(xué)，張 艷，尹雪嬌

(重慶郵電大學(xué)移動(dòng)通信安全技術(shù)實(shí)驗(yàn)室 重慶400065)

1 引言

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

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

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

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

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

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

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

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

2 改進(jìn)算法

2.1 Hadamard變換的定義和性質(zhì)

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

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

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

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

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

2.2 算法步驟

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

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

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

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

表1 改進(jìn)算法的編碼效果（PSNR）比較

表2 計(jì)算復(fù)雜度的比較

3 實(shí)驗(yàn)仿真結(jié)果

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

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

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

4 結(jié)束語(yǔ)

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

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 陳善學(xué)，李方偉.矢量量化與圖像處理.北京：科學(xué)出版社，2009

4 孫圣和，陸哲明.矢量量化技術(shù)及應(yīng)用.北京：科學(xué)出版社，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 劉麗娟，鄒雪城，沈緒榜.一種新的矢量量化編碼算法.小型微型計(jì)算機(jī)系統(tǒng),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