（微电子学与固体电子学专业论文）快速搜索算法vq图像压缩解码电路系统的研究.pdf

独创性申明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学 位论文是我个人在导师指导下进行的研究1 = 作及取得的成果。尽我所知， 除特别加以标注和致谢的地方外论文中不包含其他人的研究成果。与我 一同工作的同志对本文所论述的t 作的任何贡献均已在论文中作了明确的 说明并已致谢。 本论文及其相关资料若有禾实之处，由本人承担一切相笑责任 论文作者箍名：丧p 扣3 月孑日 保护知识产权申明 本人完全了解两安理工大学仃关保护知识产权的规定即：研究生在 校攻读学位期问所取得的所有研究成果的知识产权属西安理工大学所有。 本人保证：发表或使用与本论文相关的成果时署名单位仍然为西安理工大 学，无论何时何地未经学校许可，决不转移或扩散与之相关的任何技术 或成果。学校有权保留本人所提交论文的原件或复印件允许论文被查阅 或借阅；学校可以公布本论文的全部或部分内容，可以采用影印、缩印或 其他手段复制保存本论文。 ( 加密学位论文解密之前后，以上申明同样适用) 论文作者签名：她导师签名： d 弘年3 月孑日 摘要 快速搜索算法v q 图像压缩解码 电路系统的研究木 学科：微电子学与固体电子学 作者姓名：张如亮 签名：龄塑 指导教师：高 勇教授( 博导) 签名：二黏显 余宁梅教授( 博导)签名：叁主搔 答辩日期： 摘要 矢量量化( v q ) 是近年米图像压缩研究中的重要技术，广泛应用 于浯音编码、音视频压缩和远程会议等系统中。在该技术中，减少运 算复杂度、降低平均编码比特率、提高恢复图像的质量和便于硬件实 现等方面是当前研究的主要方向。 本文首先利用图像内部的空间相关性，提出一种旨在降低平均编码 时州的超前预测相关矢量量化快速算法，并对其进行测试。测试结果 表明该算法在减少平均编码时间的同时，也降低了平均编码比特率。 其次，为减少每个矢量的编码时问，提出一种基于均值排序码书的快 速搜索算法，测试结果显示，该算法编码速度是穷尽搜索算法的二十 多倍，但是恢复图像的质量大大地降低了。为了弥补这个缺陷，在保持 该算法编码速度快这个优点的基础上，从结构并行性和码书排序结构两 方面对其改进，得到一种既提高了恢复图像质量，又适合v l s i 硬件实 本研究得到国家自然科学基金项目资助，基金号6 0 2 7 6 0 1 7 西安理工大学硕士学位论文 现的编码算法。最后结合各个算法的优点，综合考虑各方面性能，给 出个折衷的快速搜索算法，并且设计出与算法对应的编码电路系统。 该编码电路的f p g a 实现及f p g a 验证结果表明，本文提出的快速算 法大大地减少了编码时间、有效地提高了恢复图像质量，同时也降低 r 硬件实现的难度。 关键词：矢量量化快速搜索算法恢复图像超前预测 ! ! ! ! ! ! ! ! r e s e a r c ho ff a s ts e a r c ha l g o r i t h m a n d d e c o d i n gc i r c u i ts y s t e mf o rv q i m a g e c o m p r e s s i o n s u b j e c t ：m i c r o e l e c t r o n i c sa n ds o l i de l e c t r o n i c s g r a d u a t es t u d e n t ：z h a n gr u l i a n g t u t o r ：p r o f g a oy o n g p r o f y un i n g m e i g r a d u a t ed a t e 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 ni m p o r t a n tt e c h n o l o g y i nt h ef i e l do fi m a g e c o m p r e s s i o n ，w h i c hi sw i d e l yu s e di nv a r i o u sa p p l i c a t i o n ss u c ha ss p e e c hc o d i n g 、 a u d i oa n dv i d e oc o m p r e s s i o n a n d1 e 】c c 。n f e r e n c i n gs y s t e m si h ec u r r e n tr e s e a r c h e s i n c l u d eh o wt oc u td o w nt h ec o m p u t a t i o nc o m p l e x i t y ，h o wt or e d u c et h ea v e r a g e c o d i n gb i tr a t e h o wt oi m p r o v et h eq u a l i t yo fr e c o n s t r u c t e di m a g e ，a n dw h i c h a l g o r i t h mt ob es u i t a b l et ov l s ii m p l e m e n t a t i o n i 1t h i sp a p e r , f i r s t l y ，b a s e do ni m a g es p a t i a lc o r r e l a t i o n ，af a s ta l g o r i t h mn a m e d a d v a n c ep r e d i c t i v ec o r r e l a t i o nv q ( a p c v o ) i sp r e s e n t e d w h i c ha i m sa tr e d u c i n g t h ea v e r a g ec o d i n gt i m 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 ea l g o r i t h mh a v en o to n l y c u td o o mt h ea v e r a g ec o d i n gt i m e ，b u ta l s or e d u c e dt h ea v e r a g ec o d i n gb i tr a t e t h e n ， i no r d e rt or e d u c et h ec o d i n gt i m eo fe a c hi m a g ev e c t o r ，af a s ta l g o r i t h mb a s e do n ! 堕墨三垄兰壁主堂堡堕叁 m e 8 “一o r d e r s e a r c hi sp r o p o s e d t h es i m u l a t i o nr e s u l t so ft h i sa l g o r i t h ms h o wt h a i t s 。o d i “gs p e e di st w e n t yt i m e sf a s t e rt h a nt h a to ff u l ls e a r c ha l g o r i t h m ( f s ) ，b u ti t s 。e 。o “s t 。“。l 。d i a g ei sb a d l yr u i n e d f o ro v e r c o m i n gt h i sd i s a d v a n t a g ea n dk e e p ir l g 1 5 8 d ”a “t a g eo fs h o r tc o d i n gt i m e ，w ei m p r o v et h ea l g o r i t h mo nt h et w oa s d c c i so f 8 l r u 。l l l ”p a r a l l e l i s ma n dc o d e b o o ko r d e rs t r u c t n r e ，t og a i nab e t t e rc o d i n ga l g o r i t h m “h i c hm e e t st h e r e q u i r e m e n to fr e c o n s t r u c t e di m a g ea n dv l s i i m p l e m e n l a t j o n f i n a l l y ，c o n s i d e r i n gt h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e s ea l g o r i t l l m s ai r a d e o f f 8 l g o r i t h mi sp r o p o s e d - ac o r r e s p o n d i n gv l s ic o d i n gc i r c u i ts y s t e mi sd e s i g n e da n d v e r i f i e dw i t hf p g a t h ef p g ap o s t s i m u l a t i o nr e s u l t sp r o v et h a tt h ei r a d e o 行 8 l g o r i t h mi sa ne f f e c t i v ef a s ts c a r c ha l g o r i t h mo fv q c o d i n go nt h et h r e ea s p e c t so f 7 。d “。i n gt h ec o d i n gt i m ei m p r o v i n gt h er e c o n s t r u c t e di m a g eq u a l i t ya n dl o w e r i n g t h ed i f f i c u l t yo fv l s ii m p l e m e n t a t i o n k e y w o r d s ：v e c t o rq u a n t i z a t i o nf 如ts e a r c ha l g o r i t h m r e c o n s t r u c t e di m a g e a d v a n c ep r e d i c t i v e 、， 第一章绪论 1 绪论 1 1 研究背景 近年来，i n t e r n e t 的高速发展和多媒体通信技术的不断更新换代， 极大地推动了图像和视频技术的研究。另外，数字电视、电视会议和 虚拟现实都产生大量的数据，超出实际可用的带宽和储存容量，因此， 图像视频需要高效的压缩算法。例如，目前的高分辨率电视( h d t v ) ， 其数据量高达1 2 g b i t s ，存1s 的h d t v 图像就需要两张普通光盘，如 此高的数据量即使以1 0 0 m 的带宽来传输，也需1 2 s ，因此只能采用专 用网络进行传输。 虽然表示图像需要大量数据，但图像数据是高度相关的：一幅图像 的不同部分及时问上连续的相邻图像之间有大量冗余信息。在一幅图 像内部，相邻图像小块或相邻像素之间，会存在某种关系，可以根据 一部分对另一9 部分进行预测，因而这两部分内容中存在可以不需存储 或传输的冗余信息。冗余信息一般可分为以下几类： ( 1 ) 编码冗余：如果图像的灰度级在编码时用的编码符号数多于表 示每个灰度级实际所需的符号数，则用这种编码得到的图像包含编码 冗余。 ( 2 ) 像素间冗余：一种图像中与像素间相关的直接关系。因为任何 给定像素的值呵以根据j 这个像素相邻的像素进行适当的预测，所以 单一像素对于一幅图像的多数视觉贡献是多余的，它的值可以通过以 其相邻像素值为基础进行推测。像素间冗余有空问冗余、几何冗余和 帧j 旬冗余等几种命名来表示。 ( 3 ) 视觉冗余：人类对图像信息的感知并不涉及对图像中每个像素 值的定量分析。通常，观察者寻找可区别的特征，比如边线或纹理区 域，然后在大脑中将它们合并成可识别的组群，并与先前已有知识联 西安理工大学硕士学位论文 系米完成图像的解释过程。 图像编码的目的就是尽可能地消除冗余信息，从而降低图像表示的 比特数，高效的图像压缩算法是其关键技术之一。传统的编码技术1 2 j 分为有损压缩和尤损压缩，常见编码技术有脉冲编码调制( p c m ，p u l s e c o d em o d u l a t i o n ) 、熵编码( e n t r o p yc o d i n g ) 、变换编码( t r a n s t b r m c o d i n g ) 、予带编码( s b c ，s u b b a n dc o d i n g ) 、小波变换( w a v e l e tc o d i n g ) 等。这几类编码以信息论和数字信号处理为理论基础，主要消除图像 数掘的线性相关性等冗余信息，压缩比可达l o 2 0 倍，并保持较好的 图像质量。第二代图像编码方法不局限于信息论的框架，要求充分利 用人的视觉系统和心理特点及其基于对图像内容的理解上获得高压缩 比 l 。在实际应用中，各种编码不是孤立的，而是综合应用的。这体现 在各种图像压缩标准中，如j p e g ( j o i n tp h o t o g r a p h i ce x p e r t sg r o u p ) 标准【4 】就是d c t 变换+ 标量量化+ h u f f m a n 编码+ 游程编码的混合编码方 案。h2 6 x i 。6 1 和m p e g f7 。8 1 系列标准是变换编码+ 变长编码+ 运动补偿的 混合方案。 上述算法大多适用于动态图像，在实际中已有广泛应用，但因其算 法复杂，硬件实现难度较大，不利于实时图像压缩与传输；而矢量量 化( v e ，v e c t o rq u a n t i z a t i o n ) 技术由于算法复杂度较低，解码结构简 单，压缩率较高，便于实时传输，已成为近年来静态实时图像压缩算 法及对应硬件实现的研究热点。冈此，本沦文将对其算法及相应的编 码系统电路进行研究。 矢量量化虽属于静止图像编码范围，但所提出的算法也适合动态实 时图像。它是标量量化的推广，它把标量量化的分别量化单个采样值 推广到多个采样值当成整体量化。矢量量化的优点是明显的，当码率 给定时，如果维数任意大，矢量量化可以任意接近率失真下界一j 。与 j p e g ( d c7 f - b a s e dc o d i n g ) 、基于小波的变换编码、分形编码相比，大 量的实验研究对比也显示了矢量量化在压缩比、失真、编解码结构上 第一章绪论 都比较优秀l i 。因此早在8 0 年代初，就有针对矢量量化的大量研究 工作，现在它在语音、图像、视频压缩中被广泛应用1 1 - 1 4 1 。 1 2 研究目标 图像矢量量化的概念可简单描述为，在编码端，v q 把待压缩的图 像分割成小块( 称为矢量) ，从预先准备好的码本集合( 码书) 中选取 与其距离最近的图像块( 码字) 来匹配，然后传输虽佳匹配码字的索 引号，从而图像的压缩率由码书的大小来决定：在解码端，根据传过 来的索引号在预先准备好的相同码书中找出该索引号对应的图像块， 重构图像，进而完成图像的解压缩( 解码) 。因此，矢量量化有较高的 压缩比和简单的解码结构。 矢量量化有阴个重要特点【】5 1 ： ( 1 ) 是一种渐进率失真方法界的方法； ( 2 ) 解码结构简单： ( 3 ) 能够实现给矢量的分量分配分数比特数； ( 4 ) 能够利用相邻数据的统计相关性。 v o 系统由编码器和解码器构成，编码器由码书存储器、搜索器和 索引分配器三部分组成，解码器只实现查表操作。所以矢量量化系统 设计的关键是v q 编码器的设汁中的码书存储器和搜索器的设计，而索 引分配器的作用是，它呵利用矢量间的相关性等特点来减少需传输的 索引比特数，进一步提高压缩率。码书存储器的结构随着搜索器所采 用搜索算法的不同而不同。尽管文献中已提出多种快速搜索算法来提 高v q 编码速度，但这些算法大部分基于软件实现，基于硬件实现的那 部分算法分别是用d s p 或v l s i 实现的。 文献中常见的v q 编码器的v l s i 实现方法，主要有s a ( s y s t o l i c a r r a y , , 心脉阵列) 1 6 1f m p p v q ( f u n c t i o n a lm e m o r yp a r a l l e lp r o c e s s o r v q ) 17 1 和p v q ( p a r a l l e ls t r u c t u r ev q ) 等几类。s a 结构的v l s i 西安x _ r - 大学硕士学位论文 实现方法虽然在实现乘法运算方面比较理想，但乘法运算带来的运算 复杂度比起单纯的加法运算和比较运算要高的多，而且运算本身耗费 硬件资源也比较大。f m p p 是一种内存基s i m d ( s i n g l e i n s t r u c t i o n m u l t i d a t a ) 共享总线并行处理器结构，它在每个p e ( p r o c e s s o re l e m e n t ) 中集成l l l e m o r y 和a l u ，所有p e 由共享总线连接起来，这样每个p e 就相当予一个m e m o r y ；这种结构可以有效的打破“冯诺依曼瓶颈”，提 高系统运算性能。f m p p v q 中的每个p e 由1 6 个8 位的s r a m 和一 个12 位a l u 组成。p v q 结构中搜索器部分由多个并行的m i m d ( m u l t i i n s t r u c t i o nm u l t i d a t a ) 结构的工作处理器组成，并行类型有两 种，图像矢量并行和码书并行，更适合于码书较大、矢量块较人的低 比特率图像压缩处理。 木论文将通过对上述v l s i 实现结构和现有文献中各种快速v q 搜 索算法的研究，综合考虑减少编码时州、保证恢复图像质量和降低算 法的硬件实现难度等几个方面，试图提出一种比较简单实用的快速搜 索算法，并设计出基于该算法的编码系统的v l s i 实现结构，最终给山 f p g a 验证结果。 1 3 论文工作概要 首先，本论文介绍了研究背景、研究目标和图像矢量量化的理论知 i j ，后者包括矢量量化的基本原理、相关概念、码书设计知识及编码 快速搜索算法的研究。其次，在对现有文献的研究的基础上，针对本 论文的研究目标，分别提出超前预测矢量量化算法、四分算法及其改 进型算法等几种快速算法，并给出各自的实验结果，然后综合上述算 法的优点，给出一个折衷的快速搜索算法及其实验仿真结果：为验证 综合算法的有效性，设计了算法对应的编码电路系统，并完成了该系 统的f p g a 实现与基于f p g a 的后仿验证。最后，对论文工作做出总 结并给出结论。 第二章图像矢量量化 2 图像矢量量化 2 1 矢量量化基本原理 矢量量化的理论基础是香农的率一失真理论。根据该理论，即使信 源是无记忆的，利用矢量编码总能在理论上得到更好的性能。矢量量 化可看作标量量化的推广，其定义【l9 】如下： 定义2 1 维数为k ，尺寸为的矢量量化器q 定义为从k 维欧几 里德空间到一包含个输出点的有限集合c 的映劓，即9 ：舻一c ， 其中c = 儿，y t ，y 、一1 ，只r ，f r = ( o ，l ，n l 。集合c 称作 码书，其尺寸为n ，码书的n 个元素称作码字或码矢量，它们均为r 中的矢量。 一个矢量量化器可分解为编码器和解码器两部分。编码器s 是从 彤到索引集合r 的映射；而解码器d 是从索引集合r 到重构集合( 码 书) c 的映射，即 ：r 。 f ，d ：r c( 2 1 ) 若给定输入矢量空问的一种划分，则可以完全确定某个输入矢量的编 码索引。另一方而，若给定码书，则可以通过简单查表操作确定相应 的重构矢量。实际上编码器的任务就是确定输入矢量在哪一个胞腔巾， 甚至可认为编码过程根本不需要码书。另一方面，解码过程只是一个 简单查表过程，只需要码书参与，并彳i 需要知道胞腔如何划分。对大 多数实用矢量量化器来说，由于码书可隐含地确定胞腔划分，故编码 操作可通过码书米完成。山此见，整个矢量量化可看作两部分操作 的级联或复合，即 g ( x ) = d e ( x ) = d ( f ( x ) )( 2 2 ) 为方便起见，有时认为编码器能同时产生索引号皤量化输出值q ( x 1 。 图2 1 表示如何通过编码器和解码器的级联来定义一个矢量量化器，而 西安理工大学硕士学位论文 基本的矢量量化编码、传输和解码过程如图2 2 所示。矢量量化编码器 根据一定的失真测度在码书中搜索出与输入矢量最匹配的码字。传输 时仅传输该码字的索引。矢量量化解码过程很简单，只要根据接收到 的码字索引在码书中查找该码字，并将它作为输入矢量的重构矢量。 矢量量化并不只是标量量化的简单推广。事实上，它是信号量化的 图2 1 矢量量化器示意图 输入 编码器 觥码器输h 匝弘牝西亘阿匦阉 囱囱 图2 2 矢量量化编码和解码示意图 “最终”解决方案，至今尚未有比矢量量化更好的编码技术。下面的 定理表明了矢量量化的性能可与任何给定的以矢量为处理单位的编码 系统十一媲美。 定理2 1若以矢量量化为单位的某编码系统将输入矢量映射到 n 个二进制数字之一并可用其找到相应重构矢量，则总存在码书尺寸为 n 的某矢量量化器具有同此编码系统完全一样的性能，即对任意输入矢 最，矢量量化器均能产生于给定编码系统相同的重构方案。 一般来说，用b 比特将一组k 维信号采样或参数进行量化编码的技 术，是一种分级设计的局部最优的编码技术。它将k 维输入矢量映射到 n ：2 6 个索引号之一继而再映射到个重构矢量之一。由于矢量量化可 第二章图像矢量量化 概括所有编码方案，人们自然会首先通过这种最通用的编码方法来寻 求最优的编码方案。对于给定的性能目标，总能找到最优的矢量量化 器，而并不存在能取得最佳性能的编码系统。在给定性能度量和给定 训练矢量集合条件下，如何设计最佳的码书使矢量量化编码器与解码 器同时达到最优，这是码书设计所要考虑的问题。 2 2 矢量量化的相关概念 任何传输或存储系统都有两个主要的设计目标：( 1 ) 性能尽可能的 好：( 2 ) 系统尽可能简单或成本低廉。然而这两个目标是冲突的，因 为良好性能的获得一股是以增加系统复杂度和成本为代价的。在压缩 编码硬件系统中，性能由编码速率和重构信号的质量或保真度来衡量， 而系统性能由比特率和系统复杂度束评估。下面从编码速率和比特率、 失真测度和复杂度三个方面描述矢量量化的几个相关概念【2 。 2 2 1 分辨率与编码速率 根据定义2 1 ，矢量量化器的分辨率、编码速率( 码率) 呵定义为 每个输入采样所需要的平均比特数。设码书大小为，矢量维数为k 。 对于基本的矢量量化器，由于每个码字索引所占的比特数为l 0 9 2 | v ，故每 一维分量所占的比特数即编码速率为r = ( 1 0 9 2 1 k 。它表明在码书性能 良好的情况下，用矢量量化器所能耿得的准确度和精确度，所以也称 之为分辨率。对于固定维数k 而言，分辨率由码书尺寸决定而与 存储码字的每一一分量所占用的比特数无关。 在数字通信系统中，矢挺量化编码器选择一个合适的匹配码字y ，来 近似描述输入矢量x ，并将被选中的码字的索引号i 传输( 以二进制形 式) 给接收器。然后，矢量量化解码器执行查表操作产生重构矢量y ， 西安理工大学硕士学位论文 它是原输入矢量的近似。如果系统的输入信号是一个矢量序列，即系 统处理的基本单位是矢量而不是标量，则每个输入矢量所需的比特数 称为比特率或传输率r ( 比特矢量) ，它可由r = k r 给出，其中r 为分辨 牢，女为矢量维数。若用f 来表示矢量传输速率，即每秒钟被编码的矢 量数，则每秒钟所传输的比特数为r ；= 幻，( 比特s ) 。 2 2 2 失真测度 矢量量化编码过程实质上足输入矢量与码字的匹配过程。模式匹配 的一个关键问题是矢量问差异的度量。失真测度d ( x ，y ) 表征输入矢量r 被重构矢量y 量化而产生的非负失真。在语音和图像处理中，人多数都 采用m i n k o w s k i 测度的特例。矢量x 与y 之间的p 阶m i n k o w s k i 测度， 或l p 测度( 也叫范数) ，定义为 j f d ( x ，j ，) - 4 1x y = ( 一y ，附 j = o i 种比较常见的特殊情况如下： ( 1 ) l 1 ( 绝对误差，也叫m a n h a t t a n 距离) 测度： d ( x ，y ) = l lx 一川，= i 一y ( 2 ) l 2 ( 欧几卑得，e u c l i d e a n ) 测度 ( 2 3 ) ( 2 4 ) j 女一l d ( x ，y ) 爿ix y 炉 f 一只1 2 ( 25 ) vi = 0 ( 3 ) l o o ( 切比雪夫，c h e b y s h e v ) 测度 讹y ) = 1 1x y 炉。m m a x i ix ，一y 1 ( 2 6 ) i 1 测度是常用的失真测度，因为它的计算不需要乘法，硬件实现 第二章图像矢量量化 比较容易。在码字搜索的软件实现时，经常使用e u c l i d e a n 测度，因其 几何意义明确。为避免开方运算，在实际计算中常常采用e u c l i d e a n 测 度的平方来代替。本论文中在编码系统的硬件实现时采用l 1 测度，而 在软件仿真时大多采用e u c l i d e a n 测度的平方。 上述测度是针对矢量而言，丽衡量整个输入信号和相应的重构信号 之间的失真( 即保真度) 常用均方误差( m s e ，m e a ns q u a r ee r r o r ) 、 信噪比( s n r ) 和峰值信噪比( p s n r ) 等测度。假如一幅m n 的l 级灰 度图像，原始图像像素为x ，而重构图像像素为 y 。0 茎，玉m l ，0 蔓j n 一1 ，贝0m s e 、s n r 、p s n r 分另0 定义如下： s n r = 1 0 l o g ： ( 一y 。) 2 ( 2 7 ) ( 2 8 ) 删= 1 0 x o g l 0 罐 ( 2 9 ) 图像矢量量化中一般采用p s n r 作为恢复图像的衡量标准。 2 2 3 复杂度 与标量量化相比，矢量量化的主要缺点是运算复杂度大，且复杂度 随矢鼍维数的增加呈指数形式增大，这是实现高维矢量量化器的手要 障碍。无沦从硬件考虑还是从软件考虑，复杂度有两种：时间复杂度 和空间复杂度。时间复杂度定义为量化每个输入矢量所需的计算量， 包括加减法、乘除法和比较等。空间复杂度定义为量化器所需的存储 容量。 9 兰攀 艇 西安理工大学硕士学位论文 度量矢量量化器的时间复杂度一般用两种办法：一是以每编码一 个输入矢量需用乘法运算的次数来衡量；一是以每编码个输入矢量 需用加减法、乘除法和比较运算( 即三元组) 的次数来度量。对丁| 基 本矢量量化器而言，设码书大小为，矢量维数为k ，若采用平方误差 测度，那么时间复杂度就可按这两种办法来度量。 ( 1 ) 仪用乘法运算次数度量每量化个输入矢量，其复杂度为 b = k n ( 次输入矢量) ( 2 1 0 ) 这足冈为妥对输入矢量进行穷尽搜索编码，需要计算这个输入矢量和 所有码字的平方误差测度，通过比较最小失真而找到相戍的码宁。缚 个失真计算需要 次乘法，所以计算次失真测度需要t 次乘法。 ( 2 ) 用三元组来描述容易得出，每量化一个输入矢量的时问复杂 度h 为 6 = ( ( 忉次乘法+ ( 2 女】) m 次加法+ ( m 1 ) 次比较 输入矢量 ( 211 ) 若用编码速率，和矢量维数k 来表示，则时间复杂度为 = ( 2 ) 次乘法十【( 2 女1 ) 2 “j 次加法+ ( 2 k r _ 1 ) 次比较 输入矢量( 2 1 2 ) 从式( 2 1 2 ) 可以看出，穷尽搜索矢量量化器的时间复杂度随维数和 量化器速率r 的增加呈指数形式增加，所以它的时间复杂度比较大。 虽然目| j i r o m 的容量不断增长，价格也不断下降，但若存储量很 大，则存墩时间则不能忽略。凶此，空间复杂度也是一个需要重视的 问题。穷尽搜索矢量量化器的空间复杂度u 可表示为 “= k n ( 213 ) 2 3 码书设计 第二章图像矢量量化 矢量量化的首要问题是设计出性能好的码书2 。码书的优劣直接影 响矢量量化的性能、编码效率及编码运算的复杂度。 假漫采用平方误差测度作为失真测度，训l 练矢量数为m ，目的是生 成含n ( m = 个码字的码书。码书设计过程就是寻求把m 个训练矢 量分成类的一种最佳方案( 使均方误差值最小) ，而把各类的质心矢 虽作为码书的码字。可以证明，各种，能的码书个数为 去洳1 c ， 素，；f ”c 一”， 其中c ：为组合数，尽管通过测试所有码书的性能可得到全局最优码书。 然而，在和m 比较大的情况下，搜索全部码书是根本不可能的。为 了克服这个困难，文献中的各种码书设计方法都采取搜索部分码书的 方法得到局部最优或接近全局最优的码书。因此，研究码书设计算法 的目的，就是寻求有效的算法，尽可能地得到全局晟优或接近全局最 优的码书，以提高码书性能，并尽可能减少计算复杂度。 一种文献中比较常见，且比较有效和直观的矢量量化码书设计算法 一g i ，a 算法( 也叫l b g 算法) 0 9 1 是由l i n d e 、b u z 0 和g r a v 于1 9 8 0 年首先提出来的。该算法基于最佳矢量量化嚣设计的最佳划分和最佳 码书这两个必要条件，且是劳埃德算法在矢量空问的推广，其特点为 物理概念清晰、算法理论严密及算法实现容易。由于算法简单和容易 实现，l b g 算法被认为是矢量量化器组织设计的基本方法。该算法可 以根据给定的训练序, 5 0 ，经过多次迭代运算，求出满足要求的输入矢 量的划分。其中训练序列足从具体的应用场合中选取典型图像，从这 些图像中取出图像子块的序歹0 。算法基本步骤如下： ( 1 ) 初始化：给定训练集合t = k r ，1 i 1 7 ) 、码书大小 ，( 其 中 0 、初始码书c o = c 岬f isj ) 、t 中矢量的 概率密度函数，( z ) ，置迭代次数t = 0 ，设未优化时最大量化失真d 一，= m ； 西安理工大学硕士学位论文 ( 2 ) 依掘码书c ，= f i m 划分训练集合7 和计算量化失真。 划分： p ( ( 1 ，) = 尺，1 月c7 ，i j 聊 ，且u 月：= 7 _ ，尺n 尺= 计算量化失真： d ，( q ) = e d ( x ，q ，( x ) ) = 1 p ( x ) d ( x ，q ( x ) ) 出 ( 2 1 4 ) ( 3 ) 若旦1 堕铲占，停止，否则转下一步： ( 4 ) 统计计算各个区域的质心作为新码字，更新码书： 设p 火x ) 是第i 次迭代过程中区域r 掣中的矢量的概率密度函数， ( 1 是区域月一的质心，则有： ( 7 = f x 叫= k ，印；，j ( x ) 出 ( 2 15 ) 令新码书( 1 。= c | j + 1 1l ls ， ，i = i + i 返回( 2 ) 。 但i , b g 算法有三个主要缺点：( 1 ) 在每次迭代的最佳划分阶段， 从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计 算。( 2 ) 初始码书的选择影响码书训练的收敛速度和最终码书的性能。 ( 3 ) 码书的自适应能力不强。码书设计的第一个缺点可采用各种快速 码字搜索算法来解决，但这些算法无法改善码书的性能。针对这些问 题，文献中提出各种改进的算法，这些算法大致可归为四大类：( 1 ) g i 。a 改进算法，包括针对初始码书选择的改进方法以及针对设计速度 的加速算法。( 2 ) 基于神经网络的码书设计算法，如自学习神经刚络、 竞争学习神经网络。( 3 ) 基于全局优化技术的码书设计算法，如随机 松弛算法、模拟退火算法、遗传算法和禁止搜索算法。( 4 ) 基于模糊 聚类理论的码书设计算法。 第二章图像矢量量化 2 4 矢量量化快速搜索算法的研究 矢量量化码字搜索算法是指在码书已经存在的情况下，对于给定的 输入矢量，在码书中搜索与输入矢量间失真最小的码字。 给定码书c = y 。，乃y 。只r ) ，其中n 为码书尺寸，如果矢 量x 与码字儿之间的失真测度( d i s t o r t i o nm e a s u r e ，d m ) 为娥奶) ， 则码字搜索算法就是找到码字y p 使j ( l y ，) 2 。r a ；i 。nd ( x ，y ，) 。如果采用 平方误差测度( s q u a r ee r r o rd i s t a n c e ，s e d ，也叫平方e u c l i d e a n 距离) 来播述，即 一l s e d = d ( x ，y ，) = ( ，一y , ) ? ( 2 t 6 ) = 0 对于t 维矢量，侮次失真运算需要次乘法、2 1 次加法，从而对 矢量f 进行穷尽搜索( f u l ls e a f c n ，f s ) 编码需要n k 次乘法、( 2 t 1 ) 次 加法和 ，、1 次比较。可以看出，计算复杂度由码书尺寸和矢量维数决 定。对于人尺寸码书和高维矢量，计算复杂度将很大。研究码字搜索 算法的主要目的就是寻求快速有效的算法以减少计算复杂程度。 一种快速有效的码宁搜索算法的三个必不可少的因素是：( 1 ) 良好 的初始匹配码字；( 2 ) 强有力的码字删除准则：( 3 ) 合理的码字搜索 顺序。显然，如果码字搜索开始于一个跟输入矢量比较接近的码字， 则随后的码字就易检验和排除。另一方面，如果码字删除准则非常有 效，则所需参加失真运算的码字数目将很少。 一种宵效的搜索算法往往需要附j u 运算量或额外存储空间。附加运 算量分为住线和离线两种存线附加运算量将占用编码时阿而离线 附加运算量并不占用编码时间。如何尽可能地减少附加运算量和额外 存储空问，是许多快速搜索算法必须面临的重要问题。另外，保证适 当的恢复图像质量和尽力降低编码比特率也是快速算法研究中需要考 西安理工大学硕士学位论丈 虑的重要问题。 针对穷尽搜索算法的缺点，许多文献提出各种各样的快速算法1 2 ”l ， 这些码字搜索算法町归结为以下几种：( 1 ) 基于不等式判掘的快速码 字搜索算法；( 2 ) 基于变换域的快速码字搜索算法；( 3 ) 基于金字塔 结构的快速码字搜索算法；( 4 ) 自适应搜索范围及顺序的快速码字搜 索算法：( 5 ) 降低比特率的码字搜索算法。这些算法虽然在提高运算 述艘和恢复图像的质量方面各有所长，但它们有一个共同的缺陷：都 是串彳j ：算法，硬件实现时不利于应用并行特性来减少编码利问。夺论 文通过人量的研究，将在第三章提出几种新的方法，逐步改善这方血 的缺陷。 第三章a p c v q 四分法快速搜索算法 3 超前预测算法与四分搜索算法 为改善文献中快速搜索算法在硬件实现方面的缺陷，本章将首先从文 献巾算法研究的共同目标，减少编码时间和保证恢复图像质量两个方面 进行研究，然后考虑算法的硬件实现问题，研究如何降低硬件实现难度。 减少编码时问可以从两个角度来考虑：减少一幅图像的平均编码时间 ( 也即总编码时间) ，减少图像中每个矢量的编码时间。为减少平均编码 时间，提高平均编码速度，我们可以考虑图像内部相邻区域的高度相关 性。利用这个特性，可以通过取消部分图像矢量的编码搜索运算，来减 少平均编码时间，具体研究在3 1 再中可见。 减少每个矢量的编码时间，意味着编码搜索时减少码字搜索的数量 更有利于硬件实现，但是，这样可能会削弱图像矢量与码字之问的最佳 匹配性能，印降低恢复图像质量。如何在算法中解决这个矛盾，本论文 将在3 2 节中对其进行研究，并提出一种兼顾减少每个矢量编码时间、提 高恢复图像质量和易于硬件实现三方面性能的快速搜索算法。在3 3 节将 根据前两节研究的结果，给出综合的算法及其测试结果。 3 1 超前预测快速算法及仿真实验结果 3 1 1 基本相关矢量量化算法 大家知道，在图像编码中，相邻图像块的相关性是很高的，这种相关 性主要表现在“低细节区”的平滑性以及“高细节区”的边缘连续性。 在平滑区域，这种相关性表现为相邻图像块的编码索引相同。考虑图l ( a ) 中的图像块，它的索引可以根据口、b 、c 、d 四个相邻块的编码索 引来预测。如果当前编码的图像块位置如图1 ( b ) 所示，即位于最后 列，则它的编码索引可通过n 、b 、c 三个邻块来预测。预测时，首先计 西安理工大学硕士学位论文 算x 与相邻块的失真测度d ，如果这几个失真测度的最小值小于预先设定 的阈值7 j ( 下标d 代表失真测度) ，则预测成功。这时可用2 比特信息来 表示邻块位置，即只需2 比特就可完成刈图像块的编码，解码时则根 耀对应位置的码字束设复。如果预测失败，则可以采用搜索算法来对其 编码。为区分这两种情况，需增加1 比特怍为标志位。 c6d 一 x 图3 1 ( a ) 四相邻关系图3 “b ) 三相邻关系 上述算法称为基本相关矢量量化快速算法( b f c v q ，b a s i cf a s t c o r r e l a l i o nv q ) ，其主要特点是比特率可变，且编码速度快，因为在预测 h , j ，最多先进行4 次失真运算，若预测成功则不必进行其他运算，否则 u 用前面提到的快速搜索算法来搜索最近邻码字。设将原始图像分割为 m 块( 女维) ，其中s 块预测成功，则该算法得到的平均比特率为： 月：! 兰型塑型业丝二旦 ( 3 1 ) 3 1 2 超前预测相关矢量量化算法 为了进一步提高预测效率、降低平均编码时间和编码比特率，尽量减 少重复预测时产生的运算量，本节提出一种新的超前相关预测方法 ( a d v a n c ep r e d i c t i v ec o r r e l a t i o nv q ，a p c v q ) 。该方法是用当前编码图像 块的索引值来预测未编码图像块的索引，同时用不同长度码长袭示编码 值， 第三章a p c v q 四分洳决速搜索算法 阼田脏 ( a )( b )( c ) 图3 2 超前预测中的几种相邻关系 a p c v q 算法步骤如下： 首先用搜索算法对图像块x 进行编码，然后对工的相邻块根据不同相 邻关系进行预测。预测时，先计算x 与相邻块的失真测度，当失真测度 值小丁= - 预先给定的阈值死，则对该矢量预测成功，此时将对应被预测矢 量的相邻关系标志置为l 。对被预测矢量编码时，则根据相邻关系标 志判断足否成功预测，如果已预测成功，则用2 比特表示编码结果，其 高位是码长标志，这里取i ，表示码长是2 比特，因此解码接收端只 取2 比特：低位表示相邻关系，0 代表水平相邻关系( x 与口) ，1 代表垂直相邻关系( x 与6 ) 。如果未成功预测，则用l 0 9 2 w 1 比特表示， 其最高位是码长标志，后l 0 9 2 n 位是对应的码书索引值，编码结构如图 33 所示。 篷勰尹 0 ，右相邻( 块口) i ，下相邻( 块b ) 码长标志l = 1 i ，= i ，码长取2 b i t s ( a ) 1 1 比特码长结构 b ) 2 比特码长结构 图3 3 两种长度的编码值结构( n - 1 0 2 4 ) 该算法预测时只进行两次失真运算，平均比特率为( m 、s 的含义同 ( 31 ) 式) ： 西安理工大学硕士学位论文 月：2 s + ( 1 0 9 _ , n + i ) ( m - s )( 3 2 ) m - k n ：b r ：c v q 方法巾，是用邻近的3 4 个图像块预测当前图像块，而 本文方法! | j 足以当前图像块来预测近邻的图像块。如图3 ，2 所示，考虑当 前图像块x 与图像块c 的相关性，如果x 只与c 满足相邻条件，而与 和b 不符合相邻条件，那么即使预测成功，也容易影响恢复图像的平滑 性；如果j 与n 或b 符合相邻条件，那么工与c 的相关性可由口或b 的 预测代替。因此，在本文方法中，预测时不考虑c 位置，这样既可以减 少预测运算量，又可以在预测成功时减少l 比特编码。 综合上述因素，本节提出的算法编码步骤如下： ( 1 ) 首先判断图像块的相邻关系标志，如果相邻关系标志为l ， 则表示当前图像块已被成功预测，此时可根据与相邻关系标志对应的相 邻天系，用2 比特码长来表示编码，并将高位置为l ，低位表示相邻 关系：否则转步骤( 2 ) ： ( 2 ) 用绝对误差排除算法( a e i ) f 2 4 对其进行编码，并用码长标志位 ( 最高位) 和码书索引来表示编码值，码长标志置为0 ，转步骤( 3 ) ； ( ：；) 分别计算当前图像块与不同相邻关系图像块的失真测度，如果 失真测度小于死，则对应位置预测成功，并设置相应的相邻关系标志， 转步骤( 1 ) ，对下一图像块进行编码；否则，直接转步骤( 2 ) ，对下 图像块进行编码。 由于本文采用了超前预测的方法，在对当前图像块编码时就预测束编码 矢量的编码索引，并且简化了预测中的相邻关系，从而不仅降低了预测时 的运算量，减少了预测时间，进而减少了平均编码时间，还同时降低了编 码的平均比特率。 第三章a p c v q 四分