基于BSCB模型的圖像修補(bǔ)算法

1、第 37卷 第 5期 2009年 10月福州大學(xué)學(xué)報(bào) (自然科學(xué)版 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文章編號(hào) :1000-2243(2009 05-0657-05基于 BSCB 模型的圖像修補(bǔ)算法曾勛勛 1, 陳 飛 2, 王美清 1(1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 , 福建 福州 350108; 2. 集 美大學(xué)理學(xué)院 , 福建 廈門(mén) 361021摘要 :在 BSCB 模型上考慮了圖像的梯度以及相應(yīng)鄰點(diǎn)的信息 , 引入 m ax /mi

2、n 函數(shù) , 提出用 ASG 算子代替光滑 算子 , 對(duì) BSCB 模型進(jìn)行修改 . 實(shí)驗(yàn)證明 , 新算法能較好地對(duì)圖像進(jìn)行 修補(bǔ) , 尤其是在保 持邊緣和角 點(diǎn)的特征 上效果比較好 .關(guān)鍵詞 :圖像修補(bǔ) ; 偏 微分方程 ; BSCB 模型中圖分類號(hào) :TP 391 文獻(xiàn)標(biāo)識(shí)碼 :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圖像修補(bǔ)是利用受損區(qū)域周?chē)膱D像信息給修補(bǔ)區(qū)域填充信息的一門(mén)技術(shù) , 作為圖像處理的一個(gè)分 支 , 已經(jīng)在國(guó)內(nèi)外受到廣泛的重視 . 圖像修補(bǔ)在數(shù)字圖像處理 , 視覺(jué)分析和電影工業(yè)中有許多重要的應(yīng) 用 1, 2, 如 :修補(bǔ)古老藝術(shù)品或舊照片的損壞區(qū)域、 自動(dòng)尋找并修復(fù)舊電影膠片中的劃痕、 去除圖片中的 說(shuō)明文字、 移走物體、 圖像放大等等 . 近年來(lái) , 從偏微分方程角度研究圖像修補(bǔ)已成為一種主要的方法 , 并取得了良好的效果 . Bertal m io 3, 4等人最早采用偏微分方程的方法進(jìn)行圖像修復(fù) , 他們利用三階 PDE 模 型 , 提出了 BSCB 模型 . C

6、han 等人提出了整體變分方法 (TV, To tal Variation 5, 6和基于曲率的擴(kuò)散模型 (CDD, Curvature D ri v en D iffusi o ns 7. 但是 , 以上這兩種方法都沒(méi)有考慮人類視覺(jué)的連接性原則 , 在修復(fù) 的圖像中可能產(chǎn)生人為的角點(diǎn) , Chan , Kang 和 Shen 8通過(guò)進(jìn)一步分析 CDD 模型 , 結(jié)合 BSCB 模型 , 提出 了歐拉彈性模型 (EE 模型 , 但該模型仍不能很好地保持圖像的邊緣與角點(diǎn) . 本文在 BSCB 模型基礎(chǔ)上 , 考慮到圖像的梯度以及相應(yīng)鄰點(diǎn)的信息 , 引入非線性函數(shù) , 提出用 ASG 算子代替光滑

7、算子 , 對(duì) BSCB 模型 進(jìn)行修改 .1 BSCB 模型Bertal m i o 3, 4等人根據(jù)藝術(shù)家實(shí)際的圖像修補(bǔ)方法建立了基于 PDE 的 BSCB 圖像修補(bǔ)模型 . 它的主要 思想是沿等照度線的方向?qū)⑿扪a(bǔ)區(qū)域周?chē)男畔⒌叫扪a(bǔ)區(qū)域內(nèi) , 產(chǎn)生修補(bǔ)信息 . 等照度線的方向可 以通過(guò)計(jì)算修補(bǔ)的輪廓線上的每一個(gè)點(diǎn)的離散梯度向量 (表示空間最大變化的方向 , 并將其旋轉(zhuǎn) 90 得 到 . 這樣可以在迭代的過(guò)程中 , 有效地保持邊界 . 每若干步迭代之后 , 算法進(jìn)行一個(gè)反復(fù)擴(kuò)散的過(guò)程 , 以 保持修補(bǔ)區(qū)域的平滑 . 各向異性的擴(kuò)散有利于保持穿過(guò)修補(bǔ)區(qū)域的邊界 .收稿日期 :2008-10

8、-7作者簡(jiǎn)介 :曾勛勛 (1981-, 女 , 助教 .基金項(xiàng)目 :國(guó)家自然科學(xué)基金資助項(xiàng)目 (10771036; 福建省高等學(xué)校新世紀(jì)優(yōu)秀人才支持計(jì)劃資助項(xiàng)目 (SX2006-40福州大學(xué)學(xué)報(bào) (自然科學(xué)版 第 37卷 BSCB 模型方程為 u / t = ( u u = u ( u , 其中 為等照度線方向 . 其主要思想 是沿著等照度線向待修補(bǔ)區(qū)域光滑地傳播信息 , 以達(dá)到修補(bǔ)圖像的目的 . 由于模型采用拉普拉斯算子作 為光滑算子 , 當(dāng)像素點(diǎn)進(jìn)行數(shù)值計(jì)算時(shí) , 會(huì)綜合考慮所有鄰點(diǎn) , 進(jìn)行同性擴(kuò)散 , 因此會(huì)造成圖像模糊 , 并 且容易產(chǎn)生等照度線的交叉 . 基于以上分析 , 提出 A

9、SG 算子 (Approx i m ation o f Sm ooth i n g and Gradien, t 簡(jiǎn) 稱 ASG, 使用 m ax /mi n 函數(shù) , 有選擇性地采用部分鄰點(diǎn) , 并運(yùn)行適當(dāng)?shù)募訖?quán)算法 , 對(duì)于修補(bǔ)區(qū)域較大的 圖像 , 可以更好地保持圖像的邊緣和角點(diǎn) . 2 S G 算子在計(jì)算圖像的梯度算子 u =(u x , u y 時(shí) , 通常采用的差分格式為 u x =12h (u i+1, j -u i-1, j , u y =12h(u i, j-1-u i, j+1, 其中 h 為步長(zhǎng) . u x 、 u y 通過(guò)如圖 1模板來(lái)表示 . 在 BSCB 模型中 ,

10、u / t = ( u u = u ( u , 式子右邊的中間因子是對(duì)拉普拉斯算子的運(yùn)算結(jié)果進(jìn)行梯度運(yùn)算 . 因此 , 先提出一種算子 SG (Sm oo thing and Grad ien, t 簡(jiǎn)稱 SG, 用來(lái)簡(jiǎn)化表 示平滑算子和梯度運(yùn)算的結(jié)合 , 可以更好引入后面的 ASG 算子 . SG 算子 u =(x , y , 其中 x , y 的 定義見(jiàn)圖 2. 當(dāng)參數(shù) =1, =1, =-4時(shí) , 相當(dāng)于先做拉普拉斯算子處理 , 然后進(jìn)行梯度場(chǎng)的計(jì)算 . 3 BSCB-AS G 模型在 BSCB 模型中引入 SG 算子 , 用 u 作為信息變化量代替 ( u , 模型如下 :u t =

11、u u(1圖 3 水平梯度的計(jì)算 F i g. 3 Co m puta ti on in the horizonta l d irection 該算法簡(jiǎn)單 , 易于數(shù)值實(shí)現(xiàn) , 但是該模型參數(shù)比較多 , 選擇比較復(fù)雜 . 在進(jìn)行圖像修補(bǔ)時(shí) , 會(huì)造成邊緣的模糊、 對(duì) 角點(diǎn)的處理特別差 . 為此 , 提出近似 SG 算子的 ASG 算子(Approxi m ation of S m oothing and Grad i e nt, u =(u x ,uy . 該算子有選擇性地采用部分鄰點(diǎn) , 而不是 SG 中的 采用全部鄰點(diǎn) , 從而反映了該點(diǎn)灰度值的局部情況 . 最易想到的方法是對(duì)點(diǎn) u ij

12、 以及它的所有鄰點(diǎn)進(jìn)行排序 , 選取中間的若干個(gè)點(diǎn)來(lái)反映該點(diǎn)的局部灰度值分布情況 .比如評(píng)委對(duì)選手進(jìn)行打分時(shí) , 去掉最高分和最低分 . 但是這種方法 , 需預(yù)先對(duì)這些點(diǎn)進(jìn)行排序 , 計(jì)算復(fù)雜度高 ,而且仍屬于加權(quán)平均算法 , 會(huì)對(duì)邊緣造成一定的模糊 .采用 m ax /mi n 函數(shù) , 如圖 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 模型的圖像修補(bǔ)算法 的均值 . 同理可得 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 該算法沿等照度線方向 進(jìn)行延擴(kuò) , 延擴(kuò)大小為 u .方程進(jìn)行多次迭代 , 等照度線上的像素越來(lái)越平滑 , 當(dāng)發(fā)展方程接近平衡態(tài)時(shí) , 模型就完成了傳播 , 這時(shí)有 u 0, 從而達(dá)到 填充的目的 . 前面因子 u 可以提高數(shù)值的收斂性 .另外 , 采用下列模型 :u t =k u =u(5 來(lái)控制等照度線的移動(dòng)方向 , 其中 k 是等照度線的曲率 , u 為沿方向的二階偏導(dǎo)數(shù) . 可以讓等照度線沿 梯度反方向移動(dòng) , 以保證等照度線不會(huì)出現(xiàn)交叉現(xiàn)象 , 同時(shí)光

15、滑方向?yàn)閳D像邊緣的切線方向 , 保留了圖像 的邊緣 .改進(jìn)后的模型稱為 BSCB -ASG 模型 . 方程 (4 與 (5 交替進(jìn)行 , 可以解釋為 :方程 (4 是沿等照度線 方向的平滑 ; 方程 (5 可以看成是等照度線方向的控制 , 避免等照度線的交叉 .令u = u =(u x , u y (-u y , u x x +u y (6則方程 (4 可改寫(xiě)為 :u t = u u (7 4 模型分析由于 BSCB -ASG 算子使用 m ax /min 方法 , 有選擇性地采用部分鄰點(diǎn) , 并運(yùn)行適當(dāng)?shù)募訖?quán)算法 , 因此在 圖像修補(bǔ)的時(shí)候可以保持圖像的邊緣和角點(diǎn) ; 而采用與異性擴(kuò)散算法交

16、叉進(jìn)行 , 可以加強(qiáng)沿等照度線的擴(kuò)散 并避免等照度線的交叉 , 從而達(dá)到理想的修補(bǔ)效果 . 下面對(duì)一幅大小為 9 9像素的單色圖像進(jìn)行分析 (如圖4, 方框內(nèi)的數(shù)字為圖像的灰度值 , 白色表示像素值為 1的區(qū)域 , 黑色表示像素值為 0的區(qū)域 . 圖 5是帶有 填充區(qū)域的單色圖 , 淺灰色像素區(qū)域大小 3 5為圖像待修補(bǔ)區(qū)域 , 白色和黑色區(qū)域?yàn)榇扪a(bǔ)區(qū)域的外鄰域 , 其中 a, b , c , d 為修補(bǔ)區(qū)域內(nèi)的 4個(gè)點(diǎn)的像素值. 顯然對(duì)于圖 5來(lái)說(shuō) , 邊緣線遭到破壞 .為了方便比較 , 計(jì)算出 BSCB 模型方程和 BSCB -ASG 模型方程在圖像待修補(bǔ)區(qū)域上的修補(bǔ)結(jié)果 . 假 設(shè)待修

17、補(bǔ)區(qū)域初始填充值為 0. 計(jì)算的順序采用的是從左至右 , 從上到下 . 由于原有 BSCB 模型方程采用 拉普拉斯算子作為光滑算子 , 在像素點(diǎn)進(jìn)行數(shù)值計(jì)算時(shí) , 會(huì)綜合考慮所有鄰點(diǎn) , 進(jìn)行同性擴(kuò)散 , 因此會(huì)造 成圖像模糊 , 并且容易產(chǎn)生等照度線的交叉 . 迭代 1次 , 可以得到同性擴(kuò)散使得像素點(diǎn) a 影響到像素點(diǎn) b 、 c d , .659 福州大學(xué)學(xué)報(bào) (自然科學(xué)版 第 37卷 BSCB -ASG 算法在圖像填充過(guò)程中 , 可以更好地保持圖像邊緣 . 首次迭代 , 在像素點(diǎn) b 的位置 , 就有效地 阻止了像素點(diǎn) a 的擴(kuò)散 , 迭代 18次仍未出現(xiàn)等照度線的交叉 , 而且填充有

18、序 , 保持了圖像的邊緣 . 5 模型的數(shù)值實(shí)現(xiàn)設(shè) (i , j 表示像素點(diǎn)的位置 , 時(shí)間數(shù)字化為 n =0, 1, 2, , 選取的時(shí)間步長(zhǎng)為 t , u n(i , j 表示修 補(bǔ)區(qū)域 D 內(nèi)的每個(gè)像素的第 n 次修補(bǔ) . 那么 , 模型中方程 (7 的離散化實(shí)現(xiàn)過(guò)程如下 :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 (當(dāng) u n >0(u xb M +(u xfm +(u yb M +(u yfm (當(dāng) u n <0在數(shù)值計(jì)算中 , 先計(jì)算信息變化量 u 和等照度線方向 . 然后計(jì)算 u n , 即沿著方向 的改變量 . 最后 , 把 u n 乘以圖像的梯度模的斜率限制形式 u n , 保證了中心差分格式的穩(wěn)定性 , 同時(shí)提高了收斂速度 . 下 標(biāo) b 和 f 分別表示向后和向前差分 , 而下標(biāo) m 和 M 分別表示在導(dǎo)數(shù)和 0之

20、間取得最小值和最大值 .方程 (5 的離散化過(guò)程如下 :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相應(yīng)的對(duì)稱邊界條件 :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 實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn) 1 采用不同的圖像修補(bǔ)算法 , 對(duì)五角形、 四邊形圖像進(jìn)行修補(bǔ) (圖 6. 從實(shí)驗(yàn)結(jié)果看 , BSCB 模 型、 TV 模型、 CDD 模型以及 EE 模型對(duì)角點(diǎn)的修補(bǔ)效果都不理想 , 可以看到在保持角點(diǎn)的處理上 , 改進(jìn)后 的 BSCB-ASG 的修補(bǔ)效果較好 .圖 6 五角形修補(bǔ)圖 F i g . 6 C o m par ison o f i m p l em entation for pentagon實(shí)驗(yàn) 2 采用多種圖像修補(bǔ)方法去除桌角上茶杯 (圖 7. 其中圖 7(a 是原始圖像 , 大小為 128 128, 圖 7(b 為 BSCB 迭代

22、5000次的結(jié)果 . 從實(shí)驗(yàn)結(jié)果看 , 在待填充區(qū)域比較大的時(shí)候 , BSCB 模型修補(bǔ)的效 果比較差 , 時(shí)間也比較長(zhǎng) . 圖 7(d 和 (e 分別為 TV 、 EE 修補(bǔ)效果圖 , 可以看到它們?cè)谛扪a(bǔ)過(guò)程中 , 不能 660第 5期 曾勛勛 , 等 :基于 BSCB 模型的圖像修補(bǔ)算法 較好地保存圖像的角點(diǎn) . 圖 7(f 為 BSCB -ASG 結(jié)果圖 , 其修補(bǔ)效果比較理想 , 保持了圖像的角點(diǎn) .圖 7 茶杯的去除F ig . 7 R e m ov al of a cup實(shí)驗(yàn) 3 舊照片的修補(bǔ)和圖像中文字的去除 (圖 8. 左邊為一幅舊照片 , 存在大面積的污損 . 右邊為 BSC

23、B-ASG 修補(bǔ)圖 , 可以看到處理后的圖像在保存了原有圖像特征的基礎(chǔ)上 , 顯著減少了劃痕 , 恢復(fù)了 照片的原貌 . 圖 9是一幅風(fēng)景圖片 , 在圖片左邊存在一些廣告文字 , 右邊為 BSCB-ASG 修補(bǔ)圖 , 經(jīng)過(guò)處 理 , 較好地去除了圖片上不需要的文字 .7 結(jié)語(yǔ)在 BSCB 模型上考慮了圖像的梯度以及相應(yīng)鄰點(diǎn)的信息 , 使用 m ax /mi n 函數(shù) , 有選擇性地采用部分鄰 點(diǎn) , 運(yùn)行適當(dāng)?shù)募訖?quán)算法 , 提出 ASG 算子 , 并用 ASG 算子代替光滑算子的預(yù)處理 , 對(duì) BSCB 模型進(jìn)行改進(jìn) , 提出 BSCB -ASG 模型 . 實(shí)驗(yàn)證明 , 新模型對(duì)于修補(bǔ)區(qū)域較大

24、的圖像 , 可以更好地保持圖像的邊緣和角點(diǎn) . 參考文獻(xiàn) :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