基于矢量量化编码的数据压缩算法的研究与实现
码字检索器 (i)定义如式(2.10):
: I C;
(i) = Yi,i=1,2,…,M. (2.10)
矢量量化的模型如下图2.2所示:
编码时:对任意一个输入的K维矢量X,计算Q(X)的值Yi,通过传输信道发送码字Yi的索引i到解码器端。
解码时:对输入的一个索引号i,查找码书中对应的码字Yi,输出Yi作为整个系统对矢量X的压缩恢复值。
图2.2矢量量化器结构示意图
2.3.2量化器Q(x)相关问题
我们可以看出矢量量化可以等价于一个聚类问题。但如何聚类却有很多种方法。在上文我们说当 时,Q(X)= Yi;(i=1 ,2,…,M)。这是用胞腔来定义Q(X)。反过来,也可以用Q(X)和码字Yi来定义胞腔Ri,如式(2.11)所示:
(2.11)
当然,最初必须有一个明确的Q{X〕的定义。
如何判断 昵?通常定义一个失真测度函数 (实数域),d (X,Yi)表示用Yi来代表X时产生的误差。我们用它来判断一个矢量X到底属于那个胞腔:
当d (X,Y
因此,在这里量化器的主要工作就是利用失真测度函数d进行最近邻码字收索。有时候我们也把d(X,Yi)称作X与Yi之NJ的距离。
2.3.3 失真测度函数
我们要求失真测度函数满足以下两个条件:
(1)正定性: 当且仅当 X=Y时d( X,Y)=0;
(2)对称性: ;
有时候我们也加上第三个条件:
(3)三角不等式: ;
失真测度函数通常选择线性赋范空间中的范数,根据范数的定义,它们都满足上面三个条件。在本文中若无特殊声明,我们的d(X,Y)就取最常用的2范数的平方,即K维欧几里德空间中的距离的平方: ,我们把这个测度又称为平方误差测度。它虽然不满足三角不等式但是 却是满足全部这三个条件的。
事实上,判断一个矢量X属于哪个胞腔可以有很多种标准,在本文中,我们仅仅依据最近邻(NN: Nearest Neighbor)准则为判断标准。利用矢量失真函数d,我们再定义一个胞腔失真函数:
D: Voronoi Cells R (实数域);
X为处理矢量。
因为我们通常处理的数据量都是有限的,所以有限个实数之和也是有限的,从而D(Ri)是有限的。那么我们系统的总失真就如式(2.12)所示:
(2.12)
有时为方便起见,我们也把Er记为Er(C),C为码书,把D(Ri)记为D(Ri, Yi), Yi为Ri的代表元。显而易见的,Er是越小越好。
2.4 矢量量化的关键技术及技术指标
2.4.1 矢量量化的关键技术
矢量量化的三大关键技术是【8】:码书设计、码字搜索和码字索引分配。其中前两项最关键。
1. 码书设计
矢量量化的首要问题是设计出性能好的码书。如果没有码书,那么编码将成为无米之炊。假设采用平方误差测度作为失真测度,训练矢量数为M,目的是生成含N (N M)个码字的码书,则码书设计过程就是寻求把M个训练矢量分成N类的一种最佳方案(如:使得均方误差最小),而把各类的质心矢量作为码书的码字。可以证明在这种条件下各种可能的码书个数为Num C,Num C满足公式2.13:
(2.13) 其中C为组合数。通过测试所有码书的性能可以得到全局最优码书。
然而,在N和M比较大的情况下,搜索全部码书是根本不可能的。为了克服这个困难,文献中各种码书设计方法都采取搜索部分码书的方法得到局部最优或接近全局最优的码书。所以研究码书设计算法的目的就是寻求有效的算法尽可能找到全局最优或接近全局最优的码书以提高码书的性能,并且尽可能减少计算复杂度。
2. 码字搜索
矢量量化码字搜索算法是指在码书已经存在的情况下,对于给定的输入矢量,在码书中搜索与输入矢量之间失真最小的码字。给定大小为N的码书C,如果矢量x与码字A之间的失真测度为d(x,y),则码字搜索算法的目的就是找到码字Y,使得失真测度满足公式2.14:
(2.14)
如果采用平方误差测度,对于k维矢量,每次失真计算需要k次乘法,2k一1次加法,从而为了对矢量x进行穷尽搜索编码需要Nk次乘法,N(2k -1)次加法和N-1次比较。可以看出,计算复杂度由码书尺寸和矢量维数决定。对于大尺寸码书和高维矢量,计算复杂程度将很大。研究码字搜索算法的主要目的就是寻求快速有效的算法以减少计算复杂程度,并且尽量使得算法易于用硬件实现。
3. 码字索引分配
在图示的矢量量化编码和解码系统中,如果信道有噪声,则信道左端的索引i经过信道传输可能输出索引J而不是索引i,从而将在解码端引入额外失真。为了减少这种失真,可以对码字的索引进行重新分配。如果书大小为N,则码字索引分配方案一共有N!种。码字索引分配算法就是在N!种码字索引分配方案中寻求一种最佳的码字索引分配使由信道噪声引起的失真最小。然而,当N较大时,测试N!种码字索引分配方案是不可能的。为了克服这个困难,各种码字索引分配方法都采用局部搜索算法,往往只能得到局部最优解。所以研究码字索引分配算法的目的就是寻求有效的算法尽可能找到全局最优或接近全局最优的码字索引分配方案以减少由信道噪声引起的失真,并尽可能减少计算复杂度和搜索时间。
2.4.2 矢量量化技术指标
1. 矢量量化压缩率
从矢量量化器的工作原理我们看出,码书确定之后,传输或者存储的压缩数据只是一系列码字的索引,这些索引本身并不包含原始数据的任何信息。因此矢量量化的压缩率很大,其比特率 bit/采样,也就是说压缩倍数为 B为原始采样数据所用比特(bit)数。
举例来说,当E=8, M= 256, K=64时,压缩率r=0.015625 bits/采样。压缩倍数为64。这样的压缩倍数显然很可观了从压 缩 率 与压缩倍数的计算公式我们看出,M一般是2的幂次。再例如,码书大小为150,码字索引要用8bits码书大小为256,码字索引也要用8bits.两种码书大小得到的数据压缩率相同,但后者压缩性能显然更好,所以一般我们用256而非150个码字,大小为2a的码书又称为q比特码书。
2. 信号恢复性能指标
通常信号质量有均方误差(MSE),信噪比(SNR),峰值信噪比(PSNR) 【11】等。在本文的讨论中,我们主要是灰度图像作为测试数据来源。我们的矢量量化技术的应用也主要是针对灰度图像的,因此以L级灰度图像为例,我们给出个指标的定义:设一副L级灰度图像有WXH个像亲,Xij为原始图像像素值,Yij为恢复图像像素值,那么
结过如下公式所示:
(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)本文引用地址://m.amcfsurvey.com/article/172694.htm
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交换后所能引起的失真减少量,比较这些失真减少量,获得最大的失真下降量 ;
评论