基于BSCB模型的图像修补算法

1、第 37卷 第 5期 2009年 10月福州大学学报 (自然科学版 Journa l o f F uz hou U n i versity(N a t ura l Sc i ence Ed iti onV o. l 37No. 5 O ct . 2009文章编号 :1000-2243(2009 05-0657-05基于 BSCB 模型的图像修补算法曾勋勋 1, 陈 飞 2, 王美清 1(1. 福州大学数学与计算机科学学院 , 福建 福州 350108; 2. 集 美大学理学院 , 福建 厦门 361021摘要 :在 BSCB 模型上考虑了图像的梯度以及相应邻点的信息 , 引入 m ax /mi

2、n 函数 , 提出用 ASG 算子代替光滑 算子 , 对 BSCB 模型进行修改 . 实验证明 , 新算法能较好地对图像进行 修补 , 尤其是在保 持边缘和角 点的特征 上效果比较好 .关键词 :图像修补 ; 偏 微分方程 ; BSCB 模型中图分类号 :TP 391 文献标识码 :AI m age i n painting based on the BS CB m odelZENG Xun-xun 1, C HEN Fei 2, WANG M e i-q i n g 1(1. Co lleg e o fM athe m atics and Compu ter Sc i ence , Fuzh

3、ou U niversity , Fuzhou , Fuji an 350108, Ch i na ;2. Schoo l o f Sc ience , Ji m e iU n i ve rs i ty , X i amen , Fuji an 361021, Chi naAbstract :A ne w ASG operato r is proposed by e m ploy i n g parti a l ne i g hbouring po i n ts by m ax /mi n f u ncti o n, not consi d ering all the ne i g hbour

4、 i n g grey values , and is used as an appropriate i n for m ation pr opagati n g esti m a tor to m od ify the BSCB m ode. l The m od ified i m age inpa i n ti n g m odel pr oved by ex peri m ents to be ab le to get good results at the edges and cor ners .Keywords :i m age i n pa i n ting ; PDE s ;

5、BSCB m odel图像修补是利用受损区域周围的图像信息给修补区域填充信息的一门技术 , 作为图像处理的一个分 支 , 已经在国内外受到广泛的重视 . 图像修补在数字图像处理 , 视觉分析和电影工业中有许多重要的应 用 1, 2, 如 :修补古老艺术品或旧照片的损坏区域、 自动寻找并修复旧电影胶片中的划痕、 去除图片中的 说明文字、 移走物体、 图像放大等等 . 近年来 , 从偏微分方程角度研究图像修补已成为一种主要的方法 , 并取得了良好的效果 . Bertal m io 3, 4等人最早采用偏微分方程的方法进行图像修复 , 他们利用三阶 PDE 模 型 , 提出了 BSCB 模型 . C

6、han 等人提出了整体变分方法 (TV, To tal Variation 5, 6和基于曲率的扩散模型 (CDD, Curvature D ri v en D iffusi o ns 7. 但是 , 以上这两种方法都没有考虑人类视觉的连接性原则 , 在修复 的图像中可能产生人为的角点 , Chan , Kang 和 Shen 8通过进一步分析 CDD 模型 , 结合 BSCB 模型 , 提出 了欧拉弹性模型 (EE 模型 , 但该模型仍不能很好地保持图像的边缘与角点 . 本文在 BSCB 模型基础上 , 考虑到图像的梯度以及相应邻点的信息 , 引入非线性函数 , 提出用 ASG 算子代替光滑

7、算子 , 对 BSCB 模型 进行修改 .1 BSCB 模型Bertal m i o 3, 4等人根据艺术家实际的图像修补方法建立了基于 PDE 的 BSCB 图像修补模型 . 它的主要 思想是沿等照度线的方向将修补区域周围的信息迭代到修补区域内 , 产生修补信息 . 等照度线的方向可 以通过计算修补的轮廓线上的每一个点的离散梯度向量 (表示空间最大变化的方向 , 并将其旋转 90 得 到 . 这样可以在迭代的过程中 , 有效地保持边界 . 每若干步迭代之后 , 算法进行一个反复扩散的过程 , 以 保持修补区域的平滑 . 各向异性的扩散有利于保持穿过修补区域的边界 .收稿日期 :2008-10

8、-7作者简介 :曾勋勋 (1981-, 女 , 助教 .基金项目 :国家自然科学基金资助项目 (10771036; 福建省高等学校新世纪优秀人才支持计划资助项目 (SX2006-40福州大学学报 (自然科学版 第 37卷 BSCB 模型方程为 u / t = ( u u = u ( u , 其中 为等照度线方向 . 其主要思想 是沿着等照度线向待修补区域光滑地传播信息 , 以达到修补图像的目的 . 由于模型采用拉普拉斯算子作 为光滑算子 , 当像素点进行数值计算时 , 会综合考虑所有邻点 , 进行同性扩散 , 因此会造成图像模糊 , 并 且容易产生等照度线的交叉 . 基于以上分析 , 提出 A

9、SG 算子 (Approx i m ation o f Sm ooth i n g and Gradien, t 简 称 ASG, 使用 m ax /mi n 函数 , 有选择性地采用部分邻点 , 并运行适当的加权算法 , 对于修补区域较大的 图像 , 可以更好地保持图像的边缘和角点 . 2 S G 算子在计算图像的梯度算子 u =(u x , u y 时 , 通常采用的差分格式为 u x =12h (u i+1, j -u i-1, j , u y =12h(u i, j-1-u i, j+1, 其中 h 为步长 . u x 、 u y 通过如图 1模板来表示 . 在 BSCB 模型中 ,

10、u / t = ( u u = u ( u , 式子右边的中间因子是对拉普拉斯算子的运算结果进行梯度运算 . 因此 , 先提出一种算子 SG (Sm oo thing and Grad ien, t 简称 SG, 用来简化表 示平滑算子和梯度运算的结合 , 可以更好引入后面的 ASG 算子 . SG 算子 u =(x , y , 其中 x , y 的 定义见图 2. 当参数 =1, =1, =-4时 , 相当于先做拉普拉斯算子处理 , 然后进行梯度场的计算 . 3 BSCB-AS G 模型在 BSCB 模型中引入 SG 算子 , 用 u 作为信息变化量代替 ( u , 模型如下 :u t =

11、u u(1图 3 水平梯度的计算 F i g. 3 Co m puta ti on in the horizonta l d irection 该算法简单 , 易于数值实现 , 但是该模型参数比较多 , 选择比较复杂 . 在进行图像修补时 , 会造成边缘的模糊、 对 角点的处理特别差 . 为此 , 提出近似 SG 算子的 ASG 算子(Approxi m ation of S m oothing and Grad i e nt, u =(u x ,uy . 该算子有选择性地采用部分邻点 , 而不是 SG 中的 采用全部邻点 , 从而反映了该点灰度值的局部情况 . 最易想到的方法是对点 u ij

12、 以及它的所有邻点进行排序 , 选取中间的若干个点来反映该点的局部灰度值分布情况 .比如评委对选手进行打分时 , 去掉最高分和最低分 . 但是这种方法 , 需预先对这些点进行排序 , 计算复杂度高 ,而且仍属于加权平均算法 , 会对边缘造成一定的模糊 .采用 m ax /mi n 函数 , 如图 3所示 .u x =2hm avg(Mavg (u i+2, j , u i+1, j , u i , j , m ax (u i+1, j+1, u i+1, j , m ax (u i+1, j-1, u i+1, j -m avg(Mavg (u i-2, j , u i-1, j , u i,

13、 j , m ax (u i-1, j+1, u i-1, j , m ax (u i-1, j-1, u i-1, j (2 :. 658第 5期曾勋勋 , 等 :基于 BSCB 模型的图像修补算法 的均值 . 同理可得 u y . u y =2hm avg(Mavg (u i, j+2, u i , j+1, u i , j , m ax (u i+1, j+1, u i , j+1, m ax (u i-1, j+1, u i, j+1 -m avg(Mavg (u i , j-2, u i , j-1, u i, j , m ax (u i+1, j-1, u i, j-1, m ax

14、 (u i-1, j-1, u i , j-1 (3 引入 ASG 算子的 BSCB 模型方程具有如下形式 :u t = u u(4 该算法沿等照度线方向 进行延扩 , 延扩大小为 u .方程进行多次迭代 , 等照度线上的像素越来越平滑 , 当发展方程接近平衡态时 , 模型就完成了传播 , 这时有 u 0, 从而达到 填充的目的 . 前面因子 u 可以提高数值的收敛性 .另外 , 采用下列模型 :u t =k u =u(5 来控制等照度线的移动方向 , 其中 k 是等照度线的曲率 , u 为沿方向的二阶偏导数 . 可以让等照度线沿 梯度反方向移动 , 以保证等照度线不会出现交叉现象 , 同时光

15、滑方向为图像边缘的切线方向 , 保留了图像 的边缘 .改进后的模型称为 BSCB -ASG 模型 . 方程 (4 与 (5 交替进行 , 可以解释为 :方程 (4 是沿等照度线 方向的平滑 ; 方程 (5 可以看成是等照度线方向的控制 , 避免等照度线的交叉 .令u = u =(u x , u y (-u y , u x x +u y (6则方程 (4 可改写为 :u t = u u (7 4 模型分析由于 BSCB -ASG 算子使用 m ax /min 方法 , 有选择性地采用部分邻点 , 并运行适当的加权算法 , 因此在 图像修补的时候可以保持图像的边缘和角点 ; 而采用与异性扩散算法交

16、叉进行 , 可以加强沿等照度线的扩散 并避免等照度线的交叉 , 从而达到理想的修补效果 . 下面对一幅大小为 9 9像素的单色图像进行分析 (如图4, 方框内的数字为图像的灰度值 , 白色表示像素值为 1的区域 , 黑色表示像素值为 0的区域 . 图 5是带有 填充区域的单色图 , 浅灰色像素区域大小 3 5为图像待修补区域 , 白色和黑色区域为待修补区域的外邻域 , 其中 a, b , c , d 为修补区域内的 4个点的像素值. 显然对于图 5来说 , 边缘线遭到破坏 .为了方便比较 , 计算出 BSCB 模型方程和 BSCB -ASG 模型方程在图像待修补区域上的修补结果 . 假 设待修

17、补区域初始填充值为 0. 计算的顺序采用的是从左至右 , 从上到下 . 由于原有 BSCB 模型方程采用 拉普拉斯算子作为光滑算子 , 在像素点进行数值计算时 , 会综合考虑所有邻点 , 进行同性扩散 , 因此会造 成图像模糊 , 并且容易产生等照度线的交叉 . 迭代 1次 , 可以得到同性扩散使得像素点 a 影响到像素点 b 、 c d , .659 福州大学学报 (自然科学版 第 37卷 BSCB -ASG 算法在图像填充过程中 , 可以更好地保持图像边缘 . 首次迭代 , 在像素点 b 的位置 , 就有效地 阻止了像素点 a 的扩散 , 迭代 18次仍未出现等照度线的交叉 , 而且填充有

18、序 , 保持了图像的边缘 . 5 模型的数值实现设 (i , j 表示像素点的位置 , 时间数字化为 n =0, 1, 2, , 选取的时间步长为 t , u n(i , j 表示修 补区域 D 内的每个像素的第 n 次修补 . 那么 , 模型中方程 (7 的离散化实现过程如下 :u n+1(i , j =u n (i , j + t u n (i , j u n (i , j , (i , j D u n (i, j = u n (i , j (i , j , n =u n x (i , j, u n y (i , j (i , j , n (i , j , n =-u n y (i , j

19、, u nx (i , j u n y (i , j +u nx (i , j u n (i , j =(u xbm +(u xfM +(u ybm +(u yfM (当 u n >0(u xb M +(u xfm +(u yb M +(u yfm (当 u n <0在数值计算中 , 先计算信息变化量 u 和等照度线方向 . 然后计算 u n , 即沿着方向 的改变量 . 最后 , 把 u n 乘以图像的梯度模的斜率限制形式 u n , 保证了中心差分格式的稳定性 , 同时提高了收敛速度 . 下 标 b 和 f 分别表示向后和向前差分 , 而下标 m 和 M 分别表示在导数和 0之

20、间取得最小值和最大值 .方程 (5 的离散化过程如下 :u n+1(i , j =u n (i , j + t u n 1(i , j, (i , j D其中 , u nt = u n k n = un u n u n =u n xx (u n y 2+u n yy (u n x 2-2u n x u n y u n xy (u n x 2+(u n y 2相应的对称边界条件 :u n -1,j =u n 0, j , u n I+1, j =u n I , j (j =0, 1, 2, , J u n i, -1=u n i , 0, u n i, J+1=u n i, J (i =0, 1

21、, 2, , I 6 实验结果及分析实验 1 采用不同的图像修补算法 , 对五角形、 四边形图像进行修补 (图 6. 从实验结果看 , BSCB 模 型、 TV 模型、 CDD 模型以及 EE 模型对角点的修补效果都不理想 , 可以看到在保持角点的处理上 , 改进后 的 BSCB-ASG 的修补效果较好 .图 6 五角形修补图 F i g . 6 C o m par ison o f i m p l em entation for pentagon实验 2 采用多种图像修补方法去除桌角上茶杯 (图 7. 其中图 7(a 是原始图像 , 大小为 128 128, 图 7(b 为 BSCB 迭代

22、5000次的结果 . 从实验结果看 , 在待填充区域比较大的时候 , BSCB 模型修补的效 果比较差 , 时间也比较长 . 图 7(d 和 (e 分别为 TV 、 EE 修补效果图 , 可以看到它们在修补过程中 , 不能 660第 5期 曾勋勋 , 等 :基于 BSCB 模型的图像修补算法 较好地保存图像的角点 . 图 7(f 为 BSCB -ASG 结果图 , 其修补效果比较理想 , 保持了图像的角点 .图 7 茶杯的去除F ig . 7 R e m ov al of a cup实验 3 旧照片的修补和图像中文字的去除 (图 8. 左边为一幅旧照片 , 存在大面积的污损 . 右边为 BSC

23、B-ASG 修补图 , 可以看到处理后的图像在保存了原有图像特征的基础上 , 显著减少了划痕 , 恢复了 照片的原貌 . 图 9是一幅风景图片 , 在图片左边存在一些广告文字 , 右边为 BSCB-ASG 修补图 , 经过处 理 , 较好地去除了图片上不需要的文字 .7 结语在 BSCB 模型上考虑了图像的梯度以及相应邻点的信息 , 使用 m ax /mi n 函数 , 有选择性地采用部分邻 点 , 运行适当的加权算法 , 提出 ASG 算子 , 并用 ASG 算子代替光滑算子的预处理 , 对 BSCB 模型进行改进 , 提出 BSCB -ASG 模型 . 实验证明 , 新模型对于修补区域较大

24、的图像 , 可以更好地保持图像的边缘和角点 . 参考文献 :1G u i cha rd F. A mo rpho l og ica, l affi ne and galilean i nvar i ant sca le-space fo r m ov i esJ.I EEE T rans I m ag e P rocess , 1998, 7(3:444-456.2K okaram A C , M o rris R D, F itzge ra l d W J , et al . Interpo lati on o f m i ssi ng data i n i m age sequencesJ.IEEE T rans I m ag e P rocess , 1995, 11(4:1509-1519.3Berta l m i o M, Sapiro G, C ase lles V, et al . I m age i npa i nti ngC/In P roceedings SI GGRA PH 2000. Com puter