矢量量化

矢量量化有损压缩是利用人眼的视觉特性有针对地简化不重要的数据，以减少总的数据量。

量化是有损数据压缩中常用的技术。

量化可以分为两种，即标量量化与矢量量化。

标量量化每次只量化一个采样点。

而矢量量化在量化时用输出组集合中最匹配的一组输出值来代替一组输入采样值。

根据香农的速率-失真理论，即使信源是无记忆的，利用矢量编码代替标量编码总能在理论上得到更好的性能，矢量量化可以看作标量量化的推广。

基本的矢量量化器编码，传输与解码过程如图所示。

矢量量化编码器根据一定的失真测度在码书中搜索出与输入矢量最匹配的码字。

传输时仅传输该码字的索引。

解码过程很简单，只要根据接收到的码字索引在码书中查找该码字，并将它作为输入矢量的重构矢量。

码字匹配信道查表信宿信源码书码书输入矢量索引索引编码器解码器输出矢量矢量量化编码和解码示意图假定码书}|,,,{110k j N R C ∈=-y y y y ，其中N 为码书的大小，而k 维输入矢量T k x x x ),,(110-= x 与码字T k j j j j y y y ),,()1(10-= y 之间的失真测度采用平方误差测度来表示，即：22210)(),(jjl k l l j y x d y x y x -=-=∑-=则矢量量化码字搜索问题就是在码书C 中搜索与输入矢量x 最匹配的码字bm y ，使得bm y 与x 之间的失真是所有码字中最小的，即：),(min ),(10bm N bm bm d d y x y x -≤≤= 全搜索算法（FS ）是一种最原始、最直观的码字搜索算法，它需要计算输入矢量与所有码字之间的失真，并通过比较找出失真最小的码字。

由于FS 算法每次失真计算需要k 次乘法，12-k 次加法，故为了对矢量进行编码需要Nk 次乘法，)12(-k N 次加法和1-N 次比较运算。

而FS 算法的计算复杂度是由码书的大小和矢量维数决定，而高效率矢量量化编码系统往往采用大码书和高维矢量，这时计算复杂度是非常大的，故减少码字搜索的计算负担是非常必要的，必须寻求快速有效的码字搜索算法。

通常的作法是先寻求一个初始码矢量，然后用排除准则把不匹配的码矢量排除，最后得到与输入矢量最匹配的码矢量。

所以一种快速有效的码字搜索算法的三个必不可少的因素是：(1)良好的初始匹配码字。

(2)强有力的码字删除准则。

(3)合理的码字搜索顺序。

显然，如果码字搜索开始于一个跟输入矢量比较接近的码字，则随后的候选码字就比较容易检验和排除。

另一方面，如果码字删除准则非常有效，则所需参加失真计算的码字数目将很少。

码书设计最常用的码书设计算法是LBG 算法，对于训练集}1,,1,0|{-==M m X m x 中的k 维矢量，用LBG 算法生成大小为S 的码书设计过程如下：1)随机从训练集中选择S 个矢量做为初始码书}1,,1,0|{-==S n Y n y 。

2)对于训练集中的每一个矢量，根据平方欧几里德距离失真测度找到与它失真最小的码字，并把这个训练矢量归入这个最邻近码字的聚类。

3)对于码书中的每一个码字n y ，计算这个码字与它相应聚类中所有训练矢量的平均失真∑∑-=-=-=10102),(),()(1J j K k k n k j y x J D ，其中J 为码字相应聚类中的训练矢量的个数。

4)计算所有码字总的平均失真∑-==101S n n D S Dtotal ，其中n D 表示码书中第n 个码字的平均失真。

5)如果前后两次迭代总的平均失真满足ξ≤--r r r D D D /)(1,ξ为失真阈值，或者达到预定的迭代次数则停止迭代。

6)计算出每个聚类的中心矢量，并由这些中心矢量组成下一次迭代的新的码书。

然后转第2步。

典型快速搜索算法1 基于不等式删除算法平方误差测度是两个矢量间各分量差值的平方和形式，相当于欧氏距离空间中两点之间距离的平方，这些特点使得许多常见的不等式，如绝对误差不等式、均值不等式和三角不等式，能够有效地运用到快速搜索算法中来，并成为快速搜索算法的数学基础。

1.1 绝对误差不等式删除算法定理1：假定目前最小失真为),(min p d d y x =,10-≤≤N p ，若min 1010d k y x es l il l s l il ∙≥-=∑∑-=-=, k s ≤≤1则 min y x d d i ≥),(定理1表明，随着s 从1到k 的增加，如果码字i y 与输入矢量x 之间的前s 维绝对误差分量之和满足上式，则i y 一定不是x 的最近码字。

基于定理1的快速算法称为AEI 算法。

为了进一步提高AEI 算法的删除效果，又提出基于改进的绝对误差不等式的码字删除准则。

IAEI 准则可描述如下：定理2：设目前最小失真为),(min p d d y x =,10-≤≤N p ，如果： min 1010d h y x es l il l s l il ∙≥-=∑∑-=-= k s ≤≤1,k h s ≤≤（由定理一直接可得：）则 min ),(d d i ≥y x从上式看出，IAEI 算法通过s 和h 从1到k 的取值，可排除大量码字，所以算法高利率比AEI 高。

除此之外，还有其它基于绝对误差不等式的删除准则，其中之一是Minimax 方法或超立方体方法，可用定理3来描述：定理3： 假设目前最小失真为),(min p d d y x =,10-≤≤N p ，对于任何10-≤≤k l ，如果：min d y x e il l il ≥-=则 min ),(d d i ≥y x上面所述的基于绝对误差不等式的各种算法的共同缺点是:(1)在选取初始匹配码字时，需要较多的在线绝对误差运算和比较运算。

(2）由于算法没有考虑到码字排序和码字搜索顺序，故这类算法效率有限。

1.2三角不等式删除算法三角不等式删除准则是一种有效的码字删除准则，它充分利用了欧氏距离的三角不等式特性，如下列定理所述：定理4：假定目前最小失真为),(min p d d y x =,令p i y y ,为相异码字，1,0-≤≤N p i ，x 为输入矢量，若：min 4/),(d d i p ≥y y则： min ),(d d i ≥y x定理5：假定目前最小失真为),(min p d d y x =,令p i y y ,为相异码字，1,0-≤≤N p i ，x 为输入矢量，若：min ),(),(d d d j i j ≥-y x y y则： min ),(d d i ≥y x使用定理4进行码字搜索之间，必须离线计算所有的2/)1(-N N 个码字对的失真测试并存储在码书中。

而在定理5中，由于i y 是随机选择的，故),(i d y x 的值可能很大，使得基于定理5的不等式删除准则效率不高。

此外，它还需要不少开方运算，从而造成算法效率的进一步下降。

1.3 均值不等式删除算法定义1：k 维矢量x 的均值定义为：k x m k l l x /)(10∑-==定理6：假定目前最小失真为),(min p d d y x =,i m 为码字i y 的均值，如果k d m m x i /min ≥-则： min ),(d d i ≥y x 一种有效的改进算法是文献[112]提出的等均值等方差最近邻码字搜索算法，它在运用均值不等式删除准则的同时采用了如下的方差不等式删除准则:定理7：假定目前最小失真为),(min p d d y x =，i v 为码字i y 的方差，如果 min d v v x i ≥-则： min ),(d d i ≥y x又提出另一种改进算法。

该算法同样利用均值和方差，不同的是它把均值和方差体现在一个不等式中，称为均值-方差不等式删除准则，如下所述：定理8：设目前最小失真为),(min p d d y x =，i m 和i v 为码字i y 的均值和方差，如果min 22)()(d v v m m k i x x i ≥-+-则： min ),(d d i ≥y x理论分析和仿真实验均表明，基于均值不等式删除准则和各种算法是最实用的快速码字搜索算法。

它具有良好的初始匹配码字且选取过程快，搜索范围小，搜索顺序合理，删除准则简单有效，这些优点是其他不等式删除准则无法比拟的。

2 基于金字塔结构删除算法假定图像n X 的大小为n n 22⨯，则n X 的金字塔结构可定义为一系列矩阵的形式：},,,,,,{110n m m m X X X X X +-，1-m X 为m X 分辨率降低的形式，其大小为1122--⨯m m ,如图所示。

其中0X 只有一个像素。

设),(1j i X m -为1-m 级图像1-m X 的一个像素，它可由m 级图像m X 中相邻的22⨯个像素)2,12(),12,2(),2,2(j i X j i X j i X m m m ++, )12,12(++j i X m 作适当的运算得到。

图像的金字塔类型有各种各样，其中最简单的是均值金字塔。

即：),(1j i X m -=41[()2,12()12,2()2,2(j i X j i X j i X m m m +++++)12,12(++j i X m )码字的金字塔结构n n k 22⨯=维输入矢量x 和码字i y 对应均值金字塔分别为},,,{10x =n X X X 和},,,,{10i in i i Y Y Y y = 定义：2120120)),(),((),(h l Y h l X d im l h m i m j j -=∑∑-=-=y x定理9：),(4),(4),(4),(0221i n i n i n i d d d d y x y x y x y x ≥≥≥≥--根据定理9，均值金字塔搜索算法过程可描述如下：首先离线建立所有码字的均值金字塔并保存在码书中，并按照均值的大小对码书进行升序排列。

搜索时，在线建立输入矢量x 的均值金字塔，找出与输入矢量均值最近的码字p y 作为初始匹配码字，计算),(min p d d y x =。

对所搜索的码字i y 首先判断min 0),(4d d i n ≥y x 是否成立。

如果成立，则码字i y 被排除。

否则继续判断min 11),(4d d i n ≥-y x 是否成立。

如果成立，则码字i y 被排除。

否则继续判断下一级。

提出小波金字塔搜索算法和均值-方差金字塔搜索算法。

金字塔搜索算法需要较大的附加计算量和额外存储空间。

该类算法在大码书和高维矢量的情况下比较有效。

3 基于变换域删除算法上述的各种快速算法最近邻码字搜索算法都是在空间域下使用不等式来删除码字，即输入矢量和码字都没有做任何变换。

正交变换如KLT,DCT,DWTF 都具备能量集中特性，即能量集中在少数几个变换域系数中，且变换前后能量保持不变，这个性质可用下列定理来描述：定理10：设A 为k k ⨯正交变换矩阵，设x 和i y 的变换域矢量分别为X ，i Y ：,x X A = i i A y Y =则 ),(),(i i d d Y X y x =。