基于SNAMG分割的分形图像压缩方法

贺 杰， 郭 慧， 李 琳

(1.梧州学院 广西高校行业软件技术重点实验室，广西 梧州 543002；2.梧州学院 信息与电子工程学院，广西 梧州 543002；3.武汉科技大学 计算机科学与技术学院，湖北 武汉 430081)



基于SNAMG分割的分形图像压缩方法

贺 杰1*， 郭 慧2， 李 琳3

(1.梧州学院 广西高校行业软件技术重点实验室，广西 梧州 543002；2.梧州学院 信息与电子工程学院，广西 梧州 543002；3.武汉科技大学 计算机科学与技术学院，湖北 武汉 430081)

针对分形图像压缩的编码速度与解码质量难以均衡优化的问题，依据人类视觉系统特性，使用视觉阈值对图像的SNAMG分割方法进行优化，建立了自适应子块分割机制，并将其用于改进编码过程．实验表明，较之Jacquin的经典分形算法，本文算法能够获得30～40倍的加速比和更好的解码质量．

分形图像压缩；视觉阈值；SNAMG

图像的分形编码是同等解码质量下压缩比最高的空间域压缩方法之一，并具备解码速度快、解码分辨率无关等优点，已有学者将分形编码的图像自相似性描述思想用于解决图像检索[1]、图像分割[2]、图像修复[3]、数字水印[4]等问题．

分形图像压缩方法也存在编码时间过长、解码易出现块状效应等不足．一些学者通过子块分类和邻域搜索来缩短编码时间。K. Jaferzadeh等利用像素值空间和1D-DCT矢量实现子块的模糊聚类[5]；郑秋梅等使用脉冲耦合神经网络算法对原图像进行不规则区域分割，然后利用所得二值图像的灰度值与原图像的灰度值两个特征对图像块进行联合分类[6]，这两种方法均在保证解码质量的前提下，大幅减少了编码时间。李高平等则使用转动惯量特征来实现邻域搜索，从而有效缩小匹配搜索范围，提高编码效率[7]。也有学者通过改进分割方法或结合其他算法来提高解码质量。屠添翼、石跃祥将图像的小波树加权处理、然后再结合分形编码进行混合压缩，在压缩比相同的情况下提高解码图像质量[8]；Hui Guo等则使用视觉阈值改进了四叉树分形编码方法，将解码时的失真控制在人眼无法察觉的范围内[9]；牟宇飞等对图像小波变换后的最低分辨率子带进行均匀量化编码，对高分辨率子带通过阈值控制采用四叉树分形编码，实现解码质量的提升[10]。

上述研究均可使分形压缩在速度或解码质量某一单方面获得优化，但无法做到两方面性能的均衡提升。分割方法是控制编码子块总量、保留图像局部纹理特征的关键，SNAMG(Square Non-symmetry and Anti-packing Model for Gray Images)分割方法能够自适应图像纹理，根据灰度分布自动调节子块大小，产生的子块总量少于已经广泛应用的四元树等表示方法[11]．因此，本文尝试利用人类视觉系统特性，通过视觉阈值与双线性内插法优化SNAMG分割，并将其用于改进分形编码，从而做到编码速度与解码质量的均衡优化．

1 分形图像压缩方法

分形图像压缩将图像分割为定义域块(D块)与值域块(R块)，利用图像的局部自相似性寻找它们之间的对应关系[12]．对于大小为256×256的图像，首先将图像分割为互不重叠的8×8的值域块，构成值域池(Range Pool)；然后以2个像素为步进值，将图像分割为重叠的16×16的定义域块，构成定义域池(Domain Pool)．分割过程如图1所示．

编码时每个值域块必须在定义域池中寻找最佳匹配的定义域块．仿射变换如式(1)，说明了值域块对应至定义域块的转换关系．

(1)

W为值域块的仿射变换，x、y、z分别为值域块的横坐标、纵坐标及灰度值，i与j为定义域块的坐标，p为对比度平移系数，q为亮度平移系数．ak、bk、ck及dk则构成等距变换的8种系数矩阵，代表空间域的8种同构旋转，如式(2)所示．

(2)

编码完毕后，记录(i,j)、p、q及表征旋转方式的系数k作为分形码．解码时则通过局部迭代函数系统，不断地迭代并逐步收敛以获得重建图像．

2 人类视觉系统

人类视觉系统无法完全辨别出图像中所有纹理及灰度变化，这种特性使人眼在边缘区域能够容忍较大的量化误差，视觉阈值即指恰好能够被感觉到的量化误差值．在现有图像的参考灰度值基础上加减不同阈值，然后用人眼观察与原图像的差别，若人眼辨别不出图像的变化则说明该阈值为最佳阈值．由图3可知，最佳阈值应设定在30左右．

3 SNAMG分割方法

分割方法对灰度纹理的适应性直接影响子块总量与解码效果．经典分形编码算法采取的固块分割方式简单易行，但不具备纹理自适应性．为弥补其不足，Fisher将四叉树分割方法引入分形编码[13]，通过灵活的分块机制提高了编码速度和压缩比．

灰度图像的SNAMG方法对于图像纹理的自适应性显著优于四元树方法，产生的子块数量也远少于四元树等表示方法．其原理可简述如下：预定义灰度正方形子块框架，对于给定的灰度图像，利用逆布局算法，依据匹配灰度值，分割提取并记录正方形、线段、点子块，然后用其组合来表示该给定的灰度图像．图3是一幅给定大小为8×8、位深为3的灰度图像及其逆布局表示结果，共从原图中抽取出了S1～S7共7个正方形，L1～L8共8个线段和2个孤立点P1、P2．

4 基于HVS特性与SNAMG分割的分形编码算法

4.1 基于HVS阈值的SNAMG分割

经典四元树方法与SNAMG方法仍从直观上对图像进行分割成块，均未顾及到人类视觉系统特性，而人眼对灰度误差的容忍度有助于在分割时更充分地保存局部纹理，从而使局部相似性更有效地落在子块内，故可通过阈值优化SNAMG分割，寻找像素灰度值在分割阈值范围内、覆盖面积最大的子块，从而尽可能保留图像局部灰度纹理，减少子块的总量．其基本原理是在逆布局分割时以正方形初始点的灰度值g为参考值，假设阈值为x,则在分割过程中，只要近邻像素点的灰度值处于g+/-(x/2)的区间，即可归为同一正方形．

如图4所示，未设置阈值时会形成较多线段与孤立点，图5中设置阈值后，则将线段和点尽可能地纳入正方形，减少编、解码复杂度，节省存储空间．

4.2 基于HVS阈值的SNAMG分割应用于分形编码

SNAMG分割方案与固块分割方法的区别如图6所示．

固块分割未估计图像灰度分布特征，相邻像素值之间相差不大也会被按规则分割，破坏局部纹理的整体性．图6(b)体现出使用HVS阈值的SNAMG分割方法的优势，即能够较好的适应灰度纹理特征并有效减少子块数量，从而减少后续算法的运算量，缩短编码时间．

4.3 算法描述

编码算法的具体步骤如下：

输入:尺寸为M×M的单幅灰度图像G．

输出:最佳匹配块D的左上角坐标，等距变换序号，对比度因子，灰度平移因子，均方误差．

步骤 1：设置一个计数变量square_num，记录逆布局编码过程中生成的正方形子块的个数，并设其初值为0．

步骤 2：采用SNAMG逆布局分割方法，以形成面积最大的正方形为目标．依据反对角扫描方式，从本次循环进入G的首个像素点开始逐个搜索图中未被标识的像素点，搜索到某个正方形子块的左上顶点(x,y)时，取其为起点，并将其灰度值z作为匹配参考值，设定一个阈值w，若后续被搜索的像素点灰度值处于z±w区间，则将其纳入该正方形，搜索持续至此正方形子块的面积停止增大时，在G中将其包含的所有像素点标识．

步骤 3：使square_num=square_num+1，将该正方形子块的左上顶点坐标(x,y)、边长length和灰度值z，存储到队列square中．

步骤 4：重复执行步骤2与步骤3，直到无法提取出新的正方形子块时则停止，从而获得若干互不相交且尺寸相异的正方形值域块，形成R块池．

步骤 5：对G采取水平方向和垂直方向上的1/2次采样操作，获得大小为(M/2)×(M/2)的次采样图像G’，并通过阈值SNAMG分割构造D块池．

步骤 6：为每个R块在D块池中搜索最佳匹配子块D，D通过灰度仿射变换操作与空间变换操作后，所获得的D′与R之间的平方误差值最小．

步骤 7：对于任一值域块R，均记录以下3个特征参数，形成分形码：

(1) 最佳匹配子块D的左上顶点坐标．

(2) 令R与D形成最佳匹配的等距变换的类型序号．

(3) 灰度对比度因子，灰度平移因子．

假定R中的任意一个像素值为ri，D′中的任意一个像素值为di，其中1≤i≤n，n代表R中的像素的总数目，则本算法中s和p的计算方法如下：由于

(3)

且

D′=s×T2×T1(D)+p×I,

(4)

欲求mse的最小值，只需令

(5)

联立以上两个方程易解出：

(6)

(7)

解码算法步骤与经典算法基本一致，最后通过双线性内插法对编码产生的点和线段填充补偿．

5 实验及分析

实验环境为Windows 7.0、Corei5 2.26G处理器、2G内存、Matlab7.0集成开发工具．实验图像如图7所示，均为256×256的灰度图像．

实验以Jacquin的基本分形算法为比较对象．Jacquin算法中R块尺寸为4×4，D块尺寸为8×8，D池的滑动窗口的步长为8，值域块总数为 (256/4)×(256/4)=4 096．由于不同图像的纹理相异，使用SNAMG方法达到最佳分割效果的阈值Q也有不同，如表1所示．

表1 两种分割方法的值域块总数

由表1可知，阈值SNAMG方法获得的值域块数量显著少于基本分形算法的值域块数量．两种方法的编码时间T、压缩比、相对加速比、PSNR如表2所示.

表2 两种方法的性能对比

由表2可知，本文算法是基本算法编码速度的35倍左右，且解码图像质量优于基本算法．其中oldhouse的加速比最高，解码质量最好．该图的灰度分布比较均匀，通过SNAMG分割后，纹理平滑部分形成的子块较大，从而使值域块数目最少，故编码时间比其他几幅图要少，其加速比随之增高．同时该图的边缘细节变化较为明显，因而在边缘细节形成较小子块，确保了该图在解码时能够获得最好的图像质量．同理可知，由于bird灰度分布复杂且细节较多，导致该图加速比最低且还原图像质量最差．

Jacquin算法分割所获得的值域块总数是一个固定值，实验图像大小均为256×256、位深为8，因而压缩比C为256×256×8/(S×(8+8+3+5+7))= 4.13．其中S为值域块总量，定义域块左上顶点的纵横坐标值均量化为8 比特，等距变换的类型号被量化为3 比特，灰度对比度因子与平移因子则分别量化为5 比特与7 比特．由于S为固定值4 096，故每幅实验图像的压缩比均相同．采用本文的SNAMG分形算法时，压缩比C′=256×256×8/(S×(8+8+3+5+7)．S也为值域块的总量，其余参数量化值不变．每幅图像经SNAMG分割产生的值域块总量均少于固块分割，故压缩比得以提高．

图8是使用Jaquin经典分形算法解码重建后的图像，图9是本文算法在取最佳阀值Q时解码重建后的图像，表2中数据表明本文算法所获得的PSNR均高于经典算法，解码质量更高，且此时从人眼视觉上已经无法看出与原始图像的差异．使用两种算法重建的oldhouse、plane图像的PSNR差值均大于4，图10是将这两幅图像的局部放大5倍后的细节对比，左侧为经典分形算法重建图像，右侧为本文算法重建图像，从主观视觉上即可观察出本文算法的解码效果更好．

6 总 结

利用视觉阈值优化SNAMG分割方案，将其应用于分形图像压缩，通过与Jacquin基本分形算法的实验对比，证明了本文算法有效、全面，能够使编码速度、解码质量、压缩比均得以提高．今后的工作将与分类、邻域搜索等方法结合，进一步提高分形图像压缩的性能．

[1] 洪安祥,陈刚,吴炯锋,等.基于分形编码的图像相似匹配研究[J].电子学报,2002, 30(5):624-627.

[2] IDA T, SALNBONSUGI Y. Image segmentation and contour detection using fractal coding[J].IEEE Transactions on Circuits and Systems for Video Technology,1998,8(8):968-975.

[3] 张彩明,范辉,原达.基于分形的图像修复算法[J].电子学报,2010,38(10):2 430-2 435.

[4] 聂道聪,郑洪源.一种使用正交分形编码的彩色图像水印算法[J]. 计算机与数字工程，2014, 42(1):129-133.

[5] JAFERZADEH K,KIANI K,MOZAFFARI S.Acceleration of fractal image compression sing fuzzy clustering and discrete-cosine-transform-based Metric[J]. Image Processing, 2012，6 (7) :1 024-1 030.

[6] 郑秋梅，赵敏，王风华，等.基于不规则区域分割及灰度排序分类的分形压缩算法[J].中国石油大学学报(自然科学版),2014,38(3):169-173.

[7] 李高平,杨军，陈毅红.改进转动惯量特征的快速分形图像编码算法[J].计算机工程与应用,2013,49(24):144-148.

[8] 屠添翼，石跃祥.基于小波域的加权分形图像编码[J].湘潭大学自然科学学报,2004,26(2):25-28.

[9] GUO H,ZHENG Y P,HE J. A fast fractal image compression algorithm using improved quadtree partitioning scheme[C].Proceedings of the 2011 International Conference on Electrical, Information Engineering and Mechatronics, Jiaozuo, 2011,2: 745-751.

[10] 牟宇飞,张文普,王志中,等.基于小波变换和四叉树的图像分形编码算法研究[J]. 微电子学与计算机, 2013, 30(10):54-57.

[11] HE J, ZHENG Y P,GUO H. A novel gray image representation method based on NAM using nonoverlapping square subpatterns[C]. Proceedings of the 2011 International Conference on Electrical Information and Mechatronics, Jiaozuo,2011, 3: 760-764.

[12] ARNAUD E J. Image coding based on a fractal theory of iterated contractive image transformations[J].IEEE Transactions on Image Processing, 1992, 1: 18-30.

[13] FISHER Y. Fractal image compression with quadtrees [A]. FISHER Y Ed. Fractal image compression-theory and application, New York: Springer-Verlay, 1995：55-77.

责任编辑：龙顺潮

Fratcal Image Compression Based on the Segmentation of Square Non-Symmetry Anti-Packing

HEJie1*,GUOHui1,LILin2

(1．Guangxi Collegesand Universities Key Laboratory of Professional Software Technology, Wuzhou University, Wuzhou 543002;2.School of Information and Electronic Engineering, Wuzhou University, Wuzhou 543002;3.College of Computer Science and Technology, Wuhan University of Science and Technology, Wuzhou 430081 China)

Directed against the balanced optimization of the fratcal coding speed and decoding quality, based on the characteristics of human visual system, this paper uses visual threshold to optimize the non-overlapping square anti-packing segmentation method of images, establishes a self-adaptive segmentation mechanism of sub-blocks and applies it to improve fractal encoding. According to the experimental result, the algorithm in this paper can obtain 30 to 40 times speed-up ratio and better decoding quality compared with the classical fractal algorithm of Jacquin.

Fratcal Image Compression; Visual Threshold; SNAMG

2015-01-17

广西自然科学基金项目(2013GXNSFBA019276，2013GXNSFBA019275);广西高校科研项目(2013YB227, 2013YB228);武汉科技大学青年科研骨干基金项目(2014XZ017)

贺杰(1982— ),男，湖北 荆门人， 副教授.E-mail:guohui928@qq.com

TP391.4

A

1000-5900(2015)03-0093-08