（微电子学与固体电子学专业论文）相关矢量量化图像编码电路系统的研究.pdf

独创性申明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学 位论文是我个人在导师指导卜进行的研究工作及取得的成果。尽我所知， 除特别加以标注和致谢的地方外。论文中不包含其他人的研究成果。与我 一同工作的同志对本文所论述的工作的任何贡献均已在论文中作了明确的 说明并已致谢。 本论文及其相父资料若有不实之处，由本人承担一切相关责任 论文作者签名：曼苎叁矗。佯孑月。口 保护知识产权申明 本人完全了解西安理r ：大学有关保护知识产权的规定，即：研究生在 校攻读学位期间所取得的所有研究成果的知识产秘属西安理_ 大学所有、 本人保证：发表或使用与本论文相关的成果时署名单位仍然为西安理 二大 学，无论何时何地，未经学校许可。决不转移或扩散与之相关的任何技术 或成果。学校有权保留本人所提交论文的原件或复印件，允许论文被查阅 或借阅；学校呵以公布本论文的全部或部分内容，呵以采用影印、缩印或 其他手段复制保存本论文。 ( 加密学位论文解密之前后，以上申明同样适用) 论文作者签名：芝叁差导师签名：鲐口缛3 月伊开 墒要 相关矢量量化图像编码电路 系统的研究半 学科：微电子学与固体电子学 作者姓名：王冬芳 指导教师：高勇教授( 博导) 余宁梅教授( 博导) 答辩日期： 签名： 签名： 签名： 摘要 相关矢量量化是一种有效的数据压缩技术，因其具有较高的压缩率 而被广泛应用于各种图像压缩编码系统中。相关矢量量化由普通矢量量 化和相关性编码两部分组成。本论文在对相关矢量量化图像编码算法进 行深入分析的基础上，在两个方面提出了基于v l s i 技术的新算法，并 进行了v l s i 硬件设计、模拟仿真和时序验证。 首先，在普通矢量量化基础上提出了等和值块扩展最近邻快速码字 搜索算法( e b n n s ) ，该算法在图像画质达到穷尽搜索算法的前提下， 大大降低了码字搜索率和硬件实现面积；为了提高编码效率，在相关性 编码方面，提出了相关继承编码算法，对普通矢量量化后的编码索引进 行无损重编码。较大限度地利用了图像块之间的相关性及继承性，减小 了编码数据间的冗余，在保证不损失画质的前提下，有效地提高了图像 的压缩率。 同时，为保证系统的实时处理速度和降低硬件成本，在算法的v l s i 实现时采用串并结合和并行流水线等设计。采用了硬件描述语言v e r i l o g 对整个帽关继承矢量量化图像编码电路系统在c a d e n c e 系统上进行了 本研究得到国家自然科学基金项目资助，基金号6 0 2 7 6 0 1 7 西安理工大学硕士论文 设计、仿真及时序验证。模拟与验证结果均表明该电路系统可以获得约 6 0 m p i x e l s 的数据处理速度，不但能够满足图像实时传输的需要，而且 图像压缩率较高。 关键词：图像编码相关矢量量化矢量量化v l s i a b s t r a c t r e s e a r c ho nc i r c u i ts y s t e mo fc o r r e l a t i o n v e c t o rq u a n t i z a t l 0 nf o ri m a g ec o d i n g 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 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 es t u d e n t ：w a n gd o n g f a n g g r a d u a t ed a t e ： a b s t r a c t ： c o r r e l a t i o nv 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 et e c h n o l o g yf o r d a t ac o m p r e s s i o n i ti sw i d e l yu s e di nv a r i o u si m a g e c o d i n gs y s t e m sb e c a u s e o fi t sh i g hc o m p r e s s i o nr a t i o t h i st e c h n o l o g yi sc o m p o s e do fc o n v e n t i o n a l v qa l g o r i t h ma n dc o r r e l a t i o nc o d i n ga l g o r i t h m b a s e do nac o m p r e h e n s i v e r e s e a r c ho fi m a g ec o d i n ga l g o r i t h mf o rc o r r e l a t i o nv q ，n o v e la l g o r i t h m sa r e p r e s e n t e do nt w oa s p e c t si n t h i sp a p e r ，a n dc o r r e s p o n d i n gv l s ic o d i n g c i r c u i ts y s t e mi sd e s i g n e d ，s i m u l a t e da n dv e r i f i e d f i r s t l y , b a s e do nc o n v e n t i o n a lv q ，af a s ta l g o r i t h mn a m e de q u a l - s u m b l o c k - e x t e n d i n gn e a r e s tn e i g h b o rs e a r c h ( e b n n s ) i sp r e s e n t e d ，w h i c hn o t o n l yc a na c h i e v et h er e c o n s t r u c t e di m a g eo ff u l ls e a r c ha l g o r i t h mb u ta l s o c a ng r e a t l yr e d u c eb o t ht h ec o d e w o r ds e a r c hr a t i oa n dc h i pa r e a i no r d e rt o i m p r o v ec o d i n ge f f i c i e n c y , an e wa l g o r i t h mc a l l e dc o r r e l a t i o n - i n h e r i t a n c e c o d i n gi sp r o p o s e d ，w h i c hi s e m b e d d e di nc o n v e n t i o n a lv qs y s t e mt o i m p r o v ec o m p r e s s i o nr a t i ob yr e - e n c o d i n gt h ei n d e x e s i na d d i t i o n ，b o t ht h es e r i e s - p a r a l l e lc o n n e c t i o na n dp a r a l l e lp i p e l i n ef o r t h ec i r c u i ts t r u c t u r ea r ea v a i l e dt oc u td o w nh a r d w a r ea r e aa n di m p r o v e p r o c e s s i n gs p e e do ft h es y s t e m t h ew h o l ec o r r e l a t i o n i n h e r i t a n c ec o d i n g c i r c u i ts y s t e mi sd e s i g n e d ，s i m u l a t e da n dv e r i f i e di nv e r i l o gh d lo nt h e 西安理工大学硕士论文 c a n d e n c es y s t e m s ，t h es i m u l a t i o na n dv e r i f i c a t i o nr e s u l t ss h o wt h a tt h e o p e r a t i o ns p e e do ft h ew h o l es y s t e mc a r ta c h i e v e6 6 m p i x e l st os u p p o r tr e a l t i m ea p p l i c a t i o na n dg a i nh i g hi m a g ec o m p r e s s i o nr a t i o k e y w o r d s ：i m a g ec o d i n g ，c o r r e l a t i o n v e c t o r q u a n t i z a t i o n ，v e c t o r q u a n t i z a t i o n ，v l s i 课题背景及意义 1 课题背景及意义 1 1 课题背景 近二十年来，科学技术取得了飞速的发展。由计算机技术所带来的 信息革命使人类由工业化的社会进入了信息化的社会。多媒体技术和 i n t e r n e t 互连网技术的广泛应用加速了全球高速公路的建设，基于网络的 多媒体数据传输正改变着人类的生活方式。 科学实验表明，人类从外界获取的知识之中，有8 0 以上都是通过 视觉感知获取的。跟睛获取的是图像信息，幅图胜过千言万语，图像 信息是人类认识世界及人类自身的重要源泉。 然而，数字图像中包含的数据量巨大，如考虑中分辨率( 6 4 0 4 8 0 ) 下，全屏幕显示( f u l ls c r e e n ) ，真彩色( t r u ec o l o r2 4 位) ，全动作( f u l l m o t i o n ，2 5 3 0 帧秒) 的图像序列，播放1 秒钟的视频画面数据量为： 6 4 0 4 8 0 3 3 0 = 2 7 ，6 4 8 ，0 0 0 字节 相当于存贮一千多万个汉字所占用的空间。即使降低彩色性逼真要求， 量化为8 位灰度，每秒显示2 5 帧，数据量也达： 6 4 0 x 4 8 0 2 5 = 7 ，6 8 0 ，0 0 0 字节 如此庞大的数据量，给图像的传输、存贮以及读出造成了难以克服 的困难，例如在基于i n t e r n e t 的多媒体通信中，虽然目前国内的主干网速 率已达1 g b p s ，面向最终用户的局域网的速率也有1 0 m b p s 或1 0 0 m b p s ， 如此高的传输速率仍无法完全满足视频通讯等应用的巨大数据量。 图像压缩就是在没有明显失真的前提下，将图像的位图信息转变成 另外一种能将数据量缩减的表达形式。首先，尽管图像中数据量很大， 但数据之间不是完全独立的，图像中存在着各种各样的相关性或冗余信 息。即一部分数据可以由另一部分数据完全推算出来。其次，大部分图 像视频信号的最终接收者都是人眼，而人类的视觉系统是一种高度复杂 西安理工大学硕士论文 的系统，它能从极为杂乱的图像中抽象出有意义的信息，并以非常精练 的形式反映给大脑。人眼对图像中的不同部分的敏感程度是不网的，如 聚去除图像中对人眼不敏感或不重要的部分，对图像的主观质量是不会 有很犬嚣响的。 卜山于图像压缩的必要性和可能性，图像压缩编码研究成为个越 来越活跃的领域。在诸如摹于i n t e r a c t 的多媒体通信、可视电话、数字电 视，多媒体计算机等领域得到了广泛的应用。图像编码技术包括三个主 要方面： 1 11 ) ：图像压缩的新算法的研究。2 ) ：基于v l s i 技术酶压缩算 法的硬件实现。3 ) ：面向不同应用场合的压缩编码标准的制定。其中， 压缩算法的研究是图像编码技术的关键，丽基于v l s i 技术【2 7 1 的压缩算 法的硬件实现则是实现图像实时传输的一个重要手段。 目柏作为图像压缩的国际标准，彩色静止画符号化标准方式为 j p e g ( j o i n tp h o t o g r a p h i cc o d i n ge x p e r tg r o u p ) 1 8 1 、j p e g 2 0 0 0 引，彩色动 i 两符号化标准方式为m p e g 删( m o v i n gp i c t u r ec o d i n ge x p e r t sg r o u p ) 及 h 2 6 1 等。彩色静止图像符号化标准方式j p e g ，是以2 元d c t t 8 j ( d i s c r e t e c o s i n et r a n s f o r m ) 为基础。d c t 是通过频率分解的方法将图像从低频到禹 频避行分解，并利用分解后各项的系数进行信息量的压缩。虽然频率分 饵法的效率非常高，但是，其压缩、解码的算法极其复杂，不利于硬件 实现。而且，一旦进行了一次变换，利用图像特征进行图像信息的压缩 将变得翡常困难。因此，想要在保持画质基础上进。一步提高图像的压缩 率，仪采用频率分解法已不能满足要求，急需对充分利用图像特征的凰 像符号化技术进行丌发研究。彩色静止隧像符号化标准方式j p e g 2 0 0 0 是最新的压缩标准。它是以小波变换f 9 | ( d i s c r e t ec o s i n et r a n s f o r m ) 为基础。 小波变换是一种复杂的数学变换，可以在时域和频域上对原始信号进行 多分辨率分解，算法相对复杂，却也是一个可行的新颖研究方向，研究 者已在这方面取得了不少新成果。 虽然有各种图像压缩算法对图像进行压缩，但目前实现图像实时压 课题背景及意义 缩传输还是要靠图像压缩芯片，因此基于v l s i 技术的压缩算法实现，是 国内外研究的一个热点，取得了不少的研究成果。如美国模拟器件公司 ( a d i ) 公司发布的图像压缩芯片a d v - j p 2 0 0 0 】，是世界上首款支持 j p e g 2 0 0 0 图像压缩编码标准的芯片。国内也有单位在进行这方面的研 究，如清华大学集成电路与系统设计实验室正在研究的以小波变换为基 础的课题j 基于j p e g 2 0 0 0 的图像压缩芯片系统的设计，目前仍处于 研究阶段。鉴于图像压缩处理对民用尤其是对军用的意义重大，所以开 发出具有自主知识产权的性能优良的图像压缩芯片是非常重要的。而国 内目前还未有自主知识产权的图像压缩芯片问世，因此这是一个非常迫 切的工作。 为了普及可以传输接受图像的通信系统，特别是面向个人的携带型 设备，迫切希望能够开发出一种运算速度快、易于硬件实现的压缩解码 算法。针对这一问题，本论文对矢量量化【l2 l ( v e c t o rq u a u t i z a t i o n ，简称 v q ) 图像压缩解码系统芯片进行研究。矢量量化是一种解码非常简单的 数据压缩算法。这一算法在信号处理【 j 的领域被应用，特别是在圈像、 语音压缩【1 4 1 及图形识别【h 1 领域有着较为广泛的应用。但到目前为止，大 多用软件来实现算法，使得处理时间较长，不能满足图像实时处理的要 求。为了加快处理速度，基于v l s i 技术的硬件实现是一种必然的实现方 式。 1 2 课题的研究内容及承担的主要工作 该课题来自国家自然基金资助项目( n o 6 0 2 7 6 0 1 7 ) 量子码方式图 像压缩解码专用芯片的研究。该项目的研究目标是实现超过现行图像符 号标准化压缩能力的图像压缩解码专用芯片。首先确立以量子码( 即矢 量量化) 方式的图像压缩算法，并能够快速实现这一算法的硬件及系统， 该芯片开发成功，可实现普通电话线上图像的实时传输，填补我国在具 西安理工大学硕士论文 有自主知识产权的图像压缩解码专用芯片的空白。项目量子码方式强 像压缩解码专用芯片的研究的技术路线是：首先，进行特征图形数据 库最优化的研究。针对现行k o h o n n e n f 8 】自己学习等方法形成数据库对运 算量大、诧费时f a j 长，并且对于不同图像需要生成特定数据库的缺点， 我们将根据图像的次度分布特征，提出新型特征图形数据库生成方法。 运用这一方法，可以生成适用于各种图像的标准数据库。其次，我们在 原图像t i 数据库进行比较运算时，为了减少运算量，根据图像灰度变化 幅度，谓节被分割小块的尺寸，在图像荻度变化大的区域，进行可将图 像进行精密分割，如分成4 x 4 像素的小块。丽在图像狄度变化不大的区 域，则可将图像分割成较大的小块，从而大大减少运算量。另外，从系 统的构成和电路结构上将采用并行和多段串行楣结合的手法，并根据分 割盾小块图像内灰度平均值，排除大量不必要的运算。本研究将先通过 计算极仿真进行数据库生成及图像压缩算法的验证，然后进行电路系统 的设计、仿真，最后进行系统集成芯片的设计。在完成了静止画厩缩解 码处理后，进一步进行动画韵压缩解码的研究。 本论文的工作只是浚基金项目的部分研究内容，承担的主要任务是 图像压缩电路系统的设计，包括矢量量化算法的选择优化，从而排除大 量不必要的运算，减低硬件实现成本；以及采用并行和多段串行栩结合 的手法对硬件电路系统的进行设计优化。 1 3 论文的主要内容与研究成果 本硷文主要在高画质的基础上，设计出易于硬件间实现的高压缩率 的图像编码算法，同时基于v l s i 技术对算法进行硬件实现。具体包括以 下内容： i ) 快速码字搜索算法的研究及其硬件电路实现。该部分对穷尽搜索 算法f ”1 和分块搜索算法的性能进行了分析，并给出了它们的硬件愈路结 课题背景及意义 构，并在此基础上提出了一种新的性能优良的快速码字搜索算法一一等 和值块扩展最近邻搜索算法( e q u a l s u mb l o c k e x t e n d i n gn e a r e s tn e i g h b o r s e a r c h ) ，以下简称e b n n s 。该算法在图像峰值信噪比和保真度接近穷尽 搜索算法的情况下，码字搜索率仅为穷尽搜索算法的8 6 ，硬件实现而 积接近分块搜索算法，峰值信噪比和保真度却比它高很多，达到穷尽搜 索算法的编码质量。在硬件设计上根据各种算法的特点采用串并结合和 并行流水线等电路设计，即保证了系统的时序又大大降低了硬件面积。 2 ) 相关矢量量化图像编码算法的研究及其硬件电路实现。为提高图 像压缩率，而不影响普通矢量量化后图像的重构质量，我们对无损压缩 的相关矢量量化进行了研究。首先对基本相关矢量量化编码算法【l5 j 和 s t c t ”j 相关矢量量化算法的性能进行了分析，并给出了它们的硬件电路 结构，然后在此基础上提出了一种新的性能优良的相关编码算法一一相 关继承编码算法i 1 及其硬件结构。该算法在压缩率较前两种算法大为提 高的前提下，硬件实现的面积却比s t c 相关矢量量化算法大大降低，从 而提高了压缩系统的性能。 矢量量化技术简介 2 矢量量化技术简介 2 1 引言 数据压缩的主要目标是尽 可能减少传输或存储所需的比特率或者说 是给定通信系统的带宽和存储空闻。简单地说，数据压缩是为了在现有 系统特性( 如频带限制) 条件f 满足工作的要求，或者在新系统的设计 中降低成本。数据压缩方法的分类到目莳为止还没有统一的分类方法， 多数学者将数据压缩方法分为可逆压缩( 无损压缩) 和不可逆压缩( 有 损压缩) 两大类。雨量化是有损数据雎缩中常用的技术，它基本上分为 三种，即标景量化1 1 ”、矢量量化和序列量化f l ”。最基本的标量量化每次 只量化一个采样，并对所有采样都采用特性相同的量化器进行量化，而 每个采样的量化都和其他采样无关。矢量量化和序列量化则利用相邻采 样之间的相关性。矢量量化( v e c t o rq u a n t i z a t i o n ，v q ) ，在量化时用输出 组集合中最匹配的一5 组输出值来代替一组输入采样值。序列量化是在分 组或非分组的基础上，用一些i 临近采样的信息对采样序列进行量化。矢 量量化是对数据采样进行量化的有效方式。下面简单介绍一f 矢量量化 的基本原理，并列矢量量化中常用的几个相关概念进行解释。 2 2 矢量量化的基本原理 矢量量化的发展可追溯到1 9 5 6 年，出s t e i n h a u s j j 第一次系统阐述了 最佳矢量案化问题。1 9 7 8 年，b o z o 第个提出实际的矢量量化器。他的 髓化系统分两步：第一步将语音做线性预测分析，求出预测系数；第二 步对这些系数做矢量量化。1 9 8 0 年，l i n d e ，b u z o 和g r a y 将l l o y d m a x 算法推广“，发表了第一个矢量量化器设计算法一一l b g i l2 j 算法。这是矢 量量化技术研究的一个里程碑。从那以后人们对矢量量化的理论和应用 旋丌全面研究，包括各利，矢量量化器i 眩】、鹞书设计算法f 1 2 】、码字搜索算 6 西安理工大学硕士论文 法【1 2 l 、码字索引分配算法1 1 2 1 、图像的矢量量化压缩【1 2 l 、语音的矢量量化 编码和识别【1 2 】，矢量量化系统的硬件实现1 8 叫9 1 等等。 2 2 1 矢量量化的理论基础 矢量量化的理论基础1 2 0 j 是香农的速率失真理论。1 9 8 4 年，香农定义 了信道容量，并证明只要编码速率不超过信道容量，信号就能以任意小 的差错概率在该信道中传输。1 9 5 9 年，香农定义了速率失真函数r ( d ) ， 并证明只要r ( d ) 不超过信道容量就能保证接受端的失真不超过给定的闽 值d 。在数学上，r ( d ) 定义为在给定失真d 的条件下，系统所能够达到 的最小码速率。对于幅值离散的信源，r ( d ) 定义如下： r ( d ) = r r f i n p ( x ) p ( y x ) l 0 9 2 p ( y x ) q ( y ) ( 2 - 1 ) 其中g ( y ) = y e ( x ) ( x ) ，平均失真满足条件： ：p ( x ) p ( y x ) d ( x ，y ) d ( 2 - 2 ) 式中d ( x ，) 是失真测度，它表示输出采样值y 再现原始采样值x 所 引入的失真，p ( x ，y ) 表示在已发送x 的情况下接收到y 的概率。r ( d ) 的 单位为比特采样。同样，也可定义失真速率函数d ( r ) ，它是速率一失真 函数的逆函数，其含义为：在给定速率不超过r 的情况下，系统所能够 达到的最小失真。d ( r ) 和r ( d ) 所给出的编码性能极限，适用于所有信源 编码方法。d ( r ) 是在维数k 趋向无穷大时n ( j r ) 的极限，即 d ( r ) = l 墨d a r )( 2 - 3 ) 根据香农的这一理论，可找到一个最小的信源速率使得系统发送端 到接受端的平均失真不超过给定的失真闽值，这正是数据压缩系统所要 求做的事情。因此，贝格尔于1 9 7 1 年将香农的这一理论称为“数据压缩 理论基础”。从式( 2 - 3 ) 可知，利用矢量量化，编码性能可能已接近速 率失真函数，其方法是增加矢量维数k 。在实际应用中，数据失真函数 常常作为一个理论下界与实际编码速率相比较，分析系统还有多大的改 进余地。如果某系统的最高性能都不能满足系统或者客户的要求，人们 就不必浪费精力用给定的参数来设计出一个实际系统，因为永远设计不 矢量量化技术简介 出满足要求的系统，除非降低系统的某项性能指标。相反，如果一个实 际系统的性能已经接近于理论上界，则不应该褥投入更多的资盒和瓣嘲 美追求微不足道的改善。如果某系统性能傀予理论生界，刚必须怀疑该 系统模型的准确往。如果一一个系统的性能远劣于理论最优值，则一定可 用更好的编码技术获得性能改善。总之，速率失真理论指出了矢量蓬他 的优越性。 2 , 2 2 矢量量化的定义 根据香农的速率失真理论，即使信源是无汜忆的，利用矢量编码代 符标鼙编码总能在理论上得到更好性能。矢量量化可以看作标量壁纯豹 推广，定义如f ： 定义2 1 维数为k ，尺寸位n 的矢量量化器q 定义为从k 维欧几里 德宅削r 到个包含n 个输出( 霪构) 点的有限集合c 的映射，即 q ：r 啼c ，其中c = 虬，儿，y h ) ，* r ，i f ； o ，l ，n - l 。集台c 称作 码书，其尺寸( 大小) 为n 。码书的n 个元素作码字或者码矢量，它们 均为亢2 中的矢量。 输入矢量空问r 通过尺寸为n 的量化器q 后，被分割成n 个互不 重叠的区域或胞腔，这个过程称为输入矢量空间的划分。对i f ，胞飚是 定义为 r ，2 x r 4 ：q ( x ) 2 只 ( 2 - 4 ) 根弼上述胞腔的定义，容易证明u r , ；r ，且对i ，有r i n 是，= 彩 一个无界的胞腔称作过载胞腔，所有过载胞腔的集合称作过载区域。 一一个有界的脆腔称作粒状胞腔，所有粒状媳腔的集合称作粒状区域。集 合的一个重要性质是凸性。考虑二维或三维韵情况，如果连接集合审任 意两点的直线上的所有点仍属于这个集合，则该集合被称为凸集。相似 的概念嗣样可应用于中。设集合搿口+ f i a ) b s ，对于所有的0 掰 l ， 如果列任何口，b s ，总有o t a + ( 1 一c o b s ，赠s 为一凸集。在此基础主， 叮引入规则矢量量化器的概念。 西安理工大学硕士论文 定义2 2如果一个矢量量化器满足：a ) 每个胞腔r i 均为凸集， 并且b ) ，y i r i ，i e f s o ，1 ，一1 ) 则此矢量量化器称为规则矢量量化 器。 如果一个矢量量化器的胞腔以k 维超平面上的线段为界线，则称它 多胞形矢量量化器。它的每个胞腔都是多胞形，每个胞腔由有限个具有 形式 x r i “，+ 鼠0 的“半”空间的交集所构成。作为多胞形胞腔 界限的表面是k 1 维超平面，位于表面一侧的每一个点都在胞腔之内， 而另一侧的所有点都在胞腔之外。如果一个矢量量化器既是规则又是多 胞形的，这称该矢量量化器为规则多胞形矢量量化器。显然这类矢量量 化器的胞腔是凸多胞形的。 如果一个矢量量化器定义在一个有界域q ( x ) 内，所有输入矢量x 都 在此集合中，则称该矢量量化器是有界的。集合口的容量，可用v ( b ) 来 表示，即 y ( b ) = i d x d 显然有界域集合的容量矿( b ) 也是有限的，且有界量化器的划分区域 内无任何过载区域。 一个矢量量化器可分解为两部分，即编码器和解码器。编码器占是从 胄到索引集合r 的映射；而解码器d 是从索引集合1 1 到重构集合( 码书) c 的映射，即 占：r 。斗f ，d ：f j c ( 2 5 ) 若给定输入矢量空间的一种划分，则可完全确定某个输入矢量的编 码索引。另一方面，若给定码书，则可根据索引通过简单查表操作确定 相应的重构矢量。实际上，编码器的任务就是确定输入矢量处在哪一个 胞腔中，甚至认为编码过程根本不需要码书。另一方面，解码过程只是 一个简单查表操作，只需码书参与，并不需要知道胞腔如何划分。对大 多数实用矢量量化器来说，由于码书可隐含地确定胞腔划分，故编码操 作可通过码书完成。由此可见，整个矢量量化操作可看作两步操作的级 9 矢量量化技术简介 联或复合，即 q ( x ) 2 k ( x ) = d ( ( j ) ) ( 2 - - 6 ) 为方便起见，有时认为编码器能同时产生索引号i 和量化输出值 q ( x ) 。解码器有时被称作“逆向景化器”。图2 - l 表示如何通过镛疆嚣和 解码器的级联束定义一个矢量量化器，而基本的矢量量化编码、传输和 解鸱过程如图2 2 所示。矢量量化编妈器根据一定的失真测度在码书串 搜索处于输入矢量最匹配的码字。传输时仅传输码字的索引。矢霉疑纯 解码过程很简单，只要根据接收的码字索引在码书中查找该码掌，并将 它作为输入矢量的重构矢量。 伫日恼 叶 矢量量化器q 围2 - !矢量基化器彖意囤 嫡碣器 ( j 躯) l 解码器 闰2 - 2 矢量蠢化铺鹳和解码示意围 2 ，3 矢量量化的相关概念 任何传输或存储系统都有两个重要的设计目标：( 1 ) 性能尽可- 能良 好；( 2 ) 系统尽可能简单或成本低廉。显然，这两个目标是冲突的，鼹 为良好性能的获得通常以增加系统复杂度和成本为代价。第一个露捃用 o 西安理工大学硕士论文 数学方法很容易处理，且现代技术是复杂算法越来越容易实现，从而使 这个目标相对第二个目标更受重视；但相对于用硬件实现的系统来说， 第二个目标就显得更重要了。图像压缩系统的性能通常用给定编码速率 条件下重构图像的质量或保真度来评估。设计压缩系统的目的是在可承 受的复杂度条件下取得较好的编码质量。对于般的设计，研究者常常 着眼于如何优化系统的结构和性能。却不太注重复杂度问题。然而，如 果人们在设计系统时忽略实际情况对编码系统的结构复杂度的限制，许 多系统的复杂度可能会达到天文数量级。尤其对于硬件实现的压缩系统， 算法的硬件可实现性及硬件实现的成本显得尤为重要。因此，本论文将 对此问题特别关注，并在以后的章节中对此问题重点论述。编码系统所 受的限制通常和复杂度有关。人们必须在系统复杂度和性能，成本和保 真度之间寻求折衷。下面简单介绍一下描述矢量量化器的几个相关概念。 2 3 1 矢量量化器的编码速率和比特率 根据定义2 1 ，矢量量化器的分辨率、编码速率( 码率) 可定义为每 个输入采样所需要的平均比特数。设码书大小为n ，矢量维数为k 。对于 基本的矢量量化器，由于每个码字索弓l 所占的比特数为l o g z n ，故每一维 分量所占的比特数即编码速率为r = ( 1 0 9 2 n ) k 。它表明在码书性能良好的 情况下，用矢量量化器所能取得的准确度和精确度，所以也称之为分辨 率。 在数字通信系统中，矢量量化编码器选择一个合适的匹配码字y i 来 近似描述输入矢量石，并将被选中的码字的索引号f 传输( 以二进制形式) 给接收器。然后，矢量量化解码器执行查表操作产生重构矢量只，它是 原输入矢量的近似。如果系统的输入信号是一个矢量序列，即系统处理 的基本单位是矢量而不是标量，则每个输入矢量所需的比特数称为比特 率或传输率r ( t l 特矢量) ，它可由r = k r 给出，其中r 为分辨率，k 为矢量 维数。若用来表示矢量传输速率，即每秒钟被编码的矢量数，则每秒 钟所传输的比特数为r 。= 坝( 比特s ) 。 矢量量化技术简介 2 。3 2 失真测度m i n k o w s k i 、均方误差、信曝比程蟋蕉镶噪 比 矢量量化编码过程实质上是输入矢量与码字的匹配过程。模式匹配 的个关键问题是矢量问差异的度量。失真测度d ( x ，y ) 表征输入矢量x 被 重构矢量y 量化而产生的非负失真。在语音和图像处理中，大多数泓度 都是m i n k o w s k i 测度，或l p 测度定义为 d ( x ，y ) = l x 一“= i 玉一y i ( 2 8 ) 两种比较常见的特殊情况如下： 一i ( 1 ) l t ( 绝对误差) 测度：d ( x ，y ) = | l x y i 。= x i 一只i ( 2 9 ) ( 2 ) l 2 ( 欧几甩得) 测度：a ( x ，y ) = 1 1 工一y | 1 2 = ，l t y i 2 ( 2 一l o ) j 女一l v t = o l ，( 绝对谋筹) 测度是硬件电路常用的失真测度，因为它的计算不需要 乘法，硬件实现比较容易。在码字的搜索的软件实现时，经常使甩l 2 ( 欧 几皿得) 测度，因其几何意义明确( 两个矢量问的欧几里得距离) 。 另外，在图像压缩系统中常用均方误差( m s e ) 、信噪比( s n r ) 藕峰 值信噪叱( p s n r ) 来描述重构语言或图像的质量。假如一幅m x n 的l 级 灰度图像，原始图像像素为鼍，而重构图像像索为 y 。0 s i m l ，0 j n 一1 ，则m s e 、s n r 、p s n r 分别定义如下： ( 一砖) 2 m s e ：塑! 竺 ( 2 - 1 1 ) m n # 淞= 1 0 l o g l 。蕊嵩羔t ( 2 1 2 ) ( 一b ) i f - 。j 。 胱= l o x l o g 。等( 2 - 1 3 ) 西安理工大学硕士论文 2 。3 3 复杂度 与标量量化相比，矢量量化的主要缺点是复杂度大，且复杂度随维 数的增加呈指数形式增大，这是实现高维矢量量化器的主要障碍。无论 从硬件考虑还是从软件考虑，复杂度有两种：时间复杂度和空间复杂度。 时间复杂度定义为量化每个输入矢量所需的计算量，包括加减法、乘除 法和比较等。空间复杂度定义为量化器所需的存储容量。 度量矢量量化器的时间复杂度一般用两种办法；一是以每量化一个 输入矢量需用乘法运算的次数来衡量：一是以每量化一个输入矢量需用 加减法、乘除法和比较运算( 即三元组) 的次数来度量。对于基本矢量 量化器而言，设码书大小为n ，矢量维数为k ，若采用平方误差测度，那 么时间复杂度就可按这两种办法来度量。 ( 1 ) 仅用乘法运算次数度量，每量化一个输入复杂度为 b = k n ( 次输入矢量)( 2 1 4 ) 这是因为要对输入矢量进行穷尽搜索编码，需要计算这个输入矢量 和所有码字的平方误差测度，通过比较最小失真而找到相应的码字。每 个失真计算需要k 次算法，所以计算n 个失真测度需要k n 次乘法。 ( 2 ) 用三元组来描述容易得出，每量化一个输入矢量的时间复杂度b 为 b = ( k n ) 次乘法+ ( 2 k - 1 ) n 次加法+ ( n i ) 次比较1 输入矢量( 2 - 1 5 ) 若用编码速率r 和矢量维数k 来表示，则时间复杂度为 b = ( k 2 。) 次乘法+ ( 2 k 一1 ) 2 。7 】次加法+ ( 2 k r1 ) 次比较 输入矢量 ( 2 1 6 ) 从式( 2 - 1 6 ) 可以看出，摹本的穷尽搜索矢量量化器的时间复杂度随维 数k 和量化器速率r 的增加呈指数形式增加，所以它的时间复杂度比较 大。 虽然目前r o m 的容量不断增长，价格也不断下降，但若存储量很大， 矢量量化技术简介 则存耿时间则不能忽略。因此，空间复杂度也是一个需要重视的褥题。 基本穷器搜索矢量量化器的空间复杂度可表示为 “= k j v( 2 - 1 7 ) 2 4 矢量量化的关键技术 矢量量化的三大关键技术是码书设计、码字搜索和码字索引分配， 其中前两项投术最关键，下面加以简单说明。 2 。4 1 码书设计 矢量量化的首要问题是设计出性能好的码书。如果没有码书，编码 将成为无米之炊。假设采用平方误差测度作为失真测度，训练矢量数为 m ，舀的是生成含n ( n m ) 个码字的码书。码书设计过程就是寻隶把 m 个训练矢量分成n 类的一种最佳方案( 使均方误差最小) ，丽把备类 的质心矢量作为码书的码字。可以证明，各种可能的码书个数为 去( ) ”c j f = ”，其中jc j 为组合数。通过测试所有码书的性能可得 到全局最优码书。然而，在n 和m 比较大的情况下，搜索全部码书是不 可能的。为了克服这个困难，大部分码书设计方法都采用搜索部分碍书 的力法得到局部最优或接近局部最优的码书。因此，研究码书设计算法 的目的就是寻求有效的算法尽可能找到全局最优的码书以提商码书牲 能，并尽可能减少计算复杂度。 矢量量化码书设计算法主要有( 1 ) l b g 算法及其改进算法，包 括针对初始码书选择的改进算法以及针对设计速度的加速算法。( 2 ) 蘩 于神经刚络的码书设计算法，如自学习神经网络、竞争学习神经网络。( 3 ) 基于全局优化技术的码书设计算法，如随机松弛算法、模拟退火算法、 遗传算法和禁止搜索算法。( 4 ) 基于模糨聚类理论的码书设计算法。出 于本论文的主要工作不包括码书设计，作者只在工作展开之前，采用l b g 算法生成了一个简单的2 5 6 阶的码书。论文中提到和采用的码书出本课 西安理工大学硕士论文 题项目组参与码书设计的成员提供。 2 4 2 码字搜索 矢量量化码字搜索算法是指在码书已经存在的情况下，对于给定的 输入矢量，在码书中搜索与输入矢量之间失真最小的码字。给定码书 c = y o ，y l ，y 1 i v , r ) ，其中n 为码书尺寸，如果矢量x 与码字m 之 间的失真为d ( x ，咒) ，则码字搜索算法就是找到码字y 。是 d ( x ，y ，) 2 。m i 。n d ( x ，m ) 。若采用平方误差测度，对于k 维矢量，每次失真 计算需要k 次乘法，2 k 一1 次加法，从而对矢量z 进行穷尽搜索编码需要 n k 次乘法，n ( 2 k 1 ) 次加法和一1 次比较。可以看出，计算复杂度由码 书尺寸和矢量维数决定。对于大尺寸码书和高维矢量，计算复杂度将很 大。研究码字搜索算法的主要目的就是寻求快速有效的算法以减少计算 复杂度，且尽量使算法易于用硬件实现。 针对穷尽搜索算法的缺点，许多文献提出各种各样的快速算法，这 些码字搜索算法圯1 可归纳为以下五种：( 1 ) 基于不等式判断的快速码字搜 索算法；( 2 ) 基于变换域的快速码字搜索算法；( 3 ) 基于金字塔结构的快速 码字搜索算法：( 4 ) 自适应搜索范围及顺序的快速码字搜索算法：( 5 ) 降低 比特率的码字搜索算法。本论文在第三、四章专门对作者在这方面所做 工作加以介绍。 2 4 3 码字索引分配 在图2 - 2 所示的矢量量化编码和解码系统中，如果信道有噪声，则 信道左端的索引f 经过信道传输可能输出索引j 而不是i ，从而在解码端 引入额外失真。为了减少这种失真，可对码字索引进行重新分配。如果 码书大小为n ，则码字索引分配方案一共有n ! 种。码字索引分配算法就 是在n ! 种码字索引分配方案中寻求用最佳的码字索引分配方法使出信道 噪声引起的失真最小。当然，当n 较大时，测试n ! 种码字索引分配方 矢量量化技术简介 案是不可能的。为了克服这个困难，各种码字索引分配方法都采嚣舞都 搜索算法，往往只能得到局部最优解。因此，研究码索引分配冀法韵目 的就是寻求有效的算法尽可能找到全局最优或装近全蜀最优韵磁字索引 分配方案以减少幽信道噪声引起的失真，并尽可能减少计算机复杂度鄹 搜索时间。 码字索引分配算法是矢量量化技术的一个新的研究领域。鹞字索引 分配问题及其数学模型最初有f a r v a r d i n 【4 】于1 9 9 0 年提出。之后研究者们 开始提出些分配算法。因作者未承担这部分研究工作，其体算法在论 文中不再介绍。 2 5 矢量量化算法软硬件两种实理方式的比较 矢量鬃化是目前广泛应用于各种图像压缩编码系统中的一种有效的 数掘压缩技术，大多用软件来实现此算法，但由于其算法的编码复杂度 高、运算量大，使得处理时问较长，不能满足图像实时处理的需要。为 了加快处理速度，本论文采用了用硬件方式来实现此算法。下面采用一 个例子说明二者在处理速度上的差别。 对同一幅5 1 2 5 1 2 的灰白静止图像，利用同种算法分别采甩软徉 和硬件两干中方式进行压缩处理，如采用仿真软 牛m a t l a b1 2 。z 3 l 在配餮为 c t ) p 2 4 g h z 、内存2 5 6 m 的p c 机，用软件方式压缩这幅灰白图像，编码 时间约为3 9 秒；而如果采用硬件实现这个算法，对同一幅图，如电踌驹 系统时钟为5 0 m h z ，则压缩这幅灰白图像编码时间约为5 3 l 矿秒d 因 此采用两种实现方式二者的编码时间相差三个数量级。 快速码字搜索算法的研究及其硬件实现 3 快速码字搜索算法的研究及其硬件实 现 3 1 引言 本章主要研究矢量量化器的快速码字搜索算法，它对码书结构不做 任何限制，但它能减少矢量量化器的时间复杂度，并能易于硬件实现， 减少硬件成本。编码时间是影响编码系统实时性的重要因素，而编码时 间的降低主要是减少编码计算复杂度完成。而减少硬件面积通常是通过 降低码字搜索率来实现的。矢量量化编码过程最终归结为在给定码书中 搜索与输入矢量最匹配码字的过程。假定码书c = y o ，y t ，y n 一，ly i r ， 其中n 为码字个数，而k 维输入矢量d ( x ，m ) = m 咖d ( x ，一) ，其e f 输入矢 量x = ( x o ，葺，x k 1 ) 7 与码字只= ( 蜘，t i ，x ，( k - t ) ) 7 之间的失真测度采用平 方误差测度d ( x ，只) = e ( 工，- y , 或绝对误差测度c l ( x ，y ，) = i x t y 。l 来 描述，则矢量量化码字搜索问题就是在码书c 中搜索与输入矢量x 最匹 配的码字y ，使得y i 与x 之间的失真是码字中最小的，即 d ( x ，片) 2 m m i n 】d ( x ，m ) ( 3 1 ) 穷尽搜索( f u l ls e a r c h ，f s ) 算法是一种最原始、最直观的最近邻码 字搜索算法，它需要计算输入矢量与所有码字之间的失真，并通过比较 找出失真最小的码字。这种算法搜索计算复杂度最大，图像编码质量最 好。 高效率矢量量化编码( 或识别) 系统往往采用大码书和高维矢量， 这时计算复杂度将非常大，故减少码字搜索的计算负担是非常必要的。 快速码字搜索算法可提高矢量量化编码效率，而一种快速有效的码字搜 索算法的三个必不可少的因素是：( 1 ) 良好的初始匹配码字；( 2 ) 强有 力的