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

文章摘要：第二种算法是将搜索范围定为满足：x-hi<rk<rx+hi，其中rx为输入矢量的范数，rk为码字的范数，hi为输入矢量与当前匹配码字之间的欧氏距离，此种算法不同于第一种算法，无须计算码字之间的距离；第三种算法取前两种算法搜索区域的交集作为搜索区域。这三种算法都涉及如何确定初始匹配码字的问题，一般取范数与输入矢量范数最相近的码字。第一、三种算法比第二种算法要多耗费存储空间来存储码字之间的距离。最小均方误差编码算法，取一长训练矢量序列，计算每个Voronoi区域内的训练矢量与该区域质心矢量(码字) 的最大距离di，求平方根后得ri，按其升序排列。编码时，从最小的ri开始，排除对任意 ，

基于矢量量化编码的数据压缩算法的研究与实现,标签：单片机开发,单片机原理,单片机教程,http://www.88dzw.com
第二种算法是将搜索范围定为满足：x-hi<rk<rx+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，i<j，转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，从而不需要信道编码和信道解码。

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