基于矢量量化编码的数据压缩算法的研究与实现

文章摘要：（3.8）若采用平方误差测度，则式(3.8)可以化简为式（3.9）：或 （3.9）式中， 分别为 的元素个数， 。分别为 的质心。从式(3.9)中可以看出，若胞腔 、 非空，则失真下降函数满足 。我们将胞腔Si的最优分割超平面 定义为使胞腔 具有最大失真下降 的超平面。MD算法先计算出所有胞腔的最大失真下降值 ， ，然后找出最大的最大失真下降值 ，即 ，最后将胞腔Sp分割成两个新胞腔。所以，L+l个胞腔是通过划分L个胞腔中具有最大失真下降的胞腔并保持其余胞腔不变而得到的。值得注意的是，每次分裂包腔时，并不需要重新计算所有包腔的失真函数，而只需找到新增加的两个包腔的最优分割超平面，计算它们各自的

基于矢量量化编码的数据压缩算法的研究与实现,标签：单片机开发,单片机原理,单片机教程,http://www.88dzw.com
（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；

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]  下一页