论文部分内容阅读
摘 要： 提出了一种基于Criminisi算法的改进的图像修补算法。引入了图像质量评价标准SSIM定义的结构相似度，结合结构相似度进行图像修补过程中的模板匹配，从而减少了模板匹配时错误匹配的情况，提高了图像修补的质量。仿真结果显示，改进的算法对于图像修补有不错的效果，优于原有的Criminisi修补算法。
关键词： 图像修补； 结构相似度； Criminisi算法； 模板匹配
中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2015）10-07-03
Abstract： A new inpainting algorithm based on the Criminisi algorithm is proposed in this paper. The new algorithm combines with the structural similarity， which comes from image quality evaluation criteria SSIM， to carry out the template matching in the image inpainting process. The algorithm can reduce the probability of error matching and improve the quality of image inpainting. The simulation results show that the improved algorithm has a good effect on the image inpainting， and is superior to the original Criminisi algorithm.
Key words： image inpainting； structural similarity； Criminisi algorithm； template matching
0 引言
图像修补是对图像缺失区域或者被破坏的地方进行修复，在手工修复图像时，容易破坏图像且需要大量的时间[1]。计算机的出现使得数字图像修补技术得到大幅发展。图像修补技术的原理是通过图像中无损的区域来达到修复图像缺损区域的目的。图像修补在很多领域得到应用，比如文物保护[2]、影视特技制作[3]、图像中文本或多余目标物的去除[4]，视频通信中的错误隐匿[5]。由于图像修复在实际中都有着重要的意义，因此受到国内外的广泛关注，现在已成为计算机视觉和图形学研究中的热点之一。
从Bertalmio等[6]首次提出，到目前出现了大量图像修补方法。图像修补技术分为两类。
第一类是基于扩散的修补技术，通过引入偏微分方程来传播局部的结构，使图像的信息从已知区域向缺损区域扩散[6]。在Bertalmio[6]所提算法中通过沿着等照度线的方向来修复图像。Chen[7]提出使用全变差模型（TV）修补破损区域。Zhang[8]使用调和函数改进了全变差模型，提高了图像修补质量。此类方法在修补小区域破损图像时有很好的效果，比如划痕，图像中文字去除等。但对于纹理比较丰富或者大区域破损图像时效果非常差。
另一类方法是基于样本的纹理合成方法，算法的思想是从待修补区域边界上选取一个优先权最高像素点，以该点为中心，选择一个大小合适的纹理块，然后在已知区域内寻找最相近的匹配块来代替纹理块。Criminisi[9]开创性的提出了基于纹理的修补算法。然而在Criminisi算法中，修补过程对结构、噪声等一些因素比较敏感，在计算优先权时会产生错误的判断，并且在寻找匹配块的过程中容易发生错误匹配，影响最终的修补质量。Wu[10]提出通过偏微分方程（PDE）计算优先权。Xu[11]通过结构的稀疏表示来计算优先权。Meur[12]引入结构张量计算优先权。Yin[13]在Criminisi[9]的基础上利用曲率来搜索匹配块。这一类方法对于大尺度破损区域和纹理复杂的图像有良好的修补效果。
本文在Criminisi算法的基础上进行改进，属于第二类算法。在算法中，通过使用颜色信息和结构相似度的结合来提高寻找最佳匹配块的准确程度，改善图像的修补质量。
1 Crimicisi算法
在图1中，假设Φ是已知区域，Ω是待修补区域，那Ω是待修补区域的边界，Ψp是以Ω上一点p点为中心选取的一个模板，称为待修补块，比如选取大小为9*9的方块，Ψq是以q点为中心选取的一个模板，大小与Ψp相同且模板位于已知区域Φ内。Criminisi算法是一种基于样本的图像修补算法，综合结构传输和纹理合成的优点，对于图像修补有较好的效果。Criminisi算法实现过程如下：
⑴ 在图像中选择需要修补的区域Ω，然后确定其边界_Ω；
⑵ 计算边界_Ω上所有的待修补块优先权，选择优先权最大的待修补块修补；
⑶ 在已知区域Φ内搜索一个与待修补区域大小相同的块，称为匹配块；
⑷ 将匹配块对应于待修补块中待修补区域的像素复制到待修补块中；
⑸ 重新确定待修补区域的边界，重复上述修补过程，直到待修补区域修补完成。
算法中有两个关键步骤：优先权的计算和搜索匹配块。对于任一边界点p∈Ω，定义待修补块Ψp的优先权P（p）为
其中C（p）为置信项，D（p）为数据项，|Ψp|代表Ψp的面积，即像素的总数，C（q）=0当q∈Ω，C（q）=1当q∈Φ，是p点的等照度线，np是p点的法向量，是归一化因子，在灰度图像中取255。
2 改进的图像修补算法
2.1 结构信息相似度
在Z.Wang等[14]提出的SSIM中，图像分为3部分：亮度信息、对比度信息，结构信息。 2.2 结构信息相似度
在Criminisi算法中搜索最佳匹配块，是要根据待修补块和匹配块之间的颜色信息的差异大小衡量两个块的相近程度，本算法中在搜索时引入结构相似度，判断两个块间的近似程度，d（Ψp，Φq）变为
算法的图像修补过程如图2所示。
2.3 细节实现
在算法仿真中，不同的处理方式会造成不一样的结果。在改进的算法中，首先根据图像需要确定一个二值图，像素为1的表示待修补区域，像素为0表示已知区域，如图4（c）所示。
确定优先权时，会遇到如图3的情况，白色区域为待修补区域，假设A点的优先权最大，当选取9*9的方块，方块不完全在图像内。此时将方块移动，使得方块位于图像内。
计算两个块的结构相似度，是计算待修补块中已知信息和匹配块中对应于待修补块已知区域的信息的结构相似程度。算法中，将待修补块与对应的二值图像块相乘，使得待修补块位于待修补区域的像素设置为0，将匹配快与待修补块对应的二值图像块相乘，使匹配块中对应于待修补块中待修补区域的像素也设置为0，然后计算处理后的两个块之间的结构相似度。
3 实验结果
通过MATLAB2010a进行算法仿真，实现过程中选取窗口大小为9*9，参数c为0.3。
图4中是对bungee图中目标物的移除，图4（a）为原始图像，图4（b）中绿色的部分为需要移除的区域，图4（c）是一个二值图像，白色部分为原始图像中需要移除目标物的区域。图4（d）为bungee图的修补结果，图4（e）为Criminisi所提算法的仿真，图4（f）为Wu所提算法的仿真，图4（c）是本文改进的算法的仿真结果。由图4可见，在图4（a）和图4（b）中用圆圈画的部分都有很好的修补效果。
图5是对baboon图中的缺失区域进行修补，图5（a）为原始图像，图5（b）中绿色的部分为图像中缺失的部分，图5（c）是一个二值图像，白色部分为原始图像中缺失的区域，图5（d）为Criminisi所提算法的仿真，图5（e）为Wu所提算法的仿真，图5（f）是本文改进的算法的仿真结果。
4 算法优缺点分析
在算法中引进了结构相似度，通过参数的选择，可以对不同图像进行修复。从仿真结果来看，对结构或纹理复杂的破损图像修补效果良好。但参数的选择是由试验得到的，对每幅图像有一定的差别，因此，下一步的工作是对参数进行改进，做到自适应，提高算法的实用性。
参考文献：
[1] 吴亚东，张红英，吴斌.数字图像修复技术[M].科学出版社，2010.
[2] W Huang， S Wang， X Yang and J Jia，Dunhuang murals inpainting based on image decomposition[J]. Journal of Shandong University （Engineering Sci-Ence），2010.40：24-27
[3] K. A. Patwardhan， G. Sapiro， and M. Bertalmio，Video inpainting of occluding and occluded objects[J].in Proc. IEEE Int. Conf，2005.2：69-72
[4] J. F.Wang， H. J. Hsu， and S. C. Liao，A novel framework for objectremoval from digital photogragh[J]. presented at the IEEE Conf. Image Processing，2005.
[5] Yongbing Zhang， Xinguang Xiang， Debin Zhao， Siwe Ma， Wen Gao.Packet Video Error Concealment With Auto Regressive Model[J].Circuits and Systems for Video Technology， IEEE Transactions on，2012.22（1）：12-27
[6] M. Bertalmio， G. Sapiro， C. Ballester， and V. Caselles，Imageinpainting[J]. in Proc. ACM SIGGRAPH，2000.7：417-424
[7] T. F. Chan and J. Shen，Mathematical models for local nontexture inpaintings[J]， SIAM J. Appl. Math，2001.62（3）：1019-1043
[8] H. Y. Zhang， B. Wu， Q. C. Peng， and Y. D.Wu，Digital imageinpainting based on p-harmonic energy minimization[J]. Chin. J. Electron，2007.3：525-530
[9] A. Criminisi， P. Pérez， and K. Toyama，Region filling and objectremoval by exemplar-based inpainting[J]. IEEE Trans. Image Process，2004.13（9）：1200-1212
[10] J. Wu and Q. Ruan，Object removal by cross isophotes exemplarbased image inpainting[J]. Proceeding of International Conference of Pattern Recognition，2006：810-813
[11] Z. Xu and J. Sun，Image inpainting by patch propagation usingpatch sparsity[J]. IEEE Trans. Image Process，2010.19（5）：1153-1165
[12] O. Le Meur， J. Gautier， and C. Guillemot，Examplar-based inpainting based on local geometry[J]. in Proc. IEEE Int. Conf. Image Processing （ICIP），2011.9：3401-3403
[13] Lixin Yin， Chen Chang，An effective exemplar-based image inpainting method[J]. 14th IEEE International Conference on Communication Technology （ICCT）， Chengdu， 2012.11：739-743
[14] Z. Wang， A. C. Bovik， and E. P. Sheikh， H. R. ans Simoncelli，Image quality assessment： From error measurement to structural similarity[J]. IEEE Trans. on Image Processing，2004.13（4）：600-612
关键词： 图像修补； 结构相似度； Criminisi算法； 模板匹配
中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2015）10-07-03
Abstract： A new inpainting algorithm based on the Criminisi algorithm is proposed in this paper. The new algorithm combines with the structural similarity， which comes from image quality evaluation criteria SSIM， to carry out the template matching in the image inpainting process. The algorithm can reduce the probability of error matching and improve the quality of image inpainting. The simulation results show that the improved algorithm has a good effect on the image inpainting， and is superior to the original Criminisi algorithm.
Key words： image inpainting； structural similarity； Criminisi algorithm； template matching
0 引言
图像修补是对图像缺失区域或者被破坏的地方进行修复，在手工修复图像时，容易破坏图像且需要大量的时间[1]。计算机的出现使得数字图像修补技术得到大幅发展。图像修补技术的原理是通过图像中无损的区域来达到修复图像缺损区域的目的。图像修补在很多领域得到应用，比如文物保护[2]、影视特技制作[3]、图像中文本或多余目标物的去除[4]，视频通信中的错误隐匿[5]。由于图像修复在实际中都有着重要的意义，因此受到国内外的广泛关注，现在已成为计算机视觉和图形学研究中的热点之一。
从Bertalmio等[6]首次提出，到目前出现了大量图像修补方法。图像修补技术分为两类。
第一类是基于扩散的修补技术，通过引入偏微分方程来传播局部的结构，使图像的信息从已知区域向缺损区域扩散[6]。在Bertalmio[6]所提算法中通过沿着等照度线的方向来修复图像。Chen[7]提出使用全变差模型（TV）修补破损区域。Zhang[8]使用调和函数改进了全变差模型，提高了图像修补质量。此类方法在修补小区域破损图像时有很好的效果，比如划痕，图像中文字去除等。但对于纹理比较丰富或者大区域破损图像时效果非常差。
另一类方法是基于样本的纹理合成方法，算法的思想是从待修补区域边界上选取一个优先权最高像素点，以该点为中心，选择一个大小合适的纹理块，然后在已知区域内寻找最相近的匹配块来代替纹理块。Criminisi[9]开创性的提出了基于纹理的修补算法。然而在Criminisi算法中，修补过程对结构、噪声等一些因素比较敏感，在计算优先权时会产生错误的判断，并且在寻找匹配块的过程中容易发生错误匹配，影响最终的修补质量。Wu[10]提出通过偏微分方程（PDE）计算优先权。Xu[11]通过结构的稀疏表示来计算优先权。Meur[12]引入结构张量计算优先权。Yin[13]在Criminisi[9]的基础上利用曲率来搜索匹配块。这一类方法对于大尺度破损区域和纹理复杂的图像有良好的修补效果。
本文在Criminisi算法的基础上进行改进，属于第二类算法。在算法中，通过使用颜色信息和结构相似度的结合来提高寻找最佳匹配块的准确程度，改善图像的修补质量。
1 Crimicisi算法
在图1中，假设Φ是已知区域，Ω是待修补区域，那Ω是待修补区域的边界，Ψp是以Ω上一点p点为中心选取的一个模板，称为待修补块，比如选取大小为9*9的方块，Ψq是以q点为中心选取的一个模板，大小与Ψp相同且模板位于已知区域Φ内。Criminisi算法是一种基于样本的图像修补算法，综合结构传输和纹理合成的优点，对于图像修补有较好的效果。Criminisi算法实现过程如下：
⑴ 在图像中选择需要修补的区域Ω，然后确定其边界_Ω；
⑵ 计算边界_Ω上所有的待修补块优先权，选择优先权最大的待修补块修补；
⑶ 在已知区域Φ内搜索一个与待修补区域大小相同的块，称为匹配块；
⑷ 将匹配块对应于待修补块中待修补区域的像素复制到待修补块中；
⑸ 重新确定待修补区域的边界，重复上述修补过程，直到待修补区域修补完成。
算法中有两个关键步骤：优先权的计算和搜索匹配块。对于任一边界点p∈Ω，定义待修补块Ψp的优先权P（p）为
其中C（p）为置信项，D（p）为数据项，|Ψp|代表Ψp的面积，即像素的总数，C（q）=0当q∈Ω，C（q）=1当q∈Φ，是p点的等照度线，np是p点的法向量，是归一化因子，在灰度图像中取255。
2 改进的图像修补算法
2.1 结构信息相似度
在Z.Wang等[14]提出的SSIM中，图像分为3部分：亮度信息、对比度信息，结构信息。 2.2 结构信息相似度
在Criminisi算法中搜索最佳匹配块，是要根据待修补块和匹配块之间的颜色信息的差异大小衡量两个块的相近程度，本算法中在搜索时引入结构相似度，判断两个块间的近似程度，d（Ψp，Φq）变为
算法的图像修补过程如图2所示。
2.3 细节实现
在算法仿真中，不同的处理方式会造成不一样的结果。在改进的算法中，首先根据图像需要确定一个二值图，像素为1的表示待修补区域，像素为0表示已知区域，如图4（c）所示。
确定优先权时，会遇到如图3的情况，白色区域为待修补区域，假设A点的优先权最大，当选取9*9的方块，方块不完全在图像内。此时将方块移动，使得方块位于图像内。
计算两个块的结构相似度，是计算待修补块中已知信息和匹配块中对应于待修补块已知区域的信息的结构相似程度。算法中，将待修补块与对应的二值图像块相乘，使得待修补块位于待修补区域的像素设置为0，将匹配快与待修补块对应的二值图像块相乘，使匹配块中对应于待修补块中待修补区域的像素也设置为0，然后计算处理后的两个块之间的结构相似度。
3 实验结果
通过MATLAB2010a进行算法仿真，实现过程中选取窗口大小为9*9，参数c为0.3。
图4中是对bungee图中目标物的移除，图4（a）为原始图像，图4（b）中绿色的部分为需要移除的区域，图4（c）是一个二值图像，白色部分为原始图像中需要移除目标物的区域。图4（d）为bungee图的修补结果，图4（e）为Criminisi所提算法的仿真，图4（f）为Wu所提算法的仿真，图4（c）是本文改进的算法的仿真结果。由图4可见，在图4（a）和图4（b）中用圆圈画的部分都有很好的修补效果。
图5是对baboon图中的缺失区域进行修补，图5（a）为原始图像，图5（b）中绿色的部分为图像中缺失的部分，图5（c）是一个二值图像，白色部分为原始图像中缺失的区域，图5（d）为Criminisi所提算法的仿真，图5（e）为Wu所提算法的仿真，图5（f）是本文改进的算法的仿真结果。
4 算法优缺点分析
在算法中引进了结构相似度，通过参数的选择，可以对不同图像进行修复。从仿真结果来看，对结构或纹理复杂的破损图像修补效果良好。但参数的选择是由试验得到的，对每幅图像有一定的差别，因此，下一步的工作是对参数进行改进，做到自适应，提高算法的实用性。
参考文献：
[1] 吴亚东，张红英，吴斌.数字图像修复技术[M].科学出版社，2010.
[2] W Huang， S Wang， X Yang and J Jia，Dunhuang murals inpainting based on image decomposition[J]. Journal of Shandong University （Engineering Sci-Ence），2010.40：24-27
[3] K. A. Patwardhan， G. Sapiro， and M. Bertalmio，Video inpainting of occluding and occluded objects[J].in Proc. IEEE Int. Conf，2005.2：69-72
[4] J. F.Wang， H. J. Hsu， and S. C. Liao，A novel framework for objectremoval from digital photogragh[J]. presented at the IEEE Conf. Image Processing，2005.
[5] Yongbing Zhang， Xinguang Xiang， Debin Zhao， Siwe Ma， Wen Gao.Packet Video Error Concealment With Auto Regressive Model[J].Circuits and Systems for Video Technology， IEEE Transactions on，2012.22（1）：12-27
[6] M. Bertalmio， G. Sapiro， C. Ballester， and V. Caselles，Imageinpainting[J]. in Proc. ACM SIGGRAPH，2000.7：417-424
[7] T. F. Chan and J. Shen，Mathematical models for local nontexture inpaintings[J]， SIAM J. Appl. Math，2001.62（3）：1019-1043
[8] H. Y. Zhang， B. Wu， Q. C. Peng， and Y. D.Wu，Digital imageinpainting based on p-harmonic energy minimization[J]. Chin. J. Electron，2007.3：525-530
[9] A. Criminisi， P. Pérez， and K. Toyama，Region filling and objectremoval by exemplar-based inpainting[J]. IEEE Trans. Image Process，2004.13（9）：1200-1212
[10] J. Wu and Q. Ruan，Object removal by cross isophotes exemplarbased image inpainting[J]. Proceeding of International Conference of Pattern Recognition，2006：810-813
[11] Z. Xu and J. Sun，Image inpainting by patch propagation usingpatch sparsity[J]. IEEE Trans. Image Process，2010.19（5）：1153-1165
[12] O. Le Meur， J. Gautier， and C. Guillemot，Examplar-based inpainting based on local geometry[J]. in Proc. IEEE Int. Conf. Image Processing （ICIP），2011.9：3401-3403
[13] Lixin Yin， Chen Chang，An effective exemplar-based image inpainting method[J]. 14th IEEE International Conference on Communication Technology （ICCT）， Chengdu， 2012.11：739-743
[14] Z. Wang， A. C. Bovik， and E. P. Sheikh， H. R. ans Simoncelli，Image quality assessment： From error measurement to structural similarity[J]. IEEE Trans. on Image Processing，2004.13（4）：600-612