基于插值的图像修复算法

2015-12-08 03:42王茜艳陈力李萌
关键词:权函数邻域像素点

王茜艳,陈力,李萌

(汕头大学工学院,广东汕头515063)

基于插值的图像修复算法

王茜艳,陈力,李萌

(汕头大学工学院,广东汕头515063)

目前,针对小区域缺损的图像修复算法中,大多采用基于迭代的修复算法,然而这些效果较好的图像修复算法,其时间复杂度一般都比较大.本文通过插值的方法,利用破损区域与周边邻域的有效信息之间的相关性,提出改进的基于FMM(快速行进)的图像修复算法;调用仅适用于被检测到的高局部活跃的像素,提出基于LMMSE(线性最小均方误差估计)插值的图像修复算法.实验结果表明,提出的两种算法分别与FMM算法和TV(整体变分法)算法相比,在整体上其修复效果和效率都具有明显的优势.

图像修复;快速行进法;邻近像素;线性最小均方误差估计;整体变分法

0 引言

图像修复是根据图像中信息丢失部分周围的已知信息,对该部分进行重建,其主要目的是对破损的图像进行修复,以构造人眼主观系统可以接受的图像[1].数字图像修复的研究发展至今,从方法上可以大致分为基于非纹理和基于纹理合成两大类,按破损区域则可以大致分为小尺度缺损的图像修复和大区域缺损图像的修复.其中基于非纹理的图像修复方法主要针对小尺度缺损的图像,大概分为基于变分PDE(偏微分方程)的图像修复方法和基于插值的图像修复方法.基于纹理修复的主要针对的是大区域缺损的图像,大概包含两种修复技术:一种是基于图像分解的修复技术,如文献[2]将图像分解为结构部分和纹理部分,利用已有的算法分别对其进行修补和填充,最后把这两部分修复结果叠加起来,得到修复图像;另一种方法如文献[3-4]采用样本块合成技术来填充缺损的信息.

目前,针对小尺度缺损的图像修复模型和算法中,文献[5-7]采用基于高阶偏微分的模型进行多次迭代修复.这些图像修复效果较好的算法,大多都是以较大的时间复杂度为代价,尽管可以得到较好的修复效果,但其耗时较严重.而在实际应用时,通常对处理速度有一定的要求,因此,研究快速有效地修复破损图像的算法具有重大意义[8].基

于插值的修复算法在小区域破损图像的快速修复中,具有一定的优势.其中Telea等人[9]提出的快速行进法,尽管在修复效率上有很大的改进,但其对强弱边缘的保持能力不足.因此,若分析其问题原因并将其改进,在快速修复图像的过程中保持破损区域的边缘强度,是非常有意义的.然而,利用文献[10]提出的由约束最小二乘方法改进的图像恢复方法中的迭代估计思想,可在破损区域内对其边缘像素进行线性最小二乘误差迭代估计,以达到图像的快速修复.在文献[11]中,有人通过定向滤波和数据融合边缘引导提出一种保持边缘结构的线性最小均方误差估计的图像插值技术,因缺失区域的样本在其边缘方向上与其邻近有较高的相关性,即把缺失样本附近区分为两个正交方向上的子集,通过结合两个定向的线性最小均方误差估计,得到高分辨率图像.因此,若将其应用到多个小块区域缺失的图像修复中,对保持缺损图像的边缘信息和快速修复都是具有重大意义.

因此,本文将基于插值的图像修复技术,从以下两个方面进行研究:1)针对快速行进(FMM)修复算法中对强弱边缘的保持能力不足,分析其问题原因并将其改进,提出一种新的基于FMM的修复算法,结合等照度线的扩散方向,定义新的权函数以保持边缘信息.2)将结合LMMSE的方法对缺损图像进行修复.本文将把它应用到多个小块区域缺失的图像修复中,调用仅适用于被检测到的高局部活跃的像素进行线性最小均方误差估计,在很好的保持边缘清晰的前提下,快速的修复破损图像.该方法虽然在破损区域比较大的图像中没有优势,但其在针对较规则或因传输过程中而导致的缺损图像上的效果非常显著,相对于其他方法而言,其在图像修复的速度和对破损区域边缘的处理上都很有优势.

1 FMM算法

FMM算法通过快速行进法,对缺损区域逐步修复,其主要利用待修复像素与周边邻域有效信息的相关性来定义权函数.快速行进法的基本思想是采用时间函数T(x,y)的形式模拟曲线演化过程,将修复区域边缘逐步往里推进,直到破损区域完全修复[12].假设I为待修复的图像,若记Ω为待修复图像I的缺损区域,则鄣Ω为缺损区域Ω的边界,点p位于缺损区域Ω内,且设p点的梯度方向为N.FMM算法为方便计算T值,将图像的像素分为三种状态:缺损区域边界上的像素、边界内的像素和边界外的像素,每种状态的像素都有一个对应的到达时间T.其本质是利用扩散方程求出缺损区域边界内部所有的点到边界上的距离T,其中边界内部的点T的初始值为106,而待修复边界和边界外点的T初始值为0,并将各个像素设为其对应的状态,最后根据计算出来T值,按照离缺损区域边界越近(即T值越小),越先修复的顺序进行修复,直到缺损区域Ω内的点完全修复.

图1 修复模型

2 FMM修复方法的改进

由于FMM算法设计的权函数没有考虑其等照度方向,致使边缘信息保持不佳,因

此其权函数的设计不够合理;且对已知邻域信息采取的信任是相同的,导致对破损区域往里逐步推进修复时,产生误差的累积,使修复后的破损区域比较模糊[13].本文在设计权函数时,考虑加入等照度线方向,并引入自适应插值的置信度因子,对破损区域的像素点插值.即当缺失像素进行插值时,对其邻域的原始像素全部信任,而对经修复得到的像素部分信任,由此避免误差累积导致的修复后破损区域模糊现象.

2.1 权函数设计

根据图1的修复模型,未知像素Ω的点p是由已知邻域信息Bε(p)的点q决定,所以,p点的像素可由Bε(p)中所有的点加权得出,

由于FMM中设计的加权函数W(p,q)是采用切线方向N(p)来评价已知邻域像素点与缺失像素点的相关性程度,即保证了距离p点法线方向越接近的像素点对p点的贡献越大[8].

我们定义权函数为:

N(p,q)为几何距离因子,表示已知邻域信息内与p距离越近的点其贡献越大;R(p,q)为方向因子,可以明显看出它与FMM的方向因子有区别,即利用等照度方向的信息进行传输,考虑到了图像已知区域的结构特征,使离等照度线越近的点的贡献越大;L(q)为水平距离因子,表示离经过P点的缺失图像边界越近的已知像素,对P点的贡献越大.其中为p点的等照度方向矢量,其实际上是由p点附近已知邻域信息所有像素的等照度方向共同决定的,因此,可定义为

2.2 置信度因子

破损区域修复都是通过其周围已知邻域的像素点决定.因此,在其修复的过程中,其周围已知像素越多,则越能得到更好的修复值,且被修复的点也能更好的确定其他待修复点的灰度值,以此达到整体上的修复.本文将建立一种自适应的可信度模型M,将破损区域附近所有像素分为已知像素1(原始)、已知像素2(修复后)和未知像素点三大类,初始化时,将所有的已知像素1置为1,未知像素点置为0,且选取矩阵R进行掩膜,求出已知像素2的值,如图2所示.

本文以p为中心,ε为中心到边界的距离,选取修复时以大小为(2ε+1)×(2ε+1)小方窗ψp的矩阵,模板选取ε为2的方窗,对可信度模型M进行掩膜,以计算出已知像素2(修复后)的像素点的可信度,掩膜后的结果存于矩阵P.

图2 缺损图像掩膜过程

则矩阵P中元素表明图像中相应位置的像素点中周围已修复像素的相对个数[15],且0≤P(i,j)≤1,P(i,j)的值越大,则表明破损图像中(i,j)点所在的5×5邻域内的已知像素越多.如果P(i,j)=1,则表明点(i,j)所在的小方窗邻域全部为已知像素,即处于破损区域的外部;如果0<P(i,j)<1,表明点(i,j)所在的小方窗邻域内既有已知像素也有未知像素,即处于破损区域的边缘;如果P(i,j)=0,表明点(i,j)所在的小方窗邻域全部为未知像素,即处于破损区域的内部.

2.3 修复步骤

通过对权函数和自适应插值的置信度因子分析,改进的FMM修复算法具体过程如下.

(1)初始值设定

①根据水平距离因子L(q),初始化T(q)的值.T被标识为三种状态,即设缺损区域边界上的像素和边界外的像素的T值为0,而边界内的像素取106(原本设为∞);

②将待修复图像进行标记.待修复图像输入为x0,将标记过缺损区域块的图像设为x1,对输入的x1图像取反,表示标记缺损以外的区域,且令可信度模型

(2)像素点修复过程

①根据模板R对可信度模型M进行掩膜,且保存于优先度矩阵P中;

②找出待修复区域中P值最大的像素点f(m,n);

③利用式(1)修复点f(m,n),同时将p点值更新;

④更新M值,将上一步修复完成的该像素点的M值标记为1,即令M(m,n)=1,x1(m,n)=0;

⑥重复②~④的步骤,直至缺损区域完全修复为止,输出处理过的图像x0.

3 基于LMMSE的插值修复算法

3.1 LMMSE插值

基于插值的图像修复技术主要是根据破损区域周围邻近的像素点的相关性,采用一定的修复顺序进行加权或迭代修复.本文取多个小块区域缺失的图像,利用LMMSE对

待修复的图像Dh(m,n)中的破损区域沿着两个方向进行插值:45°方向和135°方向,分别对缺损像素进行线性最小均方误差估计.通过一些线性方法对这两个方向插值的结果用D赞45(m,n)和D赞135(m,n)表示.考虑到以这两个方向作为缺失像素的插值输出时,可能会产生的噪声测量V45和V135.

图3 对像素进行45°和135°方向插值

可写成以下式子进行估计:

将上式重写成矩阵形式Y=1×Dh+V.

在实际应用中,经常用LMMSE替代MMSE,因为这个估计在最小均方误差中,必须知道缺损图像的先验信息.而实现LMMSE,只需要计算Dh和Y的一阶统计和二阶统计,他们也可以是自适应估计的.因此,Dh的LMMSE可计算为[16]:

其中,μh=E[Dh],协方差运算符

方差运算符Cov(A)=Cov(A,A).Dh通过LMMSE运算,融合两个定向测量提供的信息.根据文献[11]可假设v是零均值,并且与Dh无关,则可由(8)推出,

图4 对Dh(m,n)附近像素的迭代插值

且Var(V45)和Var(V135)可估算为:

3.2 LMMSE修复步骤

通过以上分析,本文基于LMMSE的图像插值修复方法的具体过程如下:

(1)输入待修复图像x0和将待修复图像中缺损区域标记的图像x1,检测并标记x1图像中缺损区域的边缘;

(2)通过(6)和(11)分别对破损块进行45°和135°方向上的定向融合插值;

(3)估计出相应的RV,根据式(10),对标记图像x1待修复区域中的像素点修复进行插值迭代修复;

(4)与上一节中的FMM改进算法和TV算法进行PSNR和时间上的比较.

4 实验与分析

本文的两种算法都是用Matlab R2014a在Core(TM)2 Duo,1.96 GB内存的PC机上实现的.实验中将本文提出的两种算法分别在修复效果和修复时间上与FMM算法、TV算法进行对比,快速的图像修复算法主要用于小尺度破损的图像,因此本文的实验图片Lena和Peppers都是通过对正常图像添加人工划痕得出,如图5(a)和(e),而试验图片Lena_mask则是通过模拟传输过程中导致的缺损图像而得出的多块小区域破损图,如图6(a).本文采用PSNR来对图像修复的效果进行评价,

其中,

MSE是表示原始图像与缺损区域修复后的图像之间的均方误差,N为图像的整体像素数,xi为原始图像的像素值,yi为缺损区域修复后的输出图像x0的像素值.

本文给出了三种图像(Lena图像、Peppers图像和Lena_mask图像),利用不同修复算法得出的对比结果如图5所示.本文利用提出的FMM改进算法进行实验时,Bε(p)取为以p点为中心的邻域窗口.由于改进的FMM算法加入等照度线方向,且当缺失像素使用经修复过的像素进行自适应插值时,对其邻域的原始像素全部信任,而对经修复过的像素部分信任,因此其在修复效果上对于缺损区域边缘的保护比较明显;且引入自适应插值的置信度因子对缺损区域的像素进行顺序选择,与FMM的扩散方程相比,其在修复时间上也更有优势.表1列出了相应的PSNR和修复时间T统计结果,P1和P2分别表示FMM算法和TV算法进行修复后的PSNR,P3为通过改进的FMM算法修复后的PSNR;T1和T2分别表示FMM算法和TV算法进行修复所花费的时间,T3为通过改进的FMM算法修复后所花费的时间.

表1 FMM算法、TV算法与改进后FMM算法的修复结果对比

图5 图像修复结果1

而本文提出的基于LMMSE的插值修复算法,主要是根据破损区域周围邻近的像素

点的相关性,采用一定的修复顺序进行加权或迭代修复.以Lena_mask为实验图,表2列出了LMMSE算法和FMM算法、TV算法修复的结果对比,P1、P2、T1、T2与表1中的表示是一样,P4和T4分别表示通过LMMSE的插值算法进行修复后的PSNR和花费的时间.从表1、表2中可以看出,综合考虑修复效果和时间,本文提出的两种算法比FMM和TV算法更具有优势.

表2 FMM算法、TV算法与LMMSE插值算法的修复结果对比

图6 图像修复结果2

5 结论

本文针对FMM算法修复可能导致的缺损区域修复后边缘信息模糊问题,提出了一种改进的FMM算法,结合等照度线方向,并引入自适应插值的置信度因子对缺损区域的像素点插值.而在针对多块小区域较规则破损的图像修复时,本文采用的是基于LMMSE的插值修复算法,调用仅适用于被检测到的高局部活跃的像素进行线性最小均方误差估计,因此,其可以更好的保持缺损区域的边缘信息.实验结果表明,从整体上来说,本文提出的两种算法都能在保持良好的修复效果时,有效的提高了修复效率,达到快速且有效的修复目标.

[1]魏琳,陈秀宏.基于纹理方向的图像修复算法[J].计算机应用,2008,28(9):2315-2317.

[2]张红英,彭启琮.数字图像修复技术综述[J].中国图象图形学报,2007,12(1):1-10.

[3]李景辉,张晓峰,马燕.纹理合成在图像修复中的应用研究[J].计算机工程,2009,35(7):206-208.

[4]邓悟,吴笛,腾奇志,等.基于区域填充的图像修复算法研究[J].计算机与数字工程,2014,42(3):495-525.

[5]Bertalmio M,Sapiro G,Caselles V,et al.Image inpainting[C].Proceedings of ACMSIGGRAPH 2000. New York:ACM Press,2000:417-424.

[6]Chan T F,Shen J H.Mathematical models for local non-texture inpainting[J].SIAM J Appl Math,2002,62(3):1019-1043.

[7]Chan T F,Shen J H.Non-texture inpainting by Curvature-Driven Diffusions(CDD)[J].J Visual Comm Image Rep,2001,12(4):436-449.

[8]李开宇,孙玉刚.引入连续性强度和置信度因子的快速图像修复[J].中国图象图形学报,2012,17(4):465-470.

[9]Telea A.An image inpainting technique based on fast marching method[J].Graph Tools,2004,9(1):23-34.

[10]沈瑛,吴建华,吴禄慎.由约束最小二乘方法改进的图像恢复方法[J].数据采集与处理,2002,17(3):325-327.

[11]Zhang L,Wu X L.An edge-guided image interpolation algorithm via directional filtering and data fusion[J].IEEE Trans,on Image Processing,2006,15(8):2226-2238.

[12]康佳伦,唐向宏.一种基于FMM的带方向图像修复算法[J].杭州电子科技大学学报:自然科学版,2012,32(5):147-150.

[13]孙玉刚.数字图像修复技术研究[D].南京:南京航空航天大学,2011.

[14]肖志云,张文霞,姜玉莉.基于快速行进法的快速图像修复算法[J].计算机应用,2007,27(12):60-65.

[15]侯正信,何宇清,许微.一种快速的图像修复算法[J].中国图象图形学报,2007,12(10):1909-1912.

[16]Karmen E W,Su J K.Introduction to optimal estimation[M].London:Springer-Verlag,1999.

Image Inpainting Algorithm s Based on Interpolation

WANG Xiyan,CHEN Li,LI Meng
(Department of Electronic Engineering,College of Engineering,Shantou University,Shantou 515063,Guangdong,China)

For image repair in a small defect area,iterative algorithms with high computational complexity are commonly used.In this paper,an improved fast marching method(FMM)is proposed by using correlation information in the neighborhood of damaged area.A new image restoration algorithm based on LMMSE interpolation is also proposed by using pixels with high local activity only.Experimental results show that the proposed algorithms have improved performance as compared with the FMM method and integral variation method(TV).

image inpainting;fast marching method;adjacent pixel;linear minimum mean square error estimation;integral variation method

TN 919.8

A

1001-4217(2015)02-0072-08

2014-09-29

王茜艳(1990-),女,江西吉安人.研究方向:数字图像处理.E-mail:12qywang@stu.edu.cn

猜你喜欢
权函数邻域像素点
基于改进权函数的探地雷达和无网格模拟检测混凝土结构空洞缺陷工程中的数学问题
一类广义的十次Freud-型权函数
基于局部相似性的特征匹配筛选算法
稀疏图平方图的染色数上界
异径电磁流量传感器权函数分布规律研究*
基于5×5邻域像素点相关性的划痕修复算法
基于邻域竞赛的多目标优化算法
基于canvas的前端数据加密
基于逐像素点深度卷积网络分割模型的上皮和间质组织分割
关于-型邻域空间