基于改进人工蜂群的图像矢量量化码书设计算法

　　0引言

　　矢量量化是图像压缩编码的一项重要技术。码书设计、码字搜索和码字索引分配是矢量量化的三大关键技术，其中以码书设计最为重要[1-3]。传统的码书设计算法多是在Linde等[4]提出的LBG（LindeBuzoGray）算法基础上加以改进的算法，该类算法在一定程度上改善了基本LBG算法对初始码书敏感、训练时间长的缺点；但这些算法的迭代过程缺乏全局思想，生成的码书稳定性和通用性较差。随着仿生智能优化算法的发展，遗传算法、蚁群算法和粒子群算法等已在复杂问题的优化求解和实际工程应用中显示出了强大的生命力[5-7]。本文将仿生智能优化算法的全局搜索思想应用于码书设计过程，可以使生成的码书适应性更强，压缩性能更稳定。

　　2005年，Karaboga等[8]模拟蜜蜂群体寻找优良蜜源的行为提出了人工蜂群算法，该算法与遗传算法、蚁群算法和粒子群算法相比，设置参数少，计算简单，在每次迭代中都进行全局和局部搜索，具有寻优能力强、不易陷入局部最优的优点。目前已被应用于数字滤波器设计[9]、数据聚类[10]、车辆路径优化[11]等领域，并取得了良好的效果。

　　本文将改进人工蜂群算法应用于码书设计。为了进一步减少算法的计算量，将快速码字搜索思想应用于该码书设计算法的适应度函数计算过程中，从而大大降低算法的计算量。实验结果表明，本文算法具有计算时间短、收敛速度快和生成码书质量好等优点。

　　2人工蜂群算法

　　人工蜂群算法[12]是通过对自然界的蜂群采蜜的群体行为进行研究，受到启发而提出的一种新型优化算法。在该算法中，蜂群由引领蜂、跟随蜂、侦察蜂三部分组成。蜂群的采蜜过程有搜索蜜源、招募跟随蜂、放弃蜜源三种行为。算法在求解优化问题的过程中，一个蜜源代表组合优化问题解空间中的一个点，蜜源的质量由解的适应度值来表示，蜜蜂采蜜的过程实际就是在解空间中寻找最优解的过程。算法解的个数N等于引领蜂或跟随蜂的个数。搜索之前人工蜂群算法首先随机生成含有N个解（蜜源）的初始种群X（0）={X1，X2，…，XN}，每个解是一个m维向量Xi={xi1，xi2，…，xim}。然后，蜜蜂对所有蜜源进行搜索，循环次数为C。引领蜂首先对蜜源进行一次邻域搜索，如果搜索到的蜜源的质量（适应度）优于以前，就用新的蜜源代替旧的蜜源；否则旧的蜜源位置保持不变。引领蜂完成搜索后，回到舞蹈区把花蜜质量通过摇摆舞传递给跟随蜂，跟随蜂根据蜜源的质量来选择蜜源，质量越好的蜜源被选择的概率越大。蜜源被选中后，跟随蜂也进行一次邻域搜索，保留较好的解。

　　3基于和值特性的快速码字搜索算法

　　本文采用均方误差作为基于人工蜂群优化的码书设计的适应度函数，每次迭代前都要找到要码书中距离训练矢量最近的码字，进而根据式（1）计算均方误差。传统方法是对码书中所有的码字做一次穷尽搜索，计算训练矢量与所有码字之间距离，并通过比较找出距离最近的码字。这种方法计算量很大，因此在执行人工蜂群搜索过程中，适应度函数的计算要耗费很多时间。

　　在图像压缩过程中，码字搜索也是在码书中搜索与原图像中矢量距离最近的码字，因此将快速码字搜索算法的思想应用于码书设计的适应度函数计算过程中，可以大大降低计算量。一些学者提出了许多快速码字搜索算法，如部分失真搜索算法、基于三角不等式的快速码字搜索算法和基于范数不等式的快速算法等[13-15]，本文将基于和值特性的快速码字搜索算法[16]的思想，应用于码书设计的适应度函数计算过程。算法利用各码字的和值、训练矢量的和值与它们距离之间的关系排除大部分候选码字，避免对其均方误差的计算，大大降低了计算量。

　　4基于改进人工蜂群的码书设计算法

　　基本的人工蜂群算法不容易陷入局部极值，收敛精度高，在优化求解维数较低的函数时有明显的优势，而把基本人工蜂群算法应用于维数相对较高的图像压缩码书设计领域中，例如本文中达到4096维，基本人工蜂群算法的运算时间原本就比较长，当维数增加时，不但整个算法的运算时间会更长，收敛精度也明显下降。为了提高算法的收敛精度和收敛速度，减少算法的计算量，本文对初始码书设计、搜索策略和适应度函数计算过程进行了改进。

　　4.1初始码书设计

　　6结语

　　本文将改进的人工蜂群算法应用于矢量量化图像压缩码书设计中，采用基于混沌映射和反向学习的群体初始化方法生成初始码书，减小了初始码书对优化结果的影响。将差分进化中的变异操作引入到基本人工蜂群算法的搜索策略中，提高了算法的收敛速度；并且，在适应度函数的计算过程中引入了基于和值的快速码字搜索算法的思想，大大减少了算法的计算量，节省了运算时间。实验结果表明，算法参数设计简单，收敛精度高，计算时间短，生成的码书不仅质量高，而且通用性好。