基于蚁群聚类算法的码书分类方法及其码书分类装置

摘要

一种基于蚁群聚类算法的码书分类方法及其码书分类装置，本方法码书分类过程是将设计的码书用码书分类方法分为多个子码书，分类子码书由子码书特征值代表，码书分类方法采用蚁群聚类算法，蚁群聚类算法中提出了拾起概率函数和放下概率函数，并使随机概率取值范围与概率函数取值相结合，加快了算法收敛速度；码书重排过程是将子码书按子码书特征值顺序排列构成分类码书；本装置由子码书特征值单元、子码书码字个数单元和分类码书单元构成。本发明构成的码书分类矢量量化器量化时通过子码书特征值和子码书码字个数信息，将码书分类矢量量化器码字搜索范围限定为分类码书的子码书，减小了矢量量化器码字的搜索范围，降低了矢量量化器的时间复杂度。

说明书

技术领域

本发明涉及一种语音信号处理及群智能算法技术，具体是一种采用优化蚁群聚类算法进行的码书分类方法及其码书分类装置。

背景技术

矢量量化技术在实际中的应用非常广泛，涉及到了数字图像和语音压缩编码、语音识别、情感识别、文献检索及数据库检索等领域。

矢量量化器主要由编码器和解码器组成，其中包含有相同或不同的码书。量化时输入矢量通常需要根据失真测度和矢量量化系统编码器码书中的所有码字进行失真计算，以找到失真最小的匹配码字，即采用的是穷尽搜索矢量量化的方法。穷尽搜索矢量量化器的主要优点是可以根据某一失真测度找到最匹配的码字，但其量化时的计算复杂度最大。因此提出了许多降低量化复杂度的策略，这些策略一方面从矢量量化器的构成来考虑，另一方面从码字搜索算法考虑。约束矢量量化器就是在穷尽搜索矢量量化器基础上附加各种约束条件以降低量化复杂度为目的而提出的，由此产生相应的一些编码算法和码书设计技术。一种能降低量化复杂度的方法是对量化器码书中的码字进行一些约束，使其码字不再具有任意分布，而是以一种受约束的方式分布，从而使最近邻搜索变得更容易。

作为一种约束矢量量化器，分类矢量量化器原理是根据量化参数的特性对输入矢量进行分类，然后在相应类的码书中搜索最近码字，各类码书的大小可以互不相同，合起来就构成量化器的总码书。由于这种量化器各子码书的尺寸都比较小，所以时间复杂度得到了降低。分类矢量量化器量化时会产生两个索引，一个是码书索引，一个是码字索引，其中码书索引用于确定输入矢量码字搜索过程需要在哪个码书中进行，码字索引是输入矢量在确定好的码书中搜索到最近邻码字的索引。分类矢量量化器码书的设计过程通常是先用分类器将输入训练矢量集合分为若干个子集，然后采用码书设计算法产生相应的码书，这些码书合起来就构成最终的总码书。影响分类矢量量化器性能的关键还在于在总码书大小一定的条件下如何确定各类码书的大小使得量化器的总体性能最佳。通常采用两种方法来确定各类码书大小，一种是比特分配算法，另一种是在总码书大小一定的情况下，认为各类码书的大小与训练子集的大小成正比。由于分类矢量量化器需要码书索引和码字索引，因此其量化比特数与分类器个数及各码书大小都有关。

现有蚁群算法是一种用来在图中寻找优化路径的概率搜索算法，由意大利学者MarcoDorigo等人于20世纪90年代初期提出，其灵感源于蚂蚁在寻找食物过程中发现路径的行为，是一种启发式仿生寻优算法，主要用于求解复杂的组合优化问题。迄今为止，蚁群算法已经成功地解决了许多实际问题，如旅行商问题、二次分配问题、Job-Shop调度问题及离散优化问题等。将蚁群算法用于聚类分析，灵感源于蚂蚁堆积他们的尸体和分类他们的幼体行为。由于现实的蚁群运动过程接近于实际的聚类问题，所以近年来涌现出大量的蚁群聚类算法。

基于蚁堆形成原理的聚类算法最早是Deneubourg等提出的，他们根据数据对象与其周围对象的相似性，让蚂蚁随机地移动、拾起或放下数据对象，以达到聚类数据的目的，这个基本模型已成功地应用于机器人等领域。Lumer等首先改进此算法，提出了LF算法，在用蚁群算法进行聚类分析方面取得了一定成效。

蚁群搬运物体的基本机制是：一只随机移动的无负载蚂蚁在遇到一个物体时，如果该物体与之所在位置周围物体的相似度越小，则“拾起”该物体的概率越大；反之，一只随机移动的有负载蚂蚁所背物体与其所在位置物体相似度越大，则“放下”该物体的概率越大。这种机制可以保证不破坏大堆的物体，并且能够聚集小堆的物体。

基于此，研究者提出了蚁群聚类算法的基本思路。其主要思想是将待聚类数据初始随机地散布在一个二维平面内，然后在该平面上产生一些虚拟蚂蚁对其进行聚类分析。首先将数据对象随机地投影到一个二维平面，然后每只蚂蚁随机选择一个数据对象，根据该对象在局部区域的相似性而得到的概率，决定蚂蚁是否“拾起”、“移动”或“放下”该对象。经过有限次迭代，平面上的数据对象按其相似性而聚集，最后得到聚类结果和聚类数目。

上述蚁群聚类算法影响算法收敛速度的主要因素有负载蚂蚁放下物体的速度以及无负载蚂蚁拾起物体的速度，而影响这两个速度的关键在于算法中的放下概率函数以及拾起概率函数与系统产生的随机概率之间的关系。由于现有蚁群聚类算法相似度函数取值变化时，放下概率函数和拾起概率函数随其取值改变所发生的变化不是很显著，使放下概率函数和拾起概率函数取值长时间不能大于系统产生的随机概率，导致有负载蚂蚁应该放下物体时不能立即放下物体，无负载蚂蚁应该拾起物体时不能立即拾起物体，使二维平面内的物体不能以较快的速度按其相似性形成聚类结果，从而直接影响了聚类算法的收敛速度和聚类结果。

发明内容

本发明的目的是提供一种基于蚁群聚类算法的码书分类方法及其码书分类装置，以解决穷尽搜索矢量量化器码书中码字的排列方式无序，码字搜索范围大，时间复杂度高的问题，

本发明为了解决上述问题所采取的技术方案如下：

一种基于蚁群聚类算法的码书分类方法，基于导抗谱频率参数，该方法包括：

码书分类过程：

用码书设计算法设计的码书，用基于蚁群聚类算法的码书分类方法分类为子码书，每个子码书用一个子码书特征值代表；

码书重排过程：

用码书分类方法分类的各子码书，按与子码书特征值相同的排列顺序组合在一起构成分类码书。

本发明上述技术方案中所述的蚁群聚类算法是采用下述相似度函数：

(1)式中：d(o_i，o_j)为数据o_i与数据o_j间的的欧式距离；d_MAX(o_i，o_j)为数据o_i所在聚类半径r内与o_i间的最大欧式距离，d_MAX(o_i，o_j)中的o_j为数据o_i所在聚类半径r内与o_i间具有最大欧式距离的数据；α为调节数据对象间相似性的参数，在(1)式中α＝4；

所述的蚁群聚类算法中的拾起概率函数和放下概率函数，其拾起概率函数表示如下：

式(2-4)中相似度f根据式(1)确定；b＝0.3，k₁＝11.11；

放下概率函数表示如下：

式(3-6)中相似度f根据式(1)确定；k₂＝11.11；

所述的蚁群聚类算法中的孤立点和非典型分类区的处理方法如下

其孤立点处理方法是用最近邻准则进行重新分类；

其非典型分类区处理方法是用最近邻准则与其它分类区进行合并；

所述的蚁群聚类算法的随机概率范围是根据式(2-4)和(3-6)计算值的统计结果确定。

本发明上述技术方案中所述的一种基于蚁群聚类算法的码书分类方法的码书分类装置，该装置包括子码书特征值单元、子码书码字个数单元和分类码书单元；

所述的子码书特征值单元是存储用码书分类方法得到的子码书特征值，用于对输入的待量化矢量进行码书分类时确定子码书的位置，子码书特征值单元位于码书分类矢量量化器装置编码器单元中；所述的子码书码字个数单元是存储用码书分类方法得到的各子码书包括的码字个数，用于对输入的待量化矢量进行码书分类时确定子码书的位置以及子码书的范围，子码书码字个数单元位于码书分类矢量量化器装置编码器单元中；所述的分类码书单元是存储由子码书按与子码书特征值单元内容相同的顺序排列得到的码书，位于码书分类矢量量化器装置编码器单元和解码器单元。

本发明上述技术方案中所述的码书分类矢量量化器是包含码书分类装置的矢量量化器；码书分类矢量量化器装置是由编码器单元和解码器单元构成；所述的码书分类矢量量化器装置的编码器单元包括码书分类装置和码书分类量化模块，码书分类量化模块用于对输入的待量化矢量在码书分类装置中确定对应的量化矢量，并将量化矢量的量化索引写入码流；所述的码书分类矢量量化器装置的解码器单元包括分类码书单元和解码模块，所述的解码模块用于接收通过码流传送到解码器单元的量化索引，并在分类码书单元中搜索对应量化索引值的输入待量化矢量的重构矢量。

本发明一种基于蚁群聚类算法的码书分类方法及其码书分类装置，码书分类方法采用蚁群聚类算法，与现有的蚁群聚类算法相比，本发明提出了新的拾起概率函数和放下概率函数，并使随机概率取值范围与拾起概率函数和放下概率函数取值结合起来，从而加快了算法的收敛速度，提高了聚类性能。

与现有采用LBG算法设计的码书相比，经过码书分类方法分类的码书，码书大小相同，码字相同，但码字的排列顺序发生了显著变化，具有相同子码书特征值的码字划分到一个子码书，各子码书按与子码书特征值相同的排列顺序组合在一起构成分类码书，存放在码书分类装置中。在量化时，基于码书分类方法及码书分类装置的码书分类矢量量化器量化复杂度为搜索码书分类信息时增加的复杂度加上在子码书中搜索量化矢量时的时间复杂度，因为子码书搜索范围加上码书分类信息搜索范围要低于分类码书的搜索范围，因此，该码书分类矢量量化器量化时的时间复杂度得到了大幅度的降低。

例如，对自适应多速率宽带语音AMR-WB编码算法ISF参数一级量化时，如果采用本发明所述的码书分类矢量量化器进行量化，以7维子矢量的量化为例，7维子矢量的码书大小为256，如果用优化蚁群聚类算法自动聚类后码书的分类信息数为14类，则本发明在编码器端增加的存储需求是28个浮点存储单元，但在分类码书中获取量化矢量所需的码书搜索范围却减小了很多，从而使量化复杂度得到了大幅降低。以其中一个聚类结果形成的各子码书包括的码字个数为例，其各子码书包括的码字个数分别为{39，35，13，16，15，11，7，8，52，17，15，13，7，8}。可见，各子码书所包含的码字个数是不相等的。各子码书所包含的码字个数决定了矢量量化时的时间复杂度，码字个数越少，码字搜索范围越小，量化时的时间复杂度越低。码书分类矢量量化器量化时，首先需要将输入的7维子矢量与各子码书特征值用欧式距离测度进行判断，以确定子码书及其位置，然后在子码书中进一步用穷尽搜索算法确定其量化值。量化器的时间复杂度如果用加(减)法、乘法和比较运算的次数度量，并用N表示码书大小，k表示量化矢量维数，则采用穷尽搜索矢量量化器需要的时间复杂度是3Nk-1，该3Nk-1计算方法为本领域技术人员公知的内容。分别采用穷尽搜索矢量量化器和码书分类矢量量化器量化时，时间复杂度对比如下：

采用穷尽搜索矢量量化器时时间复杂度：

3Nk-1＝3×256×7-1＝5375(次/输入矢量)

采用码书分类矢量量化器时最大时间复杂度：

3×14×7-1+3×52×7-1＝3×66×7-2＝1384(次/输入矢量)

采用码书分类矢量量化器时最小时间复杂度：

3×14×7-1+3×7×7-1＝3×21×7-2＝439(次/输入矢量)

采用码书分类矢量量化器时的时间复杂度至少降低为穷尽搜索的百分比如下：

1384/5375×100％＝25.75％

采用码书分类矢量量化器时的时间复杂度最多降低为穷尽搜索的百分比如下：

439/5375×100％＝8.17％。

与现有的分类矢量量化器相比，显著不同在于本发明设计的分类装置只需存放在编码器端，解码器端不需要存放。与码书分类装置相关的子码书特征值信息以及子码书码字个数信息也不需要传送到解码器端，因此，不占用量化比特，这样在量化比特相同的情况下，可以节省一部分比特数，使其用于编码算法的其它部分。在语音编码算法中，如果其余部分所用的比特数相同，则可使量化器的量化比特得到降低，从而使整个算法编码速率得到降低。

综上所述，本发明的一种基于蚁群聚类算法的码书分类方法及其码书分类装置，码书分类方法采用蚁群聚类算法，与现有技术相比，本发明提出了新的拾起概率函数和放下概率函数，并使随机概率取值范围与拾起概率函数和放下概率函数取值结合起来，从而加快了算法的收敛速度，提高了聚类性能。经过码书分类后的码书由子码书构成，子码书在分类码书中的排列顺序与子码书特征值排列顺序相同，子码书由具有相同子码书特征值的码字构成。矢量量化器量化时，通过子码书的特征值和子码书码字个数信息，将矢量量化器码字搜索范围限定到了分类码书的一个子码书，从而减小了矢量量化器码字搜索范围，降低了矢量量化器量化时的时间复杂度，且分类信息不需要在信道传送，因此量化比特没有增加，矢量量化器量化性能达到了透明量化的效果。

附图说明

图1是本发明实施例提供的基于蚁群聚类算法的码书分类方法原理框图；

图2是本发明实施例提供的拾起概率函数曲线变化规律比较图；

图3是本发明实施例提供的放下概率函数曲线变化规律比较图；

图4是本发明实施例提供的蚁群聚类算法原理框图；

图5是本发明实施例提供的码书分类装置结构示意图；

图6是本发明实施例提供的码书分类矢量量化器装置结构示意图；

图7是本发明实施例提供的包含码书分类装置的多级分裂矢量量化器装置结构示意图。

具体实施方式

下面对本发明的一种基于蚁群聚类算法的码书分类方法及其码书分类装置作出进一步的详细说明。

具体实施方式1

本发明基于蚁群聚类算法的码书分类方法用于码书分类的具体实施过程包括码书分类及码书重排两个过程。

图1示出了本发明实施例提供的基于优化蚁群聚类算法的码书分类方法原理框图，在用优化蚁群聚类算法对码书分类时，输入优化蚁群聚类算法的待聚类数据为预先设计的码书，设计码书的方法可以用LBG码书设计算法，LBG码书设计算法为本领域技术人员公知内容。

基于优化蚁群聚类算法的码书分类过程包括如下步骤：

步骤1.初始化参数。包括聚类最大循环次数N_MAX，蚂蚁背负物体最多移动次数门限N_1MAX，蚂蚁个数，二维平面，聚类半径等的初始值设定。

本发明设N_MAX＝20000，N_1MAX＝200，蚂蚁个数为1个，二维平面限定到(0～100，0～100)区域，聚类半径r取为3。

步骤2.将待聚类的数据对象随机映射到二维平面上，随机给每个数据对象赋予一个在初始二维平面区域的坐标，并生成一个分布在0-60％之间的随机概率p_r。

步骤3.将蚂蚁随机放置到限定区域范围的二维平面上，并设置蚂蚁初始状态为未负载。

步骤4.按下式(1)计算相似度参数f(o_i)；

(1)式中d(o_i，o_j)为映射到二维平面上的两个数据o_i与o_j间的欧式距离，d_MAX(o_i，o_j)为数据o_i所在聚类半径r内与o_i之间的最大欧式距离，o_j为数据o_i所在聚类半径r内与o_i间具有最大欧式距离的数据。α为调节数据对象间相似性的参数，其取值决定了聚类的数目和收敛的速度，α越大时，对象间相似程度越大，也许使不太相同的对象归为一类，其聚类数目越少，收敛速度也越快；反之，α越小，对象间相似程度越小，在极端情况下可能将一个大类分成了许多小类。同时聚类数目增多，收敛速度变慢；本发明根据多次实验结果最终取α＝4。

步骤5.如果蚂蚁的当前状态为未负载，则按拾起概率函数计算拾起概率，并判断拾起概率是否大于随机概率，如果大于则蚂蚁拾起它所在位置的物体，开始移动物体，否则蚂蚁随机移动到别的位置，再跳转到步骤4计算相似度参数。

现有的一个未负载的随机运动蚂蚁拾起一个对象的拾起概率函数有以下几种形式：

(1)LF/Deneubourg基本模型

$p_p={\left(\frac{k_1}{k_1+f}\right)}^2---(2-1)$

(2)Sigmoid函数

$p_p=\frac{1}{1+e^{k_{1}f}}---(2-2)$

(3)分段函数

p_p＝1-k₁f                                                    (2-3)

上面3个式子中的k₁为阈值常数，在使用时可以根据实际需要取值，且3个式子中k₁的取值一般不同。

本发明将拾起概率函数定义为下式(2-4)，其中参数f为根据式(1)确定的相似度；b、k₁为阈值常数，其值大小影响算法的收敛速度，且满足在相似度越小时拾起概率应该越大越好，随着相似度的逐渐增大，拾起概率则应该越来越小。多次实验发现，根据式(1)计算出的相似度系数一般分布在0≤f≤0.3的范围内，因此，本发明取b＝0.3，则k₁＝11.11。

图2给出了式(2-1)到(2-4)四个拾起概率函数随相似度f改变的变化规律曲线。可以看出，与前三个现有的拾起概率函数曲线比较，相似度分布在0≤f≤0.3范围时，本发明给出的拾起概率函数随f增大从概率100％逐渐减小，当f趋于0.3时，拾起概率已经趋于0，在f大于0.3以后，拾起概率都变为0。实验中发现，根据式(1)计算得到的f基本不会出现f＞0.3的情况，这就使拾起概率函数取值变化与式(1)相似度参数变化范围相结合，有利于蚂蚁以较快速度拾起与周围相异度较大的物体。

步骤6.如果蚂蚁的当前状态为负载状态，则按下述的放下概率函数计算物体放下概率，并判断放下概率是否大于随机概率，如果大于则蚂蚁放下物体，并置蚂蚁状态为未负载状态，转至步骤7；否则蚂蚁背负物体继续移动到新的数据位置，蚂蚁背负同一个物体移动次数加1，判断蚂蚁背负同一个物体移动次数是否大于门限N_1MAX，如果大于则蚂蚁背负同一个物体移动次数置0，蚂蚁放下物体，并置蚂蚁状态为未负载状态，转至步骤7，否则转至步骤4。

本发明通过设置蚂蚁背负同一个物体移动次数，并在该步骤判断蚂蚁背负同一个物体移动次数是否大于门限N_1MAX，可防止蚂蚁一直背负同一个物体找不到放下位置，程序进入无限循环，如果蚂蚁背负同一个物体移动次数超过门限值N_1MAX，则无论放下概率条件是否满足，也必须放下物体。

现有的一个负载的随机运动的蚂蚁放下一个对象的放下概率函数定义为以下几种形式：

(1)分段函数

$p_d=\left(\begin{array}{cc}{k}_{2}f& f<\frac{1}{k_2}\\ 0& f\le 0\\ 1& f=1\end{array}\right)---(3-1)$

(2)LF基本模型

(3)Sigmoid函数

$p_d=\frac{1}{1+e^{-k_{2}f}}---(3-3)$

(4)Deneubourg基本模型

$p_d={\left(\frac{f}{k_2+f}\right)}^2---(3-4)$

(5)LF改进模型

$p_d=\left(\begin{array}{cc}f& f<1.0\\ 1& f\ge 1\end{array}\right)---(3-5)$

其中参数f为根据式(1)确定的相似度；k₂为门限(阈值)常数，在使用时可以根据实际需要取值，且上述5个式子中k₂的取值一般不同。可以看出，式(3-1)、式(3-2)与式(3-5)都是按直线规律变化，只是直线斜率不一样，LF基本模型直线斜率为2，LF改进模型直线斜率为1，分段函数在时，直线斜率为k₂。下面进一步对比时，只与LF改进模型对比。

放下概率函数的变化规律应该是相似度越大，放下概率也越大；相似度越小，放下概率也越小。为此，本发明考虑用二次递增曲线来实现，并将放下概率函数定义为式(3-6)形式：

式(3-6)二次曲线的变化规律在相似度小时，可以满足拾起概率要求，随着相似度的增大，前面的系数k₂的取值直接影响概率变化，k₂太小，二次递增曲线随f增大增加太慢，k₂太大，二次递增曲线随f增大则增加太快，会很快趋于100％拾起概率。但由于式(1)相似度变化范围基本在0≤f≤0.3区间，因此应使f＞0.3时，p_d＝100％，这样k₂＝11.11。

图3给出了式(3-3)到(3-5)现有的几种放下概率函数与本发明新提出的式(3-6)放下概率函数随相似度的变化曲线。可以看出，在0≤f≤0.3时，随f增大，式(3-6)放下概率函数增大最快，在f＞0.3时，式(3-6)放下概率变为100％，其它几种典型曲线在f＞0.3时依然缓慢变化，实验结果表明根据式(1)计算得到的f基本不会出现f＞0.3的情况，这样在f接近0.3时，如果放下概率太小，则不利于蚂蚁快速放下物体。因此，式(3-6)放下概率函数变化规律可提高蚂蚁放下背负物体的速度，这有利于提高算法的运行效率，避免蚂蚁长时间背负物体放不下。

步骤7.赋给蚂蚁新的数据位置，再次生成一个0-60％之间的随机概率p_r，循环次数加1，如果循环次数大于最大循环次数N_MAX，结束聚类循环，转至步骤8，否则转至步骤4；

所述的0-60％之间的随机概率p_r是根据蚁群聚类算法的随机概率范围确定的，蚁群聚类算法的随机概率范围是根据式(2-4)和式(3-6)的计算值统计结果确定。

其计算值统计方法是将式(2-4)和式(3-6)的计算结果进行统计，统计所得结果表明p_d和p_p取值分布在0-0.6范围内，未出现大于0.6的情况。如果随机概率p_r取值仍在现有0-100％之间，则使放下概率函数和拾起概率函数取值长时间不能大于系统产生的随机概率，导致有负载蚂蚁应该放下物体时不能立即放下物体，无负载蚂蚁应该拾起物体时不能立即拾起物体，使二维平面内的物体不能以较快的速度按其相似性形成聚类结果，从而影响了算法的收敛速度和聚类结果。

步骤8.将聚类结果按聚类半径划分子空间。划分过程中，针对一个输入矢量同时属于多个子空间的情况，进一步增加欧式距离判据来决定最终分类结果。聚类时所出现的未分类孤立点，采用最近邻准则进行处理，即根据欧式距离判据判断与该孤立点距离最近的输入矢量，并将该孤立点和距离最近的输入矢量划分为一类，如果距离最近的输入矢量也是孤立点，则新建一个包括这两个孤立点的类别。

所述的孤立点是指聚类结束后所出现的不属于任何子空间的输入矢量，也叫野点。

图4所述，优化蚁群聚类算法运行结束，码书分类过程结束，接着进行码书重排过程，码书重排过程包括以下步骤

步骤(1)计算每个非空子空间的输入矢量个数，并求解出每个子空间的质心；所述非空子空间是指该子空间至少有一个输入矢量。

步骤(2)对非典型分类区用最近邻准则与其它分类区进行合并，即对输入矢量个数小于某个特定值的子空间，采用最近邻准则进行处理。该特定值是根据输入矢量的个数确定，如本发明输入矢量的个数是256，其非典型分类区的输入矢量个数是5。

所述非典型分类区是指输入矢量个数小于某个特定值的子空间。

所述采用最近邻准则进行处理是按欧式距离找到与其质心距离最小的子空间后，将两个子空间输入矢量合并为一类；本步骤是为了防止一些输入矢量个数小于某个特定值的子空间形成非典型质心，因此，将输入矢量个数小于某个特定值的子空间与其它子空间进行合并。

所述其它分类区是指非典型分类区以外的非空子空间。

步骤(3)重新计算每个非空子空间的输入矢量个数，并求解出每个子空间的质心。

步骤(4)将输入矢量按其所属的子空间存放在一起形成一个子码书，子码书的特征值用对应子空间的质心表示。

步骤(5)将各子码书按与子码书的特征值相同的顺序排列起来形成分类码书。

上述步骤1到8，以及步骤(1)到(5)一并构成本发明实施例提供的基于蚁群聚类算法的码书分类方法的完整过程，其中，步骤1到步骤8也可以作为本发明实施例提供的基于蚁群聚类算法的码书分类过程的实施方式，步骤(1)到步骤(5)也可以作为本发明实施例提供的基于蚁群聚类算法的码书重排过程的实施方式。

具体实施方式2

现在对本发明实施例提供的一种基于蚁群聚类算法的码书分类方法的码书分类装置进行详细说明如下：

图5示出了本发明实施例提供的基于蚁群聚类算法的码书分类方法的码书分类装置结构示意图，该装置包括子码书特征值单元、子码书码字个数单元和分类码书单元。

其中子码书特征值单元存储的子码书特征值，用于对输入的待量化矢量进行码书分类时确定子码书的位置；该子码书特征值位置与子码书码字个数单元存储的各子码书包括的码字个数共同确定输入待量化矢量对应的子码书在分类码书单元的入口地址；该入口地址与确定的子码书特征值位置对应的子码书码字个数共同确定输入待量化矢量对应的子码书在分类码书单元的出口地址。

子码书码字个数单元是存储用码书分类方法得到的各子码书包括的码字个数，位于码书分类矢量量化器装置的编码器单元中，用于对输入的待量化矢量进行码书分类时确定子码书的位置以及子码书的范围；

分类码书单元是存储由子码书按与子码书特征值单元内容相同的顺序排列得到的码书，位于码书分类矢量量化器装置编码器单元和解码器单元，用于给码书分类矢量量化器中的码书分类量化模块提供分类码书。

图5装置中的各个部件涉及到的计算，均可以使用本发明实施例中的基于蚁群聚类算法的码书分类方法中所提供的公式和计算方法，可以作为本发明实施例提供的基于蚁群聚类算法的码书分类方法的码书分类装置的一种实施方式，

具体实施方式3

图6示出了本发明实施例提供的基于蚁群聚类算法的码书分类矢量量化器装置结构示意图，该装置包括编码器单元和解码器单元，其中编码器单元包括：码书分类装置和码书分类量化模块，解码器单元包括分类重排码书单元和解码模块。

编码器单元依次对输入待量化矢量进行矢量量化，量化时，各部件功能如下：

码书分类装置，用于矢量量化时确定对应子码书范围，子码书范围确定后，输入待量化矢量对应的子码书搜索范围确定。子码书搜索范围确定方法为：输入待量化矢量对应的子码书入口地址与出口地址之间的码字。

码书分类量化模块，首先在码书分类装置中确定与输入待量化矢量对应的子码书范围，子码书范围确定后再进一步在子码书中确定与输入待量化矢量距离最小的码字，该码字就是输入待量化矢量在编码器单元的量化矢量，该码字在分类码书单元中的位置就是输入待量化矢量的量化索引，之后进一步将量化索引写入编码器提供的码流中。

解码器单元用于根据信道传送到解码器端的码流获得输入待量化矢量的重构矢量。解码器单元中的各个组成部分如下：

分类重排码书单元，用于存储分类码书，为解码器解码时提供查询。

解码模块，根据信道传送到解码器端的码流解析出量化索引，在分类码书单元中根据量化索引查询输入待量化矢量的重构矢量。

图6装置中的各个部件涉及到的计算，均可以使用本发明实施例中的基于蚁群聚类算法的码书分类方法中所提供的公式和计算方法，可以作为本发明实施例提供的基于蚁群聚类算法的码书分类矢量量化器装置的一种实施方式。

实施例1

本实施例中采用的量化参数为自适应多速率宽带AMR-WB语音编码器使用的16维导抗谱频率ISF，采用的量化方法是两级分裂矢量量化器，本例中的两级分裂矢量量化器一级量化时采用基于蚁群聚类算法的码书分类矢量量化器，第二级分裂矢量量化时仍采用穷尽搜索矢量量化器，称为包含码书分类装置的两级分裂矢量量化器，该量化器量化前需要预先进行以下叙述的第一步和第二步，该量化器量化过程包含以下叙述的第三步和第四步。下面进一步详细说明：

第一步：码书设计过程。

码书设计采用LBG算法。LBG码书设计算法为本领域技术人员公知的内容。对AMR-WB宽带语音编码算法16维量化参数ISF，在编码模式1到8时，第一级分裂矢量量化时所用的9维子矢量码书大小和7维子矢量码书大小都为256，第二级分裂矢量量化时，首先将9维子矢量分裂为3个维子矢量，7维子矢量分裂为3维和4维子矢量，5个子矢量码书大小分别是64，128，128，32，32。

第二步：码书分类重排过程。

可以看出，第一级分裂矢量量化时所用的9维子矢量码书和7维子矢量码书都比第二级分裂矢量量化时5个子矢量码书大小要大，因此，只对第一级分裂矢量量化采用码书分类矢量量化器实现，第二级分裂矢量量化时对5个子矢量码书仍采用穷尽搜索算法，这样只需对9维子矢量码书和7维子矢量码书进行码书分类重排过程处理，具体包括以下步骤

(1)用蚁群聚类算法进行码书分类。第一步设计的9维子矢量码书，是蚁群聚类算法的输入矢量。蚁群聚类算法运行结束，9维子矢量码书中具有相同子码书质心的码字排列在一起形成了9维子码书，9维子码书的质心就是对应9维子码书的特征值。类似，7维子矢量码书，再作为蚁群聚类算法的输入矢量，运行蚁群聚类算法，算法运行结束时，7维子矢量码书中具有相同子码书质心的码字排列在一起形成了7维子码书，7维子码书的质心就是对应7维子码书的特征值。

(2)码书重排的过程。将形成的9维子矢量的子码书按与对应的9维子码书特征值相同的顺序排列起来，构成最终的9维分类码书，将形成的各9维子码书包括的码字个数按与对应的9维子码书特征值相同的顺序排列起来。类似，将形成的7维子矢量的子码书按与对应的7维子码书特征值相同的顺序排列起来，构成最终的7维分类码书，将各7维子码书包括的码字个数按与对应的7维子码书特征值相同的顺序排列起来。

(3)分类信息及重排码书的存储过程。

将构成的9维分类码书存放于9维分类码书单元，各9维子码书包括的码字个数存放在9维子码书码字个数单元，各9维子码书的特征值则存放在9维子码书特征值单元；具体实施时，以上3个单元中的内容必须一一对应。

类似，7维分类码书、7维子码书包括的码字个数以及7维子码书特征值则分别存放在7维分类码书单元、7维子码书码字个数单元以及7维子码书特征值单元，3个单元中的内容也必须一一对应。

上述的存储单元都位于AMR-WB宽带语音编码算法中的包含码书分类装置的两级分裂矢量量化器装置中相应部分。

第三步：输入待量化矢量的编码过程。

编码时，首先将16维输入待量化矢量减去矢量均值，得到输入待量化残差矢量，其中矢量均值预先训练得到；再将16维输入待量化残差矢量分裂为9维子矢量和7维子矢量，对9维子矢量，码书分类装置1提供码书分类信息给码书分类量化模块1，码书分类量化模块1根据提供的信息利用欧式距离测度在分类码书单元1的子码书中确定9维子矢量的量化矢量，及该量化矢量在分类码书1中的量化索引I₁₁。

对7维子矢量，码书分类装置2提供码书分类信息给码书分类量化模块2，码书分类量化模块2根据提供的信息利用欧式距离测度在分类码书单元2的子码书中确定7维子矢量的量化矢量，及该量化矢量在分类码书2中的量化索引I₁₂。

第二级量化时，首先将9维子矢量减去9维子矢量的量化矢量，得到9维子矢量的残差矢量，分裂矢量量化编码模块1进一步将9维子矢量分裂为3个3维子矢量，3个3维子矢量分别利用欧式距离测度在二级码书1、二级码书2以及二级码书3中采用穷尽搜索算法确定3个3维子矢量的量化矢量及量化索引I₂₁、I₂₂及I₂₃。

类似，对7维子矢量，也是首先将7维子矢量减去7维子矢量的量化矢量，得到7维子矢量的残差矢量，分裂矢量量化编码模块2接着将7维子矢量分裂为1个3维子矢量和1个4维子矢量，3维子矢量和4维子矢量进一步分别利用欧式距离测度在二级码书4和二级码书5中采用穷尽搜索算法确定2个子矢量的量化矢量及量化索引I₂₄及I₂₅。

编码结束，将量化索引I₁₁、I₁₂、I₂₁、I₂₂、I₂₃、I₂₄及I₂₅写入码流。

第四步：输入待量化矢量的解码过程。

解码时，分裂矢量量化解码模块根据信道传送到解码器单元的码流，解析出所有的量化索引，并在分类码书1、分类码书2、二级码书1、二级码书2、二级码书3、二级码书4和二级码书5中分别查询对应子矢量的量化矢量，再将16维ISF参数各维分量一级量化矢量、二级量化矢量和均值矢量相加，得到输入待量化矢量的重构矢量。

图7示出了包含码书分类装置的两级分裂矢量量化器装置结构示意图，该装置包括编码器单元和解码器单元，其中编码器单元包括：均值矢量单元、3个加法器、码书分类装置1、码书分类装置2、码书分类量化模块1、码书分类量化模块2、分裂矢量量化编码模块1、分裂矢量量化编码模块2和二级码书单元。解码器单元包括均值矢量单元、二级码书单元、分类码书单元和分裂矢量量化解码模块。该装置中的各个部件涉及到的计算，均可以使用本发明实施例中的码书分类方法及量化过程中所提供的公式和计算方法，作为本发明实施例包含码书分类装置的两级分裂矢量量化器装置的一种实施方式。

编码器单元依次对输入待量化矢量进行矢量量化，编码器单元中各个组成部分说明如下：

均值矢量单元，用于存储16维导抗谱频率ISF各维分量的均值，需要预先训练得到，为本领域技术人员公知的内容。

加法器1，用于将输入待量化矢量各维分量与均值矢量单元中各维分量的均值相减，并将相减得到的第1维分量到第9维分量形成的残差子矢量1提供给码书分类装置1，将相减得到的第10维分量到第16维分量形成的残差子矢量2提供给码书分类装置2。

加法器2，用于将残差子矢量1与码书分类量化模块1量化得到的残差子矢量1的量化值相减，得到残差子矢量1的量化残差，并提供给分裂矢量量化编码模块1。

加法器3，用于将残差子矢量2与码书分类量化模块2量化得到的残差子矢量2的量化值相减，得到残差子矢量2的量化残差，并提供给分裂矢量量化编码模块2。

码书分类装置1，包括子码书特征值单元1、子码书码字个数单元1和分类码书单元1，各单元功能为：子码书特征值单元1用于提供9维子矢量的子码书特征值；子码书码字个数单元1用于提供9维子矢量各子码书包括的码字个数；分类码书单元1用于提供由9维子矢量各子码书构成的分类码书。以上3个单元内容共同确定对残差子矢量1量化时在分类码书1的子码书搜索范围。

码书分类装置2，包括子码书特征值单元2、子码书码字个数单元2和分类码书单元2，各单元功能为：子码书特征值单元2用于提供7维子矢量的子码书特征值；子码书码字个数单元2用于提供7维子矢量各子码书包括的码字个数；分类码书单元2用于提供由7维子矢量各子码书构成的分类码书。以上3个单元内容共同确定对残差子矢量2量化时在分类码书2的子码书搜索范围。

码书分类量化模块1，用于根据码书分类装置1提供的残差子矢量1在分类码书1的子码书搜索范围，确定残差子矢量1的量化矢量和量化索引I₁₁，并将量化索引写入码流，将量化矢量提供给加法器2。

码书分类量化模块2，用于根据码书分类装置2提供的残差子矢量2在分类码书2的子码书搜索范围，确定残差子矢量2的量化矢量和量化索引I₁₂，并将量化索引写入码流，将量化矢量提供给加法器3。

分裂矢量量化编码模块1，用于根据加法器2提供的残差子矢量1的量化残差，采用分裂矢量量化方法从二级码书单元前3个二级码书中用穷尽搜索量化方法确定3个量化矢量和量化索引I₂₁、I₂₂及I₂₃，并将量化索引写入码流。

分裂矢量量化编码模块2，用于根据加法器3提供的残差子矢量2的量化残差，采用分裂矢量量化方法从二级码书单元后2个二级码书中用穷尽搜索量化方法确定2个量化矢量和量化索引I₂₄和I₂₅，并将量化索引写入码流。

分裂矢量量化编码模块1和分裂矢量量化编码模块2所述的分裂矢量量化方法为本领域技术人员公知的内容。

二级码书单元，存储五个二级码书即二级码书1到二级码书5，为分裂矢量量化编码模块1和分裂矢量量化编码模块2提供量化时使用的码书。五个二级码书的具体训练方法采用LBG码书设计算法，为本领域技术人员公知的内容。

解码器单元依次根据信道传送到解码器端的码流解码得到输入待量化矢量的重构矢量，解码器单元中的各个组成部分说明如下：

均值矢量单元，用于存储16维导抗谱频率ISF各维分量的均值，与编码器单元中均值矢量单元中内容相同，提供给分裂矢量量化解码模块。

二级码书单元，存储五个二级码书即二级码书1到二级码书5，与编码器单元中五个二级码书内容相同，为分裂矢量量化解码模块提供查询。

分类码书单元，用于存储分类码书1和分类码书2，为分裂矢量量化解码模块提供查询。

分裂矢量量化解码模块，用于根据信道传送到解码器端的码流，解析出量化索引值，在二级码书单元各码书中查询残差子矢量1和残差子矢量2量化残差的量化值，在分类码书单元各码书中查询残差子矢量1和残差子矢量2的量化值，并将残差子矢量1量化残差的量化值与残差子矢量1的量化值相加，再与均值矢量单元前9维各维分量的均值求和，将残差子矢量2量化残差的量化值与残差子矢量2的量化值相加，再与均值矢量单元后7维各维分量的均值求和，前9维求和结果和后7维求和结果合并在一起，得到16维输入待量化矢量的重构矢量。

将包含码书分类装置的两级分裂矢量量化器装置用于AMR-WB算法，通过如下实验结果，说明本发明实施例提供的码书分类方法及其码书分类装置取得的效果：

目前，谱失真参数是评价量化器量化性能的一种客观评价标准。在语音编码算法中，要使编码语音中不引入任何附加的可感觉到的失真，一般要求矢量量化器量化谱失真需能达到透明量化的质量指标要求，即：平均谱失真约为1dB；平均谱失真大于4dB帧的百分比趋于0；平均谱失真在2～4dB范围帧的百分比为2％左右；没有平均谱失真超过4dB的语音帧。下表1给出了包含码书分类装置的两级分裂矢量量化器量化时的谱失真值，其中码书分类方法采用的是本发明所述的优化蚁群聚类算法，9维子矢量码书和7维子矢量码书的码书分类数都分别有4、6、12和14共4类。可以看出，采用本发明的码书分类装置后，两级分裂矢量量化器量化谱失真达到了透明量化的效果。

表2给出了AMR-WB算法重建语音w-PESQ值。表中S-MSVQ表示采用的是多级分裂矢量量化方法，为两级分裂，其所在列数据表示AMR-WB算法对ISF参数量化采用S-MSVQ量化方法时，重建语音的w-PESQ值；码书分类数所在列数据表示AMR-WB算法对ISF参数量化时采用的是包含码书分类装置的多级分裂矢量量化器，其重建语音的w-PESQ值，其中4/4中第一个4表示9维子矢量码书分为了4个子码书，第二个4表示7维子矢量码书也分为了4个子码书，6/6、12/12和14/14代表意义相同；与S-MSVQ差值所在列数据表示采用包含码书分类装置的多级分裂矢量量化器重建语音w-PESQ值与S-MSVQ重建语音w-PESQ值的差值。

可以看出，与采用S-MSVQ量化方法相比，码书分类数为4类和6类时，包含码书分类装置的两级分裂矢量量化器9种模式平均重建语音w-PESQ值稍有提高，码书分类数为12和14类时，9种模式平均重建语音w-PESQ值稍有下降，但下降和提高的幅度并不多，主观听觉感受基本感觉不到与原算法解码语音质量的差异。其中编码模式为2、分类数为6时，w-PESQ值提高的最多，为0.037；编码模式为0、分类数为14类时，w-PESQ值下降的最多，为-0.134。由此可知，码书分类装置的分类数也不能太多，否则会造成重建语音质量的显著下降。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，以用于帮助理解本发明的方法及其思想；但以上所述仅为本发明的具体实施例而已，并不用于限定本发明的保护范围，对于本领域的一般技术人员，依据本发明的思想，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围内。

表1

表2