（电路与系统专业论文）基于矢量量化的信息隐藏算法的研究与实现.pdf

， y 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：觉金 签字日期：2 d l 萨7 月矿日 导师签名：撕 签字日期： 矽f 隘f 7 月 作者姓名：党金 导师姓名：侯建军 学位类别：工学 学号：0 8 1 2 0 0 1 6 职称：教授 学位级别：硕士 学科专业：电路与系统研究方向：信息隐藏 北京交通大学 2 0 1 0 年6 月 e do n 立 一 致谢 两年的学习生活即将结束，在此谨向在我攻读硕士学位期间指导，关心，帮 助过我的老师和同学们表示真挚的感谢。 本论文的工作是在我的导师侯建军教授的悉心指导下完成的。侯建军教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。他不仅在学术上给予 我极大的指导，还教会了我很多做人的道理，使我树立起正确的价值观和人生观。 他教育我要在生活的道路上踏实勤奋，奋勇前进。借此机会，衷心感谢两年来侯 建军老师对我的关心和指导。 感谢陈后金教授对我的言传身教，老师深厚的理论功底、一丝不苟的工作作 风，使我受益匪浅。 衷心感谢魏学业教授对我论文的指导。魏学业教授有着深厚的专业素养和数 学功底，在我研究的过程中为我指点迷津，给予我很大的帮助，在此特别感谢魏 老师对我的指导和支持。 侯忠生教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。 在此特别感谢杜普选教授对我生活和学习的关心和指导。 在实验室工作及撰写论文期间，宋伟师兄给我的研究工作给予了热情帮助， 为了解答了很多难题。商晖，敖乃翔给我的论文提出了很多宝贵意见，在此向他 们表示感谢。 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业。 北京交通大学硕士学位论文 中文摘要 中文摘要 基于矢量量化的信息隐藏技术是近几年发展起来的一种新的信息隐藏技术。 该算法利用相邻图像块间的高度相关性，将输入的图像分块。这些图像块形成欧 几里得空间尺。对空间中的每一个矢量进行矢量量化，只传输或存储该矢量的索 引，因此该算法较传统的信息隐藏算法，可以达到更高的压缩率，且有效节约了 存储空间。 基于矢量量化信息隐藏的关键技术是码书设计，码字搜索和水印的嵌入提取 算法。l b g 算法是经典的码书设计算法，是各类码书设计算法的基础。根据水印 嵌入算法特点分类，基于矢量量化的信息隐藏算法可分为基于码书分类的信息隐 藏算法和基于索引值特点的信息隐藏算法。通过对国内外各种算法的研究，本文 对这两种算法进行了仿真与分析，并提出一种新的基于多扩展码书的信息隐藏算 法。该算法较传统算法具有更高的压缩率，更好的图像质量，有效的提高了数据 的嵌入容量且计算复杂度降低。 论文最后对当前基于矢量量化的信息隐藏技术中存在的问题进行了探讨和研 究，提出了相应的解决方案，并对基于矢量量化信息隐藏算法的发展方向进行了 讨论。 关键词：矢量量化；码书设计；l b g 算法；码字搜索算法；信息隐藏算法 分类号：t p 3 0 1 6 1 i n f o r m a t i o nh i d i n ga l g o r i t h m sb a s e do nv e c t o rq u a n t i z a t i o nh a v ed e v e l o p e di n r e c e n ty e a r s t h ea l g o r i t h m sd i v i d et h ei n p u ti m a g ei n t os e v e r a lb l o c k sa c c o r d i l 玛t o t h eh i g hc o r r e l a t i o nb e t w e e na d j a c e n ti m a g eb l o c k s t h e s ei n p u tv e c t o r sf o r mt h e s p a c er 。t h e nt h ev e c t o rq u a n t i z a t i o no p e r a t i o ni sp e r f o r m e d o n l yt h ei n d e x e so f i n p u tv e c t o r sa l et r a n s m i t t e dt ot h er e c e i v e r c o m p a r e dt ot r a d i t i o n a lq u a n t i z a t i o n m e t h o d s ，t h i sm e t h o dc a na c h i e v el l i g hc o m p r e s s i o nr a t ea n ds a v et h es t o r a g es p a c e e f f e c t i v e l y t h ec o d e b o o k d e s i g na l g o r i t h m s ，c o d e w o r d ss e a r c ha l g o r i t h m sa n dt h e a s s i g n m e n t so fi n d e x e sa r ek e yt e c h n o l o g i e so fv e c t o rq u a n t i z a t i o nm e t h o d l b g a l g o r i t h mi st h ec l a s s i c a la l g o r i t h mf o rc o d e b o o kd e s i g na n di sf o u n d a t i o no fo t h e r a l g o r i t h m s t h e r ea r ei n f o r m a t i o nh i d i n ga l g o r i t h m sb a s e do nc o d e b o o kc l a s s i f i c a t i o n a n dt h ec h a r a c t e r i s t i c so fi n d e x e sa c c o r d i n gt ot h ef e a t u r eo fw a t e r m a r ke m b e d d i n g m e t h o d s t h i sp a p e rc a r d e do u ts i m u l a t i o na n de x p e r i m e n t sa b o u tb o 也t w ok i n d so f a l g o r i t h m sa n dp r o p o s e dan e wa l g o r i t h mb a s e do nm u l t i p l ee x t e n d e dc o d c b o o k si n d e v e l o p m e n t t h i sm e t h o dc a nr e a c hh i g h e rc o m p r e s s i o nr a t e ，l l i g he m b e d d i n g c a p a c i t ya n dl o wc o m p m i n gc o m p l e x i t y k e y w o r d s ：v e c t o rq u a n t i z a t i o n ；c o d e b o o kd e s i g n ；l b ga l g o r i t h m ；c o d e w o r d s s e a r c ha l g o r i t h m s ；d a t ah i d i n ga l g o r i t h m s c la s s n 0 ：t p 3 0 1 6 i 北京交通大学硕士学位论文目录 目录 中文摘要i a b s t r a c t i i 1 弓i 言1 1 1 研究背景与意义1 1 2 国内外研究现状3 1 3 本文研究内容和组织结构4 2 矢量量化理论。6 2 1 矢量量化的相关理论6 2 1 1矢量量化的理论基础和定义6 2 1 2数据相关性理论- 9 2 1 3编码速率和比特率9 2 1 4失真测度1 0 2 1 5复杂度1 1 2 2 矢量量化的关键技术1 2 2 2 1 码书设计1 2 2 2 1 1 矢量量化设计的最优条件1 3 2 2 1 2 l b g 算法的基本原理。1 4 2 2 1 3 l b g 算法产生码书性能仿真和分析1 6 2 2 1 4 l b g 算法的问题及解决方法1 8 2 2 2 码字搜索算法2 0 2 2 3 码字索引分配。2 1 3 基于矢量量化的信息隐藏算法2 2 3 1 基于矢量量化信息隐藏算法的基本原理2 2 3 2基于码书分类的信息隐藏算法。2 4 3 2 1基于码书分类信息隐藏算法的基本原理2 4 3 2 2基于码书分类的信息隐藏算法的仿真与分析。3 1 3 3 基于索引值特点的信息隐藏算法3 9 3 3 1基于索引值特点算法的基本原理。3 9 3 3 2一种基于索引值特点的信息隐藏算法仿真与分析。4 1 4 一种新的基于多扩展码书的信息隐藏算法4 6 4 1 一种基于索引值大小的信息隐藏算法4 6 4 - 2 -一种新的基于多扩展码书的信息隐藏算法4 8 4 - 2 1算法的基本原理4 9 北京交通大学硕士学位论文 目录 4 2 2算法的仿真和分析5 3 4 2 2 1 嵌入二值水印5 3 4 2 2 2 嵌入灰度图像5 6 5 基于矢量量化信息隐藏算法的思考与展望6 2 5 1 研究过程中出现的问题6 2 5 2 结论与展望6 3 参考文献6 5 作者简历6 7 独创性声明6 8 学位论文数据集6 9 北京交通大学硕士学位论文引言 1 引言 传统的信息隐藏技术多基于时间域和变换域。基于矢量量化( v e c t o r q u a n t i z a t i o n ，以后简称v q ) 的信息隐藏技术是近几年发展起来的基于压缩域的信息 隐藏技术，其主要优点是压缩比大以及解码简单。本文研究和分析了矢量量化的 关键技术和国内外的基于矢量量化的信息隐藏算法，并在此基础上对基于码书划 分和索引值特点的信息隐藏算法进行了仿真和分析，并提出一种新的基于多扩展 码书的信息隐藏算法，较以前的算法具有更高的嵌入容量和信噪比，以及较低的 计算复杂度。 1 1 研究背景与意义 随着因特网的普及，以及信息处理技术和通信手段的飞速发展，使图像，音 频，视频等多媒体信息可以在各种通信网络中迅速，快捷的传输，给信息的压缩， 存储，复制处理提供了更大的便利，同时，也为信息资源共享提供了条件，目前 网络已经成为主要的通信手段。各种机密信息，包括国家安全信息，军事信息， 私密信息等都需要通过网络进行传输，但互联网是一个开放的环境，在其上传输 的秘密关系着国家安全，经济发展和个人隐私等方方面面的安全，所以信息安全 在当今变得越来越重要。基于矢量量化的信息隐藏技术，具有压缩率高，占用带 宽小的特点，因此在信息隐藏领域得到越来越多的重视，很多专家提出多种基于 矢量量化的信息隐藏算法。 信息主要有两种保护方法【3 3 】：一种是利用密码术对明文实施各种变化，使它 不为局外人所理解。这种利用随机性来对抗密码攻击的技术，在防止他人从中得 到信息具体内容的同时，也暴露了消息的重要性，因此，成为攻击者注意的焦点。 另一种方法就是信息隐藏技术。信息隐藏最重要的特点在于它不仅隐藏了信息的 内容，而且隐藏了信息的存在，因而在信息安全领域显示出更为优良的特性。信 息隐藏技术是2 0 世纪9 0 年代中期兴起的一种新的数字媒体保护措施，它将特定的 信息如秘密消息，版权信息等嵌入到图像，音频，视频或文本文件等各种数字媒 体中，以达到标识，注释及版权保护的目的。同时，这种特定信息对宿主媒体的 影响不足以引起人们的注意，且具有特定的恢复方法，此信息对非法接收者是不 可见且不易察觉的。这种通过把信息存在本身隐藏起来的技术使得攻击者无从获 取秘密信息的位置，在客观上增强了信息隐藏技术的隐蔽性。信息隐藏技术利用 了人类感觉器官的不敏感，以及多媒体数字信号本身存在的冗余的特点。在实际 引言 载体非常丰富，这点也在客观增强了信息隐藏技术的 可行性。 信息隐藏技术的应用非常广泛。隐写术，数字水印，数字指纹，隐匿标记， 数据锁定，隐匿通信技术，隐蔽信道( 域下信道和隐信道技术) 技术等在保护数 字作品版权和个人隐私方面都发挥着重要作用。另外，广播加密，数字现金等应 用中也使用了信息隐藏技术。还有其他一些应用也激发了对信息隐藏课题的研究 兴趣： 1 军事和其他情报机构需要保密的通信手段。现在战场上，对加密的敏 感信号的检测可能导致对发报员的快速攻击。基于此，军方通信往往 采用诸如扩展频谱或大气散射等传递技术，保证信号不易被敌方发现 或者干扰； 2 犯罪分子也关注和采用一些“隐蔽 的通信手段； 3 执法与反情报机关等也关注这些技术及它们的弱点，从而达到发现和 隐藏信息的目的； 4 有些政府最近做出了一些尝试，限制在线自由交谈和民间使用加密技 术，因此也刺激了人们致力于发展互联网络上匿名通信的热情( 如匿 名邮件中转站和代理服务器) ； 5 电子选举和电子货币中的应用； 6 有些商家使用电子邮件伪造技术，既发送了大量不合法的信息，又避 开了用户的反应。 传统的信息隐藏技术多是基于空间域和变换域，近几年又提出一种新的基于 压缩域的信息隐藏技术矢量量化技术 3 5 】。传统的均匀量化和非均匀量化方法是 对信号的各个取样点进行逐点量化。而矢量量化考虑实际信号间的相关性，把若 干个取样点集合成一个矢量作为量化单位，符合数字图像各像素点具有相关性的 特点，因此矢量量化具有较高的压缩率且解码简单。香农最早提出，可引入“块 源编码系统”，该系统先将输入信号进行分块处理，然后将每一块映射为信道代 码。这种块源码的解码过程是把块的代码映射为原输入块的重构块或矢量。通常， 用失真测度来衡量给定输入矢量与其重构矢量之间的差异。这种编码系统称为矢 量量化器，这种编码操作称为矢量量化。矢量量化的发展可追溯至f 1 9 5 6 年s t e i n h a u s 第一次系统地阐述了最佳矢量量化的问题。1 9 7 8 年，b u 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 算法。标量量化主要用于模数转换，矢量量化则主要用于数 字信号压缩。在这一类应用中，矢量量化可看成一种降低复杂度技术，因为比特 数的减少可简化紧跟其后的计算，且有时可用简单查表操作代替复杂的数字信号 2 = 一 一 硕一 葩 一 塑 葡 一 垫 m裹 一 北京交通大学硕士学位论文 引言 处理过程，因此矢量量化不只是标量量化的简单推广，近几年来它已成为语音识 别，语音编码和图像压缩的重要技术，其重要性和应用正在逐步增长与扩大。 基于矢量量化的高压缩率以及信息隐藏技术的广泛应用，本课题利用多种算 法实现了基于矢量量化的信息隐藏算法，并提出一种新的基于多扩展码书的信息 隐藏技术，相较于以前的算法，信噪比高，嵌入容量大，鲁棒性好，计算量小， 有很高的应用价值。 1 2 国内外研究现状 国外对矢量量化器的研究起源于1 9 8 0 年，并一直处于领先地位，经过近三十 年来的研究，已经在最基本的矢量量化器基础上演变出了各种各样的矢量量化器。 这些矢量量化器大致可分为两类：无记忆矢量量化器和有记忆矢量量化器。 虽然基本矢量量化器已经可以用硬件实现，但各种变种的矢量量化器的硬件 实现仍有待于研究。矢量量化的压缩标准一直没有提出，主要原因是码书的标准 与编码的对象密切相关，不同应用场合下的码书结构，码书的大小以及矢量的位 数都不相同。国内矢量量化技术还停留在理论研究方面，实际的矢量量化系统并 未见报告，更不必说实用的矢量量化产品。国际上，至今仍未形成基于矢量量化 的图像压缩国际标准。而采用标量量化的m p e g ，j p e g 2 0 0 0 ，h 2 6 4 等图像压缩标 准相继推出，这并不是说明矢量量化没有优势，其中重要的原因就是目前相关理 论和算法还没得到完全解决，尚无法找到低复杂度的码书设计算法，在线快速搜 索算法的搜索速度也有待提高。 码书形成技术是矢量量化技术的关键之一。近来，有很多有关矢量量化码书 形成算法的研究。文献【1 】中提出成对最近邻算法，算法开始令每个训练矢量各占 一类，然后每次把两个具有最小距离的类合并，直到获得所要求大小的码书( 各 类的质心矢量作为码字) ，此算法明显减少了计算复杂度，但最终得到的码书性 雠l l b g 算法差；文献 2 】中介绍了基于神经网络的码书设计算法，随机松弛码书 设计算法，遗传码书设计算法和基于模糊集合理论的码书设计算法等。这些算法 都力求做到减小计算复杂度且提高码书质量。 码字搜索算法是矢量量化技术的又一关键技术。为了减少计算复杂度，出现 了各种矢量量化的快速算法。基于金字塔的算法最早的是均方金字塔算法。另外 还有【3 】中提出的部分失真搜索算法，此后基于此算法又出现了基于绝对误差不等 式的快速码字搜索算法，基于三角不等式的快速码字搜索算法和基于均值不等式 的最近邻搜索算法等。 3 出了基于码书划分的私有水印和公有水印处理算法。文献【4 】中对两种算法进行对 比。第一种算法是，根据输入水印信息，在码书中选择用最近或者次近码字代替 输入矢量；第二种算法是，根据输入水印信息，在码书中选择用最近矢量或者训 练矢量代替输入矢量。从仿真结果得出以下几点： 1 对同一种算法，码书尺寸越大，最后重构图像的信噪比越大； 2 对同一种算法，嵌入水印大小和嵌入比特中1 所占比例都会对信噪比造 成影响。随着嵌入水印变大，信噪比下降；而嵌入水印中1 所占比例越 大，信噪比就越低； 3 第二种算法相较第一种算法有其优越性。 首先，第二种算法能达到较高信噪比；其次，嵌入水印大小和嵌入比特中1 所 占比例对图像信噪比不会有很大影响。文献 5 提出一种基于索引特点的水印嵌入 算法。在自然图像中，邻块v q 索引是相似的，利用此特性产生极性。这种方法为 以后各种基于码书索引特性的数字水印算法奠定了基础。后来又出现了多种基于 码书分类和索引值特点的信息隐藏算法。信息隐藏算法已由嵌入单个水印向多个 水印发展，将嵌入算法和编码技术结合是发展的一大趋势。 1 3 本文研究内容和组织结构 本文对基于矢量量化信息隐藏的关键技术：码书设计，码字搜索和码字索引 分配技术进行了研究。重点对基于码书分类和索引值特点的两种水印嵌入算法进 行了仿真和分析，并针对以前算法存在的问题提出一种新的基于多扩展码书的信 息隐藏算法，达到较高的嵌入容量和信噪比，以及低的算法复杂度。本文主要做 的以下工作： 1 深入探讨矢量量化概念与内涵，对矢量量化的关键技术进行了研究； 2 结合国内外研究现状，研究和分析了基于码书分类和索引值特点的信息隐 藏算法，并进行了验证和仿真。 3 针对以前算法出现的问题，提出一种新的基于多扩展码书的信息隐藏算 法，并进行仿真实验和分析。 4 对当前基于矢量量化信息隐藏算法的问题进行总结和探讨，并提出有效的 解决方案。明确了下一步的工作方向。 论文的组织如下： 第一章阐述了本论文的研究背景和意义，列出了论文的主要工作和组织结构。 4 北京交通大学硕士学位论文 引言 望。 第二章介绍了矢量量化的相关概念以及关键技术。 第三章对基于矢量量化的数字水印嵌入算法和提取算法进行了仿真和分析。 第四章提出一种新的基于多扩展码书的信息隐藏算法，并进行了仿真和分析。 第五章对论文工作进行总结，对基于矢量量化的数字水印算法进行探讨和展 5 矢量量化理论 2 矢量量化理论 2 1 矢量量化的相关理论 量化是有损数据压缩中的常用技术，基本上可以分为三种，即标量量化，矢 量量化和序列量化。最基本的标量量化每次只量化一个采样，并对所有采样都采 用具有相同特性的量化器进行量化，而且每个采样的量化都与其他采样无关。矢 量量化和序列量化则利用相邻采样之间的相关性，矢量量化( v q ) 在量化时用码 书输出集合中最匹配的一组输出值来代替一组输入采样值，其理论基础是香农的 速率失真理论，其基本原理是用码书中与输入矢量最匹配的码字的索引代替输入 矢量进行传输和存储，而解码时只需简单的查表操作。矢量量化作为一种有效地 有损压缩技术，其突出优点是压缩比大且解码算法简单。 2 1 1矢量量化的理论基础和定义 矢量量化的理论基础是香农的速率失真理论。1 9 5 9 年，香农定义了速率失真 函数r ( d ) ( r ( d ) 的单位为比特采样) 为：在给定失真d 的条件下，系统所能达到 的最小码速率。并证明只要r ( d ) 不超过信道容量就能保证接收端的失真不超过给 定阈值d 。同样，也可定义失真速率函数d ( r ) 【1 1 】，它是速率一失真函数的逆函数， 其含义为：在给定速率不超过尺的条件下，系统所能够达到的最小失真。d ( r ) 是 在维数k 趋向无穷大时砬( 尺) 的极限，即 d ( r ) = j i l i l 4 俾) ( 2 - 1 ) 根据香农的这一理论，可找到一个最小的信源速率，使得系统发送端到接收 端的平均失真不超过给定的失真阈值，这正是数据压缩系统所要做的事情。从式 ( 2 1 ) 可知，利用矢量量化，编码性能可任意接近速率失真函数，其方法是增加 矢量维数k 。利用矢量编码代替标量编码总能在理论上得到更好的性能。因为矢量 量化能有效地应用矢量中各分量之间的相互关联性质来消除数据中的冗余度。不 过，速率失真理论是一个存在性定理，并非是一个构造性定理，它未给出如何构 造矢量量化器的方法。 码书和码字的定义如下： 6 北京交通大学硕士学位论文 矢量量化理论 设输入矢量为后维矢量i = ( x o ，而，。) 丁，输入矢量构成的空间即为七维欧几 里得空间，称为天鬈。把k 维欧几里得空间分割成互不重叠的个区域墨，昱昂， 在各区域内确定一个典型量化矢量只= 。咒 ，咒。枷) 2 ，这时将区域的集合写成 尸，称其为分割。另外将典型量化矢量的歹o ，或，及虱一，的集合写成c ，即 c = 厩，只，元虱q ) ，称其为码书，码书尺寸为。码书的个元素称其为码字。 矢量量化【2 】可定义如下： 定义2 1 维数为k ，尺寸为的矢量量化器q 定义为：从七维欧几里德空间尺置 到一包含个输出( 重构) 矢量的有限集合c 的映射， 即 9 足盖专c ，咒r 点，f r 三 0 ，1 ，n - 1 f 称为索引集合。 如图2 1 所示，二维空间被分为8 个区域，即码书大小为8 ，圆圈为质心矢量， 即码字，菱形为输入矢量。输入矢量寻找与其最近的码字，并划分到此胞腔中。 矢量量化技术所要研究的问题有两个，问题一，寻找最合适的划分，使码字代表 该区域内所有的矢量引入的失真最小；问题二，当码书确定后，对每一个输入矢 量，用哪种方法可以快速找到哪个码字与输入矢量失真最小，而不必要一个个去 比较。问题一需要研究码书设计问题，问题二需要研究码字搜索问题。 那, - - - - 暑 u j 口l f “卜 口 j ? 口f孑 上一l 一- 一 名量、f 、乍一 矢量量化过程就是对一输入矢量i ： 毛，而，也 在码书】，： i ，匕- t o , ，露) 中找 出一个与j 最近z 代替j ，即乏是曼的量化值，给乏一个序号，也就构成了编码。 编码过程可看成是一个从七维空间r t 到其中一个有限子集y 的映射： q ：r t 一】，： 乏，近，盛卜编码完成的映射为g ：i 专r ： 1 ，2 ，m 。解码完成的 映射为d ：f = l ，2 ，m ) 一】，= i ，迂，露) 。其原理框图如图2 - 2 n 示- 7 北京交通大学硕士学位论文矢量量化理论 图2 - 2 矢量量化结构框图 f i g u r e2 - 2b l o c kd i a g r a mo f v e c t o rq u a n t i z a t i o n 一个矢量量化器可分解为两部分，即编码器和解码器。编码器占是从尺到索引集 合r 的映射；而解码器d 是从索引集合r 到重构集合( 码书) 】，的映射，即 s ：r 专f ，d ：r 一】， ( 2 - 2 ) 若给定输入矢量空间的一种划分，则可完全确定某个输入矢量的量化索引。 另一方面，若给定码书，则可根据索引通过简单查表操作确定相应的重构矢量。 实际上，编码器就是为输入矢量寻找与其失真最小的码字。另一方面，解码过程 根据索引找到码书中寻找重构矢量。矢量量化编码过程是根据一定的失真测度在 码书中搜索出于输入矢量最匹配的码字，传输时仅传输该码字的索引，以达到图 像压缩的目的；解码时，接受者根据接收到的码字索引在码书中查找该码字，并 将它作为输入矢量的重构矢量。矢量量化的编码过程和解码过程如图2 3 所示： 图2 - 3 矢量量化编码和解码图 f i g u r e2 - 3v e c t o rq u a n t i z a t i o ne n c o d i n ga n dd e c o d i n g 8 矢量量化理论 对数据进行信源编码的目的是压缩数据。编码方法的优劣，一般使用压缩比积 和信噪比册来综合评价。压缩比定义为 c r = 原数据比特率编码后数据比特率 ( 2 3 ) 设原数据的比特率单位为n b i t s a m p l e ，根据信息论最佳信息表达原理，取编码的 比特率为它的信源熵日，可得无失真压缩的极限压缩比为c r o = n i t 。实际情况 下的平均编码比特率q = + 占， 0 。 对于一个有记忆数据序列皓“，u 2 ，q ，) ，每个选自符号集( q ，a 2 ，口) ，则 有如下结论：利用数据相关性，做高维的向量编码将比一维编码提高极限压缩比。 这也从另一方面说明矢量量化压缩率大于标量量化。 2 1 3 编码速率和比特率 基于矢量量化的信息隐藏，编码速率是很重要的衡量指标，它的定义如下： 定义2 2 矢量量化器的分辨率，编码速率或简称码速率可定义为每个输入采样 所需要的平均比特数。设码书大小为，矢量维数为k 。一个码字对应一个索引。 1 b i t 信息可以表示2 个码字，2 b i t 表示4 个码字，同理若个码字( n 个索引) 需 要xb i t 的信息，则满足2 。= ，因此对于基本的矢量量化器，每个码字索引所占 的比特数为l o g ：n ，故每一维分量所占的比特数即编码速率 ，= l 0 9 2 n k ( 2 - 4 ) 它表明在码书性能良好的情况下，用矢量量化器所能取得的准确度和精确度， 所以也称之为分辨率。对于固定维数k 而言，分辨率由码书尺寸决定，而与存 储码字的每一分量所占用的比特数无关。 在数字通信系统中，矢量量化编码器选择一个合适的匹配码字豆来近似描述 输入矢量i ，并将被选中的码字的索引号f ( 以二进制形式) 传输给接收器。然后， 矢量量化解码器执行查表操作产生重构矢量只，它是原输入矢量的近似。如果系 统地输入信号时一个矢量序列，即系统处理的基本单位是矢量而不是标量，则每 个输入矢量所需的比特数成为比特率或称传输率g ( 比特矢量) ，它可由 r ：鼢 ( 2 5 ) 给出，其中，为分辨率，k 为矢量维数。若用工来表示矢量传输速率，即每秒钟被 编码的矢量数，则每秒钟所传输的比特数为 足= 碱( 比特s ) ( 2 6 ) 9 矢量量化理论 矢量量化编码过程实质上是输入矢量与码字的匹配过程。模式匹配的一个关 键问题是是矢量间差异的度量。失真测度d ( x ，y ) 表征输入矢量i 被重构矢量歹量化 而产生的非负失真。实际应用中有多种失真测度，每种测度均有各自的优缺点， 测度的选择依赖于实际应用场合。本课题采用平方欧几里得距离作为输入矢量i 被 重构矢量量化产生失真的测度。 1 平方误差测度 若i ，歹均为k 维矢量，且i = ( x o ，五，也一1 ) ，歹= ( y o ，乃，以一。) ，则其i ，歹的 平方欧几里得距离定义如式( 2 6 ) d ( i ，萝) = | | i 一歹屺= ( 而一乃) 2 ( 2 7 ) 2 加权平方误差测度，它们分别定义如下： 嘏力= 背 ( 2 _ 8 ) 其中要求分母不为o 3 m i n k o w s k i 测度，常见得三种测度为厶，厶，l 厶( 绝对误差) 测度： k - i d ( i ，歹) - i li 一歹l l ，= lt 一乃 i = o ( 2 - 9 ) 厶( 欧几里得) 测度： 雁r 一 d ( i ，萝) = | ii 一歹l i ：= 、i 薯一咒1 2 ( 2 1 0 ) yi = o l ( 切比雪夫) 测度： d ( i ，歹) = 忙一跳2 吲m 蜘a x 1 x , 一咒i ( 2 一1 1 ) 以上各种测度是针对矢量之间的差异而言的，对于整个输入信号和相应的重 构矢量的失真，可以用均方误差( m s e ) ，信噪比( s n r ) 和峰值信噪比( p s n r ) 来描述重构语音或图像的质量。假设一幅m x n 的级灰度图像，原始像素为吻， 而重构图像的像素为此，1 f m ，1 j5n ，则m s e ，s n r ，p s n r 分别定义 如下： 北京交通大学硕士学位论文 矢量量化理论 f l 一1 嘞- y u ) 2 m s e ：兰! ：! m n s n r = l o x l g p s n r ：1 0 1 9 坠翌 。m s e 2 1 5 复杂度 ( 2 - 1 2 ) ( 2 - 1 3 ) ( 2 - 1 4 ) 相较于标量量化，矢量量化有较高的编码效率( 压缩率高于标量量化) ，但 是相应的代价是实现复杂度增加了，且复杂度随维数的增大呈指数形式增加，这 是实现高维矢量量化器的主要障碍。复杂度有两种：时间复杂度和空间复杂度。 时间复杂度定义为量化每个输入矢量所需要的计算量，包括加减法，乘除法和比 较等。空间复杂度定义为量化器所需的存储空间。矢量量化器的时间复杂度一般 用两种办法，一是以每量化一个输入矢量，需用乘法运算的次数来衡量；一是以 每量化一个输入矢量，需用加减法，乘法和比较运算( 即三元组) 的次数来衡量。 对于基本矢量量化器而言，码书大小为，矢量维数为k ，若采用平方误差测度， 那么时间复杂度可按这两种办法来衡量。 1 仅用乘法运算次数度量：每量化一个输入矢量的复杂度为 b = 捌 。 ( 2 - 1 5 ) 这是因为要对输入矢量进行穷尽搜索编码，需要计算这个输入矢量和所有 码字平方误差测度，通过比较确定最小失真找到相应码字。每个失真计算 需要k 次乘法，所以计算个失真测度需要k n 次乘法。 2 用三元组来描述：容易得出，没量化一个输入矢量的时间复杂度b 为 b = ( 枷) 次乘法+ 【( 2 七一1 ) 】次加法+ ( 1 ) 次比较) 输入矢量 ( 2 一】6 ) 若用编码速率，和矢量维数k 来表示，则时间复杂度为： b = ( k 2 打) 次乘法+ 【( 2 七一1 ) 2 b 】次加法+ ( 2 打一1 ) 次比较 输入矢量 ( 2 一】7 ) 3 从上式可以看出，基本的穷尽搜索是时间复杂度随维数k 和量化器速率r 的 增加呈指数形式增加，所以它的时间复杂度比较大。 1 1 弓一嘶丝而 m争驭闩 矢量量化理论 可表示为 ( 2 - 1 8 ) 2 2 矢量量化的关键技术 以码字乏量化输入矢量i ，必然存在量化失真疵动：血埘营，竞脚吐z ，n ， 其中d ( i ，i ) 为矢量i 和码字z 之间的失真测度，采用2 1 4 中的平方误差测度。 解码失真的大小主要由码书质量决定，这样寻求最优码书的设计方法就成为矢量 量化的一个重要研究方向。基本的矢量量化编码器需要使用由个k 维矢量组成 的码书。对某个输入矢量进行编码时，在码书中搜索与该输入矢量之间失真最小 的码字，这一过程需要次距离计算，计算复杂度较大，此时的搜索复杂度是要 解决的重要问题，它决定了矢量量化技术是否能用于实时系统。从信源编码的角 度看，矢量量化的关键技术是码书设计和码字搜索。码字索引在信道中传输时， 若信道有噪声，则接收端收到的索引发生改变，从而矢量量化解码器从码书中获 得的码字作为输出矢量来重建输入矢量时就引入了附加失真。减少失真的一种可 行方法是重新分配所有码字的索引。因此码字索引的分配也是矢量量化的关键技 术。这里重点讨论码书设计和码字搜索技术。 2 2 1 码书设计 矢量量化码书设计是矢量量化技术的根本性问题。它是指从k 维矢量空间尺七 中选出个码字，用来量化m 个输入矢量，使整体量化失真和最小，这个码字 构成码书。寻找量化失真小，训练速度快的码书，就是矢量量化码书设计所要研 究的问题。码书设计关乎到整个压缩系统的峰值信噪比，压缩率等性能。对信息 隐藏算法来讲，一个好的码书设计算法，可以使图像量化失真减小，提高v q 压缩 图像的信噪比。另一方面，码书设计算法的优劣关系到计算的时间复杂度和空间 复杂度。优秀的码书设计算法，有很好的收敛速度，能在较短时间得到性能好的 码书，从而节省了计算时间和存储成本。一种有效和直观的矢量量化码书设计算 法l b g 算法是l i n d e ，b u z o 并1 g r a y 于1 9 8 0 年首先提出来的。该算法基于最佳矢量 量化器设计的最佳划分和最佳码书这两个必要条件，且是劳埃德算法在矢量空间 的推广，物理概念清楚，算法容易实现。但l b g 算法存在三个缺点： 1 计算量大。每次迭代时，在码书中搜索输入矢量的最近码字，需要大量的 存储空间和繁琐的计算性能 北京交通大学硕士学位论文 矢量量化理论 2 强烈依赖于舒适码书的选择。初始码书的选择影响码书训练的收敛速度和 最终码书的性能； 3 码书的自适应能力不强。用特定训练集优化的到得码书对于其他输入矢量 不一定能达n d , 的量化失真。 针对这些问题，学者们提出各种改进算法。 1 针对第一个缺点，可以采取快速码字搜索算法，但是这些算法无法改善码 书的性能； 2 针对初始码书选择的改进办法以及针对设计速度的加速算法。 3 基于神经网络的码书设计算法，如自学习神经网络，竞争学习神经网络； 4 基于全局优化技术的码书设计算法，如随机松弛算法，模拟退火算法，一 串算法和禁止搜索算法。 5 基于模糊聚类理论的码书设计算法等。 下面重点介绍l b g 算法，l b g 算法也是本论文仿真和实验的基础。 2 2 1 1 矢量量化设计的最优条件 l b g 算法基于最佳矢量量化器设计的最佳划分和最佳码书这两个必要条件， 且是劳埃德算法在矢量控件的推广，其特点为物理概念清晰，算法理论严密及算 法容易实现。 劳埃德算法定义如下： 定义2 3 劳埃德算法首先把输入点分成k 个初始化分组，可以是随机的或者使 用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它 最近的中心，重新确定分组。继续重复不断地计算中心并重新分组，直到收敛， 即对象不再改变分组( 中心点位置不再改变) 两个最优临近条件是最近邻条件和质心条件，最近邻条件定义如下： 定义2 4 给定训练矢量集z = 瓴i 而r k , 1 i m ，码书c = c ji 勺r k , 1 ，n ， 则输入矢量空间的最优划分s = 墨，是，s 一& ) 满足 s = 川( x ，q ) 。鸥地m 1 洲 ( 2 1 9 ) 最近邻条件表明：r 空间中的任意一个矢量五属于且只属于一个胞腔。如果薯 只与其中一个码字q 失真最小，那么它自然归属到q 所代表的胞腔中。如果该矢量 同时与两个或两个以上的码字之间失真最小，那么约定该矢量归属到其中序号最 小的胞腔中。 显然，当码书已经确定的情况下，对于每一个输入矢量，把它映射到与它最 近的码字量化失真最小，更换到其他任何码字都将增大量化失真，这就是最近邻 北京交通大学硕士学位论文 矢量量化理论 条件的直观解释。通常把满足最近邻条件的划分叫做v o r o n o i 戈l j 分，对应的胞腔叫 做v o r o n o i 胞腔。 码书确定以后，输入矢量的最优划分应满足最近邻条件。也就是说任何一个 输入矢量，应当映射到和它最近邻的码字。矢量空间中的任何一个矢量薯，如果 它与码字q 的失真，与比其他码字之间的任何失真都小，那么该矢量就应归到该胞 腔冠中，胞腔足中的所有矢量用码字q 量化。 质心条件定义如下： 定义2 5 对于给定划分s = s ，曼，s ) ，最优码字必须是相应胞腔的质心， 即 1 c ：l _ yx 崦i | 每 ( 2 2 0 ) 式中0s 川表示胞腔s ，中所包含的元素个数。| ls 川必须非零，也就是说，任何一 个胞腔所包含的元素个数不能为零。如果某个胞腔中的元素个数为零，就是所说 的空胞腔问题，对于空胞腔，也就没有质心可言。事实上，存在空胞腔的码书必 定不是最优码书，因为可以将代表该空胞腔的码字去掉，在其他失真大的区域增 加一个码字，这样失真肯定是下降的。在实际设计过程中，应及时处理。 给定满足最近邻条件和质心条件的矢量量化器，设 c ， 为重构矢量集， s ， 为 划分胞腔集，而如? 为如下集合： s ? = x i d ( x ，c j ) d ( x ，c i ) ，v l f n ( 2 2 1 ) t 包括最近邻胞腔0 和胞腔勺的边界点，记集合岛= 一s j 为s 3 的边界点。边 界点上的矢量与两个或两个以上的码字失真最小。这些矢量可以采用共享这条边 界的任何一个码字量化，都最优最小的量化失真。边界点没有固定的最近邻字， 这就引出了零概率边界条件。 对于给定信源分布的码书最优必要条件是： m p ( z b ，) = 0 j = i 。 ( 2 - 2 2 ) 也就是说边界点出现的概率为0 。也就是说令输入矢量拥有两个或两个以上最近 邻码字的概率为0 由于该问题对整体失真影响较小，目前又没有规范的处理办 法，实际应用中一般不考虑该问题。 2 2 1 2 l b g 算法的基本原理 l b g 算法给出了码书设计的详细处理过程，它通常用来特指基于分裂技术的 劳埃德迭代算法，它是标量量化劳埃德操作的直接推广。l b g 算法的算法流程如 图2 4 所示： 1 4 量量化理论 图2 _ 4l b g 算法流程图 f i g u r e2 - 4l b ga l g o r i t h mf l o wc h a r t l b g 算法步骤如下： 1 初始化，给定训练矢量集x = 如i 毛戤，1 f m ，码书大小，其中 ( n 0 ，初始码书c o ) = c 5 1 0 ) lc p 戤，1 ，n ) ，置 迭代次数f = 0 ，设初始失真d ( - 1 ) ：0 0 ； 2 依据最近邻法则( n e a r e s tn e i g h b o rp r i n c i p l e ，n n p ) ，将x 划分为个 v o r o n o i 胞腔，s p ) = ( g ，晶 ，其中譬满足 5 j 。) = 缸id ( x ，尊) = 熙( x ，c ；) ，x x ) ，曷n $ ) = x ，筇p r 、= q s q ( f ) = a ( 2 - 2 3 ) 矢量量化理论 ( d ( 卜1 ) 一d ( t ) d ( s ，则停止算法，码书c ，就是所要求的码书，否则转向 下一步； 4 计算个胞腔的质心，芎+ 1 2 南磊，x ，将这个质心作为新的码字， f =