【word】 基于排序分离平均算法的码书设计改进算法

【word】 基于排序分离平均算法的码书改进算法 基于排序分离平均算法的码书设计改进算 法 第11卷第33期2011年11月 1671—1815(2011)33—8186—05 科学技术与工程 ScienceTechnologyandEngineering Vo1.11No.33NOV.201l ?2011Sci.Tech.Engrg. 基于排序分离平均算法的码书设计改进算法 杨威谢林柏 (江南大学轻工过程先进控制教育部重点实验室,系统工程研究所,无锡241422) 摘要为了获得性能更佳的码书,以排序的分离平均算法为基础,在获得初始码书后,对于在LBG迭代中可能出现的空胞 腔采用填充与当前码书距离最远输入矢量的方式作为改进,有效地改善了传统LBG算法容易陷入局部最优以及排序分离平 均算法的空胞腔问题.改进算法生成的码书更加接近全局最优.仿真实验证明了该算法的有效性. 关键词矢量量化码书设计LBG 中图法分类号TN919.81;文献标志码A 由于计算机的快速普及以及通信技术的迅猛 发展,数据压缩技术已经变得十分重要.矢量量化 (vectorquantization)作为一种高效的有损数据压缩 技术,由于具有压缩比大,译码简单等特点,现已广 泛应用于语音和图像编码等领域中?J. 1980年,Linde,Buze和Gray提出了具有里程碑 意义的LBG算法,首次引入了矢量量化的概念J. 该算法具有理论严密,收敛迅速等优点,但同时也 存在着对初始码书依赖性强,容易陷入局部最优以 及可能出现空胞腔等缺点.为了改进上述缺点,学 者们也相继提出了多种算法,如模拟退火算法J, 成对最近邻算法4j,遗传算法_5等.文献[3]通过 将最小化代价函数与竞争过程相结合,提出了一种 在学习过程中引入模拟退火的码书设计随机竞争 学习算法;文献[4]提出了一种通过不断合并相近 两个胞腔来获得码书的码书设计新算法;文献[5] 则将遗传算法引入到码书设计中来,提出了一种新 的算法.这些算法的改进点主要集中于两个方面: 提高生成码书的质量或降低生成码书的时间. 本文将排序的分离平均算法作为生成初始码 书的基本算法,在后续的LBG迭代中,对于可能出 2011年8月17日收到国家自然科学基金(60804013), 中国高校基本科研业务费专项基金(JUSRP21011)资助 第一作者简介:杨威(1987一),江苏省淮安市人,硕士,研究方 向:图像压缩. 现的空胞腔采用填充与当前码书距离最远输入矢 量的方式以更新码字.本文的算法进一步降低了 码书对于源图像几何结构的依赖,使码字的分布更 趋向于合理的状态,从而获得了性能更加优越的 码书. 1矢量量化 矢量量化作为一种高效的数据压缩技术,主要 包含三个部分:码书设计,码字搜索和码字索引分 配.其中码书设计和码字矢搜索是矢量量化的 关键. 码书设计的目的是从输入矢量集中挑选并训 练出最能代表输入矢量集的码字,由这些码字构成 码书.设输入矢量集中包含k个m维输入矢量X= {,,…,},其中第i个输入矢量记作=(?, , … ,),i=l,2,…,k.把m维空间尺无遗 漏地划分成n个字空间R,R,…,R,并且满足 R=R1toR2u…R,nR:,i?.在每一个子 空间中选出一个代表矢量c,则矢量集C={C, c,…,}称为码书,凡称为码书长度. 码字搜索就是对于每一个输入矢量,在码书 中找到一个与其最接近(距离最短)的码字C来代 替.记录此码字的索引号,使输入矢量在信道上 传输就只需传输其对应的索引号,最终在解码时只 需根据索引号便可由码书还原出输入矢量,从而达 33期杨威,等:基于排序分离平均算法的码书设计改进算法 到数据压缩的目的. 2码书设计的相关算法 2.1LBG算法 LBG算法是矢量量化的经典算法,完整的LBG 算法应包括初始码书设计和码书迭代训练两个部 分.本文涉及的LBG算法在初始码书设计部分采 用最常用的随机法,其具体步骤如下:输入矢量集 X={,:,…,f,其中k为输入矢量的个数;码书 为C={C,C:,…,C},其中n为码书大小. 2.1.1初始化 令迭代次数的初始值为t=0,平均量化误差的 初始值为D?-x)=?,确定相对误差门限值(0< <1). 2.1.2随机取择 在输入矢量集中随机抽取个输入矢量,作为 初始码字,形成初始码书c??. 2.1.3划分胞腔 将经过t次迭代后的码书c??中各个码字作为 质心,根据最小距离原则把输入矢量集划分为It 个胞腔W.?={“,”,…,},其中(1< m<It)满足={ld(“,c?)=. mind(u,c), U?X}. 2.1.4检查各个胞腔 若某个胞腔内包含的输入矢量个数为0,则从 包含输入矢量个数最多的胞腔中随机抽取一个输 入矢量放人此空胞腔内. 2.1.5计算误差 计算各个胞腔的平均量化误差: 一 . 其中,1<i<k,n,为胞腔”内包含的输入矢量 个数. 计算平均量化误差: D.†?. 2.1.6计算相对误差 D(一?一D() d口—厂一. 一 若delta<,则停止算法,码书c”„即为最终码书,否 则转到步骤2.1.7. 2.1.7重新计算 各个胞腔的质心用以更新码字: . 其中,为胞腔内包含的输入矢量个数.令 It=n+1,转到步骤2.1.3. 2.2分离平均算法 相对于LBG算法中生成初始码书的随机法,一 些学者提出了一种脱离随机性的初始码书生成算 法——分离平均算法.其具体步骤如下: 设输入矢量集X={,,…},其中k为输入 矢量的个数;码书为C={C,e.…c},其中n为码 书大小. 2.2.1初始化 令迭代次数的初始值为t=0,平均量化误差的 初始值为D?-1)=?,确定相对误差门限值(0< <1). 2.2.2计算初始码 对于整个输入矢量集,先将每k/n个输入矢量 分成一组,然后对于每一组的输入矢量用求平均的 方法得到矢量均值,并以该矢量均值作为一个初始 码字,即: c= n./ 其中J.=(k/n)(i一1)+1.直到对It组输入矢量操 作完毕,获得初始码书c. 2.2.3划分胞腔 将经过t次迭代后的码书G??中各个码字作为 质心,根据最小距离原则把输入矢量集划分为n 个胞腔”„={,”,…,},其中?(1< m<n)满足={“Id(M,c)=. mnd(,cD), L?? U?X}. 2.2.4检查各个胞腔 若某个胞腔内包含的输入矢量个数为0,则从 包含输入矢量个数最多的胞腔中随机抽取一个输 入矢量放入此空胞腔内. 8188科学技术与工程11卷 2.2.5计算各个胞腔的平均量化误差 一 I. 其中,1<i<,n为胞腔”内包含的输入矢量 个数. 计算平均量化误差: D(1†?. 2.2.6计算相对误差 delta-. 若delta<,则停止算法,码书C”„即为最终码书,否 则转到步骤2.2.7. 2.2.7重新计算 各个胞腔的质心用以更新码字: †?.xI辫) 其中,n为胞腔”内包含的输入矢量个数.令 n=n+1,转到步骤2.2.3. 分离平均算法的优点在于使生成的初始码书 在一定程度上脱离了随机性,但是该算法却严重依 赖于源图像的几何结构.对于不同的源图像,尤其 是几何结构明显不同的源图像,形成的初始码书在 性能方面也有着明显的差异.因此,分离平均算法 并未使初始码书彻底地脱离随机性. 2.3排序的分离平均算法 由于分离平均算法对于源图像几何结构有着 严重的依赖,一些学者在分离平均算法的基础上提 出了改进,形成了排序的分离平均算法.其具 体步骤如下: 设输入矢量集X={,,…},其中|ic为输入 矢量的个数;码书为C={C,c. …C},其中n为码 书大小. 2.3.1初始化 令迭代次数的初始值为t=0,平均量化误差的 初始值为D?-1)=o.,确定相对误差门限值(0< <1). 2.3.2计算初始码 对输入矢量集中所有的输入矢量按照矢量和 值排序,即:={i,?,},其中S<S<… S将排序后每k/n个输入矢量分成一组对于每 一 组用求平均的方法得到矢量均值,并以该矢量均 值作为一个初始码字,即: 兰?:::?兰= k/n. 其中=(k/n)(一1)+1.直到对a组输入矢量操 作完毕,获得初始码书c. 2.3.3划分胞腔 将经过t次迭代后的码书c”中各个码字作为 质心,根据最小距离原则把输入矢量集X划分为n 个胞腔W.={,”,…,},其中?(1< m<n)满足={ld(u,c)=. mind(u,c.), M?X}. 2.3.4检查各个胞腔 若某个胞腔内包含的输入矢量个数为0,则从 包含输入矢量个数最多的胞腔中随机抽取一个输 入矢量放入此空胞腔内. 2.3.5计算各个胞腔的平均量化误差 一 . 其中,1<i<,nj为胞腔”内包含的输入矢量 个数. 计算平均量化误差: D.†?. 2.3.6计算相对误差 delta-. 若delta<,则停止算法,码书c”„即为最终码书,否 则转到步骤2.3.7. 2.3.7重新计算 各个胞腔的质心用以更新码字: 1?xj. “】%i?W 其中,ni为胞腔”内包含的输入矢量个数.令 =n+1,转至0步骤2.3.3. 排序的分离平均算法相对于分离平均算法的 改进在于多了将输入矢量按照和值排序这一步骤, 33期杨威,等:基于排序分离平均算法的码书设计改进算法 这可以尽可能地使相似矢量被划分在同一组内,从 而降低了初始码书对于源图像几何结构的依赖. 3本文的算法 本文的算法以排序的分离平均算法为基础,在 训练码书的LBG算法部分对于空胞腔的处理进行 了改进,最终得到了性能更优的码书.过程中需要 使用”输入矢量到码书的距离”这个概念,其定义如 下:设d(,C)表示输入矢量到码字C的距离,则 矢量到码书c的距离d(,C)=min{d(,C)I e?C}. 算法的步骤如下:输入矢量集X={.,,…, },其中k为输入矢量的个数.码书为C={C, C. … ,e},其中n为码书大小. 3.1初始化 令迭代次数初始值为t:0,平均量化误差的初 始值为D?-1)=o.,确定相对误差门限值s(0<< 1). 3.2计算初始码 对于输入矢量集内的所有输入矢量按矢量和 值进行排序.将排序后的输入矢量每P=k/n个输 入矢量分成一组,对于每一组的输入矢量用求平均 的方法求得矢量均值,将该矢量均值作为一个初始 码字,即: (o)一??:::?t .j—P. 其中,=0,1,…12—1.最终获得初始码书c?. 3.3划分胞腔 将经过t次迭代后的码书c?中各个码字作为 质心,根据最小距离原则把输入矢量集划分为n 个胞腔W.?={,”,…,},其中?(1< m<n)满足:{ld(“,c)=. mind(,c?), J?n IZ?X}. 3.4检查各个胞腔 若某个胞腔内包含的输人矢量个数为0,则将 与当前码书距离最远的输入矢量放人此空胞腔内. 3.5计算各个胞腔的平均量化误差 一 . 其中,1<i<k,n为胞腔”内包含的输人矢量 个数. 计算平均量化误差: D.†?.n 3.6计算相对误差 delta-. 若delta<,则停止算法,码书c??即为最终码书,否 则转到步骤3.7. 3.7重新计算各个胞腔的质心并更新码字 = 1?. “ixiW 其中,ni为胞腔内包含的输入矢量个数.令 n=n+1,转到步骤3.3. 本文算法对于过程中可能出现的空包腔的处 理进行了合理的优化,通过将离当前码书最远距离 的码字引入空包腔,从而使码字的分布更加趋于合 理,有效地提高了最终码书的质量. 4l所示,最终 的解码图像对比如图l所示,其中(a)为源图像, (b)为传统的LBG算法解码图像,(e)为排序分离 平均算法的解码图像,(d)为本文算法的解码图像. 由表l中的数据,本文算法的峰值信噪比相对