图像块自相似特征的快速分形编码算法

李高平，宋建成

(西南民族大学计算机科学与技术学院，四川 成都 610041)

图像块自相似特征的快速分形编码算法

李高平，宋建成

(西南民族大学计算机科学与技术学院，四川 成都 610041)

为了解决全搜索分形图像编码算法在编码过程中range块和domain块匹配特别耗时问题，定义了每个range块和domain块的自相似特征，由于在自仿射变换下最优匹配块间的自相似特征应该接近，因此，每个range块的最优匹配块搜索范围仅限在与其自相似特征接近的domain块邻域内，变全局搜索为局部搜索.六幅图像的仿真结果表明，它确实能够在PSNR降低0.48dB(其结构相似性SSIM值仅下降0.0015)的情况下，平均耗时仅为全搜索分形编码算法的18.65%左右，而且也优于其他特征算法，所提算法达到了加快编码过程速度的目标.

图像压缩；分形图像编码；四邻域像素值平均；自相似特征

分形图像压缩编码算法是一种基于图像具有的自相似性来实现图像数据压缩的新一代有损编码方法，用压缩映射集来表达图像信息，并用迭代的方式来恢复原图像.但它有一个明显的缺点，编码过程需要花费大量时间才能完成在一个数量庞大的码书中找寻出每个与编码range块相匹配的domain块，使其计算复杂性很高，进而限制了它在图像压缩领域的运用.近年来，在尽量不降低图像质量的情况下来加快分形编码速度，成为许多学者研究的重要内容，通过提出的措施也取得了较好的加速效果[1-16].其采用的措施主要有分类法和特征向量法，目的是减少搜寻待编码range块的最优匹配domain块的范围，变全局搜索为局部搜索.措施的有效性取决于局部搜索得到的domain块有多少是它的最优匹配块.本文继续研究特征向量法来加快编码过程，在构造图像块的特征向量时，既要便于提取又要注意其维数不能太大，以避免加重存储负担.鉴于待编码图像本身的复杂性各异，就选用蕴含在图像块中的自相似特征来刻画其信息.具体地说，首先把n×n大小的图像块通过四邻域像素值平均收缩为n/2×n/2大小的图像块，然后将收缩前后的两个图像块上像素点灰度值按某种方式向量化为向量X和，最后把它们去均值后得到的两个向量2-范数比值作为图像块的自相似特征.实验结果表明，在编码阶段的匹配过程中，以自相似特征为依据所做局部搜索来取代全局搜索，可以获取大部分待编码range块的最优匹配块.它优于相似比特征[10]和可选特征[15]，据此特征提出的快速算法在解码图像质量降低约0.48dB(其结构相似性SSIM值仅下降约0.0015)的情况下，编码时间明显减少，仅仅为全搜索算法的18.65%.

1 全搜索分形图像编码算法

全搜索分形图像编码过程流程图如图1所示.

图1 全搜索分形图像编码过程流程图Fig.1 The flow chart of the full search fractal image encoding

首先选取一种分割方式，将图像分成两类子块集:编码range块(简称R块，大小为n×n，互不重叠)集和domain块集(简称D块，大小为2n×2n，允许重叠).搜索所用码书Ω，是将domain块集中每个D块采用4ˉ邻域像素值平均收缩成n×n的子块，再经过8个等距变换而得到.

对每个待编码R块，需要求解下面的极小化问题(1)寻找其最优匹配D块的位置和自仿射变换w.

鉴于式(1)是NP难问题，故只能求次优解.首先忽略式(1)中约束｜s｜＜1，将(1)的内层约束极小化转化为(2)式的极小值问题来求解:

然后对不满足｜s｜＜1的对比度因子s以截断方式处理.式(1)的外层极小化问题用全搜索法求解:

解码图像用分形码按迭代方式重构.

2 自相似特征的快速分形编码算法

2.1 算法的理论基础

对于一个N×N大小的图像I，编码R块大小设为n×n，需要编码的R块数量，码书Ω(以符号表示码书容量)中D块大小设置为2n×2n，取生成码书步长为δ，其码书容量大小，若按全搜索方式寻找每个range块的最优匹配domain块，由式(3)可知，它需要搜寻完整个码书Ω中的D块，那编码过程需要次匹配，会因码书Ω容量庞大而消费很多时间，缩减搜索空间是势在必行.下面通过定义图像块的特征，并依据该特征把匹配过程的全搜索转换为邻域搜索.

图2 四邻域像素值平均示意图Fig.2 Four neighbour pixel values average diagram

下面来讨论在自仿射变换下，R块能与D块组成最优匹配块时，它们的自相似特征间的关系.

全搜索方式中，每个待编码R块通过自仿射变换w在码书Ω中寻找均方根误差最小的D块为最优匹配块，即

用最小二乘法求得式(2)中亮度偏移o的解为

将(5)式中o代入(4)式，有

将(6)(7)式两边同时2-范数并做比，有

从(8)式可以看出，若R块和D块能组成匹配对，那它们的自相似比也应该比较接近.

2.2 快速编码算法方案

设计加快编码过程方案时，涉及3个关键因素:编码R块集的数量、码书Ω容量以及采取的搜索法.前面2个因素由分割方案决定，在此讨论待编码的R块在码书Ω中的搜索方式.由(8)式可知，R块和D块能组成匹配对，要求S(D)应该与S(R)接近，也就是说R块的最优匹配Dm块在自相似特征意义下位于与R块自相似特征接近的D块邻域内.所以，在设计搜索法时，首先根据自相似特征值升序排列码书中的全体D块，即，然后，在升序码书Ω中采用二分法搜索与编码R块自相似特征值S(R)相差最小的初始匹配块D块:

其后，编码搜索过程在Dinit的k邻域内进行.对每个编码的R块，它的搜索码书Ωs为

3 仿真实验结果

选择6幅复杂性各异的图像Lena、Peppers、Boat、Baboon、Goldhill和bridge(512×512，8bit量化)来作为实验的测试对象，方块分割图像，R块、D块及码书步长分别取为4×4、8×8和8，此时，编码R块集数量为16384，码书Ω容量为32768，仿真实验平台为PC机(AMD Athlon，3.01GH CPU/2G内存)，算法用C＋＋编写的程序实现.

3.1 自相似特征的有效性验证

本文定义的图像块自相似特征，是用蕴含在图像块中的自相似性来刻画其信息.为了表明图像块自相似特征优于相似比特征[10]和可选特征[15]，下面通过仿真实验测出编码R块在全搜索中得到的最优匹配块，有多少落在上述特征意义下的初始匹配块Dinit的k邻域内.对每个编码R块在该邻域中找到的次优匹配块就是最优匹配块的R块总数量随邻域半径k的变化情况见图3(图中数据取的是6幅512×512测试图像的平均值).

图3 R块总数量随邻域半径k的变化情况Fig.3 The range block quantity vs.radius of neighbour k

图3显示，在相同的搜索邻域半径，在本文特征意义下，能找到最优匹配块的R块的总数量明显高于其它两种特征.在初始匹配块Dinit的邻域内找到的次优匹配块就是最优匹配块的R块数量占总编码R块数的比例分别记为P10、P50和P100，用百分数表示.本文特征、相似比特征[10]和可选特征[15]的这三项指标均列于表1(表中数据取的是测试图像的平均值).

表1 最优匹配块落入邻域N(Dinit，k)内的R块比例Table 1 Proportion of the range block of full best-matched domain block fall into neighbor N(Dinit，k)

表1中数据表明，本文特征的三项指标也好于其他两种特征.上述图表均例证了本文定义的图像块自相似特征是占优的.图表数据也显示，对本文定义的特征，只需搜索码书的10%空间，就有大约30.9%的R块找到了最优匹配块，搜索50%空间就有84.4%，R块需要搜索完整个码书才能找到最优匹配块的比例仅为1.3%.这说明绝大多数的待编码R块的最优匹配块就在图像块自相似特征意义下的初始匹配块附近，验证了它的合理性.

3.2 自相似特征快速算法的有效性验证

先通过实验确定图像块自相似特征意义下的初始匹配块Dinit的k邻域半径k值，以确定搜索码书Ωs的容量.图4是6幅测试图像的解码质量(以PSNR度量)在不同邻域半径k值下的变化情况.

图4 解码图像质量随邻域半径k的变化情况Fig.4 The quality of the decoded image vs.radius of neighbour k

选编码时间(秒)、峰值信噪比PSNR(dB)和结构相似性SSIM(structural similarity)为测试性能参数，来验证本文所提快速算法的有效性.本文算法(k＝0.5)与全搜索算法的对比实验结果列于表2.

表2数据表明，对所给测试对象，本文所提算法加快全搜索算法的编码过程的速度相差不是很大，但解码图像质量相差还是比较大的.取平均值来看，在解码图像质量(以PSNR度量)降低约0.48dB的情况下，编码过程耗时仅为全搜索算法所需时间的18.65%左右.众所周知，作为图像质量评价的客观指标PSNR，没有考虑到人眼的视觉特性，易造成评价结果与人的主观感觉不吻合.为此，引入衡量两幅图像相似度的新指标SSIM来评价图像感知质量，它们的SSIM值仅平均下降约0.0015，这充分说明所提算法的解码图像的主观质量是很不错的.

表2 本文算法与全搜索分形算法对比结果Table 2 The comparison between the proposed algorithm and the full search algorithm

4 结论

只有图像中具有自相似性及比例特性，采用分形图像编码才有效，通过去除图像的几何冗余度来实现图像数据压缩.本文定义的图像块自相似特征用到了蕴含在图像块中的自相似性，在编码过程中，能组成匹配对的R块与D块，它们的自相似特征应该是接近的，这样就把消费时间最多的R块与码书Ω中D块的匹配全搜索问题转化为初始匹配块Dinit(其自相似特征值与S(R)最接近)的邻域搜索问题，算法复杂度大大降低.仿真实验中所用6幅测试图像，验证了在Dinit的k邻域内(搜索码书Ωs)搜寻到的次优匹配块，对绝大多数的待编码R块来说，就是它要找寻的最优匹配块，表明了全搜索被邻域搜索取代是可行的.本文据此所提快速分形编码算法，在解码图像质量(以PSNR度量)降低0.48dB(以SSIM值度量仅下降约0.0015)的情况下，编码过程所需时间仅为全搜索耗时的18.65%左右.且自相似特征相较于相似比特征和可选特征，更能表述出图像块的信息.该算法既有理论分析，又有仿真实验结果的佐证，且在全搜索算法基础上实现比较容易，它无疑为加快分形图像编码过程提供了一个好的算法.

[1]ZHANG AIHUA，YANG PEI.An improved algorithm for fractal image encoding based on relative error[C]//5th International Congress on Image and Signal Processing，IEEE，2012:254-25.

[2]TANG GUOWEI，WU SHUANG，ZHANG YAN.An improved fast fractal image coding algorithm[C]//2th International Conference on Computer Science and Network Technology，IEEE，2012:730-732.

[3]YANG FENGXIA.Study on the effective measures of enhancing the fractal image coding[C]//International Conference on Computational and Information Sciences，CPS，2013:160-162.

[4]WANG JIANJI，LAN XUGUANG，LIU YUEHU et al.Fractal image encoding with flexible classification sets[J].Chin Sci Bull，2014，59 (14):1597-1606.

[5]LI LOU，YONG LI.Research of neighborhood searching fractal image coding algorithm based on ant colony optimization[C].SAI Intelligent Systems Conference，IEEE，2015:761-764.

[6]WANG XINGYUAN，ZHANG DOUDOU，WEI NA.Fractal image coding algorithm using particle swarm optimisation and hybrid quadtree [J].IET Image process，2015，9(2):153-161.

[7]李高平.三均值特征的快速分形图像编码算法[J].中国图象图形学报，2011，16(1):1-7.

[8]李高平，向慧芬，赵正武.四分位数特征的快速分形图像编码算法[J].计算机工程与应用，2011，47(22):145-148.

[9]宁培兴，黄仁.数理统计特征的快速图像分形压缩算法研究[J].计算机工程与应用，2012，48(31):161-165.

[10]张爱华，盛飞，杨培，等.基于相似比的快速分形编码算法[J].计算机技术与发展，2012，22(11):176-178.

[11]钱雅儒，郭中华，雍慧.一种改进的规范块半范数算法[J].计算机工程，2012，38(2):221-223.

[12]苏兆宝，周敏，郑红婵，等.基于像素采样的分形图像编码算法[J].计算机系统应用，2013，22(12):136-139，167.

[13]孙媛媛，孔瑞卿.一种基于字典的快速分形图像编码方法[J].计算机工程，2013，39(1):230-233.

[14]刘树群，潘章容.基于Fisher分类和空间映射的分形图像编码方法[J].计算机应用，2013，33(12):3552-3554，3558.

[15]袁宗文，鲁业频，杨汉生.可选特征的快速分形图像编码[J].中国图象图形学报，2015，20(2):0177-0182.

[16]裔传俊，刘亮.采用边缘分类和平均偏差比较的分形图像编码[J].计算机应用与软件，2015，32(2):211-214.

(责任编辑:张阳，付强，李建忠，罗敏；英文编辑:周序林)

Fast fractal encoding algorithm based on image block self-similar feature

LI Gao-ping，SONG Jian-cheng
(School of Computer Science＆Technology，Southwest University for Nationalities，Chengdu 610041，P.R.C.)

The full search fractal image algorithm requires a very long encoding time，which is essentially spent on searching for the best-matched block to an input range block in a large domain pool.In order to solve this problem，defining the self-similar features of each range block and domain block，on account of the self-similar feature for an input range block and its bestmatched domain block should be approximate based on the self affine transformation，so the self-similar feature is utilized to confine efficiently the search scope to the vicinity of the domain block having the closest self-similar feature to the input range block being encoded，it can exactly avoid the excessive search.Simulation results of six test images showed that the average time of the proposed scheme is only about 18.65%while there is averagely the PSNR decrease of 0.48dB(its the structural similarity decrease of 0.0015)，in comparison with the full search fractal algorithm.Moreover，it is better than the other feature algorithm，the proposed algorithm to speed up the encoding process.

image compression；fractal image coding；average of four neighbor pixel values；self-similar feature

TN919.81

A

2095-4271(2016)05-0544-06

10.11920/xnmdzk.2016.05.013

2016-07-04

李高平(1966—)，男，汉族，教授，研究方向:分形理论及其在图像处理中的应用研究.E-mail:pinggaoli＠163.com

四川省应用基础项目(No.2013JY0180)；四川省教育厅科研项目(No.15ZA0384)