用于LBG初始碼書設(shè)計(jì)的改進(jìn)PNN算法

陳善學(xué)，張 艷，吳立彬

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

0 引言

矢量量化（vector quantization，VQ）［1－2］是一種高效的數(shù)據(jù)壓縮編碼方式，碼書設(shè)計(jì)和碼字搜索是它的兩個(gè)關(guān)鍵技術(shù)。碼書的優(yōu)劣決定了量化器的性能，因而矢量量化的首要問(wèn)題在于設(shè)計(jì)出性能好的碼書。但是目前沒(méi)有一種通用的方法能設(shè)計(jì)出一種在全局意義下的最優(yōu)碼書。1980年，由Linde，Buzo和Gray［3］首先提出的LBG算法是一種直觀有效的矢量量化碼書設(shè)計(jì)算法。但它具有依賴對(duì)初始碼書的選取，自適應(yīng)能力不強(qiáng)，易陷于局部最優(yōu)等缺點(diǎn)。對(duì)于這些問(wèn)題，后來(lái)的研究者提出了各種改進(jìn)方法:主要有LBG的改進(jìn)算法［4］;基于神經(jīng)網(wǎng)絡(luò)的碼書設(shè)計(jì)算法［5］，如自學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)、競(jìng)爭(zhēng)學(xué)習(xí)神經(jīng)網(wǎng)絡(luò);基于隨機(jī)優(yōu)化技術(shù)的碼書設(shè)計(jì)算法，如遺傳算法、模擬退火算法、粒子群算法、蟻群算法等，或者是與LBG 的結(jié)合算法［6］;基于模糊聚類理論［7］的碼書設(shè)計(jì)算法;自適應(yīng)更新的矢量量化碼書設(shè)計(jì)算法等。本文是采用改進(jìn)的成對(duì)最鄰近（par－wise nearest neighbor，PNN）算法用于LBG初始碼書來(lái)實(shí)現(xiàn)矢量量化中的最優(yōu)碼書設(shè)計(jì)。

PNN算法［8］是一種刪除算法。它通過(guò)在設(shè)計(jì)過(guò)程中不斷地合并最鄰近的胞腔來(lái)生成碼書。每個(gè)訓(xùn)練矢量分配一個(gè)胞腔，一次迭代合并最鄰近的兩個(gè)胞腔，直到胞腔數(shù)目達(dá)到要求的碼書個(gè)數(shù)。該算法復(fù)雜性比較高，可獨(dú)立用于碼書設(shè)計(jì)，但性能不是很好。一些改進(jìn)的PNN算法在圖像編碼［9］和語(yǔ)言編碼［10］當(dāng)中都有所運(yùn)用。本文通過(guò)排序和一次迭代合并多個(gè)矢量來(lái)優(yōu)化PNN算法，使PNN算法的復(fù)雜性和迭代時(shí)間得到減少。然后將優(yōu)化后的PNN算法作為初始碼書用于LBG進(jìn)一步優(yōu)化。仿真實(shí)驗(yàn)表明，該生成的碼書性能得到了提高，將其運(yùn)用到圖像處理的碼書設(shè)計(jì)中具有較好的效果。

1 矢量量化與LBG算法

矢量量化本質(zhì)上是一個(gè)聚類過(guò)程，而碼書設(shè)計(jì)就是尋求把M個(gè)訓(xùn)練矢量分成N類的一種最佳方案。設(shè)M個(gè)k維數(shù)據(jù)組成的數(shù)據(jù)空間為{Xij}，其中i=1，…，M;j=1，…，k，矢量量化可以看做是這個(gè)k維歐幾里德空間Rk到包含N個(gè)互相不重合（R1，R2，…，RN）子空間的有限子集Y的映射。即Q:Rk→Y，其中在每一個(gè)子空間Rj中選出一個(gè)代表矢量，記為 Yj=（yj1，yj2，…，yjk），將各個(gè)子空間的代表矢量集記為Y={Yj;j=1，…，N}，通常將Y稱為碼書（code book），Yj稱為碼字（code word），而N是碼書大小。收端以Yj再現(xiàn)X必然存在失真，滿足d（X，Yi）=min（d（X，Yj）），j=1，…，N。d（X，Yi）為矢量X與碼字Yi之間的失真測(cè)度。一般在計(jì)算整個(gè)輸入信號(hào)和相應(yīng)的重構(gòu)信號(hào)之間的失真時(shí)，經(jīng)常采用峰值信噪比（peak signal noise ratio，PSNR）來(lái)描述矢量量化編碼失真，定義為

（1）式中:L為圖片灰度值;

（2）式中，xij為原始圖像像素;yij為重構(gòu)圖像像素。

碼書設(shè)計(jì)過(guò)程，即為尋找最優(yōu)子集 Y，使得PSNR最大。

LBG算法一般是先選取初始碼書，根據(jù)最鄰近原則得到新胞腔，然后根據(jù)質(zhì)心原則，通過(guò)量化、聚類、迭代由新胞腔得到新的碼書。通過(guò)某種限制條件結(jié)束，迭代產(chǎn)生最終碼書。這種迭代過(guò)程雖然不能保證最后能得到最優(yōu)碼書，但每次迭代都能降低或保持不變平均失真，使得碼書性能得到提高。但它具有依賴對(duì)初始碼書的選取，自適應(yīng)能力不強(qiáng)，易陷于局部最優(yōu)等缺點(diǎn)。

2 初始碼書算法

好的初始碼書能提高經(jīng)過(guò)進(jìn)一步迭代生成的最終碼書的性能，如果初始碼書的性能足夠好，可以在較大程度上減少其后碼書迭代過(guò)程中的系統(tǒng)開(kāi)銷和花費(fèi)的時(shí)間。初始碼書的獲取方式一般有以下幾種:隨機(jī)選擇法、分裂法、刪除算法等［11］。隨機(jī)算法是根據(jù)輸入矢量分布隨機(jī)選取矢量作為初始碼書，該方法復(fù)雜度最小，但存在碼書選取沒(méi)有針對(duì)性和空胞腔等問(wèn)題。分裂法［12］是由小的碼書生成較大的碼書，分裂法產(chǎn)生的碼書性能比較好，但復(fù)雜度高于隨機(jī)算法。刪除算法是從整個(gè)訓(xùn)練矢量中有選擇地刪除訓(xùn)練矢量，直到得到要求的矢量作為碼書。該算法的復(fù)雜度比較高。

2.1 PNN算法

由Equitz等提出的PNN算法是刪除算法中的一種。若訓(xùn)練矢量集中的矢量個(gè)數(shù)為M，每個(gè)矢量都占有一個(gè)獨(dú)立的胞腔，算法的目的是不斷合并相近的兩個(gè)胞腔直至得到所需數(shù)目的胞腔，且最終的碼書由各胞腔的質(zhì)心矢量組成。設(shè)訓(xùn)練矢量集為X={x1，x2，…，xM}，將 X 對(duì)應(yīng)的歐幾里德空間 Rk劃分為M個(gè)互相不重合的子空間R1，R2，…，RM，該算法描述如下。

步驟1 令碼字?jǐn)?shù)n=M，每個(gè)胞腔的質(zhì)心yi=xi（i=1，2，…，M）。

步驟2 計(jì)算各對(duì)碼字yl和ym之間的失真d（yl，ym），1≤l＜m≤n。

若j=n－1，則從碼書中去掉碼字 yi，否則令yj=yn－1，Rj=Rn－1，從碼書中去掉碼字 yn－1，令n=n－1。

步驟4 若n+1=N，則終止程序，其中N為所要求的碼書大小;否則，轉(zhuǎn)步驟2繼續(xù)合并最近的兩個(gè)胞腔。

2.2 改進(jìn)的PNN算法

針對(duì)PNN算法復(fù)雜度較高，對(duì)PNN算法進(jìn)行了改進(jìn)，以達(dá)到減小復(fù)雜度得目的。下面介紹PNN的兩種改進(jìn)算法，排序的鄰近搜索算法和排序多融合最鄰近搜索算法。排序的鄰近搜索算法是通過(guò)矢量和值排序來(lái)減少算法復(fù)雜度。排序多融合最鄰近搜索算法是通過(guò)一次迭代合并多個(gè)矢量來(lái)減少迭代時(shí)間。

2.2.1 排序的鄰近搜索算法

排序的鄰近搜索算法（ordered PNN，OPNN），是通過(guò)對(duì)訓(xùn)練矢量求和值后排序，再計(jì)算排序后相鄰兩個(gè)碼書的距離，對(duì)距離最小的兩個(gè)相鄰碼書進(jìn)行合并。該算法相對(duì)于PNN算法，減少了計(jì)算矢量距離的次數(shù)和尋找最小距離矢量的比較次數(shù)，使算法的復(fù)雜度得到減少，該算法描述如下。

步驟1 設(shè)一個(gè)訓(xùn)練序列{xj;j=1，…，M}，碼書大小為N。計(jì)算輸入矢量各分量的和定義為

步驟2 將訓(xùn)練矢量集xj按照矢量和值的大小進(jìn)行升序排列，得到新的序列為

步驟3 在序列xsj中，相鄰的兩個(gè)矢量的距離最近。把兩個(gè)相鄰的訓(xùn)練矢量看作一對(duì)相鄰對(duì)，計(jì)算各矢量相鄰對(duì)之間的距離為

步驟4 找出相鄰對(duì)的距離dxw中最小的一對(duì)，其距離最短的一個(gè)相鄰對(duì)為

步驟5 然后距離最近相鄰對(duì)中的兩個(gè)矢量合并成一個(gè)矢量

步驟6 迭代一次后，M個(gè)訓(xùn)練矢量減少到M－1個(gè)，反復(fù)迭代，直到達(dá)到碼書的個(gè)數(shù)及N=M，程序終止。否則繼續(xù)步驟1到步驟5。

2.2.2 排序多融合最鄰近搜索算法

在上述方法中，一次迭代只能合并一對(duì)相鄰對(duì)，因此達(dá)到期望的碼書需要很多次迭代。是在OPNN的基礎(chǔ)上，通過(guò)一次合并多個(gè)相鄰對(duì)來(lái)減少迭代次數(shù)和迭代時(shí)間。這種改進(jìn)的方法稱為排序多融合最鄰近搜索（ordered PNN with multiple merging，OPNNM）算法。在這種方法中，首先對(duì)各個(gè)相鄰對(duì)中兩個(gè)碼字的距離dxw進(jìn)行計(jì)算，把dxw按照升序進(jìn)行排列

很顯然，在序列前段的相鄰對(duì)的距離比較短，排序后，將前p對(duì)訓(xùn)練矢量進(jìn)行合并，這樣，迭代一次后，M個(gè)訓(xùn)練矢量將減少到M－p個(gè)。當(dāng)達(dá)到一定迭代次數(shù)后，將得到N個(gè)碼字，達(dá)到訓(xùn)練目的。算法描述如下。

步驟1 設(shè)一個(gè)訓(xùn)練序列{xj;j=1，…，M}，碼書大小為N。由（4）式計(jì)算各矢量和值。

步驟2 按（5）式對(duì)各矢量和值進(jìn)行升序排列。

步驟3 在序列xsj中，相鄰的兩個(gè)矢量的距離最近。把兩個(gè)相鄰的訓(xùn)練矢量看作一對(duì)相鄰對(duì)，按（6）式計(jì)算各矢量相鄰對(duì)之間的距離。

步驟4 按（9）式對(duì)各矢量、各相鄰對(duì)之間的距離進(jìn)行排序。

步驟5 在序列前段的相鄰對(duì)的距離比較短，按（8）式合并序列的前p個(gè)訓(xùn)練矢量。

步驟6 迭代一次后，M個(gè)訓(xùn)練矢量減少到M－1個(gè)，反復(fù)迭代，直到達(dá)到碼書的個(gè)數(shù)及N=M，程序終止。否則繼續(xù)步驟1到步驟5。

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

實(shí)驗(yàn)中，碼書訓(xùn)練和圖像編碼采用256×256×8 bit的2幅標(biāo)準(zhǔn)灰度測(cè)試圖像Lena和Boys。將圖像進(jìn)行預(yù)處理，生成4×4的16維輸入矢量。采用圖像的客觀測(cè)度（峰值信噪比PSNR=10lg255/MSE）對(duì)算法性能進(jìn)行比較，MSE為編碼圖像的均方誤差。表1是將 LBG、用 LBG優(yōu)化了的 PNN和 OPNN、用LBG優(yōu)化了的一次迭代合并64個(gè)矢量的OPNNM算法進(jìn)行了比較。在各種碼書尺寸下比較由各種算法重建圖像的 PSNR，其中LBG算法和用于優(yōu)化PNN和OPNN的LBG算法是經(jīng)過(guò)6次聚類迭代后的碼書重建圖像的PSNR，用來(lái)評(píng)估算法的好壞。

由表1可以看出，PNN算法用于碼書設(shè)計(jì)，性能較差，PSNR比較低。把PNN算法作為初始碼書用于LBG碼書設(shè)計(jì)，隨著碼書尺寸的增加，在Lena中，PSNR提高了0.1～0.6 dB 左右，性能得到一定程度的改善，但PSNR提高得不是很多，而在Boys中，PSNR還有所下降。將改善后的PNN算法即OPNN和OPNNM用于LBG初始碼書的設(shè)計(jì)中，隨著碼書尺寸的增大，PSNR提高了1～3 dB左右，碼書性能得到了很大提高，OPNNM算法的PSNR略低于OPNN算法，但OPNNM的復(fù)雜度較小。因而可知本文的兩種算法相對(duì)于LBG算法，PSNR提高得越多，性能很好。

表1 編碼性能（PSNR）的比較Tab.1 Comparison of the encoding quality（PSNR）

圖1給出了16維矢量和N=512時(shí)，Lena圖像的 LBG，PNN+LBG，OPNN+LBG 和 OPNNM+LBG（64）這4種方法作20次LBG算法聚類迭代的均方差MSE和迭代次數(shù)的關(guān)系圖?？梢钥吹胶玫某跏即a書使迭代避免收斂較差的局部解，以便獲得較好的最終碼書。本文算法相對(duì)于LBG算法，均方誤差降低了很多，優(yōu)勢(shì)相當(dāng)明顯。

圖1 4種算法的MSE和迭代次數(shù)的關(guān)系Fig.1 Relationship of the MSE and the number of iterations of the four algorithms

表2是對(duì)Lena圖像的OPNN算法和OPNNM算法用于LBG的初始碼書設(shè)計(jì)進(jìn)行的比較。顯而易見(jiàn)，PNN算法的時(shí)間復(fù)雜度要比改進(jìn)的兩種算法高很多，所以本文僅把一次迭代只合并一個(gè)矢量和一次迭代合并32，64，128個(gè)矢量進(jìn)行了時(shí)間和重建圖像的PSNR比較。由表2可以看出，OPNN+LBG算法的PSNR略高于OPNNM+LBG算法的PSNR。但是進(jìn)行一次迭代進(jìn)行多個(gè)合并很大程度上減少了迭代時(shí)間。對(duì)于OPNNM+LBG算法，隨著合并個(gè)數(shù)的增多，時(shí)間得到一定程度的減少，PSNR也略有增加。

表2 2種改進(jìn)算法的時(shí)間和PSNR比較Tab.2 Comparison of the time and PSNR of the two improved algorithms

4 總結(jié)

提出2種基于改進(jìn)的PNN初始碼書形成算法，算法利用矢量和值排序和一次迭代多融合，作為PNN的優(yōu)化條件，從而大大地減少了PNN的復(fù)雜性和迭代時(shí)間。而且基于PNN算法的魯棒性較好，因而改進(jìn)的PNN算法能以較快速度和以較少的計(jì)算量進(jìn)行迭代，為達(dá)到目標(biāo)質(zhì)量的各類矢量量化碼書算法的形成提供了算法支持。

［1］ 陳善學(xué)，李方偉.矢量量化與圖像處理［M］.北京:科學(xué)出版社，2009，45－187.

CHENG Shan－xue，LIFang－wei.Vector Quantization and Image Processing［M］.Beijing:Science Press，2009，45－187.

［2］WU Ping，LI li－h(huán)ua，ZHANG Ping.Unitary Space Vector Quantization codebook Design For Spatial Correlated Lim－ited feedback MIMO system［J］.The Journal of China U－niversities of Posts and Telecommunications，2008，15（1）:23－27.

［3］ LINDE Y，BUZO A，GRAY R M.An algorithm for vector quantizer design［J］.IEEE Trans on Corn，1980，28（1）:84－95.

［4］ CIERNIAK R，RUTKOWSKIL.On image compression by competitive neural networks and optimal linear predictors［J］.SP Image Communication，2000，15:559－565.

［5］徐皓淋，陳善學(xué).一種改進(jìn)的等誤差競(jìng)爭(zhēng)學(xué)習(xí)矢量量化算法［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2009，21（6）:721－724.

XU Hao－lin，CHEN Shan－xue.An improved competitive learning vector quantization algorithm based on equidistortion［J］.Journalof Chongqing University of Posts and Telecommunications:Natural Science Edition，2009，21（6）:721－724.

［6］余春東，孫世新，王茂芝，等.一種高效的基于模擬退火的LBG改進(jìn)算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2005，26（2）:218－221.

YU Chun－dong，SUN Shi－xin，WANGMao－zhi，etal.Efficient LBG Algorithm based on Simulated Annealing［J］.Mini－Micro Systems，2005，26（2）:218－221.

［7］鄭巖，黃榮懷，戰(zhàn)曉蘇，等.基于遺傳算法的動(dòng)態(tài)模糊聚類［J］.北京郵電大學(xué)學(xué)報(bào)，2005，28（1）:75－78.

ZHENG Yan，HUANG Rong－h(huán)uai，ZHAN Xiao－su，et al.Dynamic Fuzzy Clustering Method Based on Genetic Algorithm［J］.The Journal of China Universities of Posts and Telecommunications，2005，28（1）:75－78.

［8］EQUITZW H.A new vector quantization clustering algorithm［J］.IEEE Transactions on Acoustics Speech and Signal Processing，1989，37（10）:1568－1575.

［9］ 陳卡軍，朱云濤，單智陽(yáng)，等.基于PNN的算法改進(jìn)及解碼器硬件實(shí)現(xiàn)［J］.微電子學(xué)與計(jì)算機(jī)，2004，21（12）:69－92.

CHEN Ka－jun，ZHU Yun－tao，SHAN Zhi－yang，et al.Optimized PNN Algorithm and Implementation of the Decoder［J］.MICROELECTRONICS ＆ COMPUTER，2004，21（12）:69－92.

［10］吳婷婷，曾毓敏.一種基于改進(jìn)的矢量量化技術(shù)的語(yǔ)音波形編碼［J］.電子工程師，2007，33（10）:28－30.

WU Ting－ting，ZENG Liu－ming.A Speech Wave Coding Based on Modified Vector Quantization Technique［J］.ELECTRONIC ENGINEER，2007，33（10）:28－30.

［11］孫圣和，陸哲明.矢量量化技術(shù)及應(yīng)用［M］.北京:科學(xué)出版社，2002:31－49.

SUN Sheng－h(huán)e，LU Zhe－ming.Vector Quantization and its Application［M］.Beijing:Science Press，2002:31－49.

［12］ LINDE Y，BUZO A，GRAY R M.An algorithm for vector quantizer design［J］.IEEE Transactions on Communication，1980，28（1）:84－95.