矢量量化实验报告

1、矢量量化实验报告一、实验目的掌握矢量量化技术中码书搜索的基本原理；掌握几种经典的码字搜索算法；了解码字搜索算法在矢量量化技术中的重要性；尝试设计比文献性能更好的码书搜索算法。二、实验内容基础部分：完成1)中的码字搜索算法，任选2)和3)中一个码字搜索算法并完成；等均值最近邻码字搜索算法(Equal-average Nearest Neighbor Search, ENNS)和等均值等方差最近邻码字搜索算法(Equal-average Equal-variance Nearest Neighbor Search, EENNS)；哈德码变换域等均值等方差最近邻码字搜索算法(Hadamard Tra

2、nsform based Equal-average Equal-variance Nearest Neighbor Search, HTEENNS)；均值金字塔搜索算法(Mean Pyramid Search Algorithm, MPSA)。提高部分：从文献中任选一篇或者几篇论文并且实现论文中算法。发挥部分：改进文献中的算法或者设计新的码字搜索算法并详细给出实验设计的方案、 实验结果以及实验结论。三、实验原理矢量量化(VQ Vector Quantization)是70年代后期发展起来的一种数据 压缩技术基本思想：将若十个标量数据组构成一个矢量，然后在矢量空间给以整 体量化，从而压缩了数据

3、而不损失多少信息。基本的矢量量化器2可以定义为从k维欧式空间Rk到有限集合C的映射，即Q : Rk r C，其中C = y , y ,., y | y e Rk称为码书，N为码书大小。如果k0 1N-1 i维的输入矢量为X = (x ,x，,x )T，码书中的码字为y = (y ,y，,y)t，则01k-1ii 0i1i (k-1)输入矢量x和最匹配的码字j侦之间的映射满足d (x, y ) = min d (x, y )伽0i N-11按照公式(1)，对于一个输入矢量x，计算其到每个码字的距离，并将距 离最小的码字所谓最佳匹配码字。这种方法即为穷尽搜索算法(Full Search，FS)。

4、然而这种搜索算法计算量太大，速度很慢，严重制约了矢量量化在工程中的实际 应用。所以研究矢量量化中码字的快速搜索算法具有很重要的意义。1.等均值最近邻搜索算法ENNS假定当前最小失真为 d min = d (x, y，0 p N -1,0 s dmin成立，码字yj可以排除。Search,这就是等均值最近邻搜索算法(Equal-average Nearest NeighborSearch,ENNS)，它将搜索范围限定在两个平行的等均值超平面内。2.等均值等方差最近邻搜索算法EENNS假定当前最小失真为d min = d (x, yp)，0 p N -1,0 s d (4)则 d(x,y ) d

5、成立。这是一种对EENNS的改进算法IEENNS,它将搜索范围限定得比ENNS更 小并外切于EENNS的搜索区域。在二维情况下，为两个圆，在三维情况下，为 一个游泳圈状的区域。其在二维情况下的搜索范围如图1。图1 IEENNS算法搜索范围的二维示例4.哈德玛变换域等均值等方差最近邻码字搜索算法HTEENNS假定当前最小失真为dmin = d(4,与)，七为码字y_哈德玛变换矢量Yj的方差，Y.0为哈德玛变换域码字矢量Y的第一维分量，若匕一匕件jvmz(5)错误味找到引用源。则d(x,y ) d .成立，同时，若|X -仆凡；贝。d (x, y ) d .。这是哈德玛变换域等均值等方差最近邻码字

6、搜索算法(Hadamard Transform based Equal-average Equal-variance Nearest Neighbor Search, HTEENNS)，在使用 大码书大分块的情况下，HTEENNS比等均值最近邻搜索算法(ENNS)和等均值等 方差最近邻搜索(EENNS)算法有效得多。四、实验结果与分析这里采用512X512的8 bit的标准图像Lena作为训练图像用实验一中的初 始码书生成算法产生的四种码书，码书大小为N=512或N=1024,而矢量维数为： 8X8=64或：4X4=16。然后用这些码书对512X512的8 bit的Lena图像进行编 码。为了

7、比较，本文对穷尽搜索FS)、等均值最近邻搜索算法(ENNS)、等均值等 方差最近邻搜索算法(EENNS)、改进的等均值等方差最近邻搜索算法(IEENNS) 和哈德码域部分失真搜索算法(HTEENNS)均作了相应测试。编码时间的测试结 果如表1所示(单位为秒)。表1算法的编码时间比较算法N=1024N=512K=16K=64K=16K=64FS15.5131.596.7015.83ENNS0.880.930.520.64EENNS0.720.790.410.58IEENNS0.600.770.380.57HTEENNS0.530.710.310.55编码平均计算量的测试结果如表2所示(单位为失真计算次数/输入矢量)。表2算法的编码平均计算量比较算法N=1024N=512K=16K=64K=16K=64FS10241024512512ENNS18.7624.028.7216.58EENNS10.0217.646.9412.96IEENNS9.2115.975.6510.10HTEENNS6.9112.304.829.41实验结果表明