基于矢量量化编码的数据压缩算法的研究分析

图3.1 所示是EENNS算法搜索范围的二维示意图，图中以中心线L为轴心的超圆柱面分别是方差为Vmin和Vmax的等方差超圆柱面，与中心线L垂直的超平面分别是均值为Mmax和Mmin的等均值超圆柱面。等均值等方差最近邻搜索算法将码字的搜索范围限制在超圆柱面V1, V2和超平面Ll，L2所夹的范围内，即图中的阴影区域。EENNS算法减少了码字搜索范围，从而可以提高码字搜索速度。EENNS算法具体步骤如下：
(A)预处理：计算并存储码书C中的均值和方差，按均值的大小对码书进行排序。
(B)在线处理：
Step l：计算输入矢量x的均值Mx和方差Vx，在已排序码书中找到均值与Mx 最 接近的码字 作为输入矢量X的初始匹配码字。计算当前最小失真 d min = d (x ,yp )。使集合
Step 2：如果集合G为空，转Step 7；
Step 3：往返搜索法搜索初始匹配码字yp两侧的码字yj；
Step 4：如果码字满足 或者 ，则执行
下列步骤的(a)或者(b)。否则，转步骤5；
(C)如果Myj> Mx，则从集合G中删除所有码字yi，ij，转Step2。
(D)否则，则从集合G中删除所有码字yi i>j，转Step2。
Step 5：判断码字Yi的方差是否满足 或者 如果 满足， 则从删除集合G中删除码字Yi，否则，转Step6；
Step 6：用部分失真排除算法搜索码字Yi，如果d(x, Yi)dmin,. 则更新 p = J，从集合G中删除码字Yi转Step 2；
Step7：确定输入矢量x的最匹配码字为Yp。
3．3 码字索引分配算法
3．3．1 BSA算法
BSA算法是在1990年提出基于二元对称信道模型的码字索引分配算法。该算法对于任何索引映射函数 ，选择码字y，作为输入矢量x的最近码字后将产生索引 的传输，该过程与首先将码书中的码字进行位置交换等价，即对每一索i，码字y最终移动到码书中索引为 的位置。
基于这个事实，很自然地想到一种最简单的码字索引分配方法：首先在给定码书基础上随机产生一个初始码字排列，然后将所有码字的排列位置以特定方式进行交换，使信道失真不断减少。因此，这种算法的输入是一个码书，输出仍是一个码书，只不过码字存放在不同的位置。这带来一个附加优点:除了存储码书所需的空间以外，不需要任何额外信息来详细描述索引映射函数n，从而不需要信道编码和信道解码。
BSA算法的主要思想是通过不断交换码字的位置，使得信道噪声失真的目标函数场获得局部最优值.随着交换的进行 不断下降，而且索引映射函数 也跟着不断变化。在每次迭代中，码字的交换对是按一定的顺序选择的。所有的码字y，都对应一个函数 ，用来描述当该码字的索引(在当前码书中)在噪声信道中传输时可能产生的失真，其定义为公式（3.21）：
（3.21）
BSA算法每次按 从大到小的顺序对码字进行排序。拥有最大函数值 的码字被选为首先交换的候选对象。首先进行试验性的交换， 与其他每一个码字分别进行交换，并计算每次交换后 的下降值。选择能使 出现最大下降的那一个码字与 进行真正地交换，然后进入下一次迭代。如果不存在这样的码字，则对yi作相同的交换试验。如果每一个码字按这种方法与其他码字进行交换后。不再下降，则终止算法，从而获得一个局部最优的码字索引分配方案。算法的具体步骤如下：
Step 1：初始化。随机打乱码字的排序；
Step 2：整理排序。根据 从大到小的顺序对码字yi进行排序。令n=－1；
Step 3：试验性交换。令n＝n＋1从j＝n＋1到N一1，分别计算索引n和索弓!j交换后所能引起的失真减少量，比较这些失真减少量，获得最大的失真下降量 ；
Step 4：如果 >0，则交换索引n和引起最大失真下降的索引j，并转Step 2；
Step 5：终止算法。如果n=N一1，则终止算法，否则，转Step 3。
可以看出，BSA算法根据函数值 将码字进行排列而选择出哪一个码字最先进行交换，从而在运算上给出了一个方向性引导。如果由于程序运行时间的限制而使算法的迭代次数有限，则这种方向性引导将显得尤为重要。每一次成功交换的完成，代表一次迭代的结束。若一次迭代中的所有试验性交换产生的失真下降都不大于O，则说明算法已经达到一个局部最优解.应该指出的是:从不同的初始码字排序出发，可获得不同的局部最优解，从而保证BSA算法对于码字交换的限制不会影响它获得全局最优码字索引分配方案的可能性。实验证明，该算法获得的码字索引分配方案的失真比随机码字索引分配方案的失真有较大改进。
3．3．2 禁止搜索码字索引算法
禁止搜索的基本思想是通过一系列移动来搜寻所有可行解的搜索空间，并且在当前迭代中禁止某些搜索方向以避免死循环和跳入局部极小。由当前解到其邻域解的移动被部分地或完全地记录在禁止表中，目的是为了禁止以后迭代中的重复操作。
令 为测试解的集合，其中元素si可以被表示为式（3.22）：
（3.22）
其中，N为码书的尺寸，Si(j)表示在解si中分配给码字Yj的索引， 令 和 分别表示当前解和最优解。中码字Yj的索引，Sb(j)仍表示分配给解Sb中码字Yi的索引。
令 ， 和 分别代表测试解组的目标函数值集合，当前解的目标函数值和最优解的目标函数值，其中 是测试解 的目标函数值，0iNs-1。初始的当前解是随机产生的，通过随机交换当前解中的两个索引来产生测试解。禁止表中只存储交换的索引。如果从当前解中产生测试解的交换索引与禁止表中任何记录相同，则称该测试解为禁止解。该算法的具体步骤如下:
Step 1：设置禁止表大小Ts测试解个数N，以及迭代次数Im。令迭代计数器i=1，禁止表插入点t=1。随机产生当前解 ，计算其相应的目标函数值V}。令Sb=Sc以及Vb=Vc
Step 2：把当前解Sc拷贝给每一个测试解si, 0iNs-1。对每一个测试解si，0i Ns-1，产生两个随机整数r1和r2， ， ， 。N为码字个数，然后通过交换索引 和 产生新测试解组。计算测试解的函数值 。
Step 3：如果最优测试解的目标函数值比最优解的目标函数值Vb还小，则把它作为新的当前解，并令其目标函数值作为当前解的目标函数值Vc，转Step 3。否则，选出测试解中最好的非禁止解。如果能选到，则把它作为新的当前解Sc并令其目标函数值作为当前解的目标函数值Vc，转Step 3；否则，转Step 1。
Step 4： 如果vb>vc，令Sb=Sc，Vb＝Vc，把从旧当前解到新当前解所交换过的索引插入禁止表中。禁止表的插入点设为ti=ti+1;如果ti>Ts，令ti＝l，如果iIm，令i=i+1转Step 1；否则，算法结束。