结合网函数插值与TV模型的图像修复算法①

侯海娜, 戴 芳, 杨陈东

1(西安理工大学 理学院, 西安 710054)2(西安航空学院 理学院, 西安 710077)

结合网函数插值与TV模型的图像修复算法①

侯海娜1, 戴 芳1, 杨陈东2

1(西安理工大学 理学院, 西安 710054)2(西安航空学院 理学院, 西安 710077)

TV(Total Variation)模型用于图像修复时没有考虑缺损区域的方向信息, 并且存在收敛速度缓慢以及修复质量较低等问题. 针对图像上方向特征明显的条状缺损区域, 提出带方向的TV图像修复算法(ADTV). 该算法分别针对4种方向(0度、45度、90度、135度)对TV算法离散格式进行改进, 并引入方向判断, 将缺损区域归类到此4种方向进行修复. 实验结果表明, 该算法充分利用了条状缺损区域的方向信息, 有效提高了图像修复质量.为提高修复效率, 将网函数插值分别与TV算法、ADTV算法相结合提出Net-TV算法、Net-ADTV算法. 实验结果表明, 结合算法不但有效减少了迭代次数, 降低了时间成本, 加快了收敛速度, 而且提高了图像修复效果.

TV模型; 网函数插值; 图像修复

1 引言

图像修复[1]是图像处理的重要内容, 通过对图像上的信息缺损区域进行填充, 使修复结果符合人眼视觉连通原理. 基于TV模型[2]的图像修复方法由于容易实现且能够保护图像边缘的优势而成为当前应用最广泛、最成功的修复算法之一. TV模型的思想是利用物理学中的热扩散原理将待修复区域周围的已知信息延伸到缺损区域内部, 通过建立能量泛函, 用变分法最小化该能量泛函, 从而对图像的缺损区域进行修复.但该算法扩散性能低, 在修复图像上较大的缺损区域时, 不能满足人眼视觉连通原理, 在图像平坦区域容易产生阶梯效应, 且收敛速度缓慢. 针对TV模型扩散性能低的问题, Li等[3]通过构建高阶偏微分方程提高模型扩散性能以修复较大的缺损区域, 并取得较好效果, 但计算量大、修复速度慢. 林云莉等[4]通过改进TV模型, 使算法在图像特征明显区域采用各向异性扩散, 而在图像平坦区域采用各向同性扩散, 有效避免了阶梯效应的产生, 但在图像细节修复上仍不能令人满意. Ren等[5]通过对用于求解TV模型的交替方向乘子法进行改进, 使得具体的数值求解采用快速傅里叶变换方法, 算法有效加快了修复速度. 王相海等[6]通过对TV模型的扩散项引入方向梯度和边缘引导函数以确定待修复点纹理走向, 有效保护图像边缘信息,但离散过程复杂. 翟东海等[7]提出的TV双十字算法采用待修复像素邻域8个点的信息进行修复, 有效提高了修复后的图像质量, 但时间成本高.

网函数插值法[8]是一种多变元函数的插值法. 网函数插值算子是借助Lagrange算子, 定义在网函数空间的线性算子. 对于网函数空间中的函数, 用网函数插值算子计算得到的值是准确值, 而且结构简单, 便于计算机操作. 在重力勘探区域场校正[9]、植物群落种群分布格局计算机模拟[10]、图像恢复[11]、图像Bowtie效应修正[12]等方面网函数插值法都有着有效应用, 并显示出其优越性.

本文针对TV修复模型收敛速度慢及修复质量较低的问题, 对缺损区域设置4种不同方向, 并推导相应的离散格式, 提出带方向的TV改进算法, 并将其与网函数插值法相结合对缺损图像进行修复. 本文算法能够有效进行图像修复, 而且收敛速度快. 实验结果验证了算法的有效性.

2 TV修复算法与网函数插值

2.1 TV修复算法

基于TV模型的图像修复算法, 最先由Rudin等人将应用于图像去噪领域的全变分模型[13]推广得到. 其主要思想是构造一个能量泛函, 通过变分法求解此最小能量泛函对图像的缺损区域进行修复, 能量越小, 图像就越平滑. 不考虑噪声时, TV模型能量函数定义为式(1):

其中,u为待修复图像,D表示图像缺损区域, ∇u表示图像的梯度,为图像梯度的模值. 根据变分原理,J(u)取极小值所满足的Euler-Lagrange方程为:

如图1所示, 待修复像素点O的4邻域为A=｛E,N,W,S｝,A'=｛e,n,w,s｝为对应的4邻域半像素点集合. 由差分迭代法离散(2)式得到

最终求得的uO为:

图1 待修复点O及其邻域像素点示

式中uP代表A=｛E,N,W,S｝四个点的像素值,up代表A'=｛e,n,w,s｝四个半像素点的像素值,uO为中心像素点O的更正值.

2.2 网函数插值

用于图像修复的网函数插值法, 仅利用包含缺损区域最小矩形Ω的4条边界信息, 不依赖邻域相关性, 就可将缺损区域修复, 修复后图像具有较好的保真度[11]. 如图2, 记矩形Ω的4个顶点为P1(x0,y0),P2(x1,y0),P3(x1,y1),P4(x0,y1).假设Q(x,y)为Ω内任意一个点, 过点Q作矩形Ω的边界∂Ω的平行线, 平行线与Ω的四条边相交于四个点:Q1(x,y0),Q2(x1,y),Q3(x,y1),Q4(x0,y).过点Q的平行线将矩形Ω分成四个小矩形, 小矩形的面积记作Ai（i=1,2,3,4）, 如图2所示. 矩形Ω的面积记作A.如果f(x,y)在边界∂Ω上是已知连续的函数, 则网函数插值式为:

其中记A5≡A1.

对于相当广泛的函数类f(x,y), 网函数插值结果F(x,y)是精确的, 其中(x,y)表示矩形内点Q的坐标.对于其它函数f(x,y),F(x,y)≈f(x,y), 即F(x,y)为f(x,y)的近似值, 且误差与Ω的面积大小有关, Ω的面积越小, 误差越小. 所以, 式(5)可以用于图像数据修复, 只要所取的区域Ω的面积充分小[11]. 本文取矩形Ω为3×3的正方形,Q为正方形的中心, 这样点Q就与图像上待修复点O重合, 正方形边界上各点与点O的邻域相对应, 对应关系如图1所示. 将待修复点邻域8个点代入网函数插值公式(5)进行修复, 此时式(5)中Ai=1（i=1,2,3,4）,A=4, 式(5)变为下式:

经式(6)多次循环修复后, 缺损区域周围信息扩散到缺损区域内部. 可以看出, 网函数插值只需进行2次乘法运算和7次加法运算, 计算量很小. 因此, 本文利用网函数插值对图像缺损区域进行修复, 既可以提高运算效率, 又可以保证图像修复效果.

图2 矩形Ω示意图

3 本文算法

3.1 带方向的TV图像修复算法

V模型在离散过程中只考虑了待修复点邻域4个点的信息, 如式(4),uO是由邻域四点像素值加权平均得到, 并且没有考虑待修复区域方向信息. 由于信息较少, 其修复结果精度并不高. 事实上, 修复区域方向信息对修复结果具有很大影响. 本文针对0度、45度、90度、135度四种方向条状待修复区域构造相应的TV离散格式, 并将其它方向条状待修复区域归结到此四种改进TV模型进行修复. 由于在离散过程中考虑更多的信息可以有效提高修复精度, 这四种离散格式均采用待修复点邻域6点构造得到. 将此算法称为带方向的TV修复算法, 简称ADTV算法.

由于图像缺损区域内部的信息是不准确的, 如果在修复过程中仍然利用这些不准确的信息对图像缺损区域进行填充, 显然将导致修复结果不佳. 对于不同方向的缺损区域, 可以通过设计算法巧妙地避免使用不精确点的信息. 根据缺损区域的不同方向, 分别利用待修复点周围不同的6个点的信息对中心像素点进行修复. 针对0度、45度、90度、135度四种方向的缺损区域, 依次构造出TV0度算法、TV45度算法、TV90度算法、TV135度算法四种子算法. 此四种子算法进行修复时采用的6个点的分布情况如图3所示.容易看出, 各个子算法所采用6个点均呈现出了明显的方向特征. 以下对ADTV算法中4个子算法的离散格式进行详细推导.

图3 ADTV算法邻域示意图

3.1.1 ADTV算法离散方式

a. TV0度算法

对于0度方向的缺损区域,W,E两点正处于缺损区域内部, 信息不准确, 因此在对TV模型进行离散时, 分别利用此两点上下邻域的像素平均值来代替其真实像素值, 即

离散过程与原TV模型一致. 将式(7)代入式(4),可以推导出TV0度算法公式:

由式(8)可以看出, TV0度算法公式是采用{NW,N,NE,SW,S,SE}6个点的信息对待修复点O进行修复, 并且利用缺损区域的方向信息有效地避免了不精确点W,E对结果的影响.

b. TV90度算法

对于90度方向的缺损区域, 与0度方向的情况类似. 由于N,S信息不准确, 分别用其左右邻域的像素平均值来代替其真实像素值, 即

从而推导出TV90度算法公式:

由式(10)可以看出, TV90度算法公式是采用｛NW,W,SW,NE,E,SE｝ 6个点的信息对待修复点O进行修复, 避免了不精确点N,S对结果的影响.

c. TV45度算法

对于45度方向的缺损区域,NE,SW两点的信息往往不准确, 因此利用｛NW,N,W,S,E,SE｝这6个像素点对O点进行修复.

定义NW,NE,SE,SW四个点的半像素点分别为nw,ne,se,sw, 此四个半像素点均为虚拟点,nw/2,ne/2,se/2,sw/2为其对应的半像素点(对应图4中最内侧小正方形的四个顶点), 各点分布情况如图4所示. 采用式(11)进行近似:

图4 待修复点O及邻域虚拟点示意图

利用nw,ne,se,sw四点对TV算法进行离散, 具体而言, 令由差分表示为:

其中

的离散方式与Jne/2相同. 将式(11), 式(13)与式(14)代入式(12)得

d. TV135度算法

对于135度方向的缺损区域,NW,SE两点信息往往不准确, 在离散过程中采用｛NE,N,E,S,W,SW｝这6个像素点的信息. 离散过程与TV45度算法类似, 可得到TV135度算法公式:

3.1.2 ADTV算法步骤

在进行实验时, 通常先人为地破坏原始图像, 即用户给定缺损区域的掩码信息, 然后根据缺损区域周围的信息, 利用图像修复算法自动填充缺损区域. ADTV算法的4个子算法是基于方向特征的图像修复算法, 适于修复具有明显方向特征的条状缺损区域.因此需要先对实验图进行条状划痕破坏, 使每条划痕均呈现出较为明显的方向特征. 在利用ADTV算法进行图像修复之前, 需要先判断出图像上各缺损区域的方向.

本文采取的判断方向的方法是: 找出每个缺损区域的质心, 再分别计算质心沿四个方向的线段长度,取最长线段对应的角度作为该缺损区域的方向. 这样处理可以使得所有的条状缺损区域都归结于0°, 45°, 90°, 135°四个方向. 计算质心）的公式如下:

其中（xi,yj）表示缺损区域内点(i,j)的坐标. ADTV算法步骤如下:

Step1: 读入缺损图像u及原始图像u0, 确定缺损区域.

Step2: 判断图像上每一个缺损区域的方向.

Step3: 根据当前待修复点所在缺损区域的方向,选用相应的子算法进行修复. 例如, 缺损区域方向为45度, 则选用式(16)对像素值进行更新, 并保存到新图像中.

Step4: 判断是否达到最大迭代次数, 若是, 继续修复下一个缺损区域, 否则, 返回执行Step3.

3.2 结合网函数插值与TV模型的图像修复算法

考虑到TV算法与第3.1节提出的ADTV算法虽然可以有效地保护图像边缘, 但需要多次循环后方能达到较好效果, 时间成本高. 而网函数插值法时间成本低, 但不能有效保护图像边缘. 因此, 研究此两种算法的结合算法, 使其同时具有修复效果好和收敛速度快的特点是十分必要的. 本文将网函数插值法分别与TV模型、ADTV算法相结合, 提出Net-TV算法与Net-ADTV算法.

Net-TV算法在每一次迭代过程中, 都是对图像缺损区域内每一个点先执行网函数插值式(6), 再执行TV算法式(4). 结合算法可以利用网函数插值计算量小的特点, 快速完成初步填充, 然后利用TV算法进行各向异性扩散, 完善图像细节. 这样迭代一次后, 得到的更为精确的点, 可以在下次迭代中得到进一步的矫正. 从而经多次迭代后, 得到更好的修复效果.

Net-TV算法的伪代码如下:

Net-ADTV算法是先判断缺损区域的方向, 并根据方向选取相应的ADTV子算法. 同样地, Net-ADTV算法在每一次迭代过程中, 都是对图像缺损区域内每一个点先执行网函数插值式(6), 再执行相应的ADTV子算法. 具体算法流程如图5.

设置最大迭代次数T, 对待修复图像的每一个缺损区域按图5的流程进行修复. 判断图像上缺损区域方向的方法与ADTV算法一致.

图5 Net-ADTV算法流程图

由3.1节内容可以看到, ADTV算法比较适于修复图像上方向特征明显的条状缺损区域, 局限性强. 事实上, 图像上的缺损区域往往并不是规则的, 对于这一类含任意方向缺损区域的图像, 显然ADTV算法无法直接应用. 若是先对缺损区域进行分段, 用折线逼近, 再根据各段的方向, 利用ADTV算法解决, 可以作为对ADTV算法的一种扩展. 当然该方法仍有局限,预处理耗时多, 不容易满足图像处理的实时性要求.而Net-TV算法对图像的缺损区域形状没有限制, 因此对于包含非规则条状缺损区域的图像, 可以采用Net-TV算法进行修复处理.

4 实验结果及分析

本文实验环境: 2.70GHz Pentium(R) Dual-Core处理器、1.87GB内存、Windows XP操作系统、MATLAB2010(a)开发环境. 为验证本文提出的ADTV算法、Net-TV算法与Net-ADTV算法的修复效果, 将此3种算法与经典的TV算法、文献[7]中的双十字TV算法进行对比实验. 对图6中的两幅缺损图像分别采用五种算法迭代相同次数进行修复, 修复结果如图7和图8所示, 各算法修复后图像相应的PSNR值如表1所示. 图7、图8的1至5行分别表示TV算法、双十字TV算法、ADTV算法、Net-TV算法、Net-ADTV算法迭代30次、50次、100次、300次时的修复效果.可以看出, 采用TV模型修复后的图像, 经多次迭代后图像上仍然残留有部分难以去除的痕迹, 影响视觉效果, 而且收敛速度缓慢. 双十字TV算法是两个TV算法的叠加, 修复后图像较TV算法有更好的效果. Net-TV算法单次迭代效率高, 与双十字TV算法修复效果相当. ADTV算法不但可以很好地去除图像中的划痕,而且比TV模型修复时收敛速度更快, 但可以明显地看到ADTV算法在修复斜向区域时要比修复横向或纵向缺损区域收敛速度慢. 而Net-TV算法、Net-ADTV算法在修复图像时有效地解决了这一问题, 甚至Net-ADTV算法只迭代50次就达到了很好的效果.

图6 原图像及缺损图

从表1可以看出, ADTV算法与Net-TV算法比TV算法修复效果好, 同时, 在达到相同修复效果时比TV算法迭代次数要少. 而Net-ADTV算法在保持修复效果的情况下, 进一步减少了迭代次数, 明显优于双十字TV算法.

由于各个算法计算复杂度不尽相同, 迭代次数的多少不能完全说明算法修复效率的高低, 因此需要引入时间成本对各算法进行比较. 图9和图10分别为各算法在对两幅图像修复过程中, 消耗时间随迭代次数变化曲线以及PSNR随时间变化曲线. 在图9中, TV算法与ADTV算法单次迭代时间相差不大, 而Net-TV算法与Net-ADTV算法单次迭代时间略高于其它两种算法, 这是算法结合网函数插值的必然结果, 但仍然远低于双十字TV算法单次迭代的时间. 从图10中可以看出, 在相同时间成本下, Net-ADTV算法PSNR高于其它算法. 与此同时, 当PSNR达到同一水平时, Net-ADTV算法用时最短, 这是由于Net-ADTV算法只需要迭代较少的次数就可以得到较高的质量. 由于ADTV算法与Net-ADTV算法修复前需要判断缺损区域方向信息, 所以图10中曲线起初与横轴保持平行,之后快速上升. 综上所述, Net-ADTV算法虽然是通过增加单次迭代时间成本以提高修复质量, 但只需要较少的迭代次数, 从而降低了总体时间成本. 这表明, Net-ADTV算法不但修复效果好, 而且修复效率高.

5 结语

本章通过对图像缺损区域方向信息设置4种不同方向, 提出带方向的TV图像修复算法, 即ADTV算法,该算法继承了TV算法能够保护图像边缘等优点, 同时综合缺损区域方向信息和待修复点邻域6个点的信息, 有效提高了修复质量, 但在修复斜向缺损区域时的收敛速度相对于横向和纵向时慢了许多. 针对该问题, 本文将TV算法、ADTV算法分别与网函数插值相结合提出Net-TV算法、Net-ADTV算法. 此两种算法将网函数插值运算效率高的特点很好地融合在TV算法与ADTV算法中, 在保持TV算法与ADTV算法修复效果的前提下, 有效减少了迭代次数, 降低了时间成本, 从而加快了收敛速度. 但ADTV算法是基于四种方向的离散格式提出的, 只适合修复方向特征明显的条状缺损区域, 受图像缺损区域形状限制较大, 因此对于图像上非规则的缺损区域, 可采用Net-TV算法进行修复.

图7 各算法对缺损图像B的修复效果比较

表1 各算法对缺损图像A、B、C修复后PSNR结果

图8 各算法对缺损图像A的修复效果比较

图9 各算法消耗时间随迭代次数变化曲线

图10 各算法PSNR随时间变化曲线

1 Bertalmio M, Sapiro G, Caselles V, et al. Image inpainting. Annual Conference on Computer Graphics and Interactive Techniques. 2000. 417–424.

2 Shen J, Chan TF. Mathematical models for local nontexture inpaintings. SIAM Journal on Applied Mathematics, 2002, 62(3): 1019–1043.

3 Li P, Li SJ, Yao ZA, et al. Two anisotropic fourth-order partial differential equations for image inpainting. IET Image Processing, 2013, 7(3): 260–269.

4 林云莉,赵俊红,朱学峰,等.改进的TV 模型图像修复算法.计算机工程与设计,2010,(4):776–779.

5 Ren D, Zhang H, Zhang D, et al. Fast total-variation based image restoration based on derivative alternated direction optimization methods. Neurocomputing, 2015, 170: 201–212.

6 王相海,王爽,方玲玲.图像修复的方向梯度TV模型研究.吉林师范大学学报(自然科学版),2012,5(2):1–7.

7 翟东海,段维夏,鱼江.基于双十字TV模型的图像修复算法.电子科技大学报,2014,43(3):432–436.

8 邱佩璋,陈启宏.网函数插值理论及其应用.上海:上海科学技术出版社,2007.

9 邱佩璋,杨真荣,崔力科.网函数插值法在重力场区域校正中的应用.石油物探,1991,30(2):83–88.

10 杨持,郝敦元,杨在中.羊草草原群落水平格局研究.生态学报,1984,4(4):345–353.

11 戴芳,许晓革,邱佩璋.Coons 型分形曲面片在静止图像恢复中的应用.工程图学学报,2002,23(3):165–168.

12 宋莎莎,张杰,孟俊敏.基于网函数插值的MODIS Level 1B图像Bowtie效应修正.遥感技术与应用,2010,(4):552–559.

13 Rudin LI, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena, 1992, 60(1): 259–268.

Image Inpainting Based on Net Function Interpolation and TV Model

HOU Hai-Na1, DAI Fang1, YANG Chen-Dong212
(School of Science, Xi’an University of Technology, Xi’an 710054, China) (School of Science, Xi’an Aeronautical University, Xi’an 710077, China)

TV(Total Variation) model is used for image inpainting without taking the direction of damaged areas into account, while its slow convergent rate and low inpainting quality are either not as good as expected. To handle these problems, Additional Direction Total Variation (ADTV) algorithm is proposed, which aims at the strip damaged areas with obvious direction characteristic in the image. In this algorithm, discrete formats of TV model are improved in corresponding four directions (0°, 45°, 90°, 135°). The damaged areas will be inpainted in the four types by judging their directions. The experimental results show that the method makes full use of the direction information of the strip damaged areas, and effectively improves the inpainting quality. Finally, in order to improve the efficiency of inpainting, Net-TV algorithm and Net-ADTV algorithm are proposed by combining net function interpolation with TV model and ADTV algorithm respectively. The experimental results show that the combined algorithm not only effectively reduces the number of iterations and time cost, speeds up the convergence rate, but also improves the quality of image inpainting.

TV model; net function interpolation; image inpainting

陕西省工业科技攻关项目(2015GY004)

2016-03-13;收到修改稿时间:2016-05-03

10.15888/j.cnki.csa.005495