一种结合CDD模型和Criminisi算法的图像修复算法

江 平， 张 锦

(合肥工业大学数学学院，安徽 合肥 230009)

一种结合CDD模型和Criminisi算法的图像修复算法

江 平， 张 锦

(合肥工业大学数学学院，安徽 合肥 230009)

针对既含有大块缺失信息又含有划痕的图像，结合CDD模型和Criminisi算法的优点，提出一种新的修复算法。算法先采用可以强化细节的自适应直方图均衡化操作来扩大图像的动态范围，后利用形态学算子分离出待修复图像中的划痕区域与大块区域,接着用CDD模型对划痕进行修复，再用改进优先级的 Criminisi算法进行后续修复，最后把修复后的图像对应于缺失区域的像素填补到待修复图像的区域中。实验结果表明，改进后的算法克服了现有算法可能存在的偏差延续问题，使图像修复的结果更加符合人们的视觉效果。

CDD模型；Criminisi算法；图像修复；自适应直方图均衡化；形态学算子

图像修复技术是近年来计算机图形学和计算机视觉中的一个倍受关注的研究热点，所谓图像修复[1]是指针对图像中遗失或缺损的部分，利用未丢失或未破损的图像信息，按一定的方法自动填补的过程，其目的是使观察者无法察觉到图像曾经缺损或已被修复。图像修复技术在文物的保护、多余物的剔除、影视特技的制作、图像压缩等方面得到广泛的应用。

2000年，Bertalmio等[2]首先提出了一个基于三阶偏微分的 BSCB修复模型，他开创了基于偏微分方程修复的先河，其基本思想是利用待修复区域的边缘信息，将待修复区域边界的外部信息沿轮廓扩散到中间待修补区域的像素上；2002年，Chan和Shen[3]在全变分(total variation, TV)去噪模型[4]的启发下提出了基于 TV模型的图像修复方法，同时说明了TV模型不满足人类视觉中的“连续性”准则的缺点，进一步提出了曲率驱动扩散(curvature driven diffusion, CDD)[5]修复模型，让图像中不自然的大曲率迅速扩散，能以较低的计算复杂度实现有效的修复。此类修复方法对于小面积的图像缺失(例如划痕)有显著的效果，但对破损区域较大的图像修复效果不太理想。

基于样本块纹理合成方法能够较好地处理大范围缺失图像，其中较为经典的修复算法是Criminisi等[6]提出的Criminisi算法：将待修补区域分块修复，按照优先级公式计算出修补顺序，在图片中寻找与待修复区域块最相近的块将其填补；此后，文献[7]中描述了该算法，并通过更多的实例说明该算法的有效性。尽管如此，Criminisi算法在处理图像时，对较强的结构信息持续优先处理很容易造成偏差延续，导致修复效果不理想。文献[8]提出了改进优先级的方法解决偏差问题，取得了一定的成效，具有较好的视觉效果。

目前的图像修复算法主要都是针对大块信息缺失(文献[8-11])或小区域破损(文献[12-14])的图像，但是对既含有划痕又含有大块缺失信息的图像却很少涉及，如果分别用CDD算法和Criminisi算法修复此类图像时，都会产生一些不好的视觉效果：CDD算法修复大块区域会产生模糊现象，并且会有一些修复不到的孤立点；Criminisi算法修复会优先处理划痕，再修复大块区域时会产生错误信息的累积。本文分析了这些算法，找到造成修复效果不佳的原因，在此基础上，提出一种将强化细节的自适应直方图均衡化、CDD模型、改进的Criminisi算法及形态学滤波结合起来的修复方法。

1 CDD模型描述

CDD模型是建立在TV模型的基础上，而TV模型[3]是在约束条件下求泛函极值的问题：

如图1所示，这里Ω为待修复区域，Φ为待修复区域周围完好相邻的区域，I=Φ∪Ω为整幅图像，u为原始图像，0u为破损图像，▽表示梯度，λ表示Lagrange乘子。

图1 图像受损区域及其邻域

根据变分原理，可求得与之对应的Euler-Lagrange方程为：

其中：

为解决 TV模型中的不连续问题，Chan和Shen[5]在TV模型的基础上提出CDD模型，即将TV模型的扩散系数修改为此处，g的定义为：

由于这种选择可以在大曲率处扩散变强，小曲率处扩散逐渐消失，因此，CDD修复模型为：

2 Criminisi算法描述

Criminisi等[6]提出的基于样本纹理合成的图像修补方法可以概括为以下3个步骤。

2.1 计算待修补块的优先权

图2中，I表示整幅图像，Ω表示待修复区域，∂Ω代表其轮廓，Φ表示已知区域，且有 IΦ= −Ω。

图2 Criminisi算法示意图

对于以∂Ω上的点p为中心的目标块pΨ，定义其优先权为：

上式中，

其中 C(p)称为置信度项，规定优先填充那些含有较多已知像素部分的模块，是Ψp的面积，一般C(p)的初始化取值为：

D(p)为数据项，它反映边缘前沿的等照度强度，具有较强结构特征的部分优先修复。 ▽Ip⊥表示p点的等照度线的方向和强度，np表示待修补区域轮廓的单位外法线方向，α为归一化因子，这里取255。

本文采用的 Criminisi算法为改进优先权的Criminisi算法[8]，取优先权为：

这里 C(p)， D(p)满足式(5)，设{Ωi}(0 ≤i≤ N)是每执行一次修复之后新的待修复序列，则令：

2.2 搜索最佳匹配块

在∂Ω上找到 ()Pp值最大的目标块ˆpΨ后，然后在已知区域内搜索此目标块的最佳匹配块ˆqΨ，目标块与最佳匹配块有如下匹配准则：

其中，d (Ψpˆ,Ψq)表示目标块Ψpˆ和样本块Ψq中对应已知像素的颜色差的平方和，I,I′分别对应块Ψpˆ和Ψq中的已知像素点，则 d(Ψpˆ,Ψq)可由下式表示：

2.3 置信度的更新

在找到最佳匹配块ˆqΨ后，将块ˆqΨ中的像素对应复制到目标块ˆpΨ中的未知像素点，该目标块内未知像素点转变为已知像素点，因此这些点的置信度需要更新为：

重复上述的3个步骤，直至待修复区域被填完为止。

3 本文算法介绍

直方图均衡化是由图像灰度演绎得出的一种增强图像整体对比度的增强技术，但是这种变换扩大图像的动态范围却是以牺牲图像的细节为代价的，因此本文将采用可以强化细节的自适应直方图均衡化[16]，不仅扩大了图像的动态范围，还可以抑制图像噪声，即先保存图像细节，再对图像进行直方图均衡化处理，最后再把细节加在处理后的图像上。

根据文献[15-16]，强化细节的自适应直方图均衡化的原理可以用以下公式来说明：

上式中， xi,j为原始图像的灰度值， xi′,j为处理后图像的灰度值， mi,j为以点 xi,j为中心的的图像窗领域内所有像素点的灰度均值， H(xi,j)表示对点 xi,j进行直方图均衡化操作，而 k(xi,j− mi,j)是用于增强所选图像的局部对比度即强化图像的细节，为了使增强后的图像不超过[0,255]图像的灰度值范围，上式增加了判别条件。

在式(6)中，k为自适应参量，通过自适应改变的取值，可以在增强图像细节的同时抑制掉图像背景中的噪声。为了实现这个目的，将参量的表达式定义为：

上式中，σi2,j为一个选定的大小为n×n方形窗W内的灰度方差， σn2为整幅图像的噪声方差，k′为根据所选图像的实际噪声状况决定的比例系数，其数值不宜过大也不宜过小。

在图像修复前用强化细节的直方图均衡化处理，可以扩大图像的动态范围，范围越大，层次感越强，有利于CDD模型的扩散和最佳匹配块的选择，但是不可避免的会降低图像的峰值信噪比，因此本文最后把修复后的图像，对应于待修复区域位置上的像素填充到原待修复图像上，以降低对原图像的影响。

相对于本文算法，尽管Criminisi算法可以修复大块破损的图像也可以修复划痕区域，但由于划痕区域在利用块搜索时将浪费大量时间，同时由于破损处较多，可能导致无完整块进行填充，必将导致修复结果偏差，造成错误信息的累积。因此本文先人工提取图像掩膜信息，利用形态学运算，先腐蚀再膨胀的方法分离出划痕区域与大块信息缺失区域的掩膜信息；然后利用CDD模型对划痕区域修复；再利用改进的Criminisi算法进行大块信息缺失区域的填充，最后把修复后的图像对应像素填补到待修复图像中。实验结果证明改进算法具有良好的视觉效果。

算法流程可以分为三部分，第一部分：对图像进行强化细节的自适应直方图均衡化(步骤1～2)；第二部分：分离出划痕区域与大块信息缺失区域的掩膜，并用CDD算法对划痕区域处理(步骤3～4)；第三部分：用改进的Criminisi算法进行后续处理(步骤5～9)。

本文算法具体如下：

步骤 1.读入受损图像，确定自适应均衡化操作所需要的方形窗W的大小(本文选取W为5×5)和比例系数k′的值(本文选取 k′= 7)；

步骤2.计算窗内的噪声方差 σi2,j，整幅图像的噪声方差 σn2及窗内像素点的平均灰度值 mi,j，带入式(7)，即计算出 xi′,j；

步骤 3.确定图像的掩膜信息，根据形态学运算[17]分离出划痕区域与大块信息缺失区域，并分别绘制其掩膜图；

步骤4.根据步骤3找出划痕区域的掩膜，利用CDD算法修复(本文CDD算法中迭代次数均取n= 1000次)；

步骤 5.找出分离后待修复大块区域的边界∂Ωi( ∂Ω0=∂Ω)，设置(初始时 i= 0)，如果 Ωi= φ，退出循环；

步骤6.计算优先权 P(p)， ∀p ∈∂Ωi；

步骤 7.找出具有最大优先权值的待修复区域块ˆpΨ ，即

步骤8.计算最佳匹配块Ψqˆ∈Φ，并把Ψqˆ中对应的图像信息复制到中；

Ψˆp∩Ω

步骤9.i=i+1，重复步骤5～8；

步骤10.把修复后的图像对应于掩膜的部分取出填补到待修复图像中。

4 实验结果分析

本文实验用 Matlab 2012b作为工具，在 Intel酷睿 2处理器(2.0 GHz)，2 G内存的 PC机上实现的。

实验将本文的算法与本文去掉步骤1和步骤2的算法(以下简称算法1)、CDD算法、Criminisi算法及文献[8]的算法分别进行了比较，如图 3~4所示。

图3是图像修复常用的蹦极图，图3(b)出现偏差延续，存在明显的不连续性；图3(c)~(e)(本文取λ1= λ2= 1, λ3= 3)屋顶及屋顶上下都存在一定的偏差，不能自然地体现屋顶的特征；图3(d)在大块信息缺失区域产生模糊现象，白色圈出来的位置为没有修复到的孤立点；图3(f)很好地解决了以上出现的问题，取得了较好的视觉效果。

图3 蹦极修复效果比较图

如图4可见，图4(b)和4(c)出现偏差延续现象，狒狒的鼻子上均有明显的黑色部分；图4(d)在大块信息缺失处出现模糊现象；图4(e)保证了图像在大范围上的视觉效果，但鼻子的左右两侧均稍有瑕疵，纹理不自然；图4(f)显示本文算法克服了上述算法的种种瑕疵，视觉效果最好。

图4 狒狒修复效果比较图

本文选取了两幅具有代表性的图片进行修复，通过实验对比与其他算法的修复时间，从表1中可以看出，本文算法相对于其他3种算法有效地缩短了时间，虽然CDD算法时间最短，但是在大块区域时有明显的模糊现象。表2展现了本文算法与其他算法的峰值信噪比(peak signal-to-noise ratio, PSNR)比较。

表1 不同算法修复时间比较(s)

表2 不同修复算法的峰值信噪比比较(dB)

5 结 束 语

本文简单介绍了CDD模型及Criminisi算法，分别分析了这两类算法的特点，因此在对待既含有划痕又含有大块破损的区域的图像，区分对待不同的待修复区域。实验结果表明，本文提出的算法不仅在处理划痕区域与大区域破损处能够较好的结合，而且Criminisi算法还能较好的处理CDD算法修复不到的孤立点，缩短修复时间，修复后的视觉效果更好。由于目前对图像修复的质量，均是依靠人眼主观评价，未来希望对修复质量的定量客观评价进行研究。

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

[2] Bertalmio M, Sapiro G, Caselles V, Ballester C. Image inpainting [C]//SIGGRAPH 2000, Proceedings of the 27thAnnual Conference on Computer Graphics, New Orleans, USA: ACM, 2000: 417-424.

[3] Chan T, Shen J. Mathematical models for local non-texture inpainting [J]. SIAM Journal on Applied Mathematics, 2002, 62(3): 1019-1043.

[4] Rudin L I, Osher S, Faterni E. Nonlinear total variation based noise removal algorithms [J]. Physica D, 1992, 60: 259-268.

[5] Chan T, Shen J. Non-texture inpainting by curvature-driven diffusions (CDD) [J]. Journal of Visual Communication and Image Representation, 2001, 12(4): 436-496.

[6] Criminisi A, Perez P, Toyama K. Object removal by exemplar-based inpainting [C]//Proc Conf Comp Vision Pattern Rec, Madison WI, 2003: 721-728.

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

[8] 黄淑兵, 朱晓临, 徐云云, 朱 坤. 一种改进的基于纹理合成的图像修复算法[J]. 合肥工业大学学报(自然科学版), 2011, 34(2): 313-320.

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

[10] Li B R, Qi Y, Shen X K. An image inpainting method [C]//Computer Aided Design and Computer Graphics, 2005. Ninth International Conference on. IEEE, 2005: 6.

[11] Wang Min qin. A novel image inpainting method based on image decomposition [J]. Procedia Engineering, 2011, 15: 3733-3738.

[12] Bugeau A, Bertalmio M, Caselles V, Sapiro G. A comprehensive framework for image inpainting [J]. IEEE Transactions on Image Processing, 2010, 19(10): 2634-2645.

[13] 刘庚龙, 檀结庆. 一种改进的整体变分图像修复方法[J]. 计算机工程与应用, 2012, 48(7): 194-196.

[14] 赵颜伟, 李象霖. 基于 CDD模型的快速图像修复算法[J]. 计算机仿真, 2008, 25(10): 223-227.

[15] 任 慧, 李新华, 朱逸婷. 自适应直方图均衡化改进的全变分图像修复[J]. 计算机系统应用, 2013, 22(6): 98-101.

[16] 宋 刚, 刘瑶华. 一种能强化细节的自适应直方图均衡法[J]. 山东工业大学学报, 1999, 29(1): 81-93.

[17] Rafael C G, Richard E W. 数字图像处理[M]. 3版. 阮秋琦, 阮宇智, 译. 北京: 电子工业出版社, 2011: 402-493.

An Image Inpainting Algorithm Combined of CDD Model and Criminisi Algorithm

Jiang Ping, Zhang Jin
(School of Mathematics, Hefei University of Technology, Hefei Anhui 230009, China)

Aiming at images with a lot of missing information and scratches, this paper puts forward a new restoration algorithm by combining the advantages of CDD model and Criminisi algorithm. Specifically, this algorithm first adopts the equalized operation of detail-oriented and self-adaptive histogram to expand the dynamic range of the images, and then utilizes morphology operators to separate the scratch regions and large areas in the images that need to be restored. Subsequently, CDD model is applied to restore the scratches and then the improved priority Criminisi algorithm is used to implement subsequent restoration. Finally, the restored images corresponding to the pixel of missing areas are filled into the regions of images need restoration. As the experimental results indicate, the improved algorithm has overcome the possible deviation continuation problems in current algorithm and can make the restored images more consistent with people’s visual effect.

CDD model; Criminisi algorithm; image inpainting; equalization of self-adaptive histogram; morphology operators

TP391

A

2095-302X(2014)05-0741-06

2014-03-03；定稿日期：2014-06-11

国家自然科学基金资助项目(11471093)

江 平(1972–)，女，安徽安庆人，副教授，博士。主要研究方向为CAGD、图像修复。E-mail：jiang_hfut@126.com