（电路与系统专业论文）矢量量化技术及其在图像压缩中的应用研究.pdf

硕j 二学位论文 摘要 摘要 矢量量化技术是一种有效的有损压缩技术，其突出优点是压缩比 大且解码算法简单。但是由于相关理论和应用研究没有完善，矢量量 化的压缩标准一直没有提出。本文深入探讨了矢量量化的两大关键技 术码书设计和码字搜索，研究了矢量量化在图像压缩中的应用。 在码书设计算法方面，提出了分量均值正交分割码书设计新算 法。利用分量均值正交分割失真最大的胞腔，使初始码字尽量散开， 得到充分利用，并提出了针对非典型码字的解决办法。实验表明，新 算法在量化失真和训练速度两个相互冲突的指标之间，相对于以往算 法取得了更好的均衡。 在码字搜索算法方面，结合绝对误差不等式准则排除范围广的优 势和等均值等方差准则搜索速度快的优势，提出了改进的等均值等 方差最近邻码字搜索算法，并提出了初始匹配码字和码字搜索顺序的 确定方法。仿真结果表明，搜索速度相对于改进前提高了约1 0 。 在图像压缩应用方面，提出了方差法和均值法两种识别“高细节 块和“低细节块 的方法，对于细节信息丰富的“高细节块采用 高比特率编码，否则采用低比特率编码。实验表明，这种自适应的变 比特率压缩算法在编码质量、比特率和编码时间三个重要性能指标上 都有较大改进。针对编码索引非均匀分布的特点，提出了结合哈夫曼 编码的边缘匹配压缩算法，仿真结果表明，该算法在不增加失真的条 件下，编码码率逼近信息熵理论的下限，为建立基于矢量量化的图像 压缩国际标准提供了一个参考方案。 关键词：矢量量化，码书设计，码字搜索，图像压缩 硕上学位论文a b s t ra c t a b s t r a c t v e c t o rq u a n t i z a t i o n ( v q ) i sa l le f f e c t i v el o s s yc o m p r e s s i o nt e c h n i q u e w i t hp r o m i n e n tm e r i t so fh i g hc o m p r e s s i o nr a t ea n de a s yd e c o d i n g a l g o r i t h m a st h er e l e v a n tt h e o r e t i c a la n da p p l i e dr e s e a r c hh a sn o tb e e n p e r f e c t ，t h ev qc o m p r e s s i o ns t a n d a r dh a sn o tb e e nb u i l da tp r e s e n t t h i s p a p e rh a sd e e p l yr e s e a r c h e dt w ok e yt e c h n i q u e so fv q ，c o d e b o o kd e s i g n a n dc o d e w o r ds e a r c h ，a n di m a g ec o m p r e s s i o na l g o r i t h mb a s e do nv e c t o r q u a n t i z a t i o n i nc o d e b o o kd e s i g na l g o r i t h mr e s p e c t ，f o rd e f e c t so fc l a s s i cl b g a l g o r i t h mh e a v i l yd e p e n d e n to nt h ei n i t i a lc o d e b o o ka n dt h eg l o b a l o p t i m i z a t i o na l g o r i t h ml a r g ec o m p u t a t i o n ，an e wa l g o r i t h mt og e n e r a t e v e c t o rq u a n t i z a t i o ni n i t i a lc o d e b o o ki s p r o p o s e d ，c o m p o n e n tm e a n o r t h o g o n a ls e g m e n t a t i o na l g o r i t h m ( c m o s a ) c m o s ao r t h o g o n a l l y s e g m e n t s s a m p l es p a c eu s i n gc o m p o n e n tm e a nt om a k ef u l l u s eo f c o d e w o r d t h es o l u t i o nf o ra t y p i c a lc o d e w o r di sp r o p o s e d ，s ot h a tt h en e w a l g o r i t h mi s a l s os u i t e df o rn o n u n i f o r md i s t r i b u t i o n s a m p l e s t h e s i m u l a t i o nr e s u l t si n d i c a t et h a t ，b e t w e e nt r a i n i n gs p e e da n dq u a n t i z a t i o n d i s t o r t i o no ft h et w oc o n f l i c t i n gi n d i c a t o r s ，c m o s aa c h i e v e sab e t t e r b a l a n c et h a nt h ep r e v i o u sa l g o r i t h m s i nc o d e c o d es e a r c h a l g o r i t h mr e s p e c t ，t h i sp a p e r f o c u s e so n c o d e c o d es e a r c h a l g o r i t h mb a s e d o ni n e q u a l i t yp r i n c i p l ea n dm e a n v a r i a n c ep r i n c i p l e am o d i f i e de q u a l - m e a na n de q u a l - v a r i a n c en e a r e s t n e i g h b o rs e a r c hi sp r o p o s e d ，w h i c hh a sc o m b i n e dt h er a n g ea d v a n t a g eo f a b s o l u t ee r r o ri n e q u a l i t yp r i n c i p l ew i t ht h es p e e da d v a n t a g eo fm e a n v a r i a n c ep r i n c i p l e t h em e t h o d st os e l e c t i n gi n i t i a lm a t c hc o d e w o r da n d t od e c i d i n gs e a r c h i n go r d e rw e r ep r o p o s e d t h es i m u l a t i o nr e s u l t ss h o w t h a tt h e s e a r c h i n gs p e e d h a sb e i m p r o v e db ya p p r o x i m a t e l y 10 c o m p a r e dw i t ht h ef o r m e r i ni m a g ec o m p r e s s i o na p p l i c a t i o nr e s p e c t ，f o rc o r e l a t i o ns i d em a t c h v e c t o rq u a n t i z a t i o nc a nn o ta d a p t i v e l ya d ju s tb i t r a t e ，t w om e t h o d s ，m e a n m e t h o da n dv a r i a n c em e t h o d ，h a v eb e e np r o p o s e dt oi d e n t i f y ”h i g h - d e t a i l b l o c k ”a n d l o w d e t a i lb l o c k ”h i g h d e t a i lb l o c k sw h i c hi n c l u d er i c h d e t a i li n f o r m a t i o na lec o d e dw i t hh i g h e rb i t r a t e o rw i t hl o w e rb i t r a t e 硕士学位论文 t h es i m u l a t i o nr e s u l t ss h o wt h a tt h i sa d a p t i v ev a r i a b l eb i t - r a t ev qi m a g e c o m p r e s s i o na l g o r i t h mh a si m p r o v e dm o r ei nt h et h r e e i m p o r t a n t p e r f o r m a n c ei n d i c a t o r s o fc o d e i n g q u a l i t y , b i t r a t e ，a n dc o d i n g t i m e c o m b i n i n gh u f f m a nc o d i n go ns i d em a t c hv e c t o rq u a n t i z a t i o n ，an e w a l g o r i t h mi sp r o p o s e d t h es i m u l a t i o ns h o wt h a t ，b i t r a t eo ft h i sa l g o r i t h m a p p r o a c h st ot h el o w e rl i m i to ft h ei n f o r m a t i o ne n t r o p yt h e o r y , w h i l et h e d i s t o r t i o nd o e sn o ti n c r e a s e i tm a yb e c o m ear e f e r e n tm e t h o dt ob u i l d i n t e r n a t i o n a ls t a n d a r do f i m a g ec o m p r e s s i o n b a s e do nv e c t o r q u a n t i z a t i o n k e yw o r d s ：v e c t o r q u a n t i z a t i o n ，c o d e b o o kd e s i g n ，c o d e w o r ds e a r c h ， i m a g ec o m p r e s s i o n i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其它人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其它单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名： 日期：逊江年月丛日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名 导师签名i 隆生乏日期：盘弓生年上月丛日 硕上学位论文第一章绪论 第一章绪论 1 1 研究的背景、意义和目的 1 1 1 研究背景 计算机技术的飞速发展给人类社会带来了一场信息化的革命。多媒体技术和 互联网技术的广泛应用促使越来越多的数字图像信息需要存储、传输和处理。数 字图像的数据量是非常巨大的，这就给图像的存储和传输带来了极大的困难，数 字图像压缩存在必要性。例如，一幅分辨率为7 2 0 x 5 6 0 的真彩色无压缩图像的数 据量为9 6 m b i t ，若要进行实时传输，即使使用传输率为1 0 0 m b i f f s 的光纤也很难 满足要求；用4 7 g 的d v d 光盘进行存储，若以每秒2 5 帧的速度更新画面，也 只能存储约1 4 0 秒的内容【1 1 。同时，图像数据中含有大量的冗余信息使图像压缩 具有可行性。图像数据的冗余主要表现为：图像中相邻像素间的相关性引起的空 间冗余；图像序列中不同帧之间存在相关性引起的时间冗余；不同彩色平面或频 谱带的相关性引起的频谱冗余；还有其它冗余信息，如信息熵冗余、结构冗余、 知识冗余和视觉冗余等。综上所述，由于数字图像压缩同时存在必要性和可行性， 图像压缩编码研究和应用成为了目前信息技术中最为活跃的领域之一。图像压缩 编码技术可以追溯到1 9 4 8 年o l i v e 提出的电视信号数字化，至今已有五十多年 的历史【2 】很多新的压缩方法和国际标准相继提出，但是为了进一步提高压缩质 量、压缩比和压缩速度，图像压缩一直是一个研究热点课题。 矢量量化( v e c t o rq u a n t i z a t i o n ，v q ) t 3 】是一种2 0 世纪7 0 年代后期发展起来的 数据压缩技术。基于矢量量化技术的图像压缩方法是利用相邻图像数据之间的高 度相关性，将输入的图像数据序列分组【4 】，形成舻空间中的一个矢量，然后对此 矢量进行量化，只传输或存储量化地址，因而可以大大提高压缩率。由于矢量量 化技术从根本上利用了图像块内不同像素之间的相关性和相邻图像块之间的相 关性，可以达到比通常所用的标量量化更高的压缩比和重建质量，越来越受到国 内外学者的关注【5 】。矢量量化理论及其在数字图像压缩、数字水印、指纹识别等 领域的研究成果相继发表【1 1 。矢量量化在图像压缩领域展现出了很大潜力却未 得到充分利用，究其原因是目前基于矢量量化的图像压缩研究尚不成熟，相关理 论和算法优化急待解决。 在图像压缩必要性和矢量量化潜在优势背景下，提出了矢量量化技术及其在 图像压缩中的应用这一研究课题。 硕士学位论文第一章绪论 i 1 2 研究意义和目的 尽管矢量量化具有压缩比高、量化失真小的优点，在图像压缩领域有着巨大 的应用前景。国内矢量量化技术还停留在理论研究阶段，实际的矢量量化编码系 统并未见报道，更不必说实用的矢量量化产品。国际上，至今仍然没有形成基于 矢量量化的图像压缩国际标准。而采用标量量化的m p e g 、j p e g 2 0 0 0 、h 2 6 4 等图像压缩标准相继推出，这并不是说明矢量量化没有优势。其中重要的原因就 是，目前相关理论和算法问题还没有完全解决，尚无法找到低复杂度的全局最优 码书设计算法，在线快速码字搜索算法的搜索速度也有待提高，码书的标准与编 码的对象密切相关，不同的应用场合下码书的结构、码书的大小以及矢量的维数 都不相同，因此必需寻找自适应算法。正是因为矢量量化在图像压缩中有如此巨 大的应用潜力，而上述很多相关问题急待解决，才能形成统一的基于矢量量化的 图像压缩国际标准，所以本课题有重要的研究意义。 矢量量化三大关键技术是码书设计算法、码字搜索算法和码字索引分配算 法。本文主要研究码书设计算法和码字搜索算法以及矢量量化在图像压缩中的应 用。研究目的在于：在研究已有算法优缺点的基础上，探索失真更小的码书设计 算法、速度更快的码字搜索算法，提出具有自适应性的矢量量化技术及其在图像 压缩领域的具体实现方法，将改进算法应用于图像压缩实践领域，从理论上推动 基于矢量量化的图像压缩国际标准的建立。 i 2 z 矢量量化技术简介大里里儿仅小i 刨1 1 i 2 i 矢量量化的理论基础 矢量量化的理论基础是香农的率失真理论【1 2 】。1 9 5 9 年，香农定义了率失真 函数尺p ) 为：在不超过给定失真d 的条件下，编码系统所能达到的最小码率； 失真率函数d ( 尺) 为：在不超过给定码率r 的条件下，编码系统所能达到的最小 失真。 率失真理论可表述为：只要信源符号序列长度足够大，当每个符号的信 息率大于r ( d ) ，必存在一种编码方法，其平均失真可无限逼近d ；反之，若信 息率小于尺( d ) ，则任何编码的平均失真必将大于d 。 d ( j r ) 是在维数k 趋向无穷大时d k ( r ) 的极限。利用矢量量化，编码性能可以 任意接近率失真函数，其方法是增加矢量维数k 。率失真理论表明，矢量量化总 是优于标量量化，因为矢量量化能有效地应用矢量中各分量之间的相互关联性质 来消除数据中的冗余度。不过，率失真理论是一个存在性定理，并非是一个构造 性定理，它未给出如何构造矢量量化器的方法。贝格尔于1 9 7 1 年将香农率失真 2 硕十学位论文第一章绪论 理论称为数据压缩的数学基础【1 3 1 。 1 2 2 矢量量化的定义 量化是图像压缩系统中极其重要的一个环节，主要有标量量化和矢量量化两 种方法。最基本的标量量化每次只量化一个采样，并对所有采样都采用相同的量 化器进行量化，而且每个采样的量化都和其它采样无关。矢量量化则利用相邻采 样之间的相关性，在量化时用输出组集合( 码书) 中最匹配的一组输出值( 码字) 来代替一组输入采样值( 输入矢量) 。矢量量化的优点是解码简单、压缩比大。 基本的矢量量化器【1 4 】可以定义为从k 维欧几里德空间硝到其一个有限子集 c 的一个映射，即q ：融一c ，其中c = c y i c j r k , l _ ，) 称为码书，为码书大 小。该映射满足：q 0 k 硝) = 勺，其中x = ( x l ，x 2 ，x k ) i 为融中的k 维矢量，叫c p i ， c 砣，咖为码书c 中的码字，并满足 d ( x ，0 ) = m i n d ( x ，9 ) ( 1 一1 ) i ) j ) 其中，d ( x ，c j ) y 寸输入矢量x 与码字c j 之间的失真测度。失真测度一般采用平 方误差测度来描述，即 d ( x ，c j ) = 名l ( x t 一句) 2( 1 2 ) 当然，其它失真测度也是可以的，比如一维范数测度和无穷范数测度。 每一个矢量f o l x 2 ，x k ) 都能在码书c = c j l c jr k , l ，册中找到其最近 码字e p = q ( x k 舻) 。输入矢量空间通过量化器q 量化后，可以用划分 仁 s l ，& ，曲) 来描述，其中& 是所有映像到码字口的输入矢量的集合，即 s f 伍i ) = 句) 。这个子空间蜀，昆，曲满足： s j = x l d ( x ，c h = 。m i n d ( x , c , ) ，j 朋，l s ，2s ，s , p q s g = 矽 ( 1 - 3 ) jlx 2 ，、 + 。 ，、 + 、， 、 、， 。 、。 +， ， 、 一二7 乞 ，。 t ， 0 、，一，。 j ， + ， ? ， ， 、 、； + ，7 、， ，7 。+ 图1 1 矢量量化二维示意图 图1 1 为矢量量化二维示意图。二维空间被分为八个区域。所以码书规模 3 硕上学位论文第一章绪论 n = 8 ，矢量维数k = 2 。比特率r = l 0 9 2 n k = 1 5 b i t s s a m p l e 。这个结果也可以这样解释， 一个码字的索引可以用1 0 9 2 8 = 3 位表示，一个码字可以作为k = - 2 个样本的重建。 图中虚线区域叫做v o r o n o i 区域，符号代表输入矢量，+ 符号代表码字矢 量，即v o r o n o i 区域内所有输入矢量的质心。当然，v o r o n o i 区域的边界不一定 是直线，也可以是圆弧等。 矢量量化技术所要研究的问题可以通过图1 1 直观地表述，问题一：寻找最 合适的v o r o n o i 区域划分方法，使用码字矢量来代替该区域内所有的输入矢量引 入的失真最小；问题- - 当码书确定之后，对任意一个输入矢量，用什么方法可 以快速找到输入矢量与哪个码字最接近，而不必要一个一个地比较。问题一需要 研究码书设计算法，问题二需要研究码字搜索算法。 基本的矢量量化编码和解码过程如图1 2 所示。矢量量化编码器根据一定的 失真测度在码书中搜索出与输入矢量之间失真最小的码字，传输时仅传输该码字 的索引。矢量量化解码过程很简单，只要根据接收到的码字索引在码书中查找该 码字，并将它作为输入矢量的重构矢量。 固娑甲驾| 回p 甲鼍回 ；囱 il 豳 i 硕十学位论文第一章绪论 异程度，来选择与输入矢量最接近的码字。这种差异程度用失真测度来衡量。下 面介绍一些常用的失真测度。 1 ) 欧几里得测度 矢量x 与矢量y 之间的欧几里得测度定义为： d ( x ，j ，) = 忪一y i l 2 = 、压乌( x f y ， ( 1 4 ) 2 ) 厶误差测度，定义如下： d ( x ，y ) = 1 1x - y = 箧怎l 一y i i ，声 ( 1 5 ) 3 ) 。误差测度，定义如下： d ( x ，j ，) 2 罂鸶j 工，一y ，i ( 1 6 ) 4 ) 加权误差测度，权重w 一般为非负值，定义如下： d ( x ，y ) = 、：1w ，( 工f 一夕f ) 2 ( 1 - 7 ) 5 ) 均方误差和峰值信噪比 上述的各种测度是针对矢量而言的。均方误差( 肘距) 和峰值信噪比( 胱) 是信号处理领域更常用的表征重构失真的度量。对图像信号，m s e 和p s n r 分别 定义如下： m s e2 南篙名- ( x 玎一y ) 2 ( 1 - 8 ) p s n r = i o l g ( 2 b - 1 ) 2 m s e ( 1 - 9 ) 式中，m 和是图像的长宽尺寸，劫为原始图像像素，的为重构图像像素， 占为图像的灰度位数。 为了避免开方运算，本文在没有特殊说明的情况下，均采用平方误差测度， 也就是式( 1 - 4 ) 的平方作为失真测度。 1 2 3 3 复杂度 矢量量化的复杂度随维数的增大呈指数形式增加，主要分为时间复杂度和空 间复杂度。 时间复杂度定义为量化每个输入采样( 分量) 所需要的计算量，包括加减法、 乘除法和比较等。例如对输入矢量进行穷尽搜索编码，设码书大小为，矢量维 数为k ，失真测度采用平方误差测度，则每量化一个输入矢量的时间复杂度b 为 6 = ( 庀7 v ) 次乘法+ 【( 2 肛1 ) 7 v 】次加法+ ( 1 ) 次比较) 输入矢量 ( 1 - 1 0 ) 空间复杂度定义为量化器所需的存储容量。码书尺寸为维数为k 的基本 矢量量化器的空间复杂度为u = k n 。若量化器空间复杂度较高，存储量较大，则 硕七学位论文 第一章绪论 数据的存取时间会较长，也会影响量化器编解码的速度。 1 3 矢量量化关键技术及其研究现状 矢量量化的三大关键技术分别是码书设计算法、码字搜索算法和码字索引分 配算法。在矢量量化技术2 0 多年的发展过程中，学者们针对矢量量化中这三大 关键技术的不足之处，提出了多种改进算法。前两项技术最为关键，也是本课题 研究的对象。下面重点介绍前两种关键技术的研究现状，第三个关键技术只简单 介绍。 1 3 1 码书设计算法及其研究现状 矢量量化的首要问题就是设计出性能良好的码书。所设计码书性能的好坏直 接决定了重构矢量的质量，也决定了矢量量化系统的性能。码书的设计过程实质 上是对大量训练矢量进行最佳聚类的过程。用m 个训练矢量来设计尺寸为的 码书( 胗孙d ，实际上就是寻求一种最佳( 平均失真最小) 的划分，将m 个矢 量划分为个胞腔，每个胞腔的质心矢量作为码书的一个码字。用码字代替该 区域内的所有输入矢量时，平均失真最小。各种码书设计算法的目的就是寻求有 效的算法，使所设计出的码书尽可能接近甚至达到全局最优，并尽可能地减少计 算复杂度。 l i n d e 、b u z o 和g r a 3 ，【”l 于1 9 8 0 年提出来的l b g 算法是码书设计算法中的经 典算法，它催生了矢量量化技术的一个研究高潮，具有里程碑意义。之后很多相 关算法都是基于这一算法的。该算法的主要特点是简单直观、物理概念清晰、算 法理论严密和易于实现。但l b g 算法有3 个主要缺点：1 ) 在每次迭代的最佳划 分阶段，从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计算。 2 ) 初始码书的选择影响码书训练的收敛速度和最终码书的性能。3 ) 码书的自适应 能力不强。 在此后2 0 多年里，学者们针对经典算法的缺陷，相继提出了各种改进算法。 这些算法大致可以分为四类：( 1 ) l b g 改进算法。包括针对初始码书选择的改进 算法【16 1 ，如成对最近邻( p a i r w i s en e a r e s tn e i g h b o r ，p n n ) 算法【1 7 ，1 引、最大下降 法( m a xd e s c e n d ，m d ) 1 9 却】设计初始码书，针对减少码书生成迭代次数和提高 码书性能的设计算法【2 1 2 2 】以及加快码书设计速度的算法，如以熵序列收敛作算法 停止判据的码书训练算法【2 3 1 、以1 范数作为失真测度的码书训练算法【2 4 1 。( 2 ) 基 于神经网络的码书设计算法【2 5 3 0 】。如自学习神经网络码书设计算法【3 1 粕】、竞争学 习神经网络码书设计算法【3 5 。8 】和自组织特征映射神经网络码书设计算法【3 9 】等。( 3 ) 基于全局优化技术的码书设计算法 4 0 - 4 5 。如模拟退火码书设计算法m , 4 7 1 、遗传码 6 硕十学位论文第一章绪论 书设计算、法【4 8 ，4 9 】以及两者结合的遗传退火码书设计算法，禁止搜索码书设计算法 5 0 】、随机松弛码书设计算、法【5 1 1 等。( 4 ) 基于模糊聚类理论的码书设计算、法【5 2 , 5 3 】。 如模糊c 均值码书设计算澍5 4 1 、模糊矢量量化码书设计算法【5 5 5 9 1 和禁止搜索模糊 c 均值码书设计算法【6 0 6 l 】等。 各种改进算法相对于经典l b g 算法，性能已有很大提高。全局寻优能力提 高，设计的码书量化失真下降到越来越接近全局最优解，但是这种失真性能改善 是以耗费大量运算时间为代价的。为了探索量化失真和运算时间综合性能优化的 码书设计算法，这一领域仍然有很多研究工作要做。 1 3 2 码字搜索算法及其研究现状 矢量量化码字搜索算法是指在码书给定的情况下，在码书中搜索与输入矢量 失真最小的码字的算法。设给定码书为c = c j i q r k , 1 _ ，加，其中为码书尺 寸，尼为矢量维数。若输入矢量x 和码字c i 之间的失真测度为d 任，c i ) ，则码字搜 索算法就是采用一种算法找到输入矢量x 的最匹配码字岛，使 d ( 工，c ，) _ l 要璺d ( j ，c )(111)i-l ， 一 最简单的搜索算法是穷尽搜索( f u l ls e a r c h ，f s ) 算法，它需要逐一计算输 入矢量与所有码字之间的失真，并通过比较找出失真最小的码字。在尺寸为 的码书中搜索出一个输入矢量的最匹配码字，需要胍次乘法、n ( 2 k - 1 ) 次加法和 n - 1 次比较。f s 算法的计算复杂度由码书尺寸和矢量维数决定。高效率矢量量 化系统往往采用大码书和高维矢量，这时计算复杂度将非常大，故减少码字搜索 的计算负担是非常必要的。研究码字搜索算法的目的就是寻找快速有效的算法以 减少计算复杂度，并尽量使算法易于硬件实现。近年来，学者们也提出了一些快 速码字搜索算法，可归纳为以下几种：( 1 ) 基于不等式判据的快速码字搜索算法 6 2 - 8 1 】，由于失真测度采用平方失真测度，相当于欧氏空间中两点之间距离的平方， 这些特点使得许多常见不等式：如绝对误差不等式、均值不等式和三角不等式成 立，并成为快速搜索算法的数学基础。有效地运用这些不等式能够迅速地排除一 些码字。( 2 ) 基于变换域的快速码字搜索算法【8 2 ，8 3 】，主要是使用小波变换进行能 量集中，在小波域搜索。( 3 ) 基于金字塔结构的快速码字搜索算法【陴盯】，主要有 均值方差金字塔搜索算法。( 4 ) 自适应搜索范围及顺序的快速码字搜索算法【8 8 踟l ， 基本思路是根据矢量的特征值自适应确定搜索范围和搜索顺序。( 5 ) 变比特率的 码字搜索算法【9 5 1 ，针对上述几类算法比特率固定的缺陷，一些学者提出了快速 相关矢量量化编码算法和边缘匹配矢量量化编码算法等变比特率的码字搜索算 法。对细节丰富的图像块采用高码率，灰度平滑的图像块采用低码率，根据基于 拉格朗日极值法的码率控制原型矧，这种变比特率的方法可以降低整体失真。 7 硕士学位论文第一章绪论 1 3 3 码字索引分配算法及其研究现状 码书设计算法和码字搜索算法都没有考虑码字索引在信道中传输受噪声干 扰的问题。矢量量化编码系统在码书c = c j i 勺r k , l _ ，m 中搜索与输入矢量x 最匹配的码字q ，索引f 通过信道传输到接收端，如果信道没有噪声，则接收端 将收到索引i 。然后通过解码端的查表操作，从相同的码书c 中获得码字c i 作为 输出矢量来重建输入矢量x 。如果信道有噪声，则在接收端有可能收不到索引i 而收到索引j ，这样矢量量化器解码端将从码书c 中获得码字c j 作为输出矢量来 重建输入矢量x 。因为码字c i 不是输入矢量最匹配的码字，从而在解码过程中会 引入附加失真。可以通过对码字索引进行重新分配来减少这种额外失真。研究码 字索引分配算法就是在所有码字索引分配的方案中找出一种最佳或者接近最佳 的码字索引分配方案，使这种由信道噪声所引起的额外失真最小，并尽可能的减 少计算复杂度和码字搜索时间。 目前，己有一些学者提出了一些码字索引分配算法，最经典的是基于二元对 称信道模型的b s a ( b i a n r ys w i t c h i n ga l g o r i t h m ) 算、法t 9 7 】，这是一个寻找局部最优 的码字索引分配的算法。此后又有一些学者提出了如模拟退火码字索引分配算法 【9 8 】、遗传码字索引分配算法【9 9 1 和禁止搜索码字索引分配算法等改进算法【1 0 0 】。 1 4 本文的主要贡献及论文结构 矢量量化技术由于很好地利用了相邻图像数据之间的高度相关性，在图像压 缩领域具有潜在优势。本文重点研究矢量量化码书设计算法和码字搜索算法及其 在图像压缩中的应用。 本文的主要贡献有以下几个方面： 第一：在研究已有矢量量化码书设计算法的基础上，针对现有算法对初始码 书严重依赖的缺点，提出了一种新的矢量量化码书设计算法一分量均值j 下交分 割法。充分利用分量均值对样本空间进行正交分割，使初始码字尽量散丌，得到 充分利用。在量化失真和训练速度两个相互冲突的指标之间，相对于以往算法取 得了更好的均衡。 第二：在研究已有矢量量化码字搜索算法的基础上，针对现有算法搜索速度 慢的缺点，提出了结合改进绝对误差不等式删除准则和等均值等方差删除准则 的改进码字搜索算法，达到迅速缩小搜索范围，并在该范围内进一步快速搜索的 目的，搜索速度得到改进。 第三：将矢量量化技术应用于图像压缩，在已有方法的基础上，提出自适应 相关边缘匹配矢量量化图像压缩算法。利用了图像块的方差或者高低平均值差自 硕士学位论文第一章绪论 动识别图像块是“高细节块 还是“低细节块。对于细节信息丰富的图像边缘， 采用高比特率编码，对于平滑的“低细节块，采用低比特率编码。具有变比特 率性和自适应性。通过实验得到了采用边缘匹配技术后码字索引的分布规律，针 对其严重非均匀分布的特点，提出了s m v q + h u f f m a n 算法。实验表明，该算法 在不增加失真的条件下，编码码率逼近信息熵理论的下限，是一种非常接近理论 最优性能的算法，应用潜力巨大。 本文分为五章，其中二、三、四章是本文重点。论文结构安排如下： 第一章绪论。阐明了本课题的背景、研究意义和目的。并简单介绍了矢量量 化技术及其三大关键技术的研究现状。概述了本文具体研究内容和贡献。 第二章矢量量化码书设计算法。首先介绍了经典的l b g 码书设计算法，由 于经典算法严重依赖初始码书，对几种初始码书设计算法也作了简单介绍。重点 研究了码书设计新算法一分量均值正交分割法，分析了新算法原理，阐明了实 现步骤，解释了新算法对非均匀分布样本同样具有适用性的问题，并进行仿真实 验，对比研究新算法的优越性。 第三章矢量量化码字搜索算法。首先介绍了基于不等式判据和均值方差判 据的几种快速码字搜索算法，分析算法原理、实现步骤和优缺点。重点研究了改 进的等均值等方差码字搜索算法，给出了改进算法的原理和实现步骤，并进行软 件仿真。 第四章矢量量化在图像压缩中的应用。将矢量量化技术应用于图像压缩，首 先介绍了快速相关矢量量化图像压缩算法和边缘匹配矢量量化图像压缩算法及 几种改进算法。重点研究了自适应相关边缘匹配矢量量化图像压缩算法和结合哈 夫曼编码的边缘匹配矢量量化图像压缩算法，详细阐述了新算法原理和实现步 骤，并进行了仿真验证。 第五章结论与展望。概括了全文工作得到的结论，对未来工作进行展望。 9 硕上学位论文第二章矢量量化码书设计算法 第二章矢量量化码书设计算法 矢量量化码书设计，就是要从k 维矢量空间( 空间) 中选出个码字， 使用最近码字来量化旭旧个输入矢量使失真和最小，这个码字组成码书。 寻找量化失真小、训练速度快的码书，就是矢量量化码书设计算法所要研究的问 题。矢量量化码书设计算法是矢量量化技术最根本的问题。码书失真关乎到整个 压缩系统的峰值信噪比、压缩率等性能。本章首先讨论构造矢量量化器的最优条 件，然后介绍经典l b g 码书设计算法和几种初始码书设计算法，重点研究码书 设计新算法一分量均值正交分割法。 2 1 矢量量化器的最优条件 矢量量化器的主要任务是，确定一个码书以及划分规则，根据该码书及划分 规则量化输入矢量序列，使平均量化失真最小。编码器完全可由输入矢量空间 破的某个划分来描述，这里假设输入矢量空间被划分为个胞腔 s = 豳1 ，s 2 ，知) ，解码器完全由码书c = c j l c jr k , l s - ，) 确定。因此，最优矢 量量化器的必要条件至少可用三个条件来描述，即给定码书的最优划分条件( 最 近邻条件) 、给定划分的最优码书条件( 质心条件) 以及前两个条件都满足时附 加的零概率边界条件。在研究码书设计算法时，可以将这些必要条件作为指导思 想。 最近邻条件和质心条件是标量量化器的直接推广，下面先从标量量化的情况 进行数学推导，给出这两个条件的理论基础。 假设连续随机变量x 在区间厶上的概率密度函数为f x ( x ) ，厶划分为个互 不相交的区间= ，t q + 1 ) ，q = o ，l ，l 。每个区间的量化值依次为均。下面数学 方法求解怎样的小蜘使量化失真d 最小。 d = 脚n - ip o y 七) 2 g ( 2 1 ) d 取极值时必满足：d 关于岛、肋的偏导数都等于零。 d x 寸白求偏导，产生o g 一均一1 ) 2 o g ) 一( t q - y q ) 2 a o g ) = o ，对白求解方程得 南= 丝学，g = l ，2 ，n 一1( 2 2 ) 类似地，对求偏导产生 p x f x ( x ) d x 6 5 蒜g 2 1 2 一12 - 3 1 0 硕上学位论文第二章矢量量化码书设计算法 式( 2 2 ) 和式( 2 3 ) 构成了矢量量化器的基本条件。式( 2 2 ) 意味着量化器决策区 域的边界应该在量化点的中间，也就是说输入z 被编码为与工最接近的码字， 这就是最近邻条件。式( 2 3 ) 意味着码字均应该位于区域岛的质心，这就是质心 条件。 同时可以看到，上述推导是通过求d 的极值得到的，事实上，我们所要求的 是d 的最小值，最小值是所有极小值中最小的一个，因而，这些条件是必要条件 而非充分条件。 2 1 1 最近邻条件 最近邻条件是在码书已经确定的情况下，具有最小失真的胞腔划分所要遵循 的准则。按照这个条件进行的划分，是所有码书相同的划分中，失真最小的划分。 码书确定以后，输入矢量的最优划分应满足最近邻条件。也就是说，任何一 个输入矢量，应该映射到与它最近邻的码字。矢量空间的任何一个矢量而，如果 它与码字c i 的失真，比与其它任何码字之间的失真都小，那么该矢量就应归到胞 腔r f 中，胞腔r ，中的所有矢量用码字q 量化。 最近邻条件：设给定训练矢量集x = i 着a r k ，l f s m ) ，码书 c = c j i c y r k , 1 筝，则输入矢量空间的最优划分s = 豳l ，s 2 ，s n ) 满足： 墨= 扛l d kc ；) = m i n d ( x , c j ) ，1 f ( 2 - 4 ) l 纠s 最近邻条件表明，舻空间的任何一个矢量x i ，属于且只属于一个胞腔。如果 鼍只与其中一个码字c i 的失真最小，那么它自然归属到c i 代表的胞腔风中；如 果，该矢量同时与两个或两个以上的码字之间的失真最小，那么约定该矢量归属 到其中序号最小的胞腔中。 显然，当码书已经确定的情况下，对于每一个输入矢量，把它映射到与它最 近的码字量化失真最小，更换到其它任何码字都将增大量化失真，这就是最近邻 条件的直观解释。 通常把满足最近邻条件的划分叫做v o r o n o i 划分，对应的胞腔叫做v o r o n o i 胞腔。 2 1 2 质心条件 质心条件是在胞腔已经确定的情况下，具有最小失真的码字所要遵循的准 则。按照这个条件确定的码字，是在胞腔不变的情况下，失真最小的码字。 矢量量化器的第二个最优必要条件是质心条件，也就是在划分已经确定的情 况下，求得胞腔的质心，由所有质心构成最优码书。 硕士学位论文第二章矢量量化码书设计算法 质心条件：对于给定划分s = 两，s 2 ，s u ) ，最优码字必须是相应胞腔的质 心，即： c j = 志谲 ( 2 - 5 ) 式e o l l 昌l l 表示胞腔s 中所包含的元素个数。 从式( 2 5 ) 可以看出，除数i i s a l 必需非零，也就是说，任何一个胞腔包含的元 素个数不能为零。如果某个胞腔内的元素个数为零，就是所谓的空胞腔问题，对 于空胞腔，也就没有质心可言。事实上，存在空胞腔的码书必定不是最优码书， 因为可以将代表这个空胞腔的码字去掉，在其它失真大的区域增加一个码字，这 样失真肯定是下降的。在实际设计过程中，如果发现有空胞腔，应及时处理，具 体处理方法将在2 2 节论述。 2 1 3 零概率边界条件 上面两个必要条件是标量量化器的直接推广，这些条件是量化器优化的基 础。这两个条件是必要非充分的，本节讨论第三个必要条件进一步测试量化器的 最优性。 给定满足最近邻条件和质心条件的矢量量化器，设 白) 为重构矢量集， 母) 为划分胞腔集，而 s ：) 为如下集合： s ，= xld ( x ，c j ) d ( x ，c f ) ) ，v l f ( 2 6 ) s ；包括最近邻胞腔昌和胞腔与的边界点，记集合哆= s ；一母为s j 的边界点。 边界点上的矢量与两个或两个以上的码字之问的失真最小。这些矢量可以采用共 享这条边界的任何一个码字量化，都具有最小的量化失真。边界点没有固定的最 近邻码字，这就引出了零概率边界条件。 零概率边界条件：对于给定信源分布的码书最优必要条件是： p ( p b ) = 0 ( 2 7 ) j i 也就说，边界点出现的概率为零。给定这个条件的另一种说法是令输入矢量 拥有两个或两个以上等距离最近邻码字的概率为零，即： p ( x l d ( x , y ，) = 矾五乃) = l 鲤蛩以五乃) ，v i j ) = 0 ( 2 - 8 ) 对于连续随机变量信源，由于边界点所占体积为零，通过积分求得的边界点 概率自然为零。但对于离散信源，边界点的概率可能不为零，只要出现一个输入 矢量同时与两个或两个以上码字具有最小失真，该概率就不为零。但是由于该问 题对整体失真影响较小，目前又没有规范的处理办法，实际应用中一般不考虑该 1 2 硕士学位论文第二章矢量量化码书设计算法 问题。 2 2 经典l b g 算法 l b g 算法是由l i n d e 、b u z o 和g r a y 于1 9 8 0 年首先提出来的，以三个人姓 氏的首字母为缩写。该算法是矢量量化研究领域的经典之作，是后续研究的基础。 它基于最佳矢量量化器设计的最佳划分和最佳码书这两个必要条件，采用迭代方 法求得局部最优解。本节将着重讨论l b