基于退火算法的矢量量化.pdfVIP

中国科技论文在线 基于退火算法的矢量量化 张倩 北京邮电大学信息与通信工程学院，北京（100876 ） E-mail: qian.bupt@ 摘 要:矢量量化(VQ)是一种高效的数据压缩方法，它广泛地用于图像压缩、语音和模式识 别等领域。本文通过对矢量量化算法原理的研究，提出并分析了LBG 算法的局限性，并通 过退火算法优化LBG 算法，使量化结果达到全局最小。实验结果证明了方法的有效性。 关键词：适量量化；LBG 算法；退火算法；局部最优；全局最优 1 引言 矢量量化的理论基础是仙农的速率失真理论。1948 年，仙农定义了信道容量，并证明 只要码速率不超过信道容量，符号就能以任意小的差错概率在该信道中传输。1959 年，仙 农定义了速率失真函数 R(D) ，并证明只要R(D)不超过信道容量就能保证接收端的失真不超 过给定阈值 D 。根据仙农的这一理论，可以找到一个最小的信源速率使得系统发送端到接收 端的平均失真不超过给定的失真阈值，这正是数据压缩系统所要做的事情。利用矢量量化编 码技术，编码性能可以任意接近速率失真函数，其方法是增加矢量维数 k 。在实际应用中， 速率失真函数常常作为一个理论下界与实际编码速率进行比较，分析系统还有多大得改进余 地。总之，速率失真理论指出了矢量量化的优越性。但是，由于速率失真理论是一个存在性 定理而非构造性定理，它并没有指明如何构造矢量量化器。 2 矢量量化原理 基本的矢量量化编码和解码过程如图 4-1 所示。矢量量化编码器根据一定的失真测度在 码书中有哪些信誉好的足球投注网站出与输入矢量间失真最小的码书。传输时仅传输该码字的索引。矢量量化解码过 程很简单，只是根据接收到的码字索引在码书中查找该码字，并将它作为输入矢量的重构矢 量。 图 1 矢量量化示意图 Fig1 diagram of vector quantizer 基本的矢量量化编码需要使用由 N 个 k 维矢量组成的码书。对某个输入矢量进行编码 时，在码书中有哪些信誉好的足球投注网站与该输入矢量之间失真最小的码字，将其对应的标号发送到接收端。接收 端也具备相同的码书，解码时根据接收到的标号在码书中找到对应的码字。 矢量量化的三大关键技术是：码书设计、码字有哪些信誉好的足球投注网站和码字索引分配。其中前两项最为关 键。 3 LBG 算法原理及其局限性 本节将主要介绍 LBG 算法原理，并简要分析其自身的局限性。 -1- 中国科技论文在线 3.1 LBG 算法的原理 产生矢量量化码书的一般算法是 LBG 算法，是由 Linde、Buzo 和 Gray 在 1980 年提出 来的。其基本步骤如下： ˆ(1) x (1)初始化：设定一组训练矢量，作为初始的码书 i ，i=1,2,…,Nc ；畸变度量值 d；畸 ε D(0) 变改变量阈值 ，重复计数器 l 初值为 1；把在全部训练矢量上的平均畸变 初始化为一 个很大的值。