（电路与系统专业论文）矢量量化中码书设计的研究[电路与系统专业优秀论文].pdf

摘要 矢量量化( v e c t o rq u a n t i z a t i o n , v q ) 是香农信息论在信源编码理论方面的新 发展。它提出将若干标量数据组构成一个矢量，然后在矢量空间中给以整体量化， 从而压缩了数据而不损失太多信息，这是一种高效的压缩技术。本文以矢量量化 码书设计算法作为主要研究对象，对几种常用的码书设计算法：经典g l a 算法， 成对最近邻( p n n ) 算法，学习矢量量化( l v 0 ) 算法进行仿真实验，比较三种 算法重建矢量时产生的失真大小以及三种算法码书设计的计算量大小。 文中对经典的g l a 算法提出了改进措旌：用p n n 算法训练初始码书作为 g l a 算法的初始码书以降低g l a 算法对初始码书的敏感性，并通过仿真检验改 进效果。实验数据证明：利用改进算法重建矢量得到的失真比经典的g l a 小， 改进后g l a 算法对初始码书的敏感性有所降低，码本更加接近全局最优化，而 且总的计算量有所下降。 本文还提出一种改进方法以改善l v q 算法对码字更新的局部最优问题：设定 码字更新次数的阂值，使得绝大多数码字都得到更新，使算法全局最优化。实验 仿真结果证明：改进的l v q 算法码字更新均匀，大大改善了l v q 算法极容易陷 入局部最小的问题，利用改进的l v q 算法重建矢量得到的失真也降低很多，另 外，由于l v q 算法容易陷入局部最小，l v q 算法的计算量很小。改进的l v q 算法计算量的增加来换取失真的大幅降低是非常值得的。 关键词：矢量量化；学习矢量量化：g l a 算法 a b s t r a c t t h et e c h n i q u eo fv e c t o rq u a n t i z a t i o n ( v q ) i san e wd e v e l o p m e n to ft h e s h a n n o n si n f o r m a t i o nt h e o r yi nt h ea p p l i c a t i o no f t h es o u r c cc o d i n g t h ev e c t o rd a t a , w h i c hi sm a d eu po fan u m b e ro fs c a l a rd a t a , i sq u a n t i f i e di nt h ev e c t o rs p a c e v e c t o r q u a n t i z a t i o n ( v q ) i sa ne f f i c i e n tc o m p r e s s i o nt e c h n i q u e ，w h o s ep r o m i n e n t “i v a n t a g e i st h eh i 曲c o m p r e s s i o nr a t i oa n ds i m p l ed e c o d i n gp r o c e s s i nt h i sp a p e r , t h ev q c o d e b o o kd e s i g nm e t h o d sa r ed i s c u s s e da st h em a j o rt o p i co fr e s e a r c h t h e a d v a n t a g e sa n ds h o r t c o m i n g so ft h ep a i r w i s en e a r e s tn e i g h b o u r & n n ) a l g o r i t h m , g l aa l g o r i t h ma n dl v qa l g o r i t h ma r ea n a l y z e db yc o m p a r i n gt h ed i s t o r t i o n sa n d c o m p u t a t i o n a lb a s e d0 bt h es i m u l a t i o n so f t h e s ea l g o r i t h m _ t h em o d i f i e da l g o r i t h m so f g l a a l g o r i t h mw i t ht h ei n i t i a lc o d e b o o kt r a i n e db y t h ep n na l g o r i t h mi sp r o p o s e di n t h i sp a p e r t h er e s u l t so fe x p e r i m e n tf o rr a n d o m d a t as h o wt h a t ：t h ec o d e b o o kq u a l i t yo f t h eg l a a l g o r i t h mw i t h t h ei n i t i a lc o d e b o o k t r a i n e db yt h ep n n a l g o r i t h mi so b v i o u s l yb e t t e rt h a nt h a to b t a i n e db yc o n v e n t i o n a l g l aa l g o r i t h m , a n dt h er e c o n s t r u c t i o nd i s t o r t i o no ft h ei n p u tv e c t o ri sr e d u c e dw i t h c a l c u l a t i n gc o n s u m p t i o nn o ti n c r e a s e d t h em o d i f i e da l g o r i t h m so fl v q a l g o r i t h mi sa l s op r e s e n t e di nt h i sp a p e r i nt h e p r o p o s e da l g o r i t h m ，t h et h r e s h o l do fu p d a t et i m e sf o rt h er e n o v a t i o no ft h ev e c t o ro f c o d e b o o ki ss e tt oa v o i dt h es i t u a t i o no e c u r r c at h a to n l yaf e wv e c t o r so fc o d e b o o k a r er e n o v a t e di nt h et r a i n i n gp r o c e d u r e s ot h a t , m o a to ft h ev e c t o r si nt h ec o d e b o o k a r er e n o v a t e di nt h em o d i f i e dl v qa l g o r i t h m 。t h es i m u l a t i o n si n d i c a t et h a tt h e q u a l i t yo ff i n a lc o d c b o o ki si m p r o v e de f f i c i e n t l yi nt h em o d i f i e dl v qa l g o r i t h m , a n d t h er e c o n s t r u c t i o nd i s t o r t i o no f t h ei n p u tv e c t o ri sa l s or e d u c e ds i g n i f i c a n t l y k e yw o r d s ：v e c t o rq u a n t i z a t i o n ；l e a r n i n gv e c t o rq u a n t i z a t i o n ；g l aa l g o r i t h m 前言 一、选题背景【l l 【8 】 随着计算机和大规模集成电路的飞速发展，数字信号的分析和处理技术得到 很大发展，并已经广泛用于通信、雷达和自动化等领域。数字信号的明显优点是 便于传输、存储、交换、加密和处理等。一个连续的模拟信号f ( t ) ，只要它的频 带有限并允许一定的失真，往往可以经过采样变成时间离散但幅值连续的采样信 号鼬) 。对于数字系统来说，f ( n ) 还需经过量化变成时间和幅值均离散的数字信号 x o n ) 。通信系统有两大类：一类是传输模拟信号m ) 的模拟通信系统；另一类是传 输数字信号x ( n ) 的数字通信系统。在任何数据传输系统中，人们总是希望只传输 所需要的信息并以最小失真或者零失真来接收这些信息。人们常用有效性( 传输效 率) 和可靠性( 抗干扰能力) 来描述传输系统的性能。与模拟通信系统相比，数字通 信系统具有抗干扰能力强、保密性好、可靠性高，便于传输、存储、交换和处理 等优点。在数字通信中，码速率高不仅影响传输效率，而且增加了存储和处理的 负担。因此，在数字通信中通常采用如图1 一l 所示的方法对数字信号x ( n ) 进行编 码。图中，信源编码的主要任务就是降低玛速率，增加传输有效性。信道编码的 主要目的就是提高信号的抗于扰能力，增加传输可靠性。 图1 1 数字通信系统发送端基本模型 数据压缩是信源编码的目的和手段”。从广义上讲，数据压缩就是减少分配 给指定消息集合或数据采样集合的信号空间大小。该信号空间可以是物理容积， 也可以是时间间隔或带宽。数据压缩的主要目的是为了降低码速率或减少存储空 间。数据压缩可以分为可逆压缩( 冗余度压缩) 和不可逆压缩( 有损压缩或熵压缩) 两大类。熵压缩将导致信息失真，它是不可逆的。若把数据看作信息和冗余度的 叠加，冗余度压缩的工作机理就是去除或者减少数据的冗余度，它是一个可逆过 程。量化是有损数据压缩中常用的技术，基本上可以分为三种，即标量量化、矢 量量化和序列量化。最基本的标量量化每次只量化一个采样，并对所有采样都采 用相同的量化器特性进行量化，而且每个采样的量化都和其它采样无关。矢量量 i 化和序列量化则利用相邻采样之间的相关性。矢量量化( v e c t o rq u a n t i z a t i o n ， v q ) t 2 1 1 3 】【4 】1 6 1 在量化时用输出组集合( 码书) 中最匹配的一组输出值( 码字) 来代替一 组输入采样值( 输入矢量) 。矢量量化的优点是解码简单、压缩比大。 现代通信业务的发展，需要大量地存贮、记录和传输图片、气象云图、遥感 图像等静态图像，以及可视电话、工业电视、会议电视、彩色广播电视等各类动 态图像。在保证质量的前提下，人们往往希望能够以较小的空间存储图像和较少 的比特率传输图像，这就需要采用各种图像压缩编码技术来实现。图像一般都包 含大量数据，但是这些图像数据是高度相关的，而且含有大量的冗余信息。静态 图像往往含有大量的空间冗余信息，而动态图像不但含有大量的空间冗余信息还 含有大量的时闻冗余信息。除此之外，一般的图像数据中还存在其它冗余信息， 如信息熵冗余、结构冗余、知识冗余和视觉冗余等。图像压缩编码的目的是消除 各种冗余并在给定的畸变条件下使用尽量少的比特数表示和重建图像，以便更好 地存储和传输图像。图像压缩编码的应用大致分为图像的数字通信、图像的数字 存储和图像信息的数字交换三个方面。矢量量化技术的突出优点是压缩比大以及 解码算法简单，因此它已经成为图像压缩编码的重要技术之一。矢量量化图像压 缩技术的推广应用领域非常广。首先，矢量量化图像压缩技术可以用于卫星遥感 照片、航天飞机遥感图像的压缩编码，甚至可以应用到外星图像资料实时传输系 统和气象部门的图像传输系统中，从而推动航天事业的发展。其次，矢量量化图 像压缩技术在雷达图像处理、军用地图的存储与自动检索以及未来信息战争的图 像传输等方面的应用将提高军事信息处理的效率从而推动军事科技现代化。此 外，数字电视技术和d v d 的视频压缩技术已经在世界范围内展开研究，矢量 量化技术高压缩比的特点将使它成为首选的编解码技术之一，从而推动多媒体 产业的迅速发展。 矢量量化技术的研究涉及多学科领域的理论和技术，如信息论、编码理论、 通信原理、保密技术、信号处理、优化理论、模糊集合论、矩阵分析、神经网络， 小波变换、视觉模型、拓扑学、随机概率理论、预测技术、模式识别等等，矢量 量化技术的研究将给这些理论和技术注入新鲜血液。因此，无论从理论角度还是 从应用角度来看，开展对矢量量化技术的研究，不但具有重要的学术意义，还有 极为重要的国防意义和经济意义。 i v 二、矢量量化理论研究现状【1 i 8 1 矢量量化的基本理论早在二十世纪六七十年代已有人关注，而在二十世纪八 十年代开始逐步完善起来。矢量量化是分组量化的一种，受到广泛注意和使用的 分组量化方法是由黄和舒尔泰斯于1 9 6 3 年h 卸首先提出来的，他们指出分组量 化的实现方法：首先与正交矩阵相乘将相关的采样变换为不相关的采样，然后再 在每组固定的总比特数限制下，将不同的量化比特数目分配给每个不相关的采样 值。1 9 7 9 年，格尔肖在他的论文洳】中详细阐述了分组量化的一般性理论，它将 贝内特早年关于均方误差准贝1 j 的量化模型推广到分组量化中。而数据压缩的一类 崭新的分组量化方法一多径搜索编码的三种方法，即码书编码、树型编码和格型 编码，于1 9 8 2 年在文献即t 中进行了详细地评述。 将矢量量化技术推向研究高潮和推广应用应归功于1 9 8 0 年由l i n d e ，b u z o 和g r a y 提出来的一种有效的l b g 矢量量化码书设计方法州。该文献已经成为 矢量量化的经典文献，是矢量量化技术发展的基石。在2 0 多年历程中，学们在 以下五个方面对矢量量化技术展开研究。1 针对基本矢量量化器复杂度大和比特 率固定的缺点，开发其它类型的矢量量化器；2 针对基本矢量量化器的l b g 码 书设计算法容易陷入局部极小、初始码书影响优化结果和计算量大的缺点，学者 们引入了神经网络、优化理论、模糊集合等技术，提出了各种各样的码书设计算 法：3 在矢量量化编码场合中，针对基本矢量量化器的穷尽搜索编码算法的计 算量大和比特率固定的缺点，提出各种各样的快速码字搜索算法和变比特率码字 搜索算法。4 考虑到信道噪声将会在矢量量化解码端引入额外失真，学者们开 始研究码字索弓1 分配算法以减少由于信道噪声引起的失真，5 矢量量化技术的 应用。 三、论文研究的主要内容及章节安排 本文以矢量量化码书设计算法为主要研究对象，应用对象是正态分布的随机 数以及简单处理的语音波形。主要研究内容以下两个方面： 1 首先介绍经典的g l a 算法、p n n 算法和最大下降法，基于神经网络的 矢量量化码书设计算法( l v q 和各种竞争学习算法) ，并对以上算法进行仿真， 比较其失真度和算法复杂度，为后面对算法的改进工作提供理论根据和实验证 明。 v 2 对经典的g l a 算法提出改进措施，利用p n n 训练初始码书，提高g l a 算法的码书质量，并以随机数据和语音波形给予实验证明。对l v q 算法进行改 进，使得码字更新更加均匀，使算法达到全局最优，也以实验给出了证明，算法 改进是有效的。 第一章，阐述了矢量量化技术的理论根据，介绍了矢量量化技术的基本原 理和相关概念。 第二章，重点介绍了几种矢量量化码书设计算法，根据实验仿真比较了各 算法的优缺点。 第三章，提出了对经典g l a 算法的改进，并对其给出了实验仿真和比较说 明。 第四章，提出了对l v q 算法的改进措施，对其给出了实验仿真和比较说明。 结束语，总结作者所做的工作，提出文章的不足和进一步研究的考虑。 v i 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名：蔓逍乳 日期：翘 ：丝：互窆 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名：量j ： g 每 日 期：丝虹：垂：业 1 1 矢量量化的理论基础 第一章矢量量化概述 矢量量化的理论基础【1 1 是香农的速率一失真理论。1 9 4 8 年，香农定义了信道 容量，并证明只要编码速率不超过信道容量，符号就能以任意小的差错概率在该 信道中传输。1 9 5 6 年，香农定义了速率一失真函数r ( d ) ，并证明只要r ) 不超 过信道容量就能保证接受端的失真不超过给定阈值d 。根据香农的这一理论， 可找到一个最小的信源速率使得系统发送端到接受端的平均失真不超过给定的 失真阈值，即使信源是无记忆的，利用矢量编码代替标量编码总能在理论上得到 更好的性能。矢量量化并不只是标量量化的简单推广，至今尚未有比矢量量化更 好的编码技术。 1 2 矢量量化器的基本原理1 2 】 1 2 1 矢量量化器的例子 利用人们对二维或三维空闻的直觉，可方便的从几何角度理解矢量量化器的 工作原理。二维量化器的作用是将平面上任一输入点映射到此平面上n 个点中 离它最近的那个点。图1 1 给出了一个非多胞型和非规则的二维量化器的例子， 因其胞腔表面并不是直线段，截胞腔不凸。途中的点代表二维平面中的码字，包 含每个码字的区域为胞腔。图l - 2 给出了一个二维规则量化器，其有界胞腔是多 边形。一般的矢量量化器的量化胞腔不受任何几何约束，如图l l 、图1 2 所示， 可具有任意形状。一般意义下的三维规则矢量量化器则具有多面体胞腔。将此概 念推广至k 维，其量化胞腔是超立方体，具有极大结构自由度，明显比标量量化 优越。 图1 - 1 一个非规则量化器图1 2 一个规则量化器 1 2 2 矢量量化器的结构 一个矢量量化器可分解成两个部分，即编码器和解码器，编码器的任务就是 确定输入矢量处在哪一个胞腔中，由于码书可隐含地确定胞腔划分，故编码操作 可通过码书设计完成；解码过程事实上是一个查表操作，只需要码书参与，并不 需要知道胞腔如何划分。 编码器 解码器 图l 一3 矢量量化编码和解码示意图 基本的矢量量化编码、传输和解码过程如图1 - 3 所示。矢量量化器根据一定 的失真测度在码书中搜索出与输入矢量最匹配的码字。传输时仅阐述该码字的索 引，只要根据收到的码字索引在码书中查找该码字，并将它作为输入矢量的重构 矢量。 2 1 3 矢量量化的相关概念 1 3 1 矢量量化器的编码速率和比特率 矢量量化器的分辨率、编码速率( 编码率) 或简称码速率( 码率) 可定义为 每个输入采样所需要的平均比特数。设码书大小为，矢量维数为七。对于基本 的矢量量化嚣，由于每个码字索引所占的比特数为l o g ，n ，故每一维分量所占的 比特数即编码速率为r = ( 1 0 9 ， r ) 七。它表明在码书性能良好的情况下，用此矢 量量化器所能取得的准确度和精确度，所以也称之为分辨率。对于固定维数_ j 而 言，分辨率由码书尺寸 ，决定，而与存储码字的每一分量所占用的比特数无关。 在数字通信系统中，矢量量化编码器选择一个合适的匹配码字y 。来近似描 述输入矢量x ，并将被选中的码字的索弓l 号计号输给接收器。然后，矢量量化解 码器执行查表操作产生重构矢量y ，它是原输入矢量的近似。如果系统的输入信 号是一个矢量牟列，郎系统处理的基本单位是矢量而不是标量，剐每个矢量所需 的比特数称为比特率或称传输率r ( 比特矢量) ，它可由r = 鼢给出，其中r 为 分辨率，k 为矢量维数。若用疋来表示矢量传输率，即每秒钟披编码的矢量数， 则每秒所传输的比特数为r ，= 白z ( 比特s ) 。如果系统处理的基本单位为标量， 如波形编码，其中每个矢量代表波形的一个连续采样段，即每一个矢量由多个标 量采样组成。此时，矢量维数i 和采样率，( 采样数秒) 共同确定了矢量传输 数率，即工= k ( 矢量数秒) 。从而比特率r j = 谚( 比特s ) 。人们之所以 要对分辨率和比特率进行区分，是因为在矢量量化的一些重要应用中，输入矢量 表达的是信号的一组参数而非信号的一组采样。 1 3 2 失真测度 矢量量化编码过程实质上是输入矢量与码字的匹配过程模式匹配的一个 关键问题是矢量间差异的度量。测度的三个特征习包括计算复杂度、分析或设计 时的易处理性及特征评估的可信度。系统性能通常采用输入矢量和重构矢量间的 平均失真来评价；有时人们采用最大失真来描述压缩系统的性能，仅限于有界随 机矢量的情况以及量化器具有有限个无重叠胞腔的情况，而一般情况下采用失真 的统计平均值作为码书性能度量。下面介绍一些常用失真测度。 平均误差测度：输入矢量x 同重构矢量y = q ( 功之间的相似程度常常采 用平方欧几里得距离来衡量，其定义为 d ( x ，力； i x - 堰：艺喘) ： o - 1 ) 加权平方误差测度，定义为 d ( x ，力= ( x - y ) 7 w ( x - y ) = 一y 1 ) ( x ，- y ) ( 1 - 2 ) 户0 t = o 式中w = h j 为k x k 正定对称矩阵，矢量r 和y 按列向量处理。 m i n k o w s k i 测度：语音和图像处理中，大多数都是m i n k o w s k i 测度的特 例 谱失真测度 倒谱失真钡9 度 均方误差、信噪比和峰值信噪比 1 3 3 复杂度 与标量量化相比，矢量量化的主要缺点是复杂度大，且复杂度随维数的增大 呈指数形式增加，这是实现高维矢量量化器的主要障碍。无论从硬件考虑还是从 软件考虑，复杂度有两种：时间复杂度和空间复杂度嘲1 4 1 。时间复杂度定义为量 化每个输入矢量所需要的计算量，包括加减法、乘除法和比较等。空阀复杂度定 义为量化器所需的存储容量。 度量矢量量化器的时间复杂度一般用两种办法：一是以每量化一个输入矢 量，需要用乘法运算的次数来衡量；一是以每量化一个输入矢量，需要加减法、 乘法和比较运算( 即三元组) 的次数来度量。对于基本矢量量化器而言，设码书 大小为，矢量维数为k ，若采用平方误差测度，那么时间复杂度就可按这两种 办法来度量。 仅用乘法运算次数度量每量化一个输入矢量的复杂度为 b ：觚r ( 次输入矢量) ( 1 - 3 ) 4 用三元组来描述容易得出，每量化一个输入矢量的时间复杂度为 b = ( 怂，) 次乘法+ ( 2 k - 1 ) n 次加法+ ( 一1 ) 次比较j 输入矢量( 1 4 ) 若用编码速率，矢量维数七来表示，则时间复杂度为 b = ( 七2 “) 次乘法+ ( 2 七一0 2 “】次加法+ ( 2 。一1 ) 次比较 输入矢量( 1 - 5 ) 从式( 1 3 ) 可以看出，基本的矢量量化器的时间复杂度随维数七和量化器速率 r 的增加呈指数形式增加，所以它的复杂度比较大。 空间复杂度可表示为 p = 从7( 1 6 ) 1 4 矢量量化的关键技术 ( 1 ) 码书设计 矢量量化的首要问题是设计出性能好的码书。如果没有码书，那么编码将 成为无米之炊。假设采用平方误差测度作为失真测度，训练矢量数为膨，目的 是生成含n ( n 码书的自适应能力不强 针对这些问题，学者们提出各种改进的算法。这些算法大体可分为四大类： g l a 改进算法，包括针对初始码书选择的改进方法以及针对设计速度的 加速算法 基于神经网络的码书设计算法，如自学习神经网络、竞争学习神经网络 基于全局优化技术的码书设计算法，如随机松弛算法、模拟退火算法、 遗传算法和禁止算法 基于模糊聚类理论的码书设计算法 c 2 ) 码字搜索 矢量量化码字搜索算法是指在码书已经存在的情况下，对于给定的输入矢 量，在码书中搜索与输入矢量之间失真最小的码字。 ( 3 ) 码字索引分配 在图1 3 所示的矢量量化编码和解码系统中，如果信道有噪声，则信道左端 的索弓l f 经过信道传输可能输出索引j 而不是索引i ，从而在解码端引入额外失 真。为了减少这种失真，可对码字索引进行重新分配。 1 5 矢量量化与标量量化的比较 标量量化实际上是维数为k ；1 的矢量量化。一般情况下，矢量量化均指k 1 的多维量化。矢量量化之所以能够压缩数据，是由于它能去掉冗余度，能有效的 利用矢量中各分量间的四种相互关联的性质：线性依赖型、非线性依赖型、概率 密度函数的形状以及矢量维数。而标量量化只能利用线性依赖型和概率密度函数 的形状来消除冗余度。 基本的矢量量化编码器需要使用由个k 维矢量组成的码书。对某个输入矢 量进行编码时，在码书中援索与该输入矢量之问失真最小的码字，将其对应的标 号( 需要l o g ：n 比特) 发送到接收端。接受端也具备相同的码书，解码时根据接 收到的标号在码书中找到对应的码字。如果每个采样有m 个电平，刚k 维输入 6 矢量空间大小为时，但码书中仅有个码字，所以从某种意义上说，最大压缩 比可达，= m i n 。采用标量量化时，每个采样需要l 0 9 2m 比特，而用矢量量化 时，每个采样只需( 1 0 9 2 ) k 。 在相同的编码速率下，矢量量化的失真明显比标量量化的失真小；丽在相同 的失真条件下，矢量量化所需的码速率比标量量化所需的码速率低得多。矢量量 化是一种多维模式匹配、多维优化过程。而标量量化是一维模式匹配、一维优化 过程。一般来说，用一维优化是得不到多维优化结果的。但是，由于矢量量化的 复杂度随矢量维数呈指数形式增加，故矢量量化的复杂度比标量量化的复杂度 高。 归结起来，正如速率失真理论所指的那样，不论信源有无记忆，按组( 矢量) 编码总是优于单个样值的逐个编码的。当组长度趋向无穷大时，编码性能可达到 速率失真界，k 越大离速率失真界越近， 7 2 1 引言【。l 第二章矢量量化码书设计算法研究 矢量量化码书设计算法通常是基于一个能较好地反映输入矢量统计特性的 训练矢量集。设训练矢量集为石= k ，而，h 一。 ，待产生的码书为 c = y o ，咒，。 ， 其中矢量t = k ，t l ，甄户 ，码字 y ，= ( y o , y y 精一1 ) ) r ，o i 质心条件：对于给定划分忸。，墨，r 。 ，最优码字弘必须是相应胞腔 足的质心，即 2 2 2 传统码书设计算法 2 2 2 1g l a 算法 弘= c e n t ( r ，)( 2 8 ) g l a 算法是劳埃德标量量化器设计算法f 3 9 1 在矢量量化中的推广。因此，与 劳埃德算法一样，穷尽搜索矢量量化器的设计问题也可以用两个优化准则来描 述： 最近邻条件( 最佳划分) 。对于给定码书，训练矢量集的最佳划分可通过 把每个训练矢量映射为离它最近的码字得到。设给定码书为c = 乩，y l ，y 。) ， 大小为，训练矢量集为x = ( ，而，工。一。 ，则训练矢量集的最佳分类 ，r i ，r 1 满足 r ；= vl4 ( v ，y 。) = m i n d ( v ，y j ) ，v r ( 2 - 9 ) 质心条件( 最佳码书) 。对于给定训练矢量划分，最优码书的各码字为各 胞腔的质心。设给定划分 民，r 1 ，r ) ，为了使量化器的总体平均失真最小， 则码字”必须是胞腔r 中的元素个数，则质心可由下式给出； ) ，= 熹v ( 2 - 1 0 ) 只2 丽壶” g l a 算法在每次迭代中轮流使用上述两条准则。设训练矢量集 x = x o ，孔，h 一。 ，则算法的具体步骤1 4 1 如下： 1 0 步骤l ：给定初始码书c 妨= j ，5 0 ，) ，y 髭。) ，令迭代次数玎= 0 ，平均失 真d 。一，给定相对误差门限占( o 占 1 ) 。 步骤2 ：用码书c 中的各码字作为质心，根据最佳划分原则把训练矢量集 x 划分为n 个胞腔 r 扎硝，r 鼢 ，其中胄j 4 满足 r ”) = p l d ( v ，诊1 ) = m i n , i ( x 。，y ，) ，v x ) ( 2 1 1 ) o s j s n - i 步骤3 ；计算平均失真 判断相对误差是否满足 。( n ) = 面im 刍- i 碧晒j o ，y p ) ( 2 - 1 2 ) ( d ”。一d c ”) d “sg( 2 1 3 ) 若满足，则停止算法，码书c ( “就是所求的码书；否则，转步骤4 。 步骤4 ；根据最佳码书条件，计算各胞腔的质心，即 骤2 。 2 南磊? ( 2 - 1 4 ) 由这个新质心y f “，i = 0 , 1 ，n 一1 形成新码书c “) ，置胛= n + l ，转步 图2 - 1g l a 算法流程图 第一章已经提到，g l a 算法有几个主要的缺点：搜索码字计算繁琐，对初 始码书敏感性强，码书的自适应能力不强。g l a 是种下降算法，每次迭代总 能减少平均失真，而且每次迭代通常只能产生码书的局部变化，即每次迭代后， 与旧码书相比，新码书不可能有非常大的变化，因此，该算法只能得到局部最优 的码书，即g l a 算法一般不能得到全局最优的码书。 2 , 2 2 2 成对最近邻算法 成对最近邻算法( p a i r w i s en e a r e s tn e i g h b o r , p n n ) 由e q u i t z 等人提出1 9 1 。该 算法是删除算法的一种，因为它在设计过程中不断合并胞腔。刚开始每个训练矢 量都独立地占有一个胞腔，以后每次把最近的两个胞腔合并，这个合并过程不断 进行直到胞腔数目达到要求。 假设训练矢量集中的矢量个数为m ，每个矢量都占有一个独立的胞腔，算 法的目的是不断合并相近的两个胞腔直到得到所需数目的胞腔，且最终的码书由 各胞腔的质心矢量组成。设训练矢量集为石= x 0 ，而，x m 一。) ，该算法描述如下： 步骤1 ：令码字数丹= m ，每个胞腔的质心y = 毛，i = 0 , 1 ，m 一1 。 步骤2 ：计算各对码字m 和间的失真d ( y t ，y 。) ，0 ， t ，则停止迭代；否则，从训练矢量集中随机选取个训 1 4 练矢量靠，找出失真最小的码字y p ，即 按下式更新竞争获胜码字 步骤3 ：计算 d ( 靠，) = 峋m “i nd ( 靠，y p ) ( 2 - 2 0 ) 硝“k + c g t ( x 。一”1 ) ( 2 - 2 1 ) 3 1 - 1k = l e ，= k 厶- - q 蚕厶l m a , o + ”一y 2 l ( 2 - 2 2 ) 式中k 为矢量维数，如果e l v q 算法失真大，耗时短，改进该算法时可以满足更大的复杂度，提高 码书的质量。 第三章利用p n n 算法改进初始码书的g l a 算法 根据对g l a 算法和p n n 算法的仿真研究，本章提出一种改进的g l a 码书 设计算法，即利用p n n 算法得到的码书作为g l a 算法的初始码书，以改善g l a 算法的最终码书质量。 3 1g l a 算法的原理和过程闱 g l a 算法是一种迭代算法，其迭代操作是标量量化劳埃德操作的直接推广。 假定随机输入矢量的联合概率密度函数分布且已知，则设计矢量量化器的劳埃德 迭代如下： 统计特性已知的劳埃德迭代： ( a ) 给定码书，g = y 。；i = o , 1 ，n 一1 ，利用最近邻条件找到最优的胞腔 划分： r ，= k ：d g ，y ，) 确定获胜神经元s 的一个邻域范围m ，按如下公式调整虬范围内神经元 的权向量：睨= 睨+ f ( 宇一睨) v c j 。该调整过程使得m 内神经元的权向量 朝着输入向量善方向靠拢。 随着学习的不断进行，学习率占将不断减少，邻域m 也将不断缩小，所有 权向量在输入向量空间相互分离，各自代表输入空间的一类模式。 自s o m 算法提出至今，出现了多种该算法的遍体，l v q 就是其中一种。 4 1 2 学习矢量量化( l v q ) 算法 l v q 算法是对s o m 算法的一种扩展，它的基本思想源于s o m 算法，它对 应的网络结构与s o m 很相像，但并不像s o m 网络那样存在某种特定的拓扑结 构。l v q 算法是种监督型的聚类方法，该算法与s o m 算法最大的区别在于提 供给l v q 网络的每个训练矢量都有一个“标记”，该“标记”用于指明每个训练 矢量所属的类别，在网络的训练过程中起一定的监督作用。因此，l v q 算法实 际上是s o m 算法基本思想在监督学习领域中的一种应用。 l v q 算法对应的网络结构如下： 包含n 个输入神经元，输入向量为x = g ，x ：，h ) ，z 所对应的类别 记为r 。 每个输出神经元，都对应一个权向量杉= h ，吐，由册) ，记所有输出 神经元，构成的集合为q 。 c j 为输出神经元_ ，所代表的类别，不同的输出神经元可以代表同一个类 别。 l v q 网络期望通过对带有“标记”的训练矢量的学习，能够正确预测提供 给网络的测试矢量的分类。 第四章对学习矢量量化码书设计算法( l v q ) 的改进 4 1学习矢量量化的原理1 4 1 1 引言 s o m ( s e l f - o r g a n i z i n gf e a t u r em a p ，简称s o m ) i 网络是一种自组织竞争型 人工神经网络，是一种非监督的聚类方法。s o m 网络的典型拓扑结构如图禾1 所示，它由输入层和输出层( 竞争层) 两层网络组成，两层神经元之间实现全互 连，输入层有n 个神经元，输出层有m 个神经元，并均匀的排列成矩形。 l ，毛2 e 图4 。ts o m 网络的典型拓扑结构 记所有输出神经元c 组成的集合为o ，神经元c 与输入层神经元之间的连接 权向量为形，s o m 算法作为一种非监督聚类方法，理论上可以将任意维的输入 模式在输出层映射成一维、二维甚至更高维的离散图形，并保持其拓扑结构不变。 该算法的聚类功能主要是通过以下两个简单的规则实现的【4 3 】： 对于提供给网络的任一个输入向量孝，确定相应的输出层获胜神经元s ， 其中s = a r g r a i n 。眵一既i j v c 西。 确定获胜神经元s 的一个邻域范围m ，按如下公式调整虬范围内神经元 的权向量：睨= 睨+ f ( 宇一睨) v c j 。该调整过程使得m 内神经元的权向量 朝着输入向量善方向靠拢。 随着学习的不断进行，学习率占将不断减少，邻域m 也将不断缩小，所有 权向量在输入向量空间相互分离，各自代表输入空间的一类模式。 自s o m 算法提出至今，出现了多种该算法的遍体，l v q 就是其中一种。 4 1 2 学习矢量量化( l v q ) 算法 l v q 算法是对s o m 算法的一种扩展，它的基本思想源于s o m 算法，它对 应的网络结