采用顺序修复的样本例图像修复算法①

李旭峰,王 静,王国东,刘红敏,王志衡

1(河南理工大学 电气工程与自动化学院,焦作 454150)2(河南理工大学 计算机科学与技术学院,焦作 454150)

采用顺序修复的样本例图像修复算法①

李旭峰1,王 静2,王国东1,刘红敏2,王志衡2

1(河南理工大学 电气工程与自动化学院,焦作 454150)2(河南理工大学 计算机科学与技术学院,焦作 454150)

本文提出了一种采用顺序修复的样本例图像修复算法,该方法在原Criminisi经典图像修复算法的基础上对修复顺序进行新的尝试.原Criminisi经典算法的修复顺序通过计算优先级得出,随着修复的深入优先级逐渐趋近于0,导致算法失去作用.为解决该问题,本文采用顺序修复的方法来代替优先级决定顺序,避免出现算法失去作用的情况;同时本文提出的“倒L”型样本模板来增强结构的传播能力、提高匹配的正确率.实验结果证明,本文的修复算法相对Criminisi算法具有优势并取得很好的修复结果.

顺序修复;图像修复;样本块;匹配

图像修复方法主要是结合退化图像中待修复区域周围的信息复原待修复区域的未知图像信息,达到人的视觉心理要求[1].图像修复技术在恢复图片中丢失信息、去除图片中不需要的部分及隐藏视频错误信息等问题上得到广泛应用[2].Chan T F 等[3]通过计算偏微分方程实现图像信息的传播,在TV模型[4]的基础上建立曲率驱动扩散(Curvature Driven Diffusions,CDD)模型进行修复,Chen Y等[5]利用拉普拉斯变换来修复线性结构和非线性结构以及它们的混合信息.Florinabel等[6]根据视觉效果的不同程度进行改进,取得很好的效果.Xu[7]等利用样本例的稀疏性对图像信息进行导修复.Criminisi等[8]提出的样本块图像修复算法,其特点是能同时修复纹理和结构信息.通过计算待修复区域边缘点优先级顺序,确定边缘上待修复块的修复顺序,然后根据该顺序进行匹配修复.在该算法基础上,王静等[9]对其进行了修改,改善了该方法匹配错误率较高的问题;T Ružić等[10]利用马尔科夫随机场通过感知待修复区域周围信息进行修复.李旭峰等[11]提出了特征优先的块匹配图像算法,加强了结构传播能力;任澎等[12]提出利用纹理和边缘特征的改进算法,同时又提出了将纹理和边缘特征相结合的图像修复方法[13].

1 Criminis算法及其问题

1.1 算法介绍

Criminisi经典算法[4]以图像块为操作对象将图像中已知区域的信息传递到未知区域,如图1所示,其中I为整个图像,代表已知区域,代表未知区域.其算法分为两个步骤:1)计算待填充边缘的优先级顺序,寻找优先级最高的块作为待填充块;2)将待填充块中的已知部分与图像中已知区域信息进行匹配,找出最合适的块作为填充块,并将填充块填充在待填充位置.

图1 Criminisi算法修复原理

1.2 算法问题

由公式(1)可知优先级为置信项和数据项的乘积,在公式(2)中可以看出,随着修复的深入,分子的值会越来越小,而是一个恒定值,因此也会越来越小,逐渐的逼近0值,最终导致优先级也趋近为0,使算法逐渐失去应有作用.此问题严重影响Criminisi算法的修复效果.

2 本文算法

2.1 算法基础

针对上述问题,本文采用顺序修复图像的方式来避免该问题的出现,同时取得较好的修复结果.本方法中扫描块为一个边长7个像素的正方形块,当扫描块和修复区域重合时,称为待匹配块.如图2所示,为待匹配块,为最佳匹配块,为待填充块,为最佳填充块,为待匹配块的基础匹配区域,为匹配块的实际匹配区域.待匹配块的基础匹配区域和待修复区域不重叠,即Ω=0,保证修复过程中基础匹配区域能为匹配块提供足够的信息支撑.

图2 本文算法修复原理

1.2 算法步骤

修复过程包括以下步骤:

1)建立扫描块,以扫描块为基本单位从上往下、从左往右依次对待修复图像进行扫描,直到扫描块遇到待修复区域;

4)如图2所示,计算每个候选块中填充部分和待填充块两个相邻的像素块的相似度所述相似度同样由SSD距离公式计算得出,计算出的SSD距离值越大说明相似度越小,值越小相似度越大;

5)由第4步可知,每一个候选块有两个相似度值,这里取较小的相似度作为该候选块的相似度值,同时比较所有候选块的相似度值,最小的候选块作为最佳待填充块填充到待填充位置

6)重复执行以上步骤,直到图像被修复完成.

2.3 算法分析

本算法使用扫描块从左往右从上往下依次对图像进行扫描,找到待填充区域时依次对其修复.通过该修复顺序,避开优先级计算方法,同时避开优先级计算时出现的算法失效问题.本算法中采用的基础匹配区域总位于已知信息的区域并参与匹配计算,其形状为“倒 L”形,如图.该形状的优点是,匹配时同时计算了待填充位置上方和左方的图像信息,使匹配信息更全面.在以上基础上,步骤4)和步骤5)选择其中一个方向的块进行相似度计算,进一步的保证填充的信息在其中一个方向上具有更加平缓自然的过渡,保证了图像修复结果的自然、不突兀.本文通过实验结果来证明本文算法的作用及优势.

3 实验结果及分析

本章将文献[8]算法、文献[9]算法和本文算法修复结果进行比较,图4和图5为本文算法和文献[8]、文献[9]算法修复结果对比图,文章同时从定量和观感两方面对各个算法修复结果进行分析和评价.

3.1 定量分析

本文入PSNR(峰值信噪比)对修复结果进行定量分析.PSNR是最大值信号和背景噪音之间的比率,PSNR的单位为dB,为衡量经过处理后的影像品质,通常会参考PSNR值来认定图像处理程序是否令人满意.PSNR值越大,就代表失真越少,即图像修复修复效果越好.表1所示为图4和图5中各个算法修复结果的PSNR.从表中可以看出两幅图中三个算法修复结果的PSNR 中,本文算法都高于文献[8]和文献[9].数据显示本文算法的PSNR最大,说明本文算法修复结果图像质量相对更高,即本文算法更好的修复效果.

图3 “倒 L”形修复模板

表1 算法修复结果的 PSNR (dB)

3.2 感观分析

感观方面,图 4 中(a)为原图像,(b)为待处理图像,(c)为文献[8]算法处理结果,(d)为文献[9]算法处理结果,(e)为本文算法处理结果.图(c)中可以明显看到屋顶部分没有被完全修复成功,屋顶中间缺失一小块,其原因是该算法在修复到一定深度之后算法失去作用,无法控制填充的内容,导致的修复结果不完善;同时,植物向水中延伸的部分也不符合实际规律,除算法作用逐渐减小外,直线传播能力弱也是一个重要的原因.图(d)中,屋顶结构部分被修复完整,但水面也出现很多多余的树木纹理.图(e)中,山上树木纹理部分处理结果和图(c)中相当,对房屋屋顶的处理十分完整,没有出现屋顶部分缺失的情况,这说明本文算法不会随着修复深度而失效;岸边植物的延伸也被很好的限制住,没有无规则的延伸到水中,即本文算法具有很好的直线传播能力.

图4 蹦极人物修复结果

图5 反光镜修复结果

如图 5,(a)为原始图像,(b)为待修复图像,(c)为文献[8]算法修复结果,(d)为文献[9]算法修复结果,(e)为本文算法修复结果.该图像中包含树叶纹理和栏杆直线结构.针对该图片的修复结果除要求树叶纹理自然,直线结构传播无差错之外,还需要保证修复结果中没有不符合常理的多余传播.在图(c)中栏杆得到很好的传播,但是栏杆上面出现多余的栏杆结构,这种情况就属于错误传播,其原因是算法随修复深度逐渐失去作用;图(d)出现了和(c)中同样的情况;图(e)中树叶纹理部分传播合理,也完成栏杆的直线传播,但是栏杆的衔接性稍差,这也是顺序修复算法的不足之处.图(c)和(e)中其余马路部分都得到很好的修复.本文算法优势得到进一步体现.

4 实验结果及分析

本文介绍了Criminisi算法及其问题,同时提出来新的算法来解决该问题.本方法采用的顺序修复方法避免优先级计算产生的算法作用逐渐减弱的特性,同时保证待匹配块基础匹配区域的完整,待匹配块基础匹配区域为“倒L”形状,该形状的即能配合顺序修复又充分利用填充位置上方和右方的已知信息,使图像修复的正确率得到有效的提升.通过对比两者的实现过程和实验结果可以看出,本文方法在处理图像纹理方面和Criminisi经典算法具有相同的能力,但具有更强的结构传播能力;本文算法依然存在着修复范围小等问题,未来希望针对该问题对本算法进行更深入的研究.

1 Guillemot C,Le Meur O.Image inpainting:Overview and recent advances.IEEE Signal Processing Magazine,2014,31(1):127–144.[doi:10.1109/MSP.2013.2273004]

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

3 Chan TF,Shen JH.Nontexture inpainting by curvaturedriven diffusions.Journal of Visual Communication and Image Representation,2001,12(4):436–449.[doi:10.1006/jvci.2001.0487]

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

5 Chen YJ,Ranftl R,Pock T.A bi-level view of inpaintingbased image compression.Computer Vision Winter Workshop.Czech Republic.2014.

6 Florinabel DJ,Juliet SE,Sadasivam V,et al.Combined frequency and spatial domain-based patch propagation for image completion.Computers &Graphics,2011,35(6):1051–1062.

7 Xu ZB,Sun J.Image inpainting by patch propagation using patch sparsity.IEEE Trans.on Image Processing,2010,19(5):1153–1165.[doi:10.1109/TIP.2010.2042098]

8 Criminisi A,Perez P,Toyama K.Region filling and object removal by exemplar-based image inpainting.IEEE Trans.Image Processing,2004,13(9):1200–1212.[doi:10.1109/TIP.2004.833105]

9 Wang J,Lu K,Pan DR,et al.Robust object removal with an exemplar-based Image Inpainting approach.Neurocomputing,2014,123:150–155.[doi:10.1016/j.neucom.2013.06.022]

10 Ružić T,Pižurica A.Context-aware patch-based image inpainting using Markov random field modeling.IEEE Trans.Image Processing,2015,24(1):444–456.[doi:10.1109/TIP.2014.2372479]

11 李旭峰,王静,刘红敏,等.特征优先块匹配图像修复算法.计算机辅助设计与图形学学报,2016,28(7):1131–1137.

12 任澍,唐向宏,康佳伦.利用纹理和边缘特征的 Criminisi改进算法.中国图象图形学报,2012,17(9):1085–1091.[doi:10.11834/jig.20120906]

13 任澎,唐向宏,康佳伦.纹理和边缘特征相结合的图像修复算法.计算机辅助设计与图形学学报,2013,25(11):1682–1693.

Image Inpainting Algorithm Base on Sequential Repaired Exemplar

LI Xu-Feng1,WANG Jing2,WANG Guo-Dong1,LIU Hong-Min2,WANG Zhi-Heng2

1(College of Electrical Engineering and Automation,Henan Polytechnic University,Jiaozuo 454150,China)2(College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454150,China)

This paper proposes a novel image inpainting algorithm based on exemplar repaired in a sequential manner.This method makes a new experiment on inpainting order of Criminisi classical algorithm.The inpainting order of the classical algorithm is obtained by calculating the priority.But the priority is tending to 0 with the sustained inpainting.As a result,the algorithm will fail and produce error inpainting results.In order to solve this problem,we replace the priority determined order with a sequential manner,which can keep the algorithm working all the time.Moreover,we propose a novel exemplar pattern like an inverted L.The pattern in our method can help to enhance the ability of structure propagation and improve correction rate of patch matching.Experimental results prove that the novel algorithm can achieve better visual effects.

sequential;image inpainting;exemplar;match

李旭峰,王静,王国东,刘红敏,王志衡.采用顺序修复的样本例图像修复算法.计算机系统应用,2017,26(9):219–223.http://www.c-sa.org.cn/1003-3254/5948.html

①基金项后:国家自然科学基金(61401150,61472119,61572173);河南理工大学博士基金(B2013-039);河南理工大学创新型科研团队计划(T2014-3)

2016-12-22;采用时间:2017-01-18