结合颜色向量角和灰度熵的图像修复

吴长勤，王亚军，王传安

安徽科技学院数理与信息工程学院，安徽 凤阳 233100

结合颜色向量角和灰度熵的图像修复

吴长勤，王亚军，王传安

安徽科技学院数理与信息工程学院，安徽 凤阳 233100

针对现有图像修复算法效率低下的问题，提出一种结合颜色向量角和灰度熵的图像修复改进算法．根据颜色向量角能够衡量图像中不同颜色之间的差异特性，算法先构造边缘项来代替Criminisi算法中的数据项，并改进优先级计算方式；然后根据图像局部灰度均值的一维信息熵来度量图像中待修复块周围图像，进而采用局部平均灰度熵确定搜索区域的大小，以减少搜索最佳匹配块的搜索时间．实验结果表明，与Criminisi算法相比无论从速度上还是修复的质量上文中所提算法都占有优势．

图像修复；颜色向量角；灰度熵；Criminisi算法

0 引言

数字图像修复是图像处理领域的一个分支，也是目前计算机视觉方面的研究热点之一．数字图像修复的本质是利用其周围的有用信息，按照一定的规则对图像受损区域进行填充，使修复后的图像可以达到或接近人们所要求的视觉效果［1］．根据待修复区域的大小，图像修复方法可分为两类：一类是基于变分和偏微分方程的图像修复［2－4］，其基本思想是根据信息扩散原理来完成图像受损区域的修复，当图像受损区域较小时，修复效果很好，几乎没有任何痕迹，但当图像受损区域较大时，修复时会出现模糊效应；另一类是基于纹理的图像修复，该类算法几乎不受图像受损区域大小的影响，能取得较好的修复效果，其逐渐成为图像修复领域的主流算法，吸引众多国内外学者进行研究［5－7］．

1 Criminisi算法思想

先介绍算法中用到的几个变量，I表示需要修复的图像，Ω为受损区域，即待修复区域，Φ为未受损区域，∂Ω为区域边界，p为边界∂Ω上优先级最高的像素点，如图1所示．

Criminisi算法提出采用优先级进行修复的思路，并以每次匹配时的最优作为全局最优，其修复步骤可概括如下：

a.首先确定待修复区域，并标记出其边界∂Ω，若∂Ω为空，则退出．

图1 Criminisi算法变量示意图Fig.1 The related variables in Criminisi algorithm

b.计算修复优先级：选取边界∂Ω上的任意一点p，计算其优先级P（p），并以p为中心，确定一个矩形块ψp.P（p）计算公式为：

式（1）中，C（p）为置信项，D（p）为数据项，定义分别如下：

等照度线即为灰度值相同的一条曲线，故该曲线方向的颜色变化值最小．

c.以优先级最大的像素点p为中心形成待修复块ψp，并在图像未受损区域内搜索最佳匹配块ψq，即与ψp距离最小的模块：

式（4）中d为感知距离，对于灰度图是两模块对应各点的灰度值平方差之和，而彩色图像则是对应各点的RGB值平方差之和．

d.复制最佳匹配块ψq中相应的像素点到ψp中．

e.更新ψp模块中像素点的边界和置信度等信息．根据置信度的定义，其更新方式如下：

2 改进的算法

Criminisi算法属于一种典型的贪心算法，它充分考虑了图像本身的梯度和结构等信息，其修复效果相比其他算法在速度和修复质量上都有很大提升，属于图像修复领域中的里程碑，但也存在值得改进的地方［8］．

2.1 改进计算优先级

Criminisi算法在优先级计算中采用等照度线到达边缘的强度来计算数据项D（p），以保证处在强边缘的像素块获得更高的优先级，而这种优先级计算公式不仅计算量大，且不能保证准确地反映图像边缘结构信息，同时在修复过程中，置信项C（p）和数据项D（p）有可能出现一大一小两个极端，从而导致优先级极小，这不符合实际情况［9］．颜色向量角能够检测数字图像边缘的特性［10］，因此，提出采用构造边缘项来代替Criminisi算法中的数据项，从而能更准确地反映图像边缘特性，同时提高修复效率．

先将待修复图像向外扩充一个像素，以保证后续能够对边缘像素及其他像素做同样的处理．在RGB颜色空间中，以图像中某一像素点为中心P0，选取其四周3×3邻域范围内的8个像素点P1、P2，…、P7、P8，并计算P0与邻域八像素点的颜色向量角正弦值：

根据式（6）可得到8个颜色向量角正弦值，然后其中最大的正弦值来表征像素间的色差：

对整个待修复图像所有像素进行上述计算后，将结果组合在一起，得到边缘图像IM：

式（8）中m，n表示待修复图像大小为m×n．接下来，进行优先级计算：

式（9）中C（p）仍为置信项，而E（p）为边缘项：

在改进后的优先级计算中，使用边缘项取代了数据项，避免了原先计算中的等照度线和正交法向量等复杂运算，且可以统一表征图像的边缘强弱．同时，改进后的优先级为两项和的形式，以消除因置信项迅速衰减造成的优先级的极小值问题，从而避免误差过度传播．

2.2 基于灰度熵的匹配搜索

Criminisi算法采用全局搜索方式搜索最佳匹配模块，该方式不仅十分耗时，且没有考虑到图像的局部自相似性．实际上，待修复图像上某一位置的像素值与其周围邻域的像素值有密切的关系，对于图像修复问题而言，熵是一种图像特征的统计形式，它可以反应图像中信息的多少［11－12］．

基于结构纹理图像的局部性和稳定性原理，笔者对局部平均灰度的信息熵进行统计，从中发现，在待修复图像中像素值变化相对平缓的区域，如图像中天空、河流等，其修复块与邻域块之间的平均灰度值较为接近，所以局部平均灰度熵值较小．反之，在越是复杂的图像区域，其像素变化剧烈且无规则，局部平均灰度熵越大，因此可利用局部平均灰度熵确定搜索区域的大小．首先定义待修复像素点p的邻域像素集合TS（P）：

式（11）中T（p）为像素点p的邻域矩形块，且要求该邻域块要尽可能大于待修复矩形块的大小．

令Numi表示像素点p的邻域矩形块内平均灰度值为i的样本块的个数，Pi表示平均灰度值为i的样本块所占比例：

则待修复块邻域矩形块的局部平均灰度熵为：

在局部平均灰度熵大于给定熵阈值的待修复块处，由于多种纹理交错产生图像的边缘结构，需要较为细致的操作，选择相对较大的搜索区域完成匹配模块搜索操作；而在小于熵阈值的待修复块处，其纹理基元与基元之间具有统计相似性和重复性，因此，图像块与块之间的纹理具有统计相似性，选择较小的搜索区域，以加快搜索速度，从而提高修复效率．

3 实验结果与分析

对Criminisi算法和文中提出的改进算法的图像修复效果进行实验比较，实验用的PC配置为corei5四核处理器，内存为4 G，安装64位windows 7操作系统，算法编写语言为C＋＋及开源库OpenCV2．4．2．实验结果如图2、图3所示，图2是利用本文算法和Criminisi算法修复破损图像过程中得到的置信项、边缘项以及优先级曲线的对比图，图3为两算法修复图像效果的对比图．

图2 两算法参数曲线对比图Fig.2 Comparison of parameter curves of two algorithms

图3 图像修复对比Fig.3 Comparison of image restoration effects of two algorithms

从图2可看出，本文算法修复过程中获得的参数曲线不管是边缘项还是置信项或数据项，不会随着修复过程的累积而迅速下降，相比Criminisi算法取得较好的曲线效果.改进优先级计算方式所得的优先级曲线相比Criminisi算法更稳定，不会出现骤降情况.而图3表明文中提出的修复方法修复后的图像跟原始图很接近，基本上修复了破损图像部分，相比Criminisi算法取得了更好的修复效果.

为更直观明了的验证文中所提算法的修复效果，实验采用客观评价方法做为修复图像质量评估的客观标准，表1展示了两种修复算法在均方误差（MSE）、峰值信噪比（PSNR）和算法执行时间方面的客观度量．

表1 两种修复算法的客观度量Table 1 The comparison results of other parameters of two algorithms

从表1可以看出，本文提出的算法相对Criminisi算法来说均方误差比较小，峰值信噪比更大，失真较小，修复效果更好，更接近原图，且计算量大大减少．因此与Criminisi算法相比无论从速度上还是修复的质量上文中所提算法都占有优势．

4 结语

本文简单介绍了经典的Criminisi算法的基本思想，分析了该算法在修复过程中存在的不足．针对优先级极小值问题，使用边缘项取代数据项，并优先级改为两项和的形式．Criminisi算法采用全局搜索方式搜索最佳匹配模块，且没有考虑到图像的局部自相似性，导致执行时十分耗时，针对此问题，在达到与Criminisi算法相当的修复质量的前提下，提出了采用局部平均灰度熵确定搜索区域的大小，以减少搜索最佳匹配块的搜索时间．

致谢

安徽科技学院计算中心对本文实验和测试等提供帮助和支持，葛华老师在研究过程中提供了指导和帮助，在此表示感谢！

［1］BERTALMIO M，SAPlRO G，CASELLES V，et al．Image inpainting［C］//Proceedings of the International Confer-ence on Computer Graphics and Interactive Techniques．New Orleans Louisiana USA，2000，1：417－424．

［2］CHAN T F，SHEN J．Mathematical models for local nontexture inpainting［J］．SIAM Journal on Applied Mathematics，2002，62（3）：1019－1043．

［3］ESEDOGLU S，SHEN J．Digital image inpainting by the Muxnford－Shah－Euler image model［J］．European Journal of Applied Mathematics，2002，13（4）：353－370．

［4］叶学义，王靖，赵知劲，等．鲁棒的梯度驱动图像修复算法［J］．中国图像图形学报，2012，17（6）：630－635．

YE Xue-yi，WANG Jing，ZHAO Zhi－jin，et al．Robust gradient driving image inpainting method［J］.Journal of Image and Graphics，2012，17（6）：630－635．（in Chinese）

［5］EFROS A A，FREEMAN W T．Image quilting for texture synthesis and transfer［C］//Proeeedings of ACM TransactionsonGraPhics（SIGGRAPH01），USA：ACM，2001．341－346．

［6］朱晓临，陈晓冬，朱园珠，等．基于显著结构重构与纹理合成的图像修复算法［J］．图形学报，2014，35（3）：336－342．

ZHU Xiao－lin，CHEN Xiao－dong，ZHU Yuan－zhu，et al．An image restoration algorithm based on structure and texture synthesis with reconstruction of significant structure of images［J］．Journal of Graphics，2014，35（3）：336－342．（in Chinese）

［7］马爽，谈元鹏，许刚．块关联匹配与低秩矩阵超分辨融合的图像修复［J］．计算机辅助设计与图形学学报，2015，27（2）：271－278．

MA Shuang，TAN Yuan－peng，XU Gang．Image completion based on fusion of patchassociatedmatching andlow－rank matrix super resolution［J］．Journal of Computer-AidedDesign＆ComputerGraphics，2015，27（2）：271－278．（in Chinese）

［8］赵胜．基于纹理合成的图像修复算法研究［D］．成都：电子科技大学，2014．

ZHAO Sheng．The image restoration algorithm based on texture synthesis［D］．Chengdu：University of Electronic Science and Technology of China，2014．（in Chinese）

［9］陈晓冬，朱晓临．基于改进优先级的加权匹配图像修复算法［J］．合肥工业大学学报：自然科学版，2013，36（1）：113－118．

CHEN Xiao－dong，ZHU Xiao－lin．A weighted matching image restoration algorithm based on modified priority［J］．Journal of Hefei University of Technology：Natural Science，2013，36（1）：113－118．（in Chinese）

［10］叶春．数字图像水印及修复算法研究［D］．桂林：广西师范大学，2014．

YE Chun．Research on digital image water marking and repair algorithm［D］．Guilin：Guangxi Normal U-niversity，2014．（in Chinese）

［11］RIVERA M，OCEGUEDA O，MARROQUIN J L．Entropy－controlled quadratic markov measure field models for efficient image segmentation［J］．IEEE Transactions on Image Processing，2007，16（12）：3047－3057．

［12］张晴．基于样本的数字图像修复技术研究［D］．上海：华东理工大学，2012．

ZHANG Qing．Study on exemplar－based image inpainting technologies［D］．Shanghai：East China University of Science and Technology，2012．（in Chinese）

Image inpainting algorithm combining color vector angle with entropy of brightness

WU Chang－qin，WANG Ya－jun，WANG Chuan－an
College of Mathematical and Information，Anhui Science and Technology University，Fengyang 233100，China

A new restoration algorithm combining color vector angle with entropy of brightness was proposed to improve low efficiency in image inpainting．First，we measured the different characteristics of colors in the images according to the color vector angle，and redefined the calculation priority on the basis of Criminisi algorithm．Then，we calculated the one－dimensional entropy of local average gray values around the inpainting area，and used the average gray entropy to determine the size of the search area，which could reduce the search time for the best matching block．The experimental results show that the proposed algorithm has better restoration and less time consuming than Criminisi algorithms．

image inpainting；color vector angle；entropy of brightness；Criminisi algorithm

TN911.73

A

10.3969/j.issn.1674-2869.2015.06.011

1674－2869（2015）06－0051－05

本文编辑：苗变

2015－4－20

安徽省教育厅自然科学基金（KJ2013Z048）项目

吴长勤（1962－），男，安徽肥东人，副教授．研究方向：图像处理技术．