精华区文章阅读

发信人: sino (茶水博士), 信区: Theory
标题: [转载] 基于仿射变换的改进型矢量量化编码
发信站: 哈工大紫丁香 (Sun Aug 27 14:53:30 2000), 转信

发信人: jpeg (雨季), 信区: algorithm
发信站: NJU Lily BBS (Tue Jul 13 19:37:44 1999), 转信

【以下文字转载自 EEdepartment 讨论区】
【原文由 jpeg 所发表】
通信学报
JOURNAL OF CHINA INSTITUTE OF COMMUNICATIONS
1998年第19卷第11期 No.11 Vol.19 1998
科技期刊

基于仿射变换的改进型矢量量化编码

张　颖　　余英林
(华南理工大学　广州 510641)
布礼文
(香港城市大学电子工程系　香港)

摘　要　本文提出了基于仿射变换的改进型矢量量化编码算法，并给出了两种不同的实用
结构，与传统矢量量化算法相比，该方法在不需要重新训练新码本及不增加码本存储空间
的情况下，降低了编码误差，使得重建图像的PSNR显著增加，图像的主观质量也得到很大
的改善。
关键词　矢量量化　仿射变换　图像编码

Improved Vector Quantization Image Coding
Based on Affine Transformation

Zhang Ying　　Yu Yinglin
(South China University of Technology, Guangzhou 510641)
Po Laiman
(Dept of EE, City University of Hong Kong, Hong Kong)

Abstract　In this paper, an improved vector quantization (VQ) algorithm based
on affine transformation is proposed for image compression. In addtion, two
different new VQ structures are investigated in detail for practical applicat
ions. The proposed
methods can significantly improve the performance of conventional VQ in terms
of PSNR and visual quality without the need to generate an enlarged or speci
fic codebook. Thus, the memory requirement is not increased, and a relatively
small codebook size
can also achieve fairly good reconstructed image quality.
Key words　Vector Quantization, Affine Transformation, Image Compression

1　传统矢量量化编码存在问题
　　由于矢量量化(VQ)编码具有较高压缩比和解码快速等优点，特别适合图像的实时解码
恢复，因而引起研究者的广泛重视［1～3］，并被集成到多媒体芯片中，例如著名的Int
el公司开发的多媒体专用芯片i750就是一片基于VQ算法的视频图像压缩及处理的芯片。但
是，传统的VQ编码也有
其缺点，如训练码本的运算量庞大；编码时由于要和码本中码矢逐一比较，因而运算大，
压缩时间长；而其中最严重的问题是VQ的码本一般由一类具有相似特性或内容的图像训练
产生并只适用于这一类图像的编码。另一方面，由于训练矢量集并不代表实际输入的矢量
，对于一些内容与训练
图像有较大差别的图像，就难以取得较理想的编码效果。因此为了降低编码误差，改善图
像质量，就往往需要对码本进行相应的扩展。
　　码本的扩展一般有两个途径：一是采用大容量的码本即增加码矢，这样做不但大大提
高了训练码本和VQ编码时的运算复杂度，并且需要增加码本的存储空间；其二是对量化误
差大的输入矢量单独设计码本，缺点在于需要设计多个不同码本，训练码本的运算量大大
增加了，码本存储空间
也相应增加。另一方面，在许多情况下，特别是硬件实现VQ时，码本的更改或扩充甚至无
法做到，而且这样做的结果对码本的存储空间提出了新的要求，这在许多实际应用中往往
是得不偿失的。因此，如何种用现有的码本对不同内容的图像进行编码，应该是改善VQ编
码效果的一个值得研究
的课题。

2　仿射变换的原理
　　虽然仿射变换的原理早就被人们掌握，但直到Jacquin［4］将它巧妙地应用于分形压
缩算法，并取得良好的效果，才真正引起在图像压缩领域人们的研究兴趣。分形压缩［4
～5］是一种不同于传统图像压缩方法的崭新的图像编码算法，它利用迭代函数系统IFS来
抽取自然图像中存在的
自相似特性，其做法通常是将一幅图像分割成互不相交的子方块R，另一些从同一图像中
截取的可重叠的子方块D则构成搜索匹配空间。分形编码的任务就是对每一个R，都找出一
个D，使得D在适当的仿射变换ω后以最小的误差逼近R，然后将得到的仿射变换ω的参数
量化以后记录下来作为编
码器输出。
　　仿射变换通常可以分为下面三个部分：(1) 几何变换G，由于子块D的边长通常是R的
两倍，几何变换通过抽样及邻域平均得到缩小的子块，使得G(D)与R具有相同的空间尺度
；(2) 对称旋转变换S，通过适当的对称及旋转变换，使得S(D)与R尽可能具有相近的空间
灰度分布；(3)
灰度变换H，是一线性变换，其形式为H(D)=α*D+Δ，其中α和Δ是灰度变换的因子，直
接作用于像素的灰度值。对于二维灰度图像，如果用R(x,y,z)和D(x,y,z)分别表示待编码
子块与匹配子块，其中(x,y)表示像素点坐标，z表示像素的灰度值，那么仿射变换ω:D→
R可以统一用下式表示：

其中是几何及对称旋转变换的合成，由于实际应用的限制，A矩阵通常只取如文献［4～5
］所示的8种变换；(Px,Py)是匹配子块D的空间起始位置的相对坐标，这样需要记录的仿
射变换的参数包括Px,Py,A,α和Δ，用它们来表示原来的子块R。当然，分形编码中采用
的仿射变换还必须满足一
定的收敛条件，因而问题要复杂很多。但显而易见的是，如果将图像子块用矢量来表示，
那么仿射变换在分形压缩中的成功应用提示了通过仿射变换来提高VQ编码效果的途径。

3　两种改进型矢量量化编码
　　从不同角度出发，将仿射变换的概念与方法应用于传统VQ算法中来改善恢复图像的质
量，就会有不同的实现结构与方法，我们在此给出两种具体的改进型VQ编码算法。
3.1　利用仿射变换扩展码本(方法一)
　　第一种方法是将VQ码本中的码矢也看作图像子块，经过适当的仿射变换构成扩展码本
，然后用扩展后的码本中的码矢来编码输入矢量，整个改进型VQ编码/解码过程如图1所示
。假设Y=｛yi,i=1,2,…,N｝表示由N个码矢组成的码本，如果在事先设定的量化误差T下
，通过搜索整个码本，
能够找到一个码矢yi与输入矢量x匹配，那么输出码矢索引i和标识符0作为x的量化编码；
相反，如果所有的码矢都不能在设定的误差范围内量化该输入矢量，那么将它们经过仿射
变换来逼近x，找出其中误差最小，也就是最为相似的扩展码矢作为x的量化编码。由于码
矢的维数k与输入矢量
相同，所以不用进行分形压缩中的几何变换，而直接进行对称旋转变换及灰度变换得到y
＇i，这时最匹配的码矢yi事实上是使得均方误差

为最小，其中yi=α*yi+Δ，α和Δ为灰度变换系数，为确定α和Δ的值，通常采用最
小二乘法，即使MSE达到最小，这时根据极值原理，可以解得

其中　　　

由于直接存储及传送扩展码矢y＇i需要较大空间，所以实际量化后的编码输出由标识符1
、码矢索引i和仿射变换系数组成，包括对称变换的种类A、灰度变换中的参数α和Δ。解
码时根据标识符的不同而进行相应的重建过程：如果标识符为0，则按照索引号i查出相应
码矢恢复x；如果标识符
为1，则将查码本得到的码矢按所给的变换参数进行相应的仿射变换，从而恢复x。可见这
种基于仿射变换的码本扩展大大增加了每个码矢的表达能力，虽然扩充了码本容量，但却
并不需要重新训练新码本，而只是利用现成的码本，同时不增加码本存储空间，实现上较
简单。

图1　基于仿射变换的码本扩展的VQ编码和解码原理图

3.2　基于分形和矢量量化的混合编码(方法二)

　　事实上，分形编码可以看作是一种特殊的矢量量化器，它也是试图将图像子块所构成
的输入矢量用“码本”中的另一矢量来表示，只是矢量量化的码本是预先训练得到的，而
分形编码的“码本”则是直接取自于待编码图像本身，并且其中的“码矢”需要经过仿射
变换才能逼近输入矢量
，同时这种特殊的“码本”不需要保存。然而迄今为止，没有任何理由必须强制使用待编
码图像本身来作为码本，也就是说，可以用其它参考图像来作为分形压缩时的“码本”，
这样做的好处是显而易见地，即在参考图像已知的条件下，分形压缩不再受制于迭代过程
的收敛(事实上是无条
件收敛)，这一做法已广泛应用在运动图像序列的压缩中，用前帧图像通过分形变换来编
码下一帧图像。基于此，我们提出一种基于矢量量化及分形压缩的混合编码的方法。
　　整个混合编码的过程请参看图2。原始图像先进行传统的VQ编码，然后根据量化系数
重建图像，把原图与重建图像之间的差值图像作为一幅新的待编码图像，同样分割成4×
4子块后进行分形编码，只是此刻的“码本”不是差值图像本身，而是经VQ编码然后解码
的图像。为了减轻编码负
担，首先对差值子块进行分类，如果其均方误差MSE低于误差门限T，那么这样的差值子块
不必再进行分形编码，因为对应的码矢已足以在误差范围内重构原子块；相反，如果MSE
大于T，这些差值子块就需要再施加分形编码以降低误差。分形编码的具体过程可参考相
关文献［4～5］，在此不
再赘述。必须指出的是，由于采用了参考图像来进行分形压缩，因而不存在收敛问题的困
扰，在仿射变换参数的优化选取方面也就没有太多的限制。

图2　基于矢量量化和分形编码的混合压缩系统的编码/解码框图

4　实验结果与讨论

　　为了评估基于仿射变换的改进型矢量量化器的图像压缩效果，我们做了如下的对比实
验。首先把四幅256×256的训练图像即Sam、Lady、Woman和Pattern分割成4×4的图像子
块，即矢量维数k=16，然后根据LBG算法［3］训练出一个容量N=256的码本，测试图像则
不包括在训练图像中。通
过简单的计算可知，传统VQ算法的压缩比为16∶1，而改进型VQ算法由于图像内容的不同
及误差门限不同设置而会得到不同的压缩倍率。实验中的误差测度为均方误差，门限T＝
81。仿射变换的系数需要额外的存储空间，其中A矩阵总共包含8种变换，共需3bits；灰
度变换系数α和Δ分别被
均匀量化为3bits和6bits；混合编码时的匹配子块的搜索范围为［-8, +7］。
　　表1列出了实验结果的数据对比，从中可以发现，改进型VQ算法在码率稍有提高而衡
量图像质量的一个重要指标PSNR值上有2.2～4.3dB的提高。为了评估重建图像的主观质量
，图3给出了不同编码算法所恢复的对比图像。从图3(a)、图3(b)及图3(c)的比较可看出
，传统VQ所重建的图像存
在严重的块状和阶梯状模糊，图像主观质量较差，而改进型VQ的重建图像阶梯状块模糊大
大减小，主观视觉质量得到很大改善。可见，改进型VQ在相对较小的码本情况下，也能够
获得较高的图像重建质量。其中，第二种改进型算法的重构图像与第一种相比，人像轮廓
更清楚，纹理和边缘也
更清晰(特别是发梢和帽缘)。

　　表1　不同VQ编码算法的实验结果对比

图像尺寸测试图像 VQ 第一种改进型VQ 第二种改进型VQ
PSNR bit-rates PSNR bit-rates PSNR bit-rates
256×256 lenna 26.38 0.5 28.60 0.822 30.40 0.995
house 29.04 0.5 32.43 0.710 33.42 0.810
512×512 lenna 29.44 0.5 31.97 0.724 33.35 0.832
pepper 29.69 0.5 32.14 0.696 32.96 0.786

图3　不同情况下重建图像质量对比

　　显然，两种改进型VQ编码避免了重新训练大容量码本的庞大运算量，但在编码时由于
要从扩充的“码本”空间通过仿射变换搜索最佳匹配的码矢或参考图像中的子块，因而编
码的运算量会增加。我们知道，无论是训练码本还是VQ编码，需要计算的均方误差MSE的
运算量都占据了整体运
算量的绝大部分，因此相对于传统的码本直接扩展的方法，我们给出这方面运算量的大致
比较。
　　假设矢量维数为k，码本容量为N，直接扩展后的码本容量为N，M表示测试图像，并
假设编码图像与测试图像同样大小，训练集为m个M，那么应用LBG算法训练码本的运算量
就与p1×N×m×M成正比，其中p1表示训练过程的迭代次数，通常p1>15；编码时MSE的
计算次数与N＇×M成正比
，因此总的运算量大致与(p1×m+1)×N＇×M成正比。而改进型VQ编码训练码本的运算量
大致与p2×N×m×M成正比，通常有p1>p2，由于每个码矢可以有8种不同的对称旋转变换
，故码本扩充为8N，那么编码运算量基本上只与8N×M成正比，故总的运算量大致与(p2×
m+8)×N×M成正比。为了
保持相同的压缩倍率来比较，直接扩展的码本容量N＇》N，例如在图3所示的实验中，当
码率为0.822和0.995bpp时，如果采用直接扩展码本容量的方法，N＇分别约为9103和620
01，而N=256。因此很明显，从总体来说，基于仿射变换的改进型VQ的运算量要小得多，
而系统的存储容量却没有
增加，这对于硬件实现VQ是尤其有利的。
　　可见，本文提出的两种基于仿射变换的改进型矢量量化编码算法，在不增加码本的存
储空间，不需要扩大码本容量且重新训练，也不需要单独设计专用码本的情况下，大大改
善了VQ编码效果。这两种改进算法尤其适合硬件实现VQ编码时，提高恢复图像质量而无须
硬件上更改或扩充现有
码本。此外，虽然本文讨论的VQ算法是结构最简单的一种，但我们提出的基于仿射变换的
改进方法能够成功地推广到其它具有复杂结构的矢量量化的编码和解码系统中，从而相应
地改善它们的工作性能，降低编码误差，提高重建图像质量。

参　考　文　献

1　Nasrabadi N M, King R A. Image coding using vector Quantization: a review.
IEEE Trans Commun, Aug 1988,36(8):957～971
2　Gersho A, Gray R M. Vector quantization and signal compression. Kluwer Aca
demic Publishers,1991
3　Linde Y, Buzo A, Gray R M. An algorithm for vector quantizer design. IEEE
Trans Commun, Jan 1980,COM-28:84～89
4　Jacquin A E. A novel fractal block-coding technique for digital images. In
:Proc ICASSP 1990,2225～2228
5　Fisher Y.(Editor), Fractal image compression — theory and applications to
digital images. Springer-Verlag, NewYork, 1994

(1996-12-25收到，1998-07-27改定)

--
※ 来源:．NJU Lily BBS dii.nju.edu.cn．[FROM: e248jxy.nju.edu]

--
※ 修改:．fib 於 Aug 27 13:27:33 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．南京大学小百合 bbs.nju.edu.cn．[FROM: bbs.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: fib.bbs@bbs.nju.edu.]

Algorithm 版 (精华区)