基于马尔科夫随机场匹配准则的Crim inisi修复算法*

赵 娜，王慧琴，吴 萌

西安建筑科技大学 信息与控制工程学院，西安 710055

基于马尔科夫随机场匹配准则的Crim inisi修复算法*

赵 娜，王慧琴+，吴 萌

西安建筑科技大学 信息与控制工程学院，西安 710055

+Corresponding author:E-mail:hqwang@xauat.edu.cn

ZHAO Na,WANG Huiqin,WU M eng.Crim inisidigital inpainting algorithm based on M arkov random field matching criterion.Journalof Frontiersof Com puter Science and Technology,2017,11(7)：1150-1158.

传统的基于样本的修复算法在修复数字图像时精度较低，提出了一种基于马尔科夫随机场（Markov random field，MRF）匹配准则的Crim inisi数字图像修复算法。该算法以马尔科夫随机场替代欧氏距离匹配准则，在寻找最佳匹配块前首先通过马尔科夫随机场对图像纹理建模，然后计算图像全局能量对待修复像素块进行估值，最后寻找最佳匹配块以达到全局最优。实验结果表明，该算法对数字图像的修复有了很大改善，纹理误匹配率下降，修复精度得到明显提高。

Criminisi；马尔科夫随机场（MRF）；匹配准则；图像修复

1 引言

数字图像修复是指对局部区域内丢失的数据按照特定规则进行修补，以恢复其完整性，使人眼无法观察到图像曾经缺损或已被修复，在视觉上认为修复后的这幅图像是合理而完整的。目前该技术主要应用于文物字画的保护、破损图像的修补、影视特技制作以及目标物的移除等领域。图像修复从其问题本身来讲是一个数学上的病态问题，它具有不稳定且不唯一的解，也就是说人们仅通过已知信息无法使图像恢复原状。

Criminisi等人[1]提出了一种基于样本的图像修复算法，它利用了基于结构的修复方法中的扩散方式来定义修复块的优先级，可同时兼顾图像纹理信息和结构信息，并通过全图搜索设定匹配准则以寻找最佳匹配块。在实际应用中，发现待修复像素块与最佳匹配块之间匹配准则的设定对修复结果影响较大。传统的Crim inisi算法采用基于欧氏距离的匹配准则，该准则在匹配过程中仅以二者之间的空间距离作为衡量标准，并没有考虑图像的颜色分布、纹理变化等信息。Komodakis等人[2]提出运用置信传播算法解决图像修复的全局最优化问题，该方法对结构修复效果较差。Pritch等人[3]根据图像已知信息的变化规律对图像破损区域进行修复。Xue等人[4]利用图像的颜色梯度值构造新的匹配准则，从而提高了图像块的匹配度，但时间复杂度高。雷鸣等人[5]根据颜色比率梯度搜索最佳匹配块，以减少误匹配，但该算法时间复杂度较高。Wang等人[6]将匹配准则与偏微分方程结合，并考虑图像块的相似性约束对修复造成的影响。彭坤杨等人[7]利用平均灰度值的思路，减少修复时间，但修复效果并不是很理想。Bugeau等人[8]提出以Bhattacharya距离约束欧氏距离，用两种距离同时进行匹配块相似度衡量，在匹配准则改进方面取得了一定进展。Zhou等人[9]将待修复块与选取的多个匹配块转化为非负矩阵，利用非负矩阵因子化解求得填充信息。刘纯[10]将目标块及匹配块的纹理特征相似性引入匹配过程中，取得了较好的成果。张晴等人[11]提出以欧式距离为主，巴氏距离为辅的相似性度量方法，对图像平滑纹理部分的修复效果较为明显。马爽等人[12]提出利用图像块关联匹配修复算法实现对降采样受损图像的粗修复，该方法对包含渐变特征的自然图像修复具有很好的视觉效果。王新年等人[13]结合几何距离关系，采用多块同时修复的策略，引入几何距离修正因子确定各块的最佳匹配块，该方法提高了修复效率。Liang等人[14]使用中心像素映射的方法标记最大连通成分并进行片段检测，以此来加快搜索匹配块，实验结果表明该方法可节省90%的时间。李尊等人[15]提出基于蝙蝠算法的Crim inisi图像修复算法，采用蝙蝠算法进行最佳匹配块的搜索，蝙蝠算法能将全局搜索和局部搜索高效地融合，且具有很好的适应性和鲁棒性，能够降低错误信息的累积。但是上述文献都没有很好地解决复杂纹理修复时的误匹配、误差累计等问题。

本文针对复杂纹理的修复提出了基于马尔科夫随机场（Markov random field，MRF）的匹配块选取准则。马尔科夫随机场认为待修复像素块的信息只与其邻域像素块有关，不仅涵盖了欧氏距离最小的传统匹配准则，而且考虑到了匹配块的灰度统计特征，以条件概率描述图像数据分布并用于修复，具有更高的准确性，修复效果更佳。

2 Crim inisi算法及修复效果分析

2.1 Criminisi算法原理

Crim inisi算法是基于样本的修复算法，可同时兼顾图像纹理信息和结构信息，并通过全图搜索设定匹配准则以寻找最佳匹配块。Crim inisi算法修复过程主要由计算优先权，搜索最佳匹配块，复制更新3步组成。

步骤1计算待修复区域边界上像素点的优先权，由待修复像素块的置信度及数据项得到。

优先权：

置信度：

式（2）中，待修复区域边界上像素点 p的置信度C(p)为待修复块中已知像素之和与待修复块所含像素总数的比值；Size(Ψp)是待修复块所含像素总数。数据项：

式（3）中，衡量像素点 p处边缘强度的数据项D(p)是待修复区域边界上点p处的单位法向量np与等照度线向量的乘积；α是归一化参数（一般对于灰度图像α=255）；ε为一个极小的常数，避免D(p)为0。

选择优先权最高的像素块作为待修复块首先进行修复。

步骤2根据待修复块的已知信息在图像已知区域内按一定的匹配准则寻找最佳匹配块，经典Crim inisi算法采用了基于欧氏距离的匹配准则，即在已知区域中进行遍历搜索，计算灰度距离，与待修复块欧氏距离最小的块视为与其最匹配的块，其中欧氏距离d(Ψp,Ψq)定义为待修复块Ψp与匹配块Ψq对应像素点的灰度值平方和。

匹配准则：

步骤3将最佳匹配块复制到待修复块对应的位置上，更新待修复边缘置信度与数据项。

复制更新：

以上3步不停地循环，直到图像中所有的受损区域全部被修复为止。每次循环前都要重新计算新的边界上各点的优先权以确定下一个最先需要修复的目标块。

2.2 Criminisi算法修复效果分析

Crim inisi算法是基于样本的修复算法，它最大的优点就是能够修复大范围受损的图像，这是通过将像素块不断地复制到待修复区域实现的。Criminisi算法中对修复结果产生较大影响的是搜索最佳匹配块这一步骤，修复时匹配块的大小以及匹配准则的选取都会对修复结果产生质的影响。

修复时，修复块尺寸越小，修复的连续性就越好，边缘特征保持越好，人眼对于边界的不连续性就越不敏感；修复块尺寸越大，块与块的误差就越大，边界越不连续，结构信息缺损越严重，人眼就越容易识别。但是当匹配块选取过小，如选取2×2大小的匹配块时，其修复时间明显增长，修复效率大大下降。为同时兼顾修复精度与修复时间，本文选取3×3的匹配块进行修复。

修复时采用的匹配准则不同，结果也大不相同。经典Crim inisi算法采用基于欧氏距离的匹配准则，其计算两个图像块的空间距离，欧式距离值越小，图像块越相似。因为基于欧氏距离的匹配准则只考虑待修复块与匹配块之间对应像素值的相似性,并没有从整体上考虑待修复块与周围已知信息的一致性，所以该准则易从平坦区域复制像素，在衡量位于平滑区域的图像块时具有优势，而在衡量位于纹理或含有结构的图像块时存在不足[16]。若在图像已知区域搜索到错误的匹配块而造成修复错误时，此错误会在后续的修复过程中进一步扩散，从而造成大面积的修复错误。

如图1所示，（a）～（f）均是从原图中截取的图像块。从人类视觉感知的主观角度评价，与图（a）P0相似度最高的是图（f）P5；采用客观量化评价欧式距离方法衡量图像块（b）～（f）与图像块（a）之间的相似度可知，与图1（a）P0最相似也即欧式距离最小的图像块却是图1（c）P2。因此，若在算法中仅采用欧式距离作为相似性评价指标，必然引起匹配错误。

Fig.1 Sim ilarity comparison of image blocks图1 图像块的相似性比较

3 基于马尔科夫随机场的匹配块选取准则

马尔科夫随机场是一组关于马尔科夫性质随机变量的全概率分布模型。20世纪70年代，MRF被用于图像处理领域描述图像本身所特有的空间相关性，并在图像纹理分析、图像边缘检测、图像分割以及图像恢复与重建等方面发挥了优越性。本文利用MRF在图像纹理方面的特性，将其作为Crim inisi算法的新匹配准则，修复结果有了较大提高。

3.1 马尔科夫随机场原理

马尔科夫性指当一个随机过程在给定现在以及过去所有状态的情况下，其未来状态的条件概率分布仅依赖于当前状态的值，与过去所有状态无关[17]。

对于图像中一个特定的点，该点的取值只依赖于该点邻域像素点的取值，而与其他位置的像素情况无关。

如图2所示，分别为像素X的一阶邻域系统、二阶邻域系统和高阶邻域系统。

Fig.2 Neighborhood system of pixelX图2 像素X的邻域系统

一幅图像由一些区域组成，每一个区域都满足马尔科夫随机场对“平稳的自回归过程”的描述。“平稳的自回归过程”即统计特性不随时间的推移而改变，在图像中指对于小区域图像如3×3或5×5的像素块来说，每一块的灰度值是均匀的。则利用待修复像素块的一阶邻域、二阶邻域或高阶邻域信息即可估计待修复像素块的近似值[18]。由于MRF对于高阶邻域的计算复杂度高，本文选取其一阶邻域对待修复像素块进行估值。

3.2 MRF数学模型建立及求解

对待修复像素块进行估值，即是对其邻域的最大后验概率进行估计，待修复块与其邻域系统满足Bayes条件概率：

式（7）中，X为待修复像素块；Y为已知的图像及X的邻域系统；P(X=x|Y=y)为已知Y时关于X的后验概率；P(X=x)为先验概率。通过适当地选择Y使P(X=x|Y=y)达到最大，此时对应的X即为缺损部分的最佳估计值xˆ：

利用马尔科夫随机场模型对整幅数字图像进行数学建模，即：

式（9）中，δ2为图像灰度方差；M表示图像由M个区域组成；qm为每个区域的灰度均值；N1、N2表示图像的长宽值。

计算图像先验概率：

式（10）中，T是一个温度常数，最初用于模拟退火算法中，算法开始赋予T一个较大的值，随着算法迭代次数的增加T逐渐减小，在MRF随机场模型中一般取值为1；是一个归一化常数；U(X)称为Gibbs能量函数，图像的全局能量函数为：

式（11）中，Vp(xp)表示给一个像素分配一个标号的似然能量；Vpq(xp,xq)表示两个相邻像素分配两个标号的先验模型能量；(p,q)表示邻域像素对；ε表示系统中的4邻域像素对集合。

基于MRF的邻域最大后验概率估计实际上相应于最小化全局能量U(X)：

3.3 估计值与匹配块相似性度量

因MRF估值得出的3×3像素块的9个像素灰度值是相同的，若直接填充会产生严重的块效应现象，所以在估值完成后，在全局搜索3×3最佳匹配块。搜索时以平均灰度值作为衡量标准，计算匹配块的平均灰度值，若其值与估值差异越小，则表示它们越匹配，取差异值最小的匹配块作为最佳匹配块，并将最佳匹配块复制到待修复块对应的位置上。

4 算法步骤及实验结果分析

4.1 本文算法步骤

（1）读入待修复图像，二值化图像以寻找待填充边缘；

（2）初始化置信度与数据项值，计算优先权，选择优先权最高的像素块为待修复块；

（3）利用MRF图像模型对待修复块估值xˆ；

（4）全局搜索平均灰度值xˉ与估值xˆ差异最小的匹配块；

（5）将最佳匹配块复制到待修复像素块，更新填充边缘置信度与数据项；

（6）不断循环以上步骤，直至待修复像素块全部收敛修复。

4.2 实验结果

本实验在Windows平台下利用M icrosoft Visual C++6.0中的开源计算机视觉库（open source computer vision library，OpenCV 1.0）进行仿真实验。

本文设计简单纹理与复杂纹理共4组实验验证算法性能，采用峰值信噪比（peak signal to noise ratio，PSNR）、均方误差（mean squared error，MSE）、结构相似性（structural sim ilarity，SSIM）作为修复结果客观评价指标。PSNR值越大表示图像质量越好，MSE值越小表示修复图像与参考图像越相似，SSIM值越大表示修复图像质量越高。

对于简单纹理，选取Golf图像进行对比实验，复杂纹理则选取Bungee、Farmer、People等图像进行对比实验，结果如图3～图6和表1～表4所示。

Table1 Objectiveevaluation ofGolf inpainting image表1 Golf图像修复结果客观评价

Table2 Objectiveevaluation of Bungee inpainting image表2 Bungee图像修复结果客观评价

图3中，（a）与（b）分别为Golf原图与待修复图像；（c）与（d）分别是经典Crim inisi修复结果与其局部放大图；（e）与（f）分别是文献[2]修复结果与其局部放大图；（g）与（h）分别是文献[8]修复结果与其局部放大图；（i）与（j）分别为本文算法修复结果与其局部放大图。就人眼直接观察发现，Crim inisi和文献[2]修复结果均存在着不同程度的错误纹理堆积，误匹配率较高。虽然通过对算法的改进，文献[8]与本文修复结果在人眼看来纹理均比较自然，但通过客观评价发现，本文修复结果较文献[8]修复结果MSE降低，PSNR略微提高。

Fig.3 Inpainting resultsofGolf image图3 Golf图像修复结果

Fig.4 Inpainting resultsof Bungee image图4 Bungee图像修复结果

Fig.5 Inpainting resultsof Farmer image图5 Farmer图像修复结果

Table3 Objectiveevaluation of Farmer inpainting image表3 Farm er图像修复结果客观评价

Table4 Objectiveevaluation of People inpainting image表4 Peop le图像修复结果客观评价

Fig.6 Inpainting resultsof People image图6 Peop le图像修复结果

图4中，（a）与（b）分别为Bungee原图与标记后的待修复图像；（c）是经典Crim inisi修复结果，结构断裂，误匹配严重；（d）为文献[2]修复结果，较经典Criminisi有了较大改善；（e）为文献[13]修复结果，结果断裂，存在误匹配；（f）为文献[8]修复结果，结构基本修复，但仍然产生了匹配错误；（g）为本文算法修复结果，在纹理匹配方面较之前算法有了明显改善，但结构线存在部分错位现象。

图5与图6分别是对Farmer图和People图的修复。从几组对比实验可知，本文算法较经典Crim inisi修复算法在修复结果上有了很大的改善，较文献[2]与[13]改进算法，本文修复结果精度更好，PSNR与SSIM值也明显提高。对于文献[8]，其引入Bhattacharya距离与原始SSD相乘，因为Bhattacharya距离可以衡量离散概率分布的相似性，它可以较好地将位于平滑区域的图像块和位于纹理区域的图像块分开，所以对于简单纹理，本文算法与其修复结果较为相像。对于复杂纹理，由于MRF利用了图像的先验知识，修复结果更符合图像的整体分布，且不论从主观上看还是用PSNR、MSE等客观分析，本文所采用的MRF匹配准则以场论来描述纹理分布都优于Bhattacharya距离。

由SSIM值发现本文算法修复结果在结构相似性分析上较文献[8]略低，由图可知，当图像中结构信息较为复杂时，其修复出现轻微错位与模糊现象。在图像修复中，图像结构边缘应优先得到修复，但本文算法是对匹配准则的进一步改进，并没有对修复顺序进行约束，且MRF自身对纹理相关性更为敏感，对结构信息复杂区域易出现误匹配，故本文算法无法自动识别和确定多个边缘的修复顺序，结构相似性略低于文献[8]。

分析图7中数据可知，尽管本文算法与文献[8]算法修复耗时相比平均增加了45.82%，但与经典Criminisi对比仍减少了8.96%。综合而言，虽然基于MRF匹配准则的修复算法修复耗时有所增加，但其对复杂纹理提高了修复精度，获得了更好的视觉效果。

Fig.7 Running time comparison图7 修复耗时对比结果

5 总结

本文提出了一种基于MRF匹配准则的Crim inisi数字图像修复算法。本文算法以马尔科夫随机场替代欧氏距离匹配准则，实验证明了这种方法与经典Crim inisi算法的修复精度相比有很大提高，基本解决了图像误匹配现象。但该算法还存在着一些不足，如在提高修复精度的同时是以牺牲一定的速度为代价；且由于马尔科夫随机场本身只对纹理内部信息较为敏感，本文算法仅对数字图像纹理部分修复效果较好，对于较为复杂的图像结构线仍存在断裂与错位问题。这些不足将是今后研究的重点。

[1]CriminisiA,Perez P,Toyama K.Region filling and object removal by exemplar-based image inpainting[J].IEEE Transaction on Image Processing,2004,13(9):1200-1212.

[2]Komodakis N,Tziritas G.Image completion using efficient belief propagation via priority scheduling and dynam ic pruning[J].IEEE Transactions on Image Processing,2007,16(11):2649-2661.

[3]Pritch Y,Kav-Venaki E,Peleg S.Shift-map image editing[C]//Proceedings of the 12th IEEE International Conference on Computer Vision,Kyoto,Japan,Sep 29-Oct4,2009.Piscataway,USA:IEEE,2009:151-158.

[4]Xue Yanbing,Zhang Hua,Wang Fayu,etal.Exemplar-based image completion using color ratio gradient[C]//Proceedings of the 1st Congress on Image and Signal Processing,Sanya,China,May 27-30,2008.Piscataway,USA:IEEE,2008:569-572.

[5]Lei M ing,Wang Chundong,Xue Yanbing.A new exemplar based image completing method[J].Journal of Optoelectronics·Laser,2009,20(5):677-680.

[6]Wang Yuxiong,Zhang Yujin.Image inpainting viaweighted sparse non-negativematrix factorization[C]//Proceedings of the 18th International Conference on Image Processing,Brussels,Belgium,Sep 11-14,2011.Piscataway,USA:IEEE,2011:3409-3412.

[7]Peng Kunyang,Dong Lanfang.A fast image inpainting algorithm based on average gray value[J].Journal of Image and Graphics,2010,15(1):50-55.

[8]Bugeau A,Bertalmío M,Caselles V,etal.A comprehensive framework for image inpainting[J].IEEE Transactions on Image Processing,2010,19(10):2634-2645.

[9]Zhou Yatong,Li Lin,Xia Kewen.Research onweighted priority of exemplar-based image inpainting[J].Journalof Electronics,2012,29(1):166-170.

[10]Liu Chun.The research on fast image inpainting algorithms[D].Changsha:Hunan University,2012.

[11]Zhang Qing,Lin Jiajun,Liu Yunxiang.Image inpainting algorithm using improved similaritymetrics[J].Journalof Shanghai Instituteof Technology:NaturalScience,2014,14(3):228-232.

[12]Ma Shuang,Tan Yuanpeng,Xu Gang.Image completion based on fusion of patch associatedmatching and low-rank matrix super resolution[J].Journal of Computer-Aided Design&ComputerGraphics,2015,27(2):271-278.

[13]Wang Xinnian,Wang Zhe,Wang Yan.Improved Criminisi algorithm based on geometry distance[J].Computer Engineering and Design,2015,36(7):1835-1839.

[14]Liang Zaoshan,Yang Gaobo,Ding Xiangling,etal.An efficient forgery detection algorithm for object removal by exemplar-based image inpainting[J].Journalof VisualCommunication&Image Representation,2015,30(C):75-85.

[15]Li Zun,Wu Jin,Liu Jin.Crim inisi image restoration algorithm for object removal[J].Infrared Technology,2016,38(1):28-32.

[16]Shen Jianbing，Jin Xiaogang，Zhou Chuan.Gradient based image completion by solving the Poisson equation[J].Computersand Graphics,2007,31(1):119-156.

[17]RužićT,Pižurica A,PhilipsW.Markov random field based image inpainting w ith context-aware label selection[C]//Proceedings of the 19th International Conference on Image Processing,Lake Buena Vista,USA,Sep 30-Oct 3,2012.Piscataway,USA:IEEE,2012:1733-1736.

[18]Yang Xiaoping,Wang Shuwen.Dunhuangmural inpainting based on Markov random field sampling[J].Journal of ComputerApplications,2010,30(7):1835-1837.

附中文参考文献：

[5]雷鸣,王春东,薛彦兵.一种新的样本块图像修补方法[J].光电子·激光,2009,20(5):677-680.

[7]彭坤杨,董兰芳.一种基于图像平均灰度值的快速图像修复算法[J].中国图象图形学报,2010,15(1):50-55.

[10]刘纯.快速图像修复算法研究[D].长沙:湖南大学,2012.

[11]张晴,林家骏,刘云翔.改进相似性度量准则的图像修复算法[J].上海应用技术学院学报:自然科学版,2014,14(3):228-232.

[12]马爽,谈元鹏,许刚.块关联匹配与低秩矩阵超分辨融合的图像修复[J].计算机辅助设计与图形学学报,2015,27(2):271-278.

[13]王新年,王哲,王演.基于几何距离的Crim inisi图像修复算法[J].计算机工程与设计,2015,36(7):1835-1839.

[15]李尊,吴谨,刘劲.目标移除的Criminisi图像修复算法[J].红外技术,2016,38(1):28-32.

[18]杨筱平,王书文.基于马尔可夫采样的敦煌壁画修复[J].计算机应用,2010,30(7):1835-1837.

ZHAO Nawas born in 1992.She is an M.S.candidate at School of Information and Control Engineering,Xi'an University of Architecture and Technology.Her research interests include digital image inpainting and digital image processing,etc.

赵娜（1992—），女，陕西延安人，西安建筑科技大学信息与控制工程学院硕士研究生，主要研究领域为数字图像修复，数字图像处理等。

王慧琴（1970—），女，山西长治人，2002年于西安交通大学获得博士学位，现为西安建筑科技大学教授、博士生导师，CCF会员，主要研究领域为数字图像处理，多媒体通信，数字建筑，信息安全等。

WU Mengwas born in 1979.She is a lecturer at School of Information and Control Engineering,Xi'an University of Architecture and Technology.Her research interests include digital image processing andmanagement information systems,etc.

吴萌（1979—），女，陕西韩城人，西安建筑科技大学信息与控制工程学院讲师，主要研究领域为数字图像处理，管理信息系统等。

Crim inisi Digital Inpainting Algorithm Based on M arkov Random Field M atching Criterion*

ZHAO Na,WANG Huiqin+,WUMeng
Schoolof Information and Control Engineering,Xi'an University of Architecture and Technology,Xi'an 710055,China

The accuracy of traditional image exemplar-inpainting algorithm is lower.This paper proposesa new Crim inisi digital inpainting algorithm based on Markov random field(MRF)matching criterion.The MRF becomes new matching criterion instead of Euclidean distance.Before searching the bestmatching patch,the image texture model based on MRF is built.Then the global energy of the image is calculated to estimate the value of inpainting patch.Finally,the bestmatching patch is searched in order to achieve the globaloptimum.The experimental results show that the proposed algorithm achieves impressive inpainted results,the texture errormatching rate is decreased,and the inpainting accuracy is improved.

Crim inisi;Markov random field(MRF);matching criterion;image inpainting

in was born in 1970.She

the Ph.D.degree in engineering from Xi'an Jiaotong University in 2002.Now she is a professor and Ph.D.supervisor at Xi'an University of Architecture and Technology,and the member of CCF.Her research interests include digital image processing,multimedia communication,digitalarchitectureand information safety,etc.

A

：TN911.73

*The Scientific Research Foundation for the Returned Overseas Chinese Scholars,State Education M inistry of China under Grant No.K05055(教育部留学回国人员科研启动基金);the Natural Science Basic Research Plan of Shaanxi Province under Grant No.2016JM 6079(陕西省自然科学基础研究计划项目);the Science and Technology Projectof Beilin District in 2016 under Grant No.GX1605(2016年碑林区科技计划项目).

Received 2016-04,Accepted 2016-09.

CNKI网络优先出版:2016-09-08,http://www.cnki.net/kcms/detail/11.5602.TP.20160908.1045.006.htm l