Contourlet域分形编码的图像插值算法

应毓海

(安徽广播影视职业技术学院　信息工程系，合肥　230011)



Contourlet域分形编码的图像插值算法

应毓海

(安徽广播影视职业技术学院信息工程系，合肥230011)

摘要：自然图像具有分形局部自相似结构，不同区域不同尺寸的图像块之间存在相似关系。对图像作contourlet变换，根据图像的contourlet域分形编码确定子树与父树之间的变换参数，建立相邻尺度不同区域子带系数间的变换关系，由已知子带对未知的高频子带进行恢复，经contourlet逆变换得到高分辨率插值图像。实验表明，该算法能够对图像的结构细节实现准确有效的恢复，具有较高的插值精度和图像质量。

关键词：图像插值；分形；局部自相似；contourlet变换

插值是图像处理中的基本问题，图像中未知高频细节的精确恢复是图像插值的主要内容。根据Shannon采样定理，对于一个带宽有限的图像，当采样频率不低于其Nyquist频率时，用sinc函数进行内插可以恢复原始的连续图像。由于sinc函数物理不可实现，一些学者提出最邻近、双线性和B样条[1-3]等一系列经典的插值算法进行近似。这类方法实现简单、速度快，但经常会在插值图像中形成模糊或锯齿效应，插值质量不高。其根本原因在于它们所采用的是一个过度简化的分段光滑图像模型。基于局部自相似结构的图像描述方法是近年来提出的一种分形描述方法，它将图像定义为一个带映射的局部迭代函数系统的吸引子，并使用拼贴定理进行重建[4-8]。局部迭代函数系统通常由“父块-子块对”和相应的相似变换关系表示。本文利用图像中的局部自相似结构，通过contourlet域中的分形图像编码，寻找存在相似关系的最优“子树-父树对”，建立相邻尺度子带间的变换关系，由已知子带对未知的高频子带进行恢复，实现图像的精确插值。

1Contourlet域分形编码算法

Contourlet变换[9]是利用拉普拉斯分解和方向滤波器组实现的一种多分辨率、局部的、多方向图像表示方法，与普通的二维可分离小波变换相比，contourlet基函数具有多方向的各向异性支撑，能够有效地对图像中分段光滑的边界进行表达，较好地反映出图像中的边缘结构特征。设空域图像块R大小为2J×2J。若不考虑低频，则R的高频成份对应于contourlet域中一棵根在第J级子带的树TJ，该树由一簇分别代表不同方向的分支组成。设第j级子带具有2L个方向，则TJ的第j级子带数据TJ,j由2L-1个水平主导方向数据块(尺寸为2J-j-L+1×2J-j)和2L-1个垂直主导方向数据块(尺寸为2J-j×2J-j-L+1)块构成，TJ,j的尺寸为2J-j+1×2J-j+1。

空域的块对应于contourlet域中的树，因此当空域中两个块R与D具有相似性时，它们在contourlet域中所对应的树TR和TD之间也是相似的。更进一步，因为R与D的相似性不因空域分辨率的降低而改变，因此TR和TD的各级子带数据间也存在相似性(见图1)。

图1　自相似结构

(1)

(2)

c为收缩算子，它使树失去最精细的第1级子带数据，也即下降一级分辨率。c满足

(3)

gm,n为对比度拉伸因子，可按下式进行最优求解

(4)

(5)

分形解码以迭代方式进行。由(2)式及收缩算子的定义可得

(6)

2插值算法

定义树的膨胀算子d，它使树生长更精细的超分辨率子带Ψ0，也即提升一级分辨率

(7)

(8)

因为d和c为互逆算子，所以

(9)

(10)

当j=0时，得

(11)

图2　子树的第0级子带系数(以虚线框表示)由其父树的第1级子带系数恢复

以(11)式为基础，采用下列算法对图像进行插值，流程如图3所示。

图3　插值流程框图

相应的算法步骤总结如下，

Step 1：给定插值误差控制阈值εinterp；

Step 2：将根在第J级子带的所有子树加入任务队列Qsearch并标记为“高频未恢复”；

Step 5：返回Step 3，进行Qsearch中下一棵子树的恢复，直到Qsearch中的所有子树都标记为“高频已恢复”；

Step 6：作contourlet逆变换，得到2×2倍的高分辨率插值图像。

重复使用上述算法，可以获得更高倍数(4×4倍或8×8倍等)的插值图像。

3实验

为验证本文所提出的插值算法的正确性和有效性，对标准测试图像Lena、Barbara、Goldhill、Mandrill、Boat和Peppers进行插值实验，从主观视觉质量和客观PSNR值对插值结果进行考查。所使用的测试图像全部取自标准测试图像库，图像尺寸为512×512像素，8位灰度量化。插值算法中的参数为：J=3，εinterp=10，4×4次cycle-spinning循环位移操作。Contourlet变换采用Daubeches 9/7滤波器组，四个高频子带Ψ4、Ψ3、Ψ2和Ψ1的方向数分别为4、4、8和8，超分辨率子带Ψ0的方向数为16。

图4和图5给出使用本文插值算法分别对Lena和Barbara进行2×2倍和4×4倍插值的结果。从帽子的边缘、眼睛的轮廓和衣服的纹理等其他细节可以看出，本文提出的插值算法得到的图像具有清晰的边缘结构，不存在锯齿和模糊现象。主观视觉质量较高。

图5　Barbara图像及插值结果(局部)

图6给出本文算法与双立方、边缘导向插值(New Edge Direct Interpolation[10],NEDI)和基于方向滤波器及数据融合插值(Directional Filtering and Coefficients Fusion[11],FDCF)算法的4×4倍插值结果的主观对比。在参于对比的三种算法中，双立方插值没有为图像中提供任何新的信息，并且在边缘处造成了模糊，所以效果最差。对于NEDI和FDCF，尽管在图像的某些区域内提供了比双立方插值更好的高频特征，但也引入了一些虚假的边缘和人工痕迹，降低了图像质量。典型的人工痕迹如图6(c)和(d)中的屋顶瓦片，该部分因为插值算法的强制性边缘连接倾向而形成类似于金属熔融样式的错误结构。与NEDI和FDCF相比，本文算法取得的插值结果边缘清晰锐利，结构重建真实自然，因此具有最好的图像质量。

图6　Goldhill图像及插值结果对比(4×4倍，局部)

尽管PSNR的大小与图像质量的高低之间并无必然的联系，作为数值上的直观参考，我们仍然给出本文算法与上述三种插值算法之间的PSNR对比。低分辨率图像的尺寸为256×256，由原始的标准测试图像作2×2局部平均后下采样得到。

表1　插值算法PSNR值对比(2×2倍插值)

由表1可见，除Barbara图像外，本文算法具有比其他三种算法更高的PSNR值(虽然双立方插值算法在Barbara图像中取得了较高的PSNR值，但该方法得到的插值图像质量并不高)，这与图像主观视觉质量的感受基本一致。

4结论

本文对contourlet域高频子带中的树状局部自相似结构进行研究，通过contourlet域分形编码实现子树与父树的最佳搜索配对，建立相邻尺度子带间的变换关系，由已知子带对未知的高频子带进行估计。与经典方法相比，本文提出的图像插值算法主要优势为：一、contourlet小波基具有多方向性和各向异性，能够对图像中物体的边缘轮廓进行稀疏表达，有效地反映了图像的结构特征；二、算法着眼于相邻高频子带间变换关系的建立，利用不同区域的局部边缘结构之间的相似性进行插值，强调对图像边缘的恢复与重建，与人类视觉系统的特点相吻合。

下一步的研究目标应主要集中在进一步提高插值的精度上，可以对contourlet域分形编码算法进行改进，使用子树尺度可变的自适应四叉树编码策略，减小匹配误差，进一步提高图像的质量。针对插值算法中分形编码运算量较大，计算时间较长的缺点，可以研究利用GPU进行加速，缩短编码时间。

参考文献：

[1]Lehmann T M, Gönner C, Spitzer K. Survey: Interpolation Methods in Medical Image Processing[J].IEEE Trans Medical Imaging, 1999,18(11): 1049 -1075.

[2]Unser M. Splines: a Perfect Fit for Signal and Image Processing[J].IEEE Trans Signal Processing Magazine, 1999,16(6): 22-38.

[3]Lehmann T M, Gönner C, Spitzer K.Addendum: B-spline Interpolation in Medical Image Processing[J].IEEE Trans Medical Imaging, 2001,20(7): 660-665.

[4]Barnsley M F, Jacquin A. Application of Recurrent Iterated Function Systems to Images[J].Mathematics and Statistics, 1989,5(1): 3-31.

[5]Jacquin A. Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations[J]. IEEE Trans Image Processing, 1992,1(1): 18-30.

[6]Davis G. A Wavelet-based Analysis of Fractal Image Compression[J].IEEE Trans Image Processing, 1998,7(2): 141-154.

[7]Hyun J, Lickho S. A Spectrum-based Searching Technique for the Most Favorable Section of Digital Music[J]. IEEE Trans Consumer Electronics, 2009,55(4): 2122-2126.

[8]Lu J, Ye Z X, Zou Y R. Huber Fractal Image Coding Based on a Fitting Plane[J].IEEE Trans Image Processing, 2013,22(1): 134-145.

[9]Do M N, Vetterli M. The Contourlet Transform: an Efficient Directional Multiresolution Image Representation[J].IEEE Trans Image Processing, 2005,14(2): 2091-2106.

[10] Li X, Orchard M T. New Edge Directed Interpolation[J].IEEE Trans Image Processing, 2001,10(10): 1521-1527.

[11] Zhang L. An Edge Guided Image Interpolation Algorithm via Directional Filtering and Coefficients Fusion[J].IEEE Trans Image Processing, 2006,15(8): 2226-2238.

[责任编辑：张永军]

Image Interpolation Based on Fractal Encoding in Contourlet Domain

YING Yu-hai

(Department of Informaition and Engineering, Anhui Broadcasting Movie and Television Vocational College,Hefei 230011, China)

Abstract:Local self-similarities exist in nature images widely. Image blocks with different sizes in different areas are similar to each other. In this paper,such main research contents are conducted:Decompose the image using contourlet transform,calculate the parameters involves in the transform relation between child tree and parent tree based on the fractal encoding in contourlet domain,and establish the transform relation connecting different areas in adjacent subbands. With the help of relations between adjacent subbands,a restoration algorithm of the unknown high frequency subband using known subbands is studied and the high-resolution image is obtained by performing the inverse contourlet transform. Experimental results show that the proposed interpolation algorithm can effectively recover the structural details of images,and as a result high interpolation accuracy and image quality are achieved.

Key words:image interpolation; fractal; self-similarity; contourlet transform

中图分类号：TP301.6

文献标识码：A

文章编号：1673-162X(2016)01-0035-06

作者简介：应毓海(1965—)，男，安徽肥东人，安徽广播影视职业学院信息工程系副教授。

基金项目：安徽省教育厅科学技术研究重点项目(kj2014A033)资助。

收稿日期：2015-10-04修回日期：2015-12-08