矢量量化技术

VectorQuantization参考文献Linde,Y.,A.Buzo,andR.M.Gray(1980)“AnAlgorithmForVectorQuantizationDesign”,IEEETransactiononCommunication,COM-28:84-95,January.Constantinescu,C.,andJ.A.Storer(1994a)“OnlineAdaptiveVectorQuantizationwithVariableSizeCodebookEntries”,InformationProcessingandManagement,30(6)745-758Constantinescu,C.,andJ.A.Storer(1994b)“ImprovedTechniquesforSingle-PassAdaptiveVectorQuantization”,ProceedingoftheIEEE,82(6)933-939,June.Storer,JamesA.andHaraldHelfgott(1997)“LosslessImageCompressionbyBlockMatching”,TheComputerJournal40(2/3):137-145什么是矢量量化标量量化：把每个像素的颜色用一个0到255之间的整数值表示。矢量量化：把几个像素组成的像素块，用一个特定码书中的像素块来表示，码书中像素块的数目，一般远小于这些像素块所有可能颜色的组合。在图像压缩中的矢量量化：原图像将图像分割成nxn的方块（矢量）对每个方块矢量，寻找与之最接近的码矢量，即d(x,xk)最小码书：xii=1,2,…,c用k编码方块矢量量化的使用如果一个2x2像素的小块，每像素有8位表示，则所有的像素块的可能取值有：232=4G种，可以选择一个远远小于这个数的数n，作为码书中码的个数，然后对图像中的每个块（矢量），用一个码书中的码来近似，这样只需用这个码的编号来编码这个图像矢量即可，因此每一个小块，最后都只需用log2n个位来表示，由此达到压缩的目的。图像块与码书中码的匹配设图像块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算法主要步骤：1.随意选取n个图像块作为码矢量2.由这n个码矢量对所有的图像块进行划分，即分成n个集合，使每个集合中的图像块，都是与各码矢量距离中，与对应的码矢量的距离最小的3.由这n个集合的重心，得到n个新的码矢量4.如果这些个码矢量与原来的码矢量变化不大（收敛），就完成码书的训练，否则重新进行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,50),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+B2+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图像，256×256，8bpp将其分成4×4的小块，共有64×64=4096个，用LBG求它的码书(128个码矢量)，看矢量量化后的图像。压缩比：7/(4*4*8)=5.46875%Constantinescu和Storer的方法自适应矢量量化由Constantinescu和Storer开发的自适应矢量量化的方法，使用变长的图像块和码书项（这里把码书称为字典）。编码器选择一个图像块，将其与一个字典项匹配，输出一个指向该项的指针，并通过对其添加一项或多项来更新字典。自适应矢量量化编码器步骤1.把字典D初始化为图像像素的所有可能值（所有可能的单像素块），初始化增长点集GPP为一个或多个增长点；2.重复以下步骤直到GPP空；3.从GPP中取出一个增长点G;4.用G作为增长点增长一个图像块B，使用匹配算法和用户控制的保真度把它与一个字典项匹配；5.一旦B已经达到仍能与字典项d匹配的最大尺寸，就输出d的指针；6.用算法决定新的增长点加到GPP中；7.如果D满了，用算法删去一项或多项，用一个算法去更新基于B的字典。取增长点算法算法：从GPP中取出一个增长点GLIFOFIFO波浪覆盖(WaveCoverage)圆周覆盖对角覆盖图像块与字典项匹配算法算法：把图像块B（以增长点G作为它的一角）与一个字典项匹配从最小的块B(只有一个像素）开始，试着把越来越大的块与字典项匹配，直道B的下一次增长找不到任何字典项，能与B匹配到由用户规定的容忍度。匹配的控制有以下参数控制：距离容忍度覆盖类型基本子块大小GPP更新算法算法：GPP更新（新增长点的选择）选择那些位于或接近已编码图像边缘的点作为增长点，使新图像块与旧的相邻把新加进图像块的下面和右边的两个点作为新的增长点添加到GPP中把当前图像块加进已编码图像所产生的新凹角，作为新增长点的位置字典更新算法算法：字典更新基于两个原理：用每个匹配块添加一个或更多个字典项添加的新项应包含已编码图像中的像素一种简单的策略：添加两块（设当前块B）：把一列像素加到B的左边，把一行像素加到B的上边或者再增加一块：把B左边一列与它上面一行相加得到新块字典删除算法可以选择以下策略：删除最不常用的项冻结字典（即不再改变）删除全部字典（重新开始）两个选择两个能显著提高压缩性能的选择：波浪覆盖似乎能提供比圆周覆盖和对角覆盖更好的性能许多解压缩图像的视觉检查表明图像的平坦区域的数据失真对于人眼更敏感。可以对这样的区域使用较小的容忍度因子来改善这种方法。○一个简单的平滑度量A=V/M，V区域中像素的方差M区域中像素的均值A的范围容忍度A0.050.4t.05A.10.6tA0.1tLZ77方法在图像无损压缩中的应用LZ77LZ77（也称为LZ1）的思想如下图示：推广到二维情形因为像素的近邻不仅在其左右，也在其上下，所以利用搜索和比较块(譬如4x4像素)而不是单独的像素是有意义的。因此称为块匹配。THEENDTheendofthispresentation