用于LBG初始码书设计的改进PNN算法

陈善学，张 艳，吴立彬

（重庆邮电大学移动通信安全技术实验室，重庆 400065）

0 引言

矢量量化（vector quantization，VQ）［1－2］是一种高效的数据压缩编码方式，码书设计和码字搜索是它的两个关键技术。码书的优劣决定了量化器的性能，因而矢量量化的首要问题在于设计出性能好的码书。但是目前没有一种通用的方法能设计出一种在全局意义下的最优码书。1980年，由Linde，Buzo和Gray［3］首先提出的LBG算法是一种直观有效的矢量量化码书设计算法。但它具有依赖对初始码书的选取，自适应能力不强，易陷于局部最优等缺点。对于这些问题，后来的研究者提出了各种改进方法:主要有LBG的改进算法［4］;基于神经网络的码书设计算法［5］，如自学习神经网络、竞争学习神经网络;基于随机优化技术的码书设计算法，如遗传算法、模拟退火算法、粒子群算法、蚁群算法等，或者是与LBG 的结合算法［6］;基于模糊聚类理论［7］的码书设计算法;自适应更新的矢量量化码书设计算法等。本文是采用改进的成对最邻近（par－wise nearest neighbor，PNN）算法用于LBG初始码书来实现矢量量化中的最优码书设计。

PNN算法［8］是一种删除算法。它通过在设计过程中不断地合并最邻近的胞腔来生成码书。每个训练矢量分配一个胞腔，一次迭代合并最邻近的两个胞腔，直到胞腔数目达到要求的码书个数。该算法复杂性比较高，可独立用于码书设计，但性能不是很好。一些改进的PNN算法在图像编码［9］和语言编码［10］当中都有所运用。本文通过排序和一次迭代合并多个矢量来优化PNN算法，使PNN算法的复杂性和迭代时间得到减少。然后将优化后的PNN算法作为初始码书用于LBG进一步优化。仿真实验表明，该生成的码书性能得到了提高，将其运用到图像处理的码书设计中具有较好的效果。

1 矢量量化与LBG算法

矢量量化本质上是一个聚类过程，而码书设计就是寻求把M个训练矢量分成N类的一种最佳方案。设M个k维数据组成的数据空间为{Xij}，其中i=1，…，M;j=1，…，k，矢量量化可以看做是这个k维欧几里德空间Rk到包含N个互相不重合（R1，R2，…，RN）子空间的有限子集Y的映射。即Q:Rk→Y，其中在每一个子空间Rj中选出一个代表矢量，记为 Yj=（yj1，yj2，…，yjk），将各个子空间的代表矢量集记为Y={Yj;j=1，…，N}，通常将Y称为码书（code book），Yj称为码字（code word），而N是码书大小。收端以Yj再现X必然存在失真，满足d（X，Yi）=min（d（X，Yj）），j=1，…，N。d（X，Yi）为矢量X与码字Yi之间的失真测度。一般在计算整个输入信号和相应的重构信号之间的失真时，经常采用峰值信噪比（peak signal noise ratio，PSNR）来描述矢量量化编码失真，定义为

（1）式中:L为图片灰度值;

（2）式中，xij为原始图像像素;yij为重构图像像素。

码书设计过程，即为寻找最优子集 Y，使得PSNR最大。

LBG算法一般是先选取初始码书，根据最邻近原则得到新胞腔，然后根据质心原则，通过量化、聚类、迭代由新胞腔得到新的码书。通过某种限制条件结束，迭代产生最终码书。这种迭代过程虽然不能保证最后能得到最优码书，但每次迭代都能降低或保持不变平均失真，使得码书性能得到提高。但它具有依赖对初始码书的选取，自适应能力不强，易陷于局部最优等缺点。

2 初始码书算法

好的初始码书能提高经过进一步迭代生成的最终码书的性能，如果初始码书的性能足够好，可以在较大程度上减少其后码书迭代过程中的系统开销和花费的时间。初始码书的获取方式一般有以下几种:随机选择法、分裂法、删除算法等［11］。随机算法是根据输入矢量分布随机选取矢量作为初始码书，该方法复杂度最小，但存在码书选取没有针对性和空胞腔等问题。分裂法［12］是由小的码书生成较大的码书，分裂法产生的码书性能比较好，但复杂度高于随机算法。删除算法是从整个训练矢量中有选择地删除训练矢量，直到得到要求的矢量作为码书。该算法的复杂度比较高。

2.1 PNN算法

由Equitz等提出的PNN算法是删除算法中的一种。若训练矢量集中的矢量个数为M，每个矢量都占有一个独立的胞腔，算法的目的是不断合并相近的两个胞腔直至得到所需数目的胞腔，且最终的码书由各胞腔的质心矢量组成。设训练矢量集为X={x1，x2，…，xM}，将 X 对应的欧几里德空间 Rk划分为M个互相不重合的子空间R1，R2，…，RM，该算法描述如下。

步骤1 令码字数n=M，每个胞腔的质心yi=xi（i=1，2，…，M）。

步骤2 计算各对码字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为所要求的码书大小;否则，转步骤2继续合并最近的两个胞腔。

2.2 改进的PNN算法

针对PNN算法复杂度较高，对PNN算法进行了改进，以达到减小复杂度得目的。下面介绍PNN的两种改进算法，排序的邻近搜索算法和排序多融合最邻近搜索算法。排序的邻近搜索算法是通过矢量和值排序来减少算法复杂度。排序多融合最邻近搜索算法是通过一次迭代合并多个矢量来减少迭代时间。

2.2.1 排序的邻近搜索算法

排序的邻近搜索算法（ordered PNN，OPNN），是通过对训练矢量求和值后排序，再计算排序后相邻两个码书的距离，对距离最小的两个相邻码书进行合并。该算法相对于PNN算法，减少了计算矢量距离的次数和寻找最小距离矢量的比较次数，使算法的复杂度得到减少，该算法描述如下。

步骤1 设一个训练序列{xj;j=1，…，M}，码书大小为N。计算输入矢量各分量的和定义为

步骤2 将训练矢量集xj按照矢量和值的大小进行升序排列，得到新的序列为

步骤3 在序列xsj中，相邻的两个矢量的距离最近。把两个相邻的训练矢量看作一对相邻对，计算各矢量相邻对之间的距离为

步骤4 找出相邻对的距离dxw中最小的一对，其距离最短的一个相邻对为

步骤5 然后距离最近相邻对中的两个矢量合并成一个矢量

步骤6 迭代一次后，M个训练矢量减少到M－1个，反复迭代，直到达到码书的个数及N=M，程序终止。否则继续步骤1到步骤5。

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

在上述方法中，一次迭代只能合并一对相邻对，因此达到期望的码书需要很多次迭代。是在OPNN的基础上，通过一次合并多个相邻对来减少迭代次数和迭代时间。这种改进的方法称为排序多融合最邻近搜索（ordered PNN with multiple merging，OPNNM）算法。在这种方法中，首先对各个相邻对中两个码字的距离dxw进行计算，把dxw按照升序进行排列

很显然，在序列前段的相邻对的距离比较短，排序后，将前p对训练矢量进行合并，这样，迭代一次后，M个训练矢量将减少到M－p个。当达到一定迭代次数后，将得到N个码字，达到训练目的。算法描述如下。

步骤1 设一个训练序列{xj;j=1，…，M}，码书大小为N。由（4）式计算各矢量和值。

步骤2 按（5）式对各矢量和值进行升序排列。

步骤3 在序列xsj中，相邻的两个矢量的距离最近。把两个相邻的训练矢量看作一对相邻对，按（6）式计算各矢量相邻对之间的距离。

步骤4 按（9）式对各矢量、各相邻对之间的距离进行排序。

步骤5 在序列前段的相邻对的距离比较短，按（8）式合并序列的前p个训练矢量。

步骤6 迭代一次后，M个训练矢量减少到M－1个，反复迭代，直到达到码书的个数及N=M，程序终止。否则继续步骤1到步骤5。

3 仿真实验结果及分析

实验中，码书训练和图像编码采用256×256×8 bit的2幅标准灰度测试图像Lena和Boys。将图像进行预处理，生成4×4的16维输入矢量。采用图像的客观测度（峰值信噪比PSNR=10lg255/MSE）对算法性能进行比较，MSE为编码图像的均方误差。表1是将 LBG、用 LBG优化了的 PNN和 OPNN、用LBG优化了的一次迭代合并64个矢量的OPNNM算法进行了比较。在各种码书尺寸下比较由各种算法重建图像的 PSNR，其中LBG算法和用于优化PNN和OPNN的LBG算法是经过6次聚类迭代后的码书重建图像的PSNR，用来评估算法的好坏。

由表1可以看出，PNN算法用于码书设计，性能较差，PSNR比较低。把PNN算法作为初始码书用于LBG码书设计，随着码书尺寸的增加，在Lena中，PSNR提高了0.1～0.6 dB 左右，性能得到一定程度的改善，但PSNR提高得不是很多，而在Boys中，PSNR还有所下降。将改善后的PNN算法即OPNN和OPNNM用于LBG初始码书的设计中，随着码书尺寸的增大，PSNR提高了1～3 dB左右，码书性能得到了很大提高，OPNNM算法的PSNR略低于OPNN算法，但OPNNM的复杂度较小。因而可知本文的两种算法相对于LBG算法，PSNR提高得越多，性能很好。

表1 编码性能（PSNR）的比较Tab.1 Comparison of the encoding quality（PSNR）

图1给出了16维矢量和N=512时，Lena图像的 LBG，PNN+LBG，OPNN+LBG 和 OPNNM+LBG（64）这4种方法作20次LBG算法聚类迭代的均方差MSE和迭代次数的关系图。可以看到好的初始码书使迭代避免收敛较差的局部解，以便获得较好的最终码书。本文算法相对于LBG算法，均方误差降低了很多，优势相当明显。

图1 4种算法的MSE和迭代次数的关系Fig.1 Relationship of the MSE and the number of iterations of the four algorithms

表2是对Lena图像的OPNN算法和OPNNM算法用于LBG的初始码书设计进行的比较。显而易见，PNN算法的时间复杂度要比改进的两种算法高很多，所以本文仅把一次迭代只合并一个矢量和一次迭代合并32，64，128个矢量进行了时间和重建图像的PSNR比较。由表2可以看出，OPNN+LBG算法的PSNR略高于OPNNM+LBG算法的PSNR。但是进行一次迭代进行多个合并很大程度上减少了迭代时间。对于OPNNM+LBG算法，随着合并个数的增多，时间得到一定程度的减少，PSNR也略有增加。

表2 2种改进算法的时间和PSNR比较Tab.2 Comparison of the time and PSNR of the two improved algorithms

4 总结

提出2种基于改进的PNN初始码书形成算法，算法利用矢量和值排序和一次迭代多融合，作为PNN的优化条件，从而大大地减少了PNN的复杂性和迭代时间。而且基于PNN算法的鲁棒性较好，因而改进的PNN算法能以较快速度和以较少的计算量进行迭代，为达到目标质量的各类矢量量化码书算法的形成提供了算法支持。

［1］ 陈善学，李方伟.矢量量化与图像处理［M］.北京:科学出版社，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－hua，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］徐皓淋，陈善学.一种改进的等误差竞争学习矢量量化算法［J］.重庆邮电大学学报:自然科学版，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］.小型微型计算机系统，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］郑岩，黄荣怀，战晓苏，等.基于遗传算法的动态模糊聚类［J］.北京邮电大学学报，2005，28（1）:75－78.

ZHENG Yan，HUANG Rong－huai，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］ 陈卡军，朱云涛，单智阳，等.基于PNN的算法改进及解码器硬件实现［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］.电子工程师，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］孙圣和，陆哲明.矢量量化技术及应用［M］.北京:科学出版社，2002:31－49.

SUN Sheng－he，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.