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

基于矢量量化编码的数据压缩算法的研究与实现 二转自：.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)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 2END：算法结束。对于LBG算法来说，初始码本选择的好坏将直接影响到后面的迭代计算结果，一个不好的初始码本会降低算法的收敛速度和最终码本的性能。因此在LBG算法中要对初始码本的选择作一定的处理。如果初始码本随机产生，即直接从训练序列中随机选择N个训练矢量作为初始码字，构成初始码本，可能会选到一些非典型的训练矢量作码字，因而该胞腔可能含有少数几个矢量甚至只有1个。另外，有可能把某些空间分得过疏。这可能会导致码本中的有些码字得不到充分利用，设计出来的码本性能就可能较差。3.1.2 MD算法最大下降(MD)【13】码本设计算法与经典的LBG算法不同，它是一种分裂算法，而没有初始码本。在MD算法中，首先将训练矢量集作为一个原始包腔，然后该包腔被它的最优分割超平面分成两个子包腔。依此类推，每次分裂产生一个包腔，直到生成最后的N个包腔，计算它们的质心，就可以得到设计的码本C=yi=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.整数投影法整数投影法是一种适用于图像矢量量化的快速码字搜索算法。他们为每个mm图像块，定义三种整数投影【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-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 ij，转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交换后所能引起的失真减少量，比较这些失真减少量，获得最大的失真下降量；Step 4：如果0，则交换索引n和引起最大失真下降的索引j，并转Step 2；Step 5：终止算法。如果n=N一1，则终止算法，否则，转Step 3。可以看出，BSA算法根据函数值将码字进行排列而选择出哪一个码字最先进行交换，从而在运算上给出了一个方向性引导。如果由于程序运行时间的限制而使算法的迭代次数有限，则这种方向性引导将显得尤为重要。每一次成功交换的完成，代表一次迭代的结束。若一次迭代中的所有试验性交换产生的失真下降都不大于O，则说明算法已经达到一个局部最优解.应该指出的是：从不同的初始码字排序出发，可获得不同的局部最优解，从而保证BSA算法对于码字交换的限制不会影响它获得全局最优码字索引分配方案的可能性。实验证明，该算法获得的码字索引分配方案的失真比随机码字索引分配方案的失真有较大改进。3.3.2禁止搜索码字索引算法禁止搜索的基本思想是通过一系列移动来搜寻所有可行解的搜索空间，并且在当前迭代中禁止某些搜索方向以避免死循环和跳入局部极小。由当前解到其邻域解的移动被部分地或完全地记录在禁止表中，目的是为了禁止以后迭代中的重复操作。令为测试解的集合，其中元素si可以被表示为式【8】(3.22)：(3.22)其中，N为码书的尺寸，Si(j)表示在解si中分配给码字Yj的索引，令和分别表示当前解和最优解。中码字Yj的索引，Sb(j)仍表示分配给解Sb中码字Yi的索引。令，和分别代表测试解组的目标函数值集合，当前解的目标函数值和最优解的目标函数值，其中是测试解的目标函数值，0 iNs-1。初始的当前解是随机产生的，通过随机交换当前解中的两个索引来产生测试解。禁止表中只存储交换的索引。如果从当前解中产生测试解的交换索引与禁止表中任何记录相同，则称该测试解为禁止解。该算法的具体步骤如下：Step 1：设置禁止表大小Ts测试解个数N，以及迭代次数Im。令迭代计数器i=1，禁止表插入点t=1。随机产生当前解，计算其相应的目标函数值V。令Sb=Sc以及Vb=Vc Step 2：把当前解Sc拷贝给每一个测试解si,0 iNs-1。对每一个测试解si，0 iNs-1，产生两个随机整数r1和r2，。N为码字个数，然后通过交换索引和产生新测试解组。计算测试解的函数值。Step 3：如果最优测试解的目标函数值比最优解的目标函数值Vb还小，则把它作为新的当前解，并令其目标函数值作为当前解的目标函数值Vc，转Step 3。否则，选出测试解中最好的非禁止解。如果能选到，则把它作为新的当前解Sc并令其目标函数值作为当前解的目标函数值Vc，转Step 3；否则，转Step 1。Step 4：如果vb vc，令Sb=Sc，Vb=Vc，把从旧当前解到新当前解所交换过的索引插入禁止表中。禁止表的插入点设为ti=ti+1；如果ti Ts，令ti=l，如果i Im，令i=i+1转Step 1；否则，算法结束。第四章矢量量化算法的实现4.1需求分析与整体设计4.1.1需求分析随着数字技术的飞速发展，越来越多的信息(文本、图形、图像、动画、音频及视频影像等)采用数字化的形式存储、传输和检索。由于网络上的数据流量飞速增长，而且网络的带宽总是满足不了需求，数据压缩编码技术的迅猛发展，要求在尽量不损伤多媒体质量的情况下压缩数据量。正是由于这种需求的存在，要求开发一套完整的数据压缩软件，利用矢量量化的数据压缩算法，能够调用BMP格式的图像，对载入的图像进行压缩并显示解压后的图像效果，能够选择路径保存解压后的图像实现SNR信噪比的计算，便于对压缩软件性能的评价。4.1.2整体设计软件的设计在Eclipse开发工具下编译Java应用程序。利用Java语言的面向对象的特点，充分利用他的可封装性，重用性和多态性等特点，开发一整套完整的基于矢量量化数据压缩算法的压缩软件。将这个数据压缩软件从整体上分五个模块来实现的。Bmp格式图像的调入和保存模块，图像矢量块的划分模块，初始码书生成模块，LBG量化模块，图像解压模块。如图4.1所示：图4.1程序模块框图软件界面的设计。在JAVA的运行环境下要实现基于矢量量化数据压缩算法对BMP格式的静止图像进行压缩与解压。软件界面的设计，在图像界面的左侧可以显示调入的图像，右侧显示图像信息。在浏览按钮上可以调入待压缩的图像，并且可以选择解压后的图像的保存位置。选择好解压图像后点击压缩按钮即可开始对图像进行矢量量化的压缩。最后显示压缩的结果，包括原始图像的大小，压缩后的大小，压缩比，压缩时间及PSNR值等信息。软件运行的初始界面如图4.2所示：图4.2程序运行初始界面4.2矢量量化算法的实现过程及说明4.2.1初始码书的生成这个程序利用了随机编码生成码书的方法，即根据输入信源分布直接从训练序列中随机选择N个训练矢量作为初始码字以构成初始码书。该方法的优点是计算量低，初始码书的生成较为容易。虽然可能出现码书的分布不均匀的现象，但是配合LBG算法的多次迭代可以得到补偿。需要注意，这里所说的随机编码是说初始码书的选择方式是随机的，而一旦码书选定，编码器的工作方式则是按着最近邻方式进行的。随机码书的生成代码如下：codebook=new MyBlockN；for(int i=0；i N；i+)codebooki=new MyBlock()；codebook0=tv.randomselect()；for(int j=1；j N；j+)int t=0；dot+；n=0；codebookj=tv.randomselect()；for(int l=0；l j；l+)if(codebookj.vcmp(codebookl)=0)n=1；break；while(n！=0&t 100)；4.2.2 LBG矢量量化图4.2 LBG码书设计流程图如图4.2所示的流程图，对随机生成初始码书，码书大小N，训练矢量序列，停止计算门限和起始平均失真的初始码书进行劳埃德迭代。用初始码书为已知的心形，把训练序列重新划分为N个胞腔。计算新的平均失真和相对失真，判断新的失真是否满足门限条件，如果满足则退出劳埃德迭代否则继续进行劳埃德迭代直到满足门限条件，生成码书。LBG算法的关键代码如下：flag=0；/循环标识tcb(s,tv)；/训练集和码本建立关系for(int i=0；i N；i+)for(int j=0；j tv.M；j+)if(sj=i)n+；yni=n；dsum=0；for(int i=0；i tv.M；i+)dsum=dsum+(long)min1(tv.traini,1)；d1=(double)(dsum/tv.M)；d=Math.abs(double)(d0-d1)/(double)d1)；if(d1 d0&d e)for(int i=0；i N；i+)if(yni！=0)o=core(tv,i,s)；codebooki.vcopy(o)；d0=d1；flag=1；while(flag=1)；在这段代码中，首先建立码本与训练矢量的关系，并经过多次的劳埃德迭代直到满足门限条件，生成新的码书。这里应用了LBG算法他具有如下的优点：1.不用初始化计算，可大大减少计算时间2.初始码字选自训练序列，无空胞腔问题虽然LBG算法有如上的优点，但是他本身也存在一些缺点和不足的地方，比如在计算的过程中可能会选到一些非典型矢量作码字，因而该胞腔中只有很少矢量，甚至只有一个初始码字，而且每次迭代又都保留了这些非典型矢量的形心；还可能会造成在某些空间把胞腔分得过细，而有些空间分得太大。这些缺点都会导致码书中有限个码字得不到充分利用，还需要进一步的改进算法。程序整体流程图如图4.3所示：图4.3软件流程图4.2.3矢量量化码字索引与恢复在这个程序中没有考虑快速码字搜索的算法，应用了最佳码字搜索的方法，使输入矢量与所有的码字进行比较，选出距离最小的那个码字成为匹配码字，生成索引。这种算法虽然增加了计算量，但是减少了图像数据压缩过程中的失真。在输出端，将编码过后生成的索引对照码书，将图像数据进行还原。4.3实验结果及评价在初始界面点击浏览按钮调入.BMP图像。图像就会显示在程序运行初始界面的左侧，如图4.3所示：图4.4压缩前的程序界面点击压缩按钮，程序就会自动进行矢量量化的压缩，下面的进度条会显示压缩的百分比，当进度达到100%时，程序就会将解压好的图像显示在程序界面的左侧。并显示一系列的压缩信息，包括压缩源文件的大小，压缩后的码本大小，压缩比，压缩过程所需要的时间以及峰信噪比PSNR等信息。压缩后的界面如图4.5所示：图4.5恢复后的程序界面程序显示的压缩结果的压缩比和压缩时间上可以看出，这个利用矢量量化编码算法的压缩软件可以达到16：1的高压缩比，并且压缩时间比较短。所以矢量量化压缩编码是一种非常有效的压缩算法。从压缩图像的效果来看，实验测试的图像均采用的512512，8比特/象素的women图像作为训练图像产生各种大小的码书，矢量维数均为16，对压缩程序进行测试。通过变换码书的大小，运行程序得到不同的信噪比。测试结果如下表4.1所示：表4.1不同码书的信噪比序号码书大小PSNR 164 27.36 2128 27.74 3256 28.54 4512 29.28如上表所示，随着码书的加大，系统的信噪比在升高，当码书大小为512时，PSNR可以达到29.28。图像虽然有一定程度上的失真，但是并不是十分明显，基本上保持了图像原有的图像质量。这个程序采用的是矢量量化码书生成算法中的LBG算法，通过运行程序以及对运行结果的分析可以看出这种从标量量化劳埃德迭代操作推广出来的迭代算法具有以下