一种基于混沌粒子群算法的矢量量化码书构造方法

摘要

本发明请求保护一种基于混沌粒子群算法的矢量量化码书构造方法，具体地说是一种可用于语音压缩编码和图像压缩系统中的基于粒子群的矢量量化器。此方法把粒子群算法与混沌算法相结合用于矢量量化码书的构造，并可将该算法扩展到多级矢量量化器中。由于本发明在粒子群优化算法中融入了混沌优化，加快了粒子群算法摆脱局部极值点的速度，提高了算法的收敛精度，使矢量量化器的性能得到了改善。

说明书

技术领域

本发明属于数据压缩领域，具体涉及一种矢量量化方法及矢量量化器，在 语音压缩编码及图像压缩系统中具有广泛的应用。

背景技术

矢量量化是香农信息论在信源编码理论方面的新发展，将若干个标量数据 构成一个矢量，然后在矢量空间中给以整体量化，达到既压缩了数据又不损失 太多的信息。因此，矢量量化是一种高效的数据压缩技术，具有压缩比大，解 码简单等优点，在语音和图像编码领域有着广泛的应用。矢量量化的基本理论 早在二十世纪六七十年代已有人关注，在二十世纪八十年代开始逐步完善起来。 实现一个实用的矢量量化器，首先需要解决的是码书的设计。如果码书性能不 佳，将影响矢量量化系统的编码质量，如导致解码端语音合成质量或图像重构 质量的下降。LBG算法是由Linde、Buzo和Gray于1980年提出的一种经典的 码书构造方法，因其具有理论严密、实施简便、收敛快速的特点，在矢量量化 领域取得了广泛的应用。但是LBG算法的性能过于依赖初始码书，且容易陷入 局部最优。为此，学者们在LBG算法的基础上，提出了很多改进的码书构造算 法，如模拟退火码书算法、PNN码书算法、神经网络码书算法、免疫猫群优化 码书算法等。本发明是将粒子群算法与混沌算法相结合，提出了一种基于混沌 粒子群算法的码书构造方法。该方法能增加解空间的多样性，提高全局搜索能 力及收敛精度，同时也能处理空胞腔的问题。

混沌是自然界广泛存在的一种非线性现象,混沌变量看似杂乱，但其变化过 程含有内在的规律性，被誉为上世纪末最大的发现，正在为推动现代科学进步 发挥着重要的作用。目前对混沌尚无严格的定义，一般将由确定性方程得到的 具有随机性的运动状态称为混沌，呈现混沌状态的变量称为混沌变量。混沌运 动貌似随机，却隐含着精致的内在结构，具有遍历性、随机性和对初始条件敏 感性的特点，能在一定范围内按其自身规律不重复地遍历所有状态，因此，利 用混沌运动的这些性质可以进行优化搜索。如下的logic方程描述了一个最典型 的混沌系统。

Z_n+1＝μZ_n(1-Z_n),n＝0,1,2,…

上式中的μ为控制参量，该值确定后，由任意初值Z₀(0,1)可迭代出一个确定 的时间序列Z₀,Z₁,…,Z_n。

粒子群优化(ParticleSwarmOptimization，PSO)算法最初是由Kennedy和 Eberhart于1995年受人工生命研究结果的启发，在模拟鸟群觅食过程中的迁徙 和群集行为时提出的一种基于群体智能进化的计算技术。由于该算法简单、收 敛速度快，并且对目标函数要求较少(如无需梯度信息)等特点，因此发展十 分迅速，且在诸多领域得到成功应用。在PSO模型中，优化问题的每个解对应 搜索空间中的一只鸟，该“鸟”也称为粒子，每个粒子有一个速度，决定其飞 翔的方向和距离。PSO初始化为一群随机粒子，然后粒子开始追随当前的最优 粒子运动，直到在整个解空间中搜索找到最优解为止。在每次迭代中，粒子通 过追踪两个极值来更新自己，一个是粒子自己找到的最优解，称为个体极值p_best； 另一个是整个粒子群找到的最优解，称为全局极值g_best。假设用表 示第i个粒子，其中n是粒子的维数，它经历的最好位置表示为而整个群体经历的最好位置表示为粒子i的速度为 按搜寻当前最优粒子原理，粒子i按(1)式和(2)式来改变速 度和位置。

$v_i^j(t+1)={\mathrm{wv}}_i^j\left(t\right)+c_1{r}_1\left(p_i^j\right(t)-x_i^j(t\left)\right)+c_2{r}_2\left(g_i^j\right(t)-x_i^j(t\left)\right)---\left(1\right)$

$x_i^j(t+1)=x_i^j\left(t\right)+v_i^j(t+1)---\left(2\right)$

其中,t为当前的迭代次数；c₁、c₂为学习因子；r₁、r₂为服从(0,1)分布的随 机数，w为惯性权重因子。研究表明：较大的w值有利于跳出局部极小值点，较 小的w值有利于算法收敛和提高解的精度。在很多算法中，常采用(3)式计算w 的线性递减值。

$w=w_{max}-(w_{max}-w_{min})\frac{t}{t_{max}}---\left(3\right)$

t_max为设定的最大迭代次数；w_max为最大惯性权重；w_min为最小惯性权重。此 外，为使粒子速度不至于过大，可设定速度上限值V_max。当某一维的速度超过这 一设定速度时，就令这一维的速度为V_max。

粒子群优化算法虽然具有原理简单，易于应用的优点，但也有易陷入局部 极值点，进化后期收敛速度慢，精度较差等缺点。

发明内容

针对粒子群优化算法的不足，提出了一种基于混沌粒子群算法的矢量量化 码书构造方法。本发明的技术方案如下：一种基于混沌粒子群算法的矢量量化 码书构造方法，其包括以下步骤：

101、提取语音信号或图像信号的特征参数值，提取的特征参数值作为构造 码书的训练矢量；

102、将生成矢量量化码书所需的全部训练矢量X存储在计算机内存中，全 部X的集合用S表示；

103、种群初始化，设置迭代算法的最大迭代次数MaxLoop，粒子的个数K， 矢量量化级数M，最大速度V_max，最小速度V_min；设置粒子的初始速度 p[k].v,k＝1,2,...,K；设置适应度初值p[k].f,k＝1,2,...,K；设置迭代初值m＝1，级数 初值kkk＝1；

104、从步骤102中的全部训练矢量X中，随机提取N个训练矢量组成一个 初始码书重复K次，获得K个粒子p[k]；根据 最邻近准则，每输入一个粒子，将其划分到N个子集中，即当时，下式成立：

$d(X,y_l^{m-1})\le d(X,y_i^{m-1}),\forall i,i\ne l$

$d(X,y_l^{m-1})=\left|\right|X-y_l^{m-1}|{|}^2$

105、计算新码字$p\left[k\right].Y=\left(p\right[k].y_1^m,p[k].y_2^m,...,p[k].y_N^m),$其中是的质心， 计算公式如下，num_i是集合中训练矢量的个数；

$p\left[k\right].y_i^m=\frac{1}{{\mathrm{num}}_i}\underset{X\in S_i^m}{\Sigma }X$

统计每一个胞腔，即每个子集包含的训练矢量数，将每一个训练矢量的 失真按从大到小排序。对于空胞腔，则将胞腔训练矢量数不为1且失真最大的 训练矢量作为新的码字代替空胞腔，同时将此胞腔中的训练矢量数减1；

106、计算各个粒子的适应度

$p\left[k\right].f^{\left(m\right)}=\underset{i=1}{\overset{N}{\Sigma }}\underset{X\in S_i^m}{\Sigma }d(X,y_i^m)$

比较适应度p[k].f^(m)与p[k].f_best，如果p[k].f^(m)小于最优位置的适应度p[k].f_best， 则更新p[k].f_best与比较每个粒子的适应度 p[k].f_best与群的最优位置的适应度f_gbest，如果p[k].f_best小于f_gbest，则更新f_gbest与群体 最优粒子$p.Y_{gbest}=\left(p\right[k].y_1^m,p[k].y_2^m,...,p[k].y_N^m);$

107、如果迭代次数m能整除3，则对最优粒子进行混沌优化。在下式中，β_i和α_i是特征参数第i维的最大值和最小值，μ为控制参量；

$z_i=\frac{p\left[k\right].y_i-{\alpha }_i}{{\beta }_i-{\alpha }_i}$

z_i＝μ(1-z_i)

p[k].y_i＝α_i+(β_i-α_i)z_i

循环三次，产生3个粒子，保留适应度最小的粒子，并取代当前群体中随 机选取的一个粒子；判定迭代次数是否大于MaxLoop，如果大于MaxLoop，则跳 到步骤109，否则转到步骤108，继续执行；

108、更新粒子及粒子的速度；

109、求训练矢量量化残差，输出码字，级数kkk加1，如果kkk>M，结束； 如果kkk≤M，重新设置初值，并将训练矢量改为上一级的量化残差矢量。

进一步的，如果矢量量化级数M设为1，设计出来的是单级矢量量化器码书； 如果M>1，设计出的是M级矢量量化器码书。

进一步的，粒子群算法中惯性权重因子w的计算公式为：

$w=w_{\min }+(w_{max}-w_{min})\frac{1+cos\left[\frac{f_g(m-1)}{f_i(MaxLoop-1)}\pi \right]}{2}$

上式中，f_g是全局最优适应度，w_max表示最大惯性权重，w_min表示最小惯性 权重，f_i是当前粒子适应度，MaxLoop是最大迭代次数，m是当前迭代次数。

本发明的优点及有益效果如下：

本发明充分利用了粒子群算法搜索范围广以及混沌算法具有遍历性的特 点，将粒子群算法与混沌算法结合起来，增加解空间的多样性，提高全局搜索 能力及收敛精度，同时对空胞腔的问题也作了有效的处理，优化了量化器的性 能。本发明能用于语音和图像压缩编码中，具有良好的应用前景和实用价值。

附图说明

图1是本发明提供优选实施例基于混沌粒子群的码书构造算法流程图。

具体实施方式

以下结合附图，对本发明作进一步说明：

把混沌优化思想引入到粒子群优化算法中，提出了一种基于混沌粒子群算 法。该算法使得解空间具有多样性，能提高全局搜索能力及收敛精度。采用混 沌粒子群算法构造矢量量化码书的步骤如图1所示。

在粒子群算法中，惯性权重因子w的大小影响了算法的搜索能力。当w较大 时，有利于提高算法的全局搜索能力，但局部搜索能力较弱；当w较小时，可以 增强粒子的局部搜索能力，但探索新区域的能力较弱。在标准粒子群算法中，w 为定值，这样就无法充分利用粒子的探索能力。在线性递减惯性权重粒子群算 法中，w不是固定的，是按照公式(3)进行更新，使得w与迭代次数有关，随 着迭代次数增加，w线性减小。相对于标准粒子群算法，该算法虽然在性能上有 所改进，但早熟收敛问题依然没有得到根本性解决，尤其是粒子后期的多样性 变差，导致收敛速度变慢，极易陷入局部最优。

粒子的适应度f是反映粒子当前位置优劣的一个参数，对于某个具有较高适 应度的粒子，它所在的局部区域可能存在能够得到更新全局最优的点p_best，即p_best所表示的解优于全局最优g_best。为了使全局最优能够迅速得到更新，即能迅速找 到p_best，应该减小粒子的惯性权重因子以增强其局部搜索能力。而对于适应度较 低的粒子，当前位置较差，在区域存在优于全局最优解的概率较低，为了跳出 当前的区域，应当增大惯性权重因子，以增强全局搜索能力。所以惯性权重因 子不仅与迭代次数有关，也与适应度f密切相关，在本发明中，将惯性权重因子 w按下面公式进行计算。

$w=w_{min}+(w_{max}-w_{min})\frac{1+cos\left[\frac{f_g(m-1)}{f_i(MaxLoop-1)}\pi \right]}{2}$

上式中，f_g是全局最优适应度，f_i是当前粒子适应度，MaxLoop是最大迭代 次数，m是当前迭代次数。为了进一步增强粒子的全局搜索能力与收敛精度， 对每次搜索出的最优值进行混沌优化。利用混沌运动的遍历性，以当前整个粒 子群搜索到的最优位置为基础产生混沌序列，把产生的混沌序列中的最优位置 的粒子随机替代当前粒子群中一个粒子的位置。为了降低算法的复杂度，本发 明不是每次都进行混沌优化，而是采取每Q次迭代进行一次混沌优化，这样能 有效地降低算法复杂度，对最后获得粒子的质量影响不大。

最优矢量量化器的构造需要遵循以下两条原则：

1、最近邻条件

设给定码书C＝{y₀,y₁,…,y_N-1}，尺寸大小为N，则输入矢量空间的最优划分 {R₀,R₁,…,R_N-1}应满足$R_i=\left\{x\right|d(x,y_j)=\underset{0\le j\le N-1}{min}d(x,y_j)\}.$

2、质心条件

对给定的划分{R₀,R₁,…,R_N-1}，最优码字y_j必须是相应胞腔R_j的“质心”，即 y_j＝cent(R_j)。

在本发明实例中，拟对语音特征参数线谱对频率LSF进行三级矢量量化，要 构造一个三级LSF码书，其大小分别为256、64、32，所用的训练矢量是采用混 合激励线性预测(MELP)编码器从大量中英文语音数据库中提取的LSF参数， 矢量维数为10。具体的步骤如下：

1)将生成矢量量化码书所需的全部训练矢量X存储在计算机内存中，全部 X的集合用S表示；

2)设置迭代算法的最大迭代次数MaxLoop＝20，粒子的个数K＝15，矢量量 化级数M＝3，最大速度V_max＝150，最小速度V_min＝-150，级数初值kkk＝1；

3)设置粒子的初始速度p[k].v,k＝1,2,...,K；

4)设置适应度初值p[k].f,k＝1,2,...,K；

5)设置迭代初值m＝1；

6)从训练矢量中，随机提取N个训练矢量组成一个初始码书 $p\left[k\right].Y=\left(p\right[k].y_1^0,p[k].y_2^0,...,p[k].y_N^0),$重复K次，获得K个粒子p[k]；

7)根据最邻近准则，每输入一个粒子，将其划分到N个子集中， 即当时，下式成立：

$d(X,y_l^{m-1})\le d(X,y_i^{m-1}),\forall i,i\ne l$

$d(X,y_l^{m-1})=\left|\right|X-y_l^{m-1}|{|}^2$

8)计算新码字$p\left[k\right].Y=\left(p\right[k].y_1^m,p[k].y_2^m,...,p[k].y_N^m),$其中是的质心， 计算公式如下，num_i是集合中训练矢量的个数。

$p\left[k\right].y_i^m=\frac{1}{{\mathrm{num}}_i}\underset{X\in S_i^m}{\Sigma }X$

9)统计每一个胞腔包含的训练矢量数，将每一个训练矢量的失真按从大到 小排序。对于空胞腔，则将胞腔训练矢量数不为1且失真最大的训练矢 量作为新的码字代替空胞腔，同时将此胞腔中的训练矢量数减1；

10)计算每个粒子的适应度

$p\left[k\right].f^{\left(m\right)}=\underset{i=1}{\overset{N}{\Sigma }}\underset{X\in S_i^m}{\Sigma }d(X,y_i^m)$

11)比较适应度p[k].f^(m)与p[k].f_best，如果p[k].f^(m)小于p[k].f_best，则更新p[k].f_best 与$p\left[k\right].Y_{best}=\left(p\right[k].y_1^m,p[k].y_2^m,...,p[k].y_N^m);$

12)比较适应度p[k].f_best与f_gbest，如果p[k].f_best小于f_gbest，则更新f_gbest与群体最 优粒子$p.Y_{gbest}=\left(p\right[k].y_1^m,p[k].y_2^m,...,p[k].y_N^m)$

13)如果m能够整除3，则对最优粒子进行混沌优化，下式中β_i是LSF第i维 的最大值，α_i是LSF第i维的最小值，μ为控制参量；

$z_i=\frac{p\left[k\right].y_i-{\alpha }_i}{{\beta }_i-{\alpha }_i}$

z_i＝μ(1-z_i)

p[k].y_i＝α_i+(β_i-α_i)z_i

循环三次，产生3个粒子，保留适应度最小的粒子，并取代当前群体中 随机选取的一个粒子。

14)判定迭代次数是否大于MaxLoop，如果大于MaxLoop，则跳到步骤17，否 则转到步骤15，继续执行。

15)根据以下式子更新粒子及粒子的速度

$p\left[k\right].v_i^{m+1}=wp\left[k\right].v_i^m+c_1{r}_1\left(p\right[k].Y_{best}-p[k].y_i^m)+c_2{r}_2(p.Y_{gbest}-p[k].y_i^m)$

$p\left[k\right].y_i^{m+1}=p\left[k\right].y_i^m+p\left[k\right].v_i^{m+1}$

m＝m+1

16)跳到第7步，继续执行；

17)求得训练矢量量化残差，输出码字，级数kkk加1。如果kkk>M，跳到 步骤18；如果kkk≤M，重新设置初值，并将训练矢量改为上一级量化 的残差。初值设置如下：

if(kkk＝2)

N＝64；

V_max＝f_gbest；V_min＝-f_gbest；

if(kkk＝3)

N＝32；

V_max＝f_gbest；V_min＝-f_gbest；

18)结束

以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范 围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或 修改，这些等效变化和修饰同样落入本发明权利要求所限定的范围。