基于视觉阈值的分形图像压缩算法研究.doc

基于视觉阈值的分形图像压缩算法研究摘 要 本文提出一种基于视觉阈值的四叉树分割方案，应用于定义域块和值域块的划分，并引入人类视觉系统理论，对传统的定义域块的搜索方法进行了改进，将其与基本的分形图像压缩算法通过实验进行了比较。实验结果表明，在保证重建图像质量的前提下，当视觉阈值为30、60、90 时，该算法的编码速度是基本算法的827倍，是一种有效的图像压缩方法。关键词 视觉阈值； 分形； 图像压缩； 四叉树； 人类视觉系统doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 02. 031中图分类号 tp391 文献标识码 a 文章编号 1673 - 0194（2012）02- 0055- 02 引 言在信息技术领域，图像压缩已经成为一个十分重要的课题。目前出现的图像压缩技术已达到上百种，但是压缩比和压缩效果不佳，且编码、解码时间过长，远不能满足当前信息时代的需要。分形图像编码技术是一种思想新颖的图像压缩技术，具有压缩比率高、解码分辨率无关、解码速度快等优点，受到了国际科学界的广泛关注。但是，分形编码技术具有不对称性，虽然具有很高的压缩比且能快速解码，但是编码时间非常长，使得该技术一直没有得到广泛应用。因此对如何加快分形编码速度方面的研究将具有重要的理论意义和实际意义。 分形图像压缩的基本原理图像数据的分形压缩是利用图像的自相似和自仿射性质，寻找生成该图像的若干局部，将所得的局部参数保存起来，形成编码文件（即压缩后的图像），这就是编码过程。分形压缩的理论基础是迭代函数系统定理和拼贴定理。至于解码过程，是从任意一个初始图像出发，用编码文件中的局部参数，经过若干次迭代生成不变集，所得到的就是与原图像近似的一个图像。 经典的分形图像压缩算法首次成功实现了分形图像压缩的全自动算法，该算法成为分形图像压缩的一个新的里程碑，其编码算法的主要步骤如下：步骤：对大小为 的原始图像进行正方形分割，得到互不重叠且大小相同的 的图像子块，将其称为值域块，用表示，以下相同。步骤： 对于每一个块，在原始图像中找出一个尺寸为 的子块（称之为定义域块，用表示，以下相同），确保对 进行灰度仿射变换及空间变换后，所得到的与之间的平方误差值最小。步骤：对于每一个值域块，记录下面个参数：（） 搜索到的最佳匹配子块的左上角坐标（，）。（） 使与成为最佳匹配的等距变换的序号（一共有种等距变换）。（） 灰度对比度因子，灰度平移因子。以上参数便为原始图像的码，解码时可从任意一个初始图像出发，利用这些码，经过次迭代生成不变集，得到与原图近似的重建图像。 基于视觉阈值分割的分形图像编码算法的算法是将图像分割成固定尺寸的方块，但图像的自相似性不一定会精确地落在给定尺寸的方块内，因此影响了压缩效果。于是学者们提出了更多的分割方法。由等人提出的四叉树分割法最大特点在于可依据匹配误差及压缩比自适应地调整子块和父块的尺寸，尽可能合理地分割图像。与的基本分形压缩算法相比，虽然解码图像质量有一定下降，但具备灵活的分块机制和较高的压缩比，使其较为流行。分割法将原始图像分割成一系列矩形子块，对于搜索不到匹配父块的子块，水平或垂直地将其划分为两个矩形区域，在划分时须使矩形子块的边与图像中出现的水平边、垂直边位置对应，使得子块与父块的图像内容具备自相似性，故能更好地进行匹配。 基于视觉阈值分割的分形图像编码算法的提出四叉树分割法、分割法及其后续的一些改进方案，基本思路都是把图像分割成矩形，但均未考虑到人类视觉系统（）的特性，故无法确保图像子块间的相似性一定能落在矩形块内。由于人眼对灰度的分辨能力仅有几十个数量级，故在一幅相邻像素灰度值相近的的灰度图像中，即便其包含的信息量较为丰富，人眼也难以精确地识别和提取。这说明了人类视觉系统的一个显著特性就是非均匀、非线性的认知图像，即人眼并不能完全感知到图像中的任意细节和变化。因此，如能把压缩过程中一些由数量化误差引起的解码图像变化控制在人眼无法察觉的范围内，就能够在认可的相同图像质量下获得较高的压缩比。本文提出了一种基于视觉阈值分割的分形编码方案，是在改进的四叉树法的图像块分割过程中，引入了检测像素灰度值一致性的步骤，即划分过程中要确保同一块内的各像素灰度值的取值范围不超过给定的阈值。的取值一般为几十个数量级，这是由人类视觉系统的特性决定的。与等人提出的四叉树分割法相比，本文提出的算法主要改进的方面为：（） 对值域块的分割方案。若值域块内所有像素灰度值的两个最值之差超过给定阈值，则把该值域块分割成4个尺寸相同的子块，直至小于给定阈值或达到预设的图像分割尺度时，则分割过程停止，最后得到多种不同尺寸的块。本方案将的视觉阈值这一特性纳入了考量，按照一致性准则，图像块的相似性必定落在矩形内。（） 对定义域块的分割方案。首先将 的原始图像整体进行水平与垂直的的子采样，得到子采样图像，其尺寸为（） （），该方法通过对图像整体的一次子采样即实现了对全部块的缩放，大大加快了编码速度。随后采用对值域块的分割方案对采样图像进行定义域块分割，最后得到多种不同尺寸的块。（） 对搜索块方案的改进。寻找与某一块形成最佳匹配的块，只需搜索池的一个子集，该子集中所有块的尺寸均与该块相同，故避免了对池进行全域搜索，有效地缩小了搜索范围。因此，本文算法总的搜索空间仅仅为不同尺寸值域块的总数和定义域块的总数的乘积之和的倍，之所以要乘以是因为每个定义域块还存在种等距变换。显然，这种基于视觉阈值的分割方案能极大地缩小搜索空间，从而也能显著地降低编码时间，并且由于引入的视觉阈值分割方案，也保证了重建图像的质量。设原始图像的尺寸为 ，以下是编码算法的详细步骤：步骤：给定视觉阈值，将分割为个尺寸相同的正方形子块，对每个子块进行一致性标准检测，即检测子块内像素灰度值的取值范围不超过阈值。步骤：设置分割块时的深度范围，即块尺寸的最大值、最小值。步骤：若子块尺寸分割已达最小深度范围，即便其各像素灰度值的范围大于，仍停止分割；否则若块内像素灰度值范围大于，则将其分割为个更小的正方形子块，并对这些子块进行深度范围检测和像素灰度值范围检测。步骤：循环执行步骤，当全部方块的像素灰度值范围均不超过时（即满足一致性标准），退出循环，得到所有块。步骤：对进行水平与垂直的的子采样，得到次采样图像，其尺寸为（） （），将分成4个大小相同的方块，判断每个方块是否满足一致性标准。步骤：重复步骤，直到所有的方块都满足一致性标准才结束。得到多种尺寸的块，形成块池。步骤：对任意块，在块池中搜索一个尺寸相同的最佳匹配块。使得经空间位置变换和等距变换后，与块具有最小平方误差。步骤：记录每个块的如下参数：最佳匹配块的空间坐标（其左上角坐标，）、等距变换的编号、灰度对比度因子、灰度平移因子。 实验结果本节将本文提出的算法和基本的算法进行了实验比较，以期证明本文算法的有效性和正确性。在本实验中机器配置为：为 ，为 ，为。实验环境为 ，通过编程分别实现了这两种算法。在本实验中，基本算法的值域块的大小定义为 ，定义域块的大小定义为 ，定义域块的水平和垂直移动步长均设定为；根据客观情况，为了获得较好的重建图像质量，方块（定义域块或值域块）所允许的最小与最大尺寸分别定义为 和 。根据的特性，阈值通常是几十个数量级。以 的标准灰度图像和为测试对象，本实验获得了为、的实验结果，如表所示。当采用的基本分形算法时，由于对图像进行分割后所获得的值域块的总数是一个固定值，如在本实验中即为： ，因而采用的基本分形算法时图像的压缩比为： （ （ ） 。而当采用本文算法时，压缩比是会随着阈值的变化而变化的。表中压缩比的计算公式是： （ （ ），其中表示值域块的总数。其中，定义域块左上角的坐标值和被量化为 和 ，等距变换的矩阵号被量化为 ，灰度对比度因子被量化为 ，灰度平移因子被量化为 。本实验结果中的压缩比是在熵编码前所获得的。 结 论本文将改进的四叉树分割方案同时应用于定义域块和值域块的划分上。同时，基于人类视觉系统理论，对传统的定义域块的搜索方法进行了改进，提出了一种新的搜索方法。最后，基于基本分形算法，提出