矢量量化技术

1、矢量量化,Vector Quantization,参考文献,Linde, Y., A. Buzo, and R. M. Gray( 1980) “An Algorithm For Vector Quantization Design”, IEEE Transaction on Communication, COM-28: 84-95, January. Constantinescu, C., and J. A. Storer( 1994a) “Online Adaptive Vector Quantization with Variable Size Codebook Entries”, In

2、formation Processing and Management, 30(6) 745-758 Constantinescu, C., and J. A. Storer( 1994b) “Improved Techniques for Single-Pass Adaptive Vector Quantization”, Proceeding of the IEEE, 82(6)933-939, June. Storer, James A. and Harald Helfgott(1997) “Lossless Image Compression by Block Matching”, T

3、he Computer Journal 40(2/3): 137-145,什么是矢量量化,标量量化：把每个像素的颜色用一个0到255之间的整数值表示。 矢量量化：把几个像素组成的像素块，用一个特定码书中的像素块来表示，码书中像素块的数目，一般远小于这些像素块所有可能颜色的组合。 在图像压缩中的矢量量化：,矢量量化的使用,如果一个2x2像素的小块，每像素有8位表示，则所有的像素块的可能取值有：232=4G种，可以选择一个远远小于这个数的数n，作为码书中码的个数，然后对图像中的每个块（矢量），用一个码书中的码来近似，这样只需用这个码的编号来编码这个图像矢量即可，因此每一个小块，最后都只需用log2

4、n个位来表示，由此达到压缩的目的。,图像块与码书中码的匹配,设图像块B=(b1, b2, , bn) 码矢量：C=(c1, c2, , cn) 图像块与码矢量的匹配程度，由它们之间的“距离”来度量，一般d(B, C)可取如下之一： |bi - ci| (bi ci)2 Max|bi - ci| d(B, C) 可以看成失真程度的一种度量(B用C表示时),LBG算法,LBG算法是由Linde, Buzo 和 Gray三位学者提出的方法。其主要的思想是：从一组码矢量出发，将所有的图像矢量进行划分，然后再重新计算码矢量，直到码矢量的变化收敛时，即完成了码书的选择。,LBG算法,主要步骤： 随意选取n

5、个图像块作为码矢量 由这n个码矢量对所有的图像块进行划分，即分成n个集合，使每个集合中的图像块，都是与各码矢量距离中，与对应的码矢量的距离最小的 由这n个集合的重心，得到n个新的码矢量 如果这些个码矢量与原来的码矢量变化不大（收敛），就完成码书的训练，否则重新进行2、3步,例子,假设每像素8位，分成两个像素的小块。 图像共有24个像素，12个小块： B1=(32,32), B2=(60,32), B3=(32,50), B4=(60,50), B5=(60,150), B6=(70,140), B7=(200,210), B8=(200,32), B9=(200,40), B10=(200,5

6、0), B11=(215,50), B12=(215,35) 初始码书：C1=(70,40), C2=(60,120), C3=(210,200), C4=(225, 50),例子.,图示,例子.,根据上图，很容易确定初始划分： P1 = (B1, B2, B3, B4), P2=(B5, B6), P3=(B7), P4=(B8, B9, B10, B11, B12) 平均失真为D(可用D/D作为收敛判断准则)： mean(1508, 164, 1544, 200, 900, 500, 200, 949, 725, 625, 100, 325) = 645 计算4个新的码矢量为： (B1+B

7、2+B3+B4)/4, (B5+B6)/2, B7, (B8+B9,B10,B11,B12)/5，所以新的码矢量为： C1=(46,41), C2=(65, 145), C3=(200,210), C4=(206,41),进一步的例子,看lena图像，256256，8bpp 将其分成44的小块，共有6464=4096个，用LBG求它的码书(128个码矢量)，看矢量量化后的图像。压缩比：7/(4*4*8) = 5.46875%,自适应矢量量化,Constantinescu和Storer的方法,自适应矢量量化,由Constantinescu和Storer开发的自适应矢量量化的方法，使用变长的图像块

8、和码书项（这里把码书称为字典）。编码器选择一个图像块，将其与一个字典项匹配，输出一个指向该项的指针，并通过对其添加一项或多项来更新字典。,自适应矢量量化编码器步骤,把字典D初始化为图像像素的所有可能值（所有可能的单像素块），初始化增长点集GPP为一个或多个增长点； 重复以下步骤直到GPP空； 从GPP中取出一个增长点G; 用G作为增长点增长一个图像块B，使用匹配算法和用户控制的保真度把它与一个字典项匹配； 一旦B已经达到仍能与字典项d匹配的最大尺寸，就输出d的指针； 用算法决定新的增长点加到GPP中； 如果D满了，用算法删去一项或多项，用一个算法去更新基于B的字典。,取增长点算法,算法：从GP

9、P中取出一个增长点G LIFO FIFO 波浪覆盖(Wave Coverage) 圆周覆盖 对角覆盖,图像块与字典项匹配算法,算法：把图像块B（以增长点G作为它的一角）与一个字典项匹配 从最小的块B(只有一个像素）开始，试着把越来越大的块与字典项匹配，直道B的下一次增长找不到任何字典项，能与B匹配到由用户规定的容忍度。 匹配的控制有以下参数控制： 距离 容忍度 覆盖类型 基本子块大小,GPP更新算法,算法：GPP更新（新增长点的选择） 选择那些位于或接近已编码图像边缘的点作为增长点，使新图像块与旧的相邻 把新加进图像块的下面和右边的两个点作为新的增长点添加到GPP中 把当前图像块加进已编码图像

10、所产生的新凹角，作为新增长点的位置,字典更新算法,算法：字典更新 基于两个原理： 用每个匹配块添加一个或更多个字典项 添加的新项应包含已编码图像中的像素 一种简单的策略： 添加两块（设当前块B）：把一列像素加到B的左边，把一行像素加到B的上边 或者再增加一块：把B左边一列与它上面一行相加得到新块,字典删除算法,可以选择以下策略： 删除最不常用的项 冻结字典（即不再改变） 删除全部字典（重新开始）,两个选择,两个能显著提高压缩性能的选择： 波浪覆盖似乎能提供比圆周覆盖和对角覆盖更好的性能 许多解压缩图像的视觉检查表明图像的平坦区域的数据失真对于人眼更敏感。可以对这样的区域使用较小的容忍度因子来改善这种方法。 一个简单的平滑度量A = V/M， V 区域中像素的方差 M 区域中像