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

文章摘要：结过如下公式所示：（2.15）（2.16）（2.17）第三章 矢量量化的算法研究3．1 矢量量化码书设计算法的研究3．1．1 经典的LBG算法如前所述，在矢量量化器的构造过程中，码本设计是最初的也是最重要的部分，根据各种码本设计算法的思想和迭代过程，我们可以将码本设计问题归结为Lloyd算法的两条基本准则【12】：1. 最佳划分准则(Optimal Partition)对于给定的码本 利用最近邻条件对训练矢量集进行重新划分。将每个训练矢量映射到与它之间失真最小的码字，最后形成一组以现有码本中的码字为中心的最佳划分。设训练矢量集为：则训练矢量集的最佳分类 满足公式（3.1）：式中，i,j= 1,

基于矢量量化编码的数据压缩算法的研究与实现,标签：单片机开发,单片机原理,单片机教程,http://www.88dzw.com
结过如下公式所示：
（2.15）
（2.16）
（2.17）
第三章 矢量量化的算法研究
3．1 矢量量化码书设计算法的研究
3．1．1 经典的LBG算法
如前所述，在矢量量化器的构造过程中，码本设计是最初的也是最重要的部分，根据各种码本设计算法的思想和迭代过程，我们可以将码本设计问题归结为Lloyd算法的两条基本准则【12】：
1. 最佳划分准则(Optimal Partition)
对于给定的码本 利用最近邻条件对训练矢量集进行重新划分。将每个训练矢量映射到与它之间失真最小的码字，最后形成一组以现有码本中的码字为中心的最佳划分。设训练矢量集为：
则训练矢量集的最佳分类 满足公式（3.1）：
式中，i,j= 1,2,…,N （3.1）
如果存在D(x,yi )= D (x,yj ), 则将训练矢量归入码字yi的集合。
通常把这种最佳划分称为Voronoi划分，对应的子集凡称为Voronoi胞腔。设训练矢量x为k维的 ，如果用平方误差测度用来表征训练矢量x和码字yi之间的失真，即：
（3.2）

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）：

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