矢量量化.doc

矢量量化有损压缩是利用人眼的视觉特性有针对地简化不重要的数据，以减少总的数据量。量化是有损数据压缩中常用的技术。量化可以分为两种，即标量量化与矢量量化。标量量化每次只量化一个采样点。而矢量量化在量化时用输出组集合中最匹配的一组输出值来代替一组输入采样值。根据香农的速率-失真理论，即使信源是无记忆的，利用矢量编码代替标量编码总能在理论上得到更好的性能，矢量量化可以看作标量量化的推广。基本的矢量量化器编码，传输与解码过程如图所示。矢量量化编码器根据一定的失真测度在码书中搜索出与输入矢量最匹配的码字。传输时仅传输该码字的索引。解码过程很简单，只要根据接收到的码字索引在码书中查找该码字，并将它作为输入矢量的重构矢量。 矢量量化编码和解码示意图 假定码书，其中为码书的大小，而维输入矢量与码字之间的失真测度采用平方误差测度来表示，即：则矢量量化码字搜索问题就是在码书中搜索与输入矢量最匹配的码字，使得与之间的失真是所有码字中最小的，即： 全搜索算法（FS）是一种最原始、最直观的码字搜索算法，它需要计算输入矢量与所有码字之间的失真，并通过比较找出失真最小的码字。由于FS算法每次失真计算需要次乘法，次加法，故为了对矢量进行编码需要次乘法，次加法和次比较运算。而FS算法的计算复杂度是由码书的大小和矢量维数决定，而高效率矢量量化编码系统往往采用大码书和高维矢量，这时计算复杂度是非常大的，故减少码字搜索的计算负担是非常必要的，必须寻求快速有效的码字搜索算法。通常的作法是先寻求一个初始码矢量，然后用排除准则把不匹配的码矢量排除，最后得到与输入矢量最匹配的码矢量。所以一种快速有效的码字搜索算法的三个必不可少的因素是：(1)良好的初始匹配码字。(2)强有力的码字删除准则。(3)合理的码字搜索顺序。显然，如果码字搜索开始于一个跟输入矢量比较接近的码字，则随后的候选码字就比较容易检验和排除。另一方面，如果码字删除准则非常有效，则所需参加失真计算的码字数目将很少。码书设计最常用的码书设计算法是LBG算法，对于训练集中的维矢量，用LBG算法生成大小为的码书设计过程如下：1)随机从训练集中选择个矢量做为初始码书。2)对于训练集中的每一个矢量，根据平方欧几里德距离失真测度找到与它失真最小的码字，并把这个训练矢量归入这个最邻近码字的聚类。3)对于码书中的每一个码字，计算这个码字与它相应聚类中所有训练矢量的平均失真，其中为码字相应聚类中的训练矢量的个数。4)计算所有码字总的平均失真，其中表示码书中第个码字的平均失真。5)如果前后两次迭代总的平均失真满足,为失真阈值，或者达到预定的迭代次数则停止迭代。6)计算出每个聚类的中心矢量，并由这些中心矢量组成下一次迭代的新的码书。然后转第2步。典型快速搜索算法1 基于不等式删除算法平方误差测度是两个矢量间各分量差值的平方和形式，相当于欧氏距离空间中两点之间距离的平方，这些特点使得许多常见的不等式，如绝对误差不等式、均值不等式和三角不等式，能够有效地运用到快速搜索算法中来，并成为快速搜索算法的数学基础。1.1 绝对误差不等式删除算法定理1：假定目前最小失真为,，若, 则 定理1表明，随着从1到的增加，如果码字与输入矢量之间的前维绝对误差分量之和满足上式，则一定不是的最近码字。基于定理1的快速算法称为AEI算法。为了进一步提高AEI算法的删除效果，又提出基于改进的绝对误差不等式的码字删除准则。IAEI准则可描述如下：定理2：设目前最小失真为,，如果： ,（由定理一直接可得：） 则 从上式看出，IAEI算法通过和从1到的取值，可排除大量码字，所以算法高利率比AEI高。除此之外，还有其它基于绝对误差不等式的删除准则，其中之一是Minimax方法或超立方体方法，可用定理3来描述：定理3： 假设目前最小失真为,，对于任何，如果： 则 上面所述的基于绝对误差不等式的各种算法的共同缺点是:(1)在选取初始匹配码字时，需要较多的在线绝对误差运算和比较运算。(2）由于算法没有考虑到码字排序和码字搜索顺序，故这类算法效率有限。1.2三角不等式删除算法三角不等式删除准则是一种有效的码字删除准则，它充分利用了欧氏距离的三角不等式特性，如下列定理所述：定理4：假定目前最小失真为,令为相异码字，为输入矢量，若：则： 定理5：假定目前最小失真为,令为相异码字，为输入矢量，若：则： 使用定理4进行码字搜索之间，必须离线计算所有的个码字对的失真测试并存储在码书中。而在定理5中，由于是随机选择的，故的值可能很大，使得基于定理5的不等式删除准则效率不高。此外，它还需要不少开方运算，从而造成算法效率的进一步下降。1.3 均值不等式删除算法定义1：维矢量的均值定义为：定理6：假定目前最小失真为,为码字的均值，如果 则： 一种有效的改进算法是文献112提出的等均值等方差最近邻码字搜索算法，它在运用均值不等式删除准则的同时采用了如下的方差不等式删除准则:定理7：假定目前最小失真为，为码字的方差，如果 则： 又提出另一种改进算法。该算法同样利用均值和方差，不同的是它把均值和方差体现在一个不等式中，称为均值-方差不等式删除准则，如下所述：定理8：设目前最小失真为，和为码字的均值和方差，如果则： 理论分析和仿真实验均表明，基于均值不等式删除准则和各种算法是最实用的快速码字搜索算法。它具有良好的初始匹配码字且选取过程快，搜索范围小，搜索顺序合理，删除准则简单有效，这些优点是其他不等式删除准则无法比拟的。2 基于金字塔结构删除算法假定图像的大小为，则的金字塔结构可定义为一系列矩阵的形式：，为分辨率降低的形式，其大小为,如图所示。其中只有一个像素。设为级图像的一个像素，它可由级图像中相邻的个像素, 作适当的运算得到。图像的金字塔类型有各种各样，其中最简单的是均值金字塔。即：=(+)码字的金字塔结构维输入矢量和码字对应均值金字塔分别为和定义：定理9：根据定理9，均值金字塔搜索算法过程可描述如下：首先离线建立所有码字的均值金字塔并保存在码书中，并按照均值的大小对码书进行升序排列。搜索时，在线建立输入矢量的均值金字塔，找出与输入矢量均值最近的码字作为初始匹配码字，计算。对所搜索的码字首先判断是否成立。如果成立，则码字被排除。否则继续判断是否成立。如果成立，则码字被排除。否则继续判断下一级。提出小波金字塔搜索算法和均值-方差金字塔搜索算法。金字塔搜索算法需要较大的附加计算量和额外存储空间。该类算法在大码书和高维矢量的情况下比较有效。3 基于变换域删除算法上述的各种快速算法最