基于矢量量化编码的数据压缩算法的研究与实现
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的索引。
令 , 和 分别代表测试解组的目标函数值集合,当前解的目标函数值和最优解的目标函数值,其中 是测试解 的目标函数值,0iNs-1。初始的当前解是随机产生的,通过随机交换当前解中的两个索引来产生测试解。禁止表中只存储交换的索引。如果从当前解中产生测试解的交换索引与禁止表中任何记录相同,则称该测试解为禁止解。该算法的具体步骤如下:
Step 1:设置禁止表大小Ts测试解个数N,以及迭代次数Im。令迭代计数器i=1,禁止表插入点t=1。随机产生当前解 ,计算其相应的目标函数值V}。令Sb=Sc以及Vb=Vc
Step 2:把当前解Sc拷贝给每一个测试解si, 0iNs-1。对每一个测试解si,0i Ns-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,如果iIm,令i=i+1转Step 1;否则,算法结束。本文引用地址://m.amcfsurvey.com/article/172694.htm
第四章矢量量化算法的实现
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 MyBlock[N];
for(int i=0;iN;i++)
{ codebook[i]=new MyBlock();
} codebook[0]=tv.randomselect();
for(int j=1;jN;j++) {
int t=0;
do{ t++;
n=0;
codebook[j]=tv.randomselect();
for(int l=0;lj;l++)
{ if(codebook[j].vcmp(codebook[l])==0)
{ n=1; break; }
}
}while(n!=0t100);}
4.2.2 LBG矢量量化
图4.2 LBG码书设计流程图
如图4.2所示的流程图,对随机生成初始码书,码书大小N,训练矢量序列,停止计算门限和起始平均失真的初始码书进行劳埃德迭代。用初始码书为已知的心形,把训练序列重新划分为N个胞腔。计算新的平均失真和相对失真,判断新的失真是否满足门限条件,如果满足则退出劳埃德迭代否则继续进行劳埃德迭代直到满足门限条件,生成码书。LBG算法的关键代码如下:
flag=0;//循环标识
tcb(s,tv);//训练集和码本建立关系
for(int i=0;iN;i++)
{ for(int j=0;jtv.M;j++)
{if(s[j]==i) n++;
yn[i]=n;
} }dsum=0;
for(int i=0;itv.M;i++)
{dsum=dsum+(long)min1(tv.train[i],1);
}d1=(double)(dsum/tv.M);
d=Math.abs(((double)(d0-d1)/(double)d1));
if(d1d0d>e)
{for(int i=0;iN;i++)
{if(yn[i]!=0)
{o=core(tv,i,s);
codebook[i].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的高压缩比,并且压缩时间比较短。所以矢量量化压缩编码是一种非常有效的压缩算法。
从压缩图像的效果来看,实验测试的图像均采用的512×512,8比特/象素的women图像作为训练图像产生各种大小的码书,矢量维数均为16,对压缩程序进行测试。通过变换码书的大小,运行程序得到不同的信噪比。测试结果如下表4.1所示:
表4.1 不同码书的信噪比
序号 码书大小 PSNR
1 64 27.36
2 128 27.74
3 256 28.54
4 512 29.28
如上表所示,随着码书的加大,系统的信噪比在升高,当码书大小为512时,PSNR可以达到29.28。图像虽然有一定程度上的失真,但是并不是十分明显,基本上保持了图像原有的图像质量。
这个程序采用的是矢量量化码书生成算法中的LBG算法,通过运行程序以及对运行结果的分析可以看出这种从标量量化劳埃德迭代操作推广出来的迭代算法具有以下两个优点:
1.不用初始化计算,可大大减少计算时间
2.初始码字选自训练序列,无空胞腔问题
虽然LBG算法在具有如上的优点,但是因为LBG算法是一种下降算法,每次迭代总能减少(至少保持不变)平均失真,而且每次迭代通常只能产生码书的局部变化,即每次迭代后,与旧码书相比,新码书不可能有非常大的变化。所以初始码书的选择影响码书训练的收敛速度和最终码书的性能,一旦选定初始码书,该算法只能得到局部最优的码书,即LBG算法一般不能得到全局最优的码书。
在每次迭代的最佳划分阶段,从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计算;这对软件大的运行要求比较高的运行环境。这个可以通过快速码字搜索的算法来解决这个问题。
第五章 结论与展望
本文主要针对矢量量化的算法和实现研究与探讨,本章主要对本文内容与研究工作进行一下总结。最后对矢量量化技术在今后发展方向上作了一些展望。
矢量量化技术作为数据压缩领域里的一个分支,主要优点是压缩比大以及解码简单,在图像压缩方面已经得到成功地应用。目前, 矢量量化技术的研究主要集中在三个方面:矢量量化器的码本设计,矢量量化码字快速搜索算法设计,矢量量化码字索引分配问题。本文主要研究了矢量量化码本设计算法和码字快速搜索算法,并讨论了矢量量化技术的应用问题。全文主要工作可以总结如下:
首先,介绍了数据压缩算法的基本理论和发展现状,讨论了数据压缩算法的分类体系和发展历程。
其次,介绍了矢量量化技术的来源和发展历程,重点介绍了关于矢量量化技术的技术基础和矢量量化算法中的关键技术。
再次,研究了经典的矢量量化的设计算法,分别研究讨论了矢量量化中的LBG算法,最大下降算法;快速搜索算法中的基于不等式的快速搜索算法和码字索引分配中的BSA算法等,并讨论了现有各种矢量量化算法。
最后,介绍了一种LBG矢量量化算法的实现方法,并对实验结果进行了性能评价。
以上是本文内容的总结。还有许多问题没有涉足或研究的深度不够。矢量量化技术领域虽然已经取得了长足的进步,但总体上来说还有许多问题需要进一步研究。下面对矢量量化未来发展的展望:
(1) 矢量量化是一种信源编码技术,在矢量量化器设计的过程中,考虑如何降低信道传输中可能造成的噪声干扰的影响,可以提高矢量量化系统的整体性能。归结起来,可以用矢量量化码书索引分配问题来描绘,即研究如何合理的安排码书中码字的排序,使得编码系统在信道传输中的容错能力增强。
(2) 矢量量化作为一种数据压缩技术,如何更好地应用到实际的数据压缩和传输系统中去,在实际应用中体现编码算法的优越性,是一个很实际的问题,在设计算法的同时,要考虑应用的实际情况。
(3) 本文中在图像的编码方面对矢量量化进行研究,矢量量化技术并不仅仅用在图像编码中,可以根据实际需要,可以深入对其进行深入研究,如可以在语音压缩编解码、音视频压缩和远程会议等方面,还可以将这些成果应用到其方面一数字水印、语音识别、语音合成以及文字合成以及文字的识别等。
评论