一种改进的BSCB图像修补算法

代妮娜，蔡 黎，戴闽鲁，2

（1.重庆三峡学院 信息与信号处理重点实验室，重庆 404000；2.数字电视国家工程实验室（北京），北京 101000）

一种改进的BSCB图像修补算法

代妮娜1，蔡 黎1，戴闽鲁1，2

（1.重庆三峡学院 信息与信号处理重点实验室，重庆 404000；2.数字电视国家工程实验室（北京），北京 101000）

针对传统BSCB算法对颜色复杂度高或缺损区域较大的图像修补效果较差的问题，提出一种改进的BSCB图像修补算法。考虑传统算法中初始化、光滑算子和修补扩散等步骤中存在的缺陷，分别对其进行了改进。改进的BSCB算法进行图像修补时，采用随机初始化方法，引入平滑和梯度算子代替原拉普拉斯图像平滑算子，并采用加权平均算法选择所有邻点进行异向性扩散，从而得到最终修补结果。实验表明，新方法修补图像，特别是修补颜色复杂度高、缺损区域较大的图像具有较好的效果。

图像修补；BSCB；随机初始化；平滑和梯度算子；峰值信噪比

对于多种因素导致的数字图像缺损，需要应用图像修补技术对其进行处理，以去除缺损信息还原原始图像。图像修补技术的基本原理为通过一定的算法，提取缺损图像中缺损区域的近似信息去填充缺损区域，最终使图片观察受体从感官上无法觉察该图像曾经受损。图像修补技术在计算机视觉、空间测量与摄像、医疗或特种行业图像匹配、艺术品处理与修复等领域都有广泛的应用。

目前较成熟的数字图像修补算法是由美国明尼苏达大学Bertalmio、Sapiro和庞培法布拉大学Caselles、Belleste四位学者受到艺术工作者修补艺术作品方法的启示，在2000年的美国计算机协会计算机图形专业组会议首次提出[1]，并用他们名字首字母命名的BSCB算法。BSCB算法引入偏微分方程（Partial Differential Equation，PDE）概念，对缺损图像建立BSCB模型，而后提取待修补区域的边缘信息，同时采用一种由粗到精的方法来估计等照度线方向[2]，最后用传播机制将提取的信息扩散到缺损区域，以得到较好的修补效果。

现有文献表明，传统BSCB算法对缺损区域较小，缺损图片颜色较单一的受损图像有较好的修补效果[2]，但是对颜色复杂，受损区域较大的图像却得不到好的修补效果，结果往往容易产生高斯模糊效应等不良表现。文献[3]提出了一种传统的BSCB算法，本文在文献[3]的基础上，展开进一步工作，对常规BSCB算法进行改进，以进一步提高BSCB修补算法的性能。

1 传统BSCB模型算法

传统BSCB算法的思路如下：首先用全变分量最小化法提取图像结构建模成矩阵，然后选择特定函数对缺损区域部分建模，从而将图像分解成原始信息和缺损信息两个部分，再用BSCB模型来修补缺损部分，用特定的算法来填充纹理部分，最后叠加修补和填充结果，得到最终修补图像。其本质是一个沿等照度线驱动图像采样过程，工作流程如图1所示。

图1 传统BSCB修补算法流程

1）修补区域识别与判定。读取图片，初始化后识别判定颜色偏差，从而识别出修补区域，模型如图2所示。

图2 区域识别图

图2中，Ω是待修补区域，Ω0是原始的待修补图像，∂Ω是图像边界。

2）扩散方向及等照线。所有点的灰度值都相等或者是近似相等所组成的一条线叫做等照线[4]。修补图像的过程就是从待修补区域的边界∂Ω向待修补区域Ω扩散的过程，扩散依据就是等照线。如图2，其中N为扩散的方向，N与边界∂Ω是一致的，图2中椭圆框内区域的N如箭头所指，这样可以取得较好的扩散效果。

其中，原始的图像为 I0(i,j):[0,M]×[0,N]→N ，[0,M]×[0,N]→N×N，其中I0（i,j)表示原始图像中各点的灰度值，M和N表示图像的尺度信息。

式中：Nn(i,j)表示的是在(i,j)点第n次迭代得到的等照线的方向；Ln(i,j)表示的是第n次向(i,j)点延伸的信息；ΔLn(i,j)表示Ln(i,j)在两个方向的变化量，In+1(i,j)≈In(i,j)时，有(i,j)=ΔLn(i,j)·Nn(i,j)≈0，即认为图像信息已经稳定。

传统算法中采用拉普拉斯因子作为图像平滑算子Ln(i,j)，表达式为

2 改进后的BSBC模型算法

2.1 改进初始化判定环节

传统BSCB算法对缺损图像采用纯色初始化算法，即把待修补的区域初始化为同一种颜色（一般为白色），此种方法非常容易实现，但人为指定的单一颜色可能和待修补的缺损区域颜色差别较大，导致原图像信息不能得以保存，所以对于图像颜色复杂或缺损区域较大的图像最终修补效果不佳。

改进纯色初始化为随即初始化，具体的步骤如下：在带修补区域中任取一目标点O，以O为中心，沿横、纵方向寻找到与该点距离最近的非污损区域的4个交点，如图3记为k1，k2，k3，k4。

图3 平均值初始化坐标图

计算X，Y方向上2个点的间距ΔkC= ||k2-k1，ΔkL= ||k4-k3。若ΔkC＞ΔkL，说明Y方向边缘距离O点近，纵向相关性大，则参考Y方向上的2个边缘点k3和k4，选取它们灰度值的平均值间给O点赋初始值，反之亦然。

2.2 改进光滑算子的选择

现有文献一般采用拉普拉斯算子作为修复的光滑算子，优点是计算速度快，对颜色相邻域缺损修补效果好，但因为其考虑部分邻点进行同性扩散，对于某些颜色复杂度高的缺损，修补后的图像会变得很模糊，需要对光滑算子进行重新选择。

已有文献引入平滑和梯度（Smoothing and Gradient，SG）算子替代拉普拉斯算子[6]，SG是平滑度和梯度的结合，传统BSCB算法的平滑拉普拉斯算子只是SG算子参数为某值时的特例。SG算子参数较多且难以确定，运算复杂导致修补时间表现不佳[7]，若参数确定不佳反而降低其性能表现，因此诸多文献对其做了近似处理，文献[8]提出一种平滑和梯度近似（Approximation of Smoothing and Gradient，ASG）算子来替代SG算子。但是引入ASG算子是以牺牲修复效果为代价的，ASG算子没有改变将图像做各向同性扩散的本质，所以仍然可能导致修复图像纹理变模糊[9]。为避免上述缺陷，文献[8]在引入ASG算子后对自变量采用Max/Min函数做选择，本文用加权平均函数做选择，具体算法如下：

式中：mavg为去掉3个数中最小值求平均；Mavg为去掉3个数中最大值求平均。

引入的ASG算子的方程算式如下

式中：ζ是等照线的方向向量，当ut→0时，可达到扩散的目的[10]。

另外，采用式（7）模型来确定等照线的移动轨迹

式中：k是等照线曲率，uζζ是沿着方向的二阶偏导数，式（7）可以保证等照线不会交叉[11]，沿受损图像边缘的切线的进行光滑扩散，最大限度地保留图像边缘。

2.3 改进修补扩散算法

扩散是修补的重要步骤，核心区域选取是扩散的基础，反复迭代是扩散的核心[12]。为了保证扩散修复的过程正确的演化，本文改善核心区域的选取，优化迭代次数，进一步降低噪声，以获得更好的修补区域边缘锐利性。

如图4，首先定义区域直径：在一个区域中选择两点，使得两点之间的距离d最大，定义d为此区域直径。显而易见，Ωε就是Ω经过扩散而来，其中圆的直径选的即为待修补区域Ω的直径，圆心为区域直径中心点。

图4 扩散示意图

采用第1节中图2的方向进行等照线异向性扩散，算法方程为

κ(i,j)表示的是等照线在点(i,j)的曲率[12]，至此，核心区域选择完成。

改善后的迭代算式为

式中：In(i,j)是I(i,j,n)的简写形式，表示的是第n步所得到的结果，(i,j)表示的是像素坐标，Int(i,j)表示的是对In(i,j)的修正，Δt表示的是迭代的步长，公式的作用域在Ω里面。随着n的增大[5]，图像修补的效果越来越明显，当n增加到一定的时候，这里的In(i,j)将不会有太大的变化，此时如果继续迭代，修补效果不会增强甚至可能变差，同时极大地延长了修复时间，所以选择满足式（11）的制约条件时迭代停止：

3 实验结果

在MATLAB7.0（R14）平台编辑M文件实现上述算法，选择分辨率为600×450的两张位图（Bitmap，BMP）图像作为实验对象。一张为轻微缺损的颜色较单一图像即图5b所示的受损图像，一张为非轻微缺损的颜色较复杂图像即图6b所示的受损图像，分别用传统BSCB和改进的BSCB算法对其进行修补。

图5 实验结果1

图6 实验结果2

图像修补结果评价包含主观评价和客观评价两部分[3]。

首先进行人眼主观评价，因为人眼始终是图像最后的信息判断受体，所以主观评价更为重要，若人眼不能判断出图像是原始图像还是修复后的图像，则说明此图像修复效果为优。

观察图5所示的实验结果1，可见对于颜色复杂度较低的轻微缺损图像，传统和改进的BSCB模型算法均有较好的表现，在保持原有分辨率未进行放大的情况下，人眼几乎不能判断出修补效果的优劣，放大以后，能观察到修补区域有细微的模糊表现。

观察图6所示的实验结果2，对于颜色复杂度较高的非轻微缺损图像，传统BSCB修补算法品质恶化严重，拉普拉斯算子考虑了所有的邻点进行同性扩散，造成了修补区域和相邻区域的大面积色块模糊，同时纯色初始化导致丰富的颜色信息丢失，修补效果不令人满意。而改进的BSCB算法在随机初始化时充分保留了缺损周围区域的颜色信息，使得待修补区域在开始的时候就保留一定的信息特征[13]，引入ASG算子后加权平均周围所有点的图像信息进行异向性扩散，使修补区域边缘锐利性更平滑，表现出较好的修补效果。

客观评价选用两个指标：峰值信噪比（PeakSignal Noise Ratio，PSNR）测度和修补时间t[13]，PSNR的计算公式为

式中：MSE代表最小均方误差。

实验结果1和实验结果2的PSNR评价分别见表1和表2。

表1 实验结果1的PSNR评价

表2 实验结果2的PSNR评价

测试平台硬件为Intel i3-2120CPU、4 Gbyte RAM、NVID⁃IA GeForce 405显示卡、512 Gbyte显示内存、ST3500413硬盘、容量300 Gbyte，软件平台为WindowsXP SP2（5.1.2600）、MATLAB7.0。在该平台运行具修补时间观测功能的M文件处理上述图像，得到结果如表3所示。

表3 实验结果1、2的修补时间对比

表1、表2表明改进的BSCB算法修补结果PSNR值更大，更忠于原始图像，修补效果更好。表3表明对于颜色复杂度较低的轻微缺损图像修补时间t，两种算法相差无异，对于颜色复杂度较高的非轻微缺损图像修补时间t，改进后的BSCB算法时间增加约10%，但是相对于修补品质的优化，这个时间增加是可以接受的。

4 结语

在传统BSCB图像修补算法的基础上，本文提出了一种改进的BSCB图像修补算法。与传统算法相比，本文的方法对于颜色复杂度高、缺损区域较大的图像修补效果更好。若对相关子算法的运算策略做进一步优化，如引入快速矩阵算法、多分辨率匹配等，能更好地降低算法的复杂度，缩短修补时间，增强图像修补效果。今后将重点研究快速矩阵运算策略，进而与该匹配方法结合，在保持图像修补效果的同时缩短修补时间。

[1]BERTALMIO M，SAPIRO G.Image inpainting[C]//Proc.the ACM SIGGRAPH Conference on ComputerGraphics.SIGGRAPH: ACM Press，2000：417-424.

[2] 张红英，彭启琮.数字图像修复技术综述[J].中国图象图形学报，2007，12（1）：1-8.

[3]卢小宝，王维兰.基于样本块的破损唐卡图像修复算法的改进[J].计算机应用，2010，30（4）：943-946.

[4]胡时琳.自适应图像修复算法研究[D].重庆：重庆大学，2012.

[5] 谢爱敏.BSCB图像修补方法介绍[EB/OL].[2014-03-20].http:// www.pudn.com/downloads333/sourcecode/math/detail1460973.ht⁃ml.

[6]吴东亚.数字图像修复技术[M].北京：科学出版社，2010.

[7] 曾勋勋，陈飞.基于BSCB模型的图像修补算法[J].福州大学学报：自然科学版，2009，37（5）：657-661.

[8]CRIMINISIA，PEREZ P，TOYAMA K.Region filling and object⁃tremoval by exemplar-based image inpainting[J].IEEE Transac⁃tions on ImageProcessing，2004，13（9）：1200-1212.

[9] 张静，余烨，叶强强，等.一种改进的BSCB修复模型[J].系统仿真学报，2011，23（1）：277-281.

[10]BERTALMIOM.Strong-continuation，contrast-invariant inpaint⁃ing with a third order optimal PDE[J].IEEE Trans.Image Pro⁃cessing(S1057-7149)，2006，15（7）：1934-1938.

[11]BUADESA，COLL B，MOREL JM.A non-local algorithm for image denoising[C]//Proc IEEE Conf.on Computer Vision and Pattern Recognition.Piscataway：IEEE Press，2005:60-65.

[12]田素云，王小明，赵雪青，等.基于拉普拉斯算子和图像修补的图像去噪算法[J].计算机应用，2012，32（10）：2793-2797.

[13] 纪利娥，杨风暴，王志社，等.图像配准中特征点检测算法的探讨[J].电视技术，2013，37（19）：27-31.

代妮娜（1983—），讲师，主研数字信号处理；

蔡 黎（1981—），讲师，主研通信与控制技术；

戴闽鲁（1958—），教授，主研数字电视技术。

责任编辑：闫雯雯

Im proved BSCB Image Inpainting A lgorithm

DAI Nina1，CAI Li1，DAIMinlu1，2
（1.Chongqing Three Gorges University，Signal and Information Processing Key Lab，Chongqing 404000，China；2.Beijing Digital Television National Engineering Laboratory，Beijing 101000，China）

The traditional BSCB algorithm has less effect on inpainting image with the high complexity of color or large defect area.An improved BSCB image inpainting algorithm is proposed,which makes up for defects of the traditional algorithm in the initialization，smooth operator and patch diffusion steps.The improved BSCB adopts the random initialization method in image inpainting.Then it uses the smooth and gradient operators instead of laplace smoothing operator，and selects all the adjacent points to do the anisotropic diffusion by the weighted average to get the final inpainting result.The experiment shows that this new algorithm has better effect on inpainting image with complex color and large defect area.

image inpainting;BSCB;random initialization;smoothing and gradient;peak signal noise ratio

TN911.73

A

10.16280/j.videoe.2015.02.019

2014-03-24

重庆市教育科学技术研究资助项目（KJ121114）；重庆三峡学院信息与信号处理重点实验室开放基金项目（SXXY201218）

【本文献信息】代妮娜，蔡黎，戴闽鲁.一种改进的BSCB图像修补算法[J].电视技术，2015，39（2）.