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

2. 质心条件 (CentroidC ondition)
利用由上面步骤得到的训练矢量划分集 重新计算它们各自的质心，得到新的码本：
（3.3）
（3.4）
式中， 代表子集Si中训练矢量的个数。
各种矢量量化码本设计算法基本都是上面两个步骤的交替迭代的基础上得到最后的码本。不难看出，码本生成过程中的计算量是随着码本矢量的维数k和码本尺寸N的增大而急剧增长的，对于需要高维大码本的矢量量化器来说，测试所有可能的码本来寻求全局最优码本将是十分困难的。为了克服这个困难，Linde . Buzo和Gray提出了经典的LBG算法。
1980年Linde，Buzo和Gray将Lloyd算法推广到矢量空间【8】， 算法的步骤简单描述如下：
Step 1 ：给定初始码本 ，令迭代次数m=0，平均失真初始值为 ，给定失真下降阈值 ；
Step 2：用码本 中的码字作为质心，根据最佳划分原则将训练矢量集x划分为对应于每个码字的N个聚类，
满足： ；
Step 3：计算本次迭代的平均失真 判断相对误差是否满足 ，若满足，则停止算法，码本C(m)就是所求的码本;
否则，转Step 4；
Step 4：根据质心条件，计算各聚类的质心，即公式（3.5）：
（3.5）
产生新码本 并置m=m+1，转Step 2
END：算法结束。

对于 LBG算法来说，初始码本选择的好坏将直接影响到后面的迭代计算结果，一个不好的初始码本会降低算法的收敛速度和最终码本的性能。因此在LBG算法中要对初始码本的选择作一定的处理。如果初始码本随机产生，即直接从训练序列中随机选择N个训练矢量作为初始码字，构成初始码本，可能会选到一些非典型的训练矢量作码字，因而该胞腔可能含有少数几个矢量甚至只有1个。另外，有可能把某些空间分得过疏。这可能会导致码本中的有些码字得不到充分利用，设计出来的码本性能就可能较差。
3．1．2 MD算法
最大下降（MD）【13】码本设计算法与经典的LBG算法不同，它是一种分裂算法，而没有初始码本。在MD算法中，首先将训练矢量集 作为一个原始包腔，然后该包腔被它的最优分割超平面分成两个子包腔。依此类推，每次分裂产生一个包腔，直到生成最后的N个包腔，计算它们的质心，就可以得到设计的码本C={y}i=1,2,…,N)。与LBG算法相比，MD算法的计算量少并且所产生的码本性能好。另一方面，MD算法倾向于分割元素较多的胞腔，而不会去分割只有一个元素的胞腔，避免了非典型码字的形成，提高了码本的整体性能。在MD算法中，从L个包腔向(L+ l )个包腔扩展时，先要找出每个现有包腔的最优分割超平面，并计算它们各自带来的失真下降幅度，然后依据失真下降最大准则来选择究竟对哪一个包腔进行分裂。这在k维空间里是比较困难的事，需要大量的计算和比较。图3.2所示为MD算法的分裂过程示意图，图中每一步骤中有阴影的包腔 是当前符合失真下降最大准则的包腔，它被最优分割超平面分成下面的两个子包腔 和 。从L个包腔生成(L+ 1)个包腔的具体实现描述如下：
设超平面 将某胞腔 分成两个非空胞腔如式（3.6）所示：

（3.6）
式中 ， ， ， T表示转置。
当 中的矢量被质心 量化时，胞腔的失真D(Si)定义为公式（3.7）： （3.7）
则由分割超平面H,划分胞腔S,所引起的失真下降可表示为式（3.8）：
（3.8）
若采用平方误差测度，则式(3.8)可以化简为式（3.9）：
或 （3.9）
式中， 分别为 的元素个数， 。分别为 的质心。
从式(3.9)中可以看出，若胞腔 、 非空，则失真下降函数满足 。
我们将胞腔Si的最优分割超平面 定义为使胞腔 具有最大失真下降 的超平面。MD算法先计算出所有胞腔的最大失真下降值 ， ，然后找出最大的最大失真下降值 ，即 ，最后将胞腔Sp分割成两个新胞腔。所以，L+l个胞腔是通过划分L个胞腔中具有最大失真下降的胞腔并保持其余胞腔不变而得到的。值得注意的是，每次分裂包腔时，并不需要重新计算所有包腔的失真函数，而只需找到新增加的两个包腔的最优分割超平面，计算它们各自的失真函数，再与其它包腔的失真函数值进行比较即可找出新的满足失真下降最大准则的包腔。产生最后的N个胞腔，一共需计算(2N-3)次最大失真下降函数。
3．1．3 码书设计算法比较
LBG算法是一种迭代算法，其迭代操作是标量量化劳埃德迭代操作的直接推广。LBG算法他具有如下的优点：
1. 不用初始化计算，可大大减少计算时间
2. 初始码字选自训练序列，无空胞腔问题
LBG算法在具有如上的优点的同时也有一些缺点和不足:
1. 在每次迭代的最佳划分阶段，从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计算；
2. 初始码书的选择影响码书训练的收敛速度和最终码书的性能；
码书设计的第一个缺点可采用各种快速码字搜索算法来解决，但这些算法无法改善码书的性能，第2个缺点产生的原因是:LBG算法是一种下降算法，每次迭代总能减少(至少保持不变)平均失真，而且每次迭代通常只能产生码书的局部变化，即每次迭代后，与旧码书相比，新码书不可能有非常大的变化。因此，一旦选定初始码书，该算法只能得到局部最优的码书，即LBG算法一般不能得到全局最优的码书。
与LBG算法相比，MD算法的计算量少且所产生的码书性能好。另一方面， MD算法倾向于分割元素较多的胞腔，而不会去分割只有一个元素的胞腔，而这种情况在LBG算法中却常常出现。然而，在MD算法中，多维胞腔的最优分割超平面的搜索是一个非常困难的问题。为减少计算量，这些算法的搜索范围被限制在与矢量空间的基本矢量正交的超平面上，这个矢量空间可由离散余弦变换(DCT)得到。但是，在这种限制条件下，算法常常搜索不到最优超平面。
3．2 码字搜索算法
3．2．1 基于不等式的快速码字搜索算法
1. 部分失真不等式排除法
部分失真搜索(Partial Distortion Search，PDS)算法【12】是一种较简单有效的最近邻搜索算法。它的基本思想是：在计算某个码字与输入矢量之间失真测度的过程中，始终判断累加的部分失真是否已经超过目前的最小失真，如果一旦超出则终止该码字与输入矢量之间的失真计算，转而开始计算另一个码字与输入矢量的失真测度。PDS常被用来与其他快速搜索算法结合起来运用，来排除其它快速算法最后无法排除的码字。
在编码过程中计算前面部分维数的失真距离，若其超出当前最小距离，则排除此码字为最匹配码字，否则继续搜索其它码字。
据如下（3.10）所示的柯西一许瓦尔兹不等式【14】：
（3.10）
可得一个不等式判据 若 ，则能保证 ，yi可被排除。因为|yi|可离线计算，所以节省了计算量。
首先判断 是否成立，若成立，则排除码字Yi否则，再判断是否满足 ，若满足，yi也可被排除。这缩小了搜索范围，他们还融入部分距离失真法节省计算量。双测试法的缺陷在于要求矢量的所有分量都为正值，而图像变换域编码中产生的变换系数有正有负，必须对这些系数进行正补偿，使所有矢量分量均大于零。
2. 整数投影法
整数投影法是一种适用于图像矢量量化的快速码字搜索算法。他们为每个m×m图像块 ，定义三种整数投影【14】，如下公式（3.11）（3.12）（3.13）所示：
块状投影： （3.11）
垂直投影： （3.12）
水平投影： （3.13）
在这三种投影的基础上定义了三个不等式条件，公式（3.14）（3.15）（3.16）所示：
（3.14）
（3.15）
（3.16）
可以证明，只要不满足上述任何一个条件，可排除yi是最匹配码字。
3. 三角不等式法
基于三角不等式d(Y i,yj) d (x ,Yi)+ d (x ,yj)提出三种改进算法【14】。第一种算法先计算码书中每两个码字之间的距离，以当前匹配码字yi为中心，2hi(h i为输入矢量与当前匹配码字之间的欧氏距离)为半径划定搜索范围，即只搜索满足d(yj,yi) 2hi的码字yj,j= 1,2,…,N；
第二种算法是将搜索范围定为满足：x-hirkrx+hi，
其中rx为输入矢量的范数，rk为码字的范数，hi为输入矢量与当前匹配码字之间的欧氏距离，此种算法不同于第一种算法，无须计算码字之间的距离；
第三种算法取前两种算法搜索区域的交集作为搜索区域。
这三种算法都涉及如何确定初始匹配码字的问题，一般取范数与输入矢量范数最相近的码字。第一、三种算法比第二种算法要多耗费存储空间来存储码字之间的距离。最小均方误差编码算法，取一长训练矢量序列，计算每个Voronoi区域内的训练矢量与该区域质心矢量(码字) 的最大距离di，求平方根后得ri，按其升序排列。编码时，从最小的ri开始，排除对任意 ，满足 .的码字；那些对所有j，满足 的码字，则采用部分失真排除判定法，确定此码字为最佳匹配码字或者在以该码字为开始的剩余码字中搜索最佳匹配码字。
3．2．2 等均值等方差最近邻搜索算法
均值等方差最近邻码字搜索算法是将均值不等式判据和用方差不等式判据相结合，进一步缩小了码字搜索范围。k维输入矢量x的方差定义公式（3.17）【9】为
（3.17）
其中：Mx为输入矢量x的均值。
等均值等方差最近邻搜索算法所用到的方差判别准则为：
设码字 为输入矢量x的当前最近邻码字， ，输入矢量x和码字Y，的方差分别为Vx和Vyi，如果公式（3.18）成立，
（3.18）
则有d(x,yi) >d( x,yp)，码字yi，可以被排除是输入矢量x的最近邻码字。对式(3.12)作适当变形，可得公式（3.19）和（3.20）
(3.19)
(3.20)
即码字Yi的方差满足以上两式时，码字Yi可以被排除是输入矢量x的最近邻码字。
由几何知识可知，在欧几里得空间 中以空间中心线L为轴心的超圆柱面上，各点的方差相等，该超圆柱面称为等方差超圆柱面。由式(3.13)和(3.14)可知，等方差判别准则将码字搜索范围限制在方差分别为Vmax和V min的两个超圆柱面内。则等均值判别准则与等方差判别准则相结合的等均值等方差最近邻搜索算法将码字的搜索范围限制在了如图3.2所示的阴影部分内。
图3.1 等均值等方差最近邻搜索算法搜索范围二维示意图

图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年提出基于二元对称信道模型的码字索引分配算法【16】。该算法对于任何索引映射函数 ，选择码字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交换后所能引起的失真减少量，比较这些失真减少量，获得最大的失真下降量 ；