基于遗传算法的分形图像压缩技术研究
- 格式：pdf
- 大小：626.81 KB
- 文档页数：4
第３０卷第４期
２０１３年４月 计算机应用与软件
Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｓｏｆｔｗａｒｅ Ｖ０１．３０ Ｎｏ．４
Ａｐｒ．２０１３
基于遗传算法的分形图像压缩技术研究
田振川 李冠朋 王蒙蒙 朱贵良
（华北水利水电学院信息工程学院河南郑州４５００１ １）
摘要 针对分形图像压缩过程中匹配编码效率和保证解码图像质量的冲突问题，构造一种基于遗传算法的适应度函数，对杂交 算子和变异算子进行设计和优化。实验结果表明，新算法与Ｆｉｓｈｅｒ自适应四叉树算法、均值聚类算法和自适应遗传等四种算法，以
编码耗时（Ｓ）、压缩比和ＰＳＮＲ差值为指标进行比较，在保证解码图像质量的前提下，新算法匹配编码效率获得了令人满意的效果。 该项研究成果为探索图像新型压缩算法提供了一种途径，具有重要参考借鉴价值。
关键词 图像压缩 分形图像编码匹配 遗传算法 杂交算子 变异算子 临界速度
中图分类号ＴＰ３－０ 文献标识码Ａ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３８６ｘ．２０１３．０４．０３８
ｏＮ ＦＲＡＣＴＡＬ ＩＭＡＧＥ ＣｏＭＰＲＥＳＳＩＯＮ ＴＥＣＨＮＯＬＯＧＹ ＢＡＳＥＤ ＯＮ ＧＥＮＥＴＩＣ ＡＬＧＯＲＩＴＨＭ
Ｔｉａｎ Ｚｈｅｎｃｈｕａｎ Ｌｉ Ｇｕａｎｐｅｎｇ Ｗａｎｇ Ｍｅｎｇｍｅｎｇ Ｚｈｕ Ｇｕｉｌｉａｎｇ
（Ｓｃｈｏｏｌ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｏｒｔｈ Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＷａｔｅｒ Ｒｅｓｏｕｒｃｅｓ ａｎｄ Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ，Ｚｈｅｎｇｚｈｏｕ ４５００１１，Ｈｅｎａｎ，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ Ａｉｍｉｎｇ ａｔ ｔｈｅ ｃｏｎｆｌｉｃｔ ｂｅｔｗｅｅｎ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｃｏｄｅ ｍａｔｃｈｉｎｇ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｆｒａｅｔａｌ ｉｍａｇｅ ｃｏｍｐｒｅｓｓｉｏｎ ａｎｄ ｅｎｓｕｒｉｎｇ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｄｅｃｏｄｅｄ ｉｍａｇｅｓ，ｗｅ ｃｏｎｓｔｒｕｃｔ ｎｅｗ ｆｉｔｎｅｓｓ ｆｕｎｃｔｉｏｎ ｗｈｉｃｈ ｉｓ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｔｏ ｄｅｓｉｇｎ ａｎｄ ｏｐｔｉｍｉｓｅ ｔｈｅ ｃｒｏｓｓｏｖｅｒ ｏｐｅｒａｔｏｒ ａｎｄ
ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｈｓ ｓｈｏｗ ｔｈａｔ，ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｃａｎ ｏｂｔａｉｎ ｓａｔｉｓｆａｃｔｏｒｙ ｒｅｓｕｌｔｓ ｗｈｉｌｅ ｅｎｓｕｒｉｎｇ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｄｅｃｏｄｅｄ ｉｍａｇｅ ｃｏｍｐａｒｉｎｇ ｗｉｔｈ ｔｈｅ ａｌｇｏｒｉｔｈｍｓ ｏｆ Ｆｉｓｈｅｒ ａｄａｐｔｉｖｅ ｑｕａｄｔｒｅｅ，Ｋ—ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ａｄａｐｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｎ ｔｅｒｍｓ ｏｆ
ｅｎｃｏｄｉｎｇ ｔｉｍｅ ｃｏｎｓｕｍｉｎｇ（ｓ），ｃｏｍｐｒｅｓｓｉｏｎ ｒａｔｉｏ ａｎｄ ＰＳＮＲ ｄｉｆｆｅｒｅｎｃｅ．Ｔｈｉｓ ｒｅｓｅａｒｃｈ ｏｕｔｃｏｎｍ ｐｒｏｖｉｄｅｓ ａ ｎｅｗ ｗａｙ ｆｏｒ ｅｘｐｌｏｒｉｎｇ ｔｈｅ ｎｏｖｅｌ ｉｍａｇｅ ｃｏｍｐｒｅｓｓｉｏｎ ａｌｇｏｒｉｔｈｍ ａｎｄ ｈａｓ ａｎ ｉｍｐｏｒｔａｎｔ ｒｅｆｅｒｅｎｃｅ ｖａｌｕｅ．
Ｋｅｙｗｏｒｄｓ Ｉｍａｇｅ ｃｏｍｐｒｅｓｓｉｏｎ Ｆｒａｃｔａｌ ｉｍａｇｅ Ｃｏｄｅ ｍａｔｃｈｉｎｇ Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ Ｃｒｏｓｓｏｖｅｒ ｏｐｅｒａｔｏｒ Ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒ
Ｃｒｉｔｉｃａｌ ｓｐｅｅｄ
０ 引 言
分形图像压缩技术是分形理论和几何学延伸发展的一脉重 要分支 Ｊ。它从少量的数据出发，利用空间结构的对称性和自
相似性，实现对图像信息的大幅度压缩。使解码后的图像呈现 出细节的无穷回归特性。在高压缩比的情况下，分形图像压缩 编码仍具有很高的信噪比和良好的视觉效果 ｊ。解码速度快
且与分辨率无关，当放大到任意尺寸时，亦能保持精细的结 构 Ｊ。与其它图像压缩技术相比，分形图像压缩技术彰显出的
巨大优势，受到广泛重视。是一款极具发展前景的图像压缩 算法 ’一 。
分形图像压缩实现过程的关键环节是搜索匹配编码 。
目前业界专家主要采用全局搜索和局部搜索法进行匹配编
码 。全局搜索法虽然进行能够获得最佳匹配值，但耗时过大
的缺陷限制了应用于实际的可能性。目前普遍采用的局部搜索
法虽然可以有效缩短匹配编码时间，但解码图像质量都有不同 程度下降。文献［８］提出的Ｋ均值聚类算法能够有效缩小搜索
匹配范围，但因分类粗糙增大了丢失最佳匹配块的机率，很难获
得稳定的解码图像质量。文献［９］提出的自适应遗传算法减少
了匹配编码时间，但遗传算子设计的不理想降低了解码图像质 量，而且搜索匹配编码耗时也比较大。文献［１０］提出的通过减 少搜索定义域块的领域搜索匹配编码方法，在满足视觉效果的
情况下，仍将近有一半的最佳匹配块需要通过全域搜索法来完 成，显然，降低编码匹配耗时的效果并不理想。
针对局部搜索算法存在的缺陷，本文利用遗传算法所具有 的良好鲁棒性、搜索能力和简单通用特性 “Ｊ，本文采用二进
制编码模式 的染色体，构造了一个适应度函数，经过对遗传 算子的改进，与分形图像压缩编码匹配误差计算相结合，较好地
解决了匹配编码耗时少、解码图像质量低，解码图像质量好、匹 配编码耗时多的冲突问题。实验结果表明，在保证解码图像质 量的前提下，匹配编码也获得了令人满意韵低耗时效果。
分形图像压缩的四个阶段
分形图像压缩实现过程包括预处理，搜索匹配，参数量化编 码和解码四个阶段［ Ｉ６ 。为讨论方便．以２ Ｘ ２ Ｘ ８ｂｉｔｓ原始灰
度图像为例，分形图像压缩的四个阶段过程分述如下： （１）预处理阶段该阶段的任务是将原始灰度图像分割为
收稿日期：２０１２—０９—１１。２０１２年度河南省科技攻关计划重点资助 项目（１２２１０２２１０１７７）。田振川，硕士，主研领域：信息安全，软件工程。
李冠朋，硕士。王蒙蒙，硕士。朱贵良，教授。 第４期 田振川等：基于遗传算法的分形图像压缩技术研究 １３９
值域块（Ｒａｎｇｅ，简称为Ｒ块）和定义域块（Ｄｏｍａｉｎ，简称为Ｄ
块）。Ｒ块的子项，即每个小块记为Ｒ ，且 为ｒ×ｒ（ｒ一般为 ２，或４，或８，或１６的像素数）大小且块与块之间互不重叠。Ｄ
块的子项，即每个小块记为Ｄ 。Ｄ，一般为２ｒ×２ｒ大小且允许块
与块之间重叠。尽管Ｄ块的分割步长可以为任意整数６，但一
般取步长为ｒ或２ｒ，分割后一般用４一领域值平均法或４一采样
法对Ｄ，进行缩减合并处理，缩减后的Ｄ 记为Ｄ （２）搜索匹配阶段该阶段的任务是在Ｄ块中找到一个
与Ｒ 的最佳匹配块Ｄ，。Ｒ 与Ｄ，最佳匹配的标志是两者之间的
匹配误差最小。对找到的Ｄ，进行变换，然后再进行匹配编码。
与Ｄ 匹配编码的误差计算公式 ‘。 为：
（Ｒｉ， ）＝． 。Ｈ ．．，｛ｌｌＲ一 × （Ｆ＇（Ｄｉ））一Ｄ ｘｌ ｌ Ｊ｝（１）
其中的Ｅ（Ｒ ，Ｄ ）Ｒ 为与Ｄ，匹配误差；ｌｌ ｌｌ为２一范数；，定
义为ｒ×ｒ的全１矩阵；Ｐ（Ｄ ）是用４一领域平均法将Ｄ 相邻四 点压缩为一点的几何变换； （１≤ ≤８）表示８种放射变换，
即包括４种旋转变换和４种反射变换；ｓ 和０ 分别为
（Ｐ（Ｄ，））块的压缩因子和亮度偏移量…。
（３）量化编码阶段由阶段（１）和阶段（２）可以获得最佳 匹配块的位置坐标（ ，Ｙ）、对应压缩因子ｓ 和亮度偏移值０ｉ及变
换类型 。五元组｛（ ，ｙ），ｓ ，０ ，ｎ｝可以依序组成一个完整的 分形编码数列。显然，由（ ，Ｙ）也可计算出相应Ｒ 的块号ｍ 。
因此也可以将四元组｛ｍ ，ｓ ，０ ， ｝视为一个分形编码数列。Ｒ
的编码集合描述了吸引子近似于原始图像的迭代函数系统。 （４）解码阶段该阶段是一个相对简单的迭代过程 。Ｊ，
首先设置一幅与原始图像大小相同且像素可以是任意灰度值的 图像Ｆ，并将Ｆ分割。然后依据已知的分形图像编码，对于每一
个子块Ｒ ，用Ｒ ＝ｓ × （Ｐ（Ｄ ））＋０ ×，进行替代。已知的
研究成果表明，一般经过１０次左右迭代即可获得令人满意的解
码图像…。
２适应度函数与遗传算子设计
遗传算法的适应度函数也叫评价函数… ，是在分形图像
压缩实现过程中，用来判断种群体中的Ｄ，映射 的优劣程度的
核心指标。适应度函数的设计¨ 主要满足：①单值、连续、最
大化；②合理、一致性；③计算量小；④通用性强四个指标。依
据遗传算法所具有的良好的鲁棒性和搜索能力等特性，构造一
个基于匹配编码误差的适应度函数，对遗传算子进行设计优化， 以达到保证解码图像质量，又能降低编码匹配耗时的期望目标。
２．１适应度函数的数学模型
确定Ｒ 对应的最佳匹配块Ｄ 是实现分形图像压缩过程的
主要耗时因素 一 。本文用二进制标示Ｄ 坐标（ ，Ｙ），作为个
体染色体，其前一部分表示坐标 ，后一部分表示坐标Ｙ １４］。
求出Ｒ 对应的最佳匹配块Ｄ 一般需要经过多次迭代，每一 次迭代，都会产生一个Ｒ 与Ｄ 的编码匹配计算误差。适应度函
数建模过程描述如下：先由前述可知，式（１）可表示为Ｅ（Ｒ，Ｄ）
＝ｍｉｎ ｌｌ Ｒ—ｓＤ～ｏｌ【Ｉ，该式极小化问题的解为 ， ：
： 。： 一 －ｇ （２） ＩＩ Ｄ—ｄ， 、
且： Ｅ（Ｒ，Ｄ） ＝ｌｌ 一ｒ，ｌｌ 一ｓ。ｌｌ Ｄ一 ｌＩ （３） 具甲，＜ ， ＞表不颐瓦冈 ；ｒ，ｄ分别表不Ｒ，Ｄ的是发均 值。将式（２）代入式（３）可导出： （Ｒ，Ｄ） ＝Ｉｆ Ｒ一＿，ｆｌ ＿８２ ＩＩ Ｄ一 ＩＩ
＝ＩＩ ｎ－；Ｉ ＩＩ 一（ ） ×ＩＩ Ｄ－
＝Ｉｌ Ｒ— ｌｌ ×（ 一 ）
＝“ 一＿，－ ×｛ 一（ ； ； ） ）
＝ｌｌ Ｒ一＿，ｌＩ。×｛ 一（ ） ）（４）
令：
： 二 ： 二 三 ｆ５ ｌｌ Ｄ—ｄｌ ｌＩ 由式（４）、式（５）可知，Ｅ（Ｒ，Ｄ） 的大小取决于ＩＡＩ，ＩＡＩ越 大，则Ｅ（Ｒ，Ｄ） 就越小， 越接近为Ｒｉ的最佳匹配块。同时，由
式（２）和式（５）可导出：
Ａ — Ａ —————— ——一 Ｏ＝ｒ一——————————＝一 Ｄ一 』ｌ ｌｌ Ｄ—ｄ， ×ｄ （６）
由以上推导可知，Ｉ ＡＩ的计算可替代Ｅ（Ｒ，Ｄ） 的计算。在
找到最佳匹配块Ｄ 后，通过 的计算式，显然能够减少编码匹 配误差的计算耗时，同时也获知对比度因子 和亮度因子０的
计算结果。建立适用于分形压缩的适应度函数：
ｆ（ｘ） （７）
其中ｌｌ ｌ『为向量二范式， 为 块对应的匹配块，即Ｄ，，ｒ，
分别为Ｒ，Ｘ块的亮度均值。Ｉ厂（ ）Ｉ值越大，则说明 与Ｒ块编
码匹配质量越高。
２．２遗传算子设计与优化
遗传算子包括选择、杂交（交叉）和变异等算子。杂交算子 是遗传算法的主要进化过程” Ｊ。在分形图像压缩实现过程
中，本文设计的杂交算子是采用赌轮选择法在种群中选择两个
父代个体进行杂交，本文的杂交过程描述如下： 两个父代染色体的基因位先进行“与”运算获得一个临时
