基于矢量量化编码的数据压缩算法的研究分析

第四章 矢量量化算法的实现
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所示：