代妮娜，蔡 黎，戴閩魯，2

（1.重慶三峽學(xué)院 信息與信號處理重點實驗室，重慶 404000；2.數(shù)字電視國家工程實驗室（北京），北京 101000）

一種改進(jìn)的BSCB圖像修補(bǔ)算法

代妮娜1，蔡 黎1，戴閩魯1，2

（1.重慶三峽學(xué)院 信息與信號處理重點實驗室，重慶 404000；2.數(shù)字電視國家工程實驗室（北京），北京 101000）

針對傳統(tǒng)BSCB算法對顏色復(fù)雜度高或缺損區(qū)域較大的圖像修補(bǔ)效果較差的問題，提出一種改進(jìn)的BSCB圖像修補(bǔ)算法?？紤]傳統(tǒng)算法中初始化、光滑算子和修補(bǔ)擴(kuò)散等步驟中存在的缺陷，分別對其進(jìn)行了改進(jìn)。改進(jìn)的BSCB算法進(jìn)行圖像修補(bǔ)時，采用隨機(jī)初始化方法，引入平滑和梯度算子代替原拉普拉斯圖像平滑算子，并采用加權(quán)平均算法選擇所有鄰點進(jìn)行異向性擴(kuò)散，從而得到最終修補(bǔ)結(jié)果。實驗表明，新方法修補(bǔ)圖像，特別是修補(bǔ)顏色復(fù)雜度高、缺損區(qū)域較大的圖像具有較好的效果。

圖像修補(bǔ)；BSCB；隨機(jī)初始化；平滑和梯度算子；峰值信噪比

對于多種因素導(dǎo)致的數(shù)字圖像缺損，需要應(yīng)用圖像修補(bǔ)技術(shù)對其進(jìn)行處理，以去除缺損信息還原原始圖像。圖像修補(bǔ)技術(shù)的基本原理為通過一定的算法，提取缺損圖像中缺損區(qū)域的近似信息去填充缺損區(qū)域，最終使圖片觀察受體從感官上無法覺察該圖像曾經(jīng)受損。圖像修補(bǔ)技術(shù)在計算機(jī)視覺、空間測量與攝像、醫(yī)療或特種行業(yè)圖像匹配、藝術(shù)品處理與修復(fù)等領(lǐng)域都有廣泛的應(yīng)用。

目前較成熟的數(shù)字圖像修補(bǔ)算法是由美國明尼蘇達(dá)大學(xué)Bertalmio、Sapiro和龐培法布拉大學(xué)Caselles、Belleste四位學(xué)者受到藝術(shù)工作者修補(bǔ)藝術(shù)作品方法的啟示，在2000年的美國計算機(jī)協(xié)會計算機(jī)圖形專業(yè)組會議首次提出[1]，并用他們名字首字母命名的BSCB算法。BSCB算法引入偏微分方程（Partial Differential Equation，PDE）概念，對缺損圖像建立BSCB模型，而后提取待修補(bǔ)區(qū)域的邊緣信息，同時采用一種由粗到精的方法來估計等照度線方向[2]，最后用傳播機(jī)制將提取的信息擴(kuò)散到缺損區(qū)域，以得到較好的修補(bǔ)效果。

現(xiàn)有文獻(xiàn)表明，傳統(tǒng)BSCB算法對缺損區(qū)域較小，缺損圖片顏色較單一的受損圖像有較好的修補(bǔ)效果[2]，但是對顏色復(fù)雜，受損區(qū)域較大的圖像卻得不到好的修補(bǔ)效果，結(jié)果往往容易產(chǎn)生高斯模糊效應(yīng)等不良表現(xiàn)。文獻(xiàn)[3]提出了一種傳統(tǒng)的BSCB算法，本文在文獻(xiàn)[3]的基礎(chǔ)上，展開進(jìn)一步工作，對常規(guī)BSCB算法進(jìn)行改進(jìn)，以進(jìn)一步提高BSCB修補(bǔ)算法的性能。

1 傳統(tǒng)BSCB模型算法

傳統(tǒng)BSCB算法的思路如下：首先用全變分量最小化法提取圖像結(jié)構(gòu)建模成矩陣，然后選擇特定函數(shù)對缺損區(qū)域部分建模，從而將圖像分解成原始信息和缺損信息兩個部分，再用BSCB模型來修補(bǔ)缺損部分，用特定的算法來填充紋理部分，最后疊加修補(bǔ)和填充結(jié)果，得到最終修補(bǔ)圖像。其本質(zhì)是一個沿等照度線驅(qū)動圖像采樣過程，工作流程如圖1所示。

圖1 傳統(tǒng)BSCB修補(bǔ)算法流程

1）修補(bǔ)區(qū)域識別與判定。讀取圖片，初始化后識別判定顏色偏差，從而識別出修補(bǔ)區(qū)域，模型如圖2所示。

圖2 區(qū)域識別圖

圖2中，Ω是待修補(bǔ)區(qū)域，Ω0是原始的待修補(bǔ)圖像，?Ω是圖像邊界。

2）擴(kuò)散方向及等照線。所有點的灰度值都相等或者是近似相等所組成的一條線叫做等照線[4]。修補(bǔ)圖像的過程就是從待修補(bǔ)區(qū)域的邊界?Ω向待修補(bǔ)區(qū)域Ω擴(kuò)散的過程，擴(kuò)散依據(jù)就是等照線。如圖2，其中N為擴(kuò)散的方向，N與邊界?Ω是一致的，圖2中橢圓框內(nèi)區(qū)域的N如箭頭所指，這樣可以取得較好的擴(kuò)散效果。

其中，原始的圖像為 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，即認(rèn)為圖像信息已經(jīng)穩(wěn)定。

傳統(tǒng)算法中采用拉普拉斯因子作為圖像平滑算子Ln(i,j)，表達(dá)式為

2 改進(jìn)后的BSBC模型算法

2.1 改進(jìn)初始化判定環(huán)節(jié)

傳統(tǒng)BSCB算法對缺損圖像采用純色初始化算法，即把待修補(bǔ)的區(qū)域初始化為同一種顏色（一般為白色），此種方法非常容易實現(xiàn)，但人為指定的單一顏色可能和待修補(bǔ)的缺損區(qū)域顏色差別較大，導(dǎo)致原圖像信息不能得以保存，所以對于圖像顏色復(fù)雜或缺損區(qū)域較大的圖像最終修補(bǔ)效果不佳。

改進(jìn)純色初始化為隨即初始化，具體的步驟如下：在帶修補(bǔ)區(qū)域中任取一目標(biāo)點O，以O(shè)為中心，沿橫、縱方向?qū)ふ业脚c該點距離最近的非污損區(qū)域的4個交點，如圖3記為k1，k2，k3，k4。

圖3 平均值初始化坐標(biāo)圖

計算X，Y方向上2個點的間距ΔkC= ||k2-k1，ΔkL= ||k4-k3。若ΔkC＞ΔkL，說明Y方向邊緣距離O點近，縱向相關(guān)性大，則參考Y方向上的2個邊緣點k3和k4，選取它們灰度值的平均值間給O點賦初始值，反之亦然。

2.2 改進(jìn)光滑算子的選擇

現(xiàn)有文獻(xiàn)一般采用拉普拉斯算子作為修復(fù)的光滑算子，優(yōu)點是計算速度快，對顏色相鄰域缺損修補(bǔ)效果好，但因為其考慮部分鄰點進(jìn)行同性擴(kuò)散，對于某些顏色復(fù)雜度高的缺損，修補(bǔ)后的圖像會變得很模糊，需要對光滑算子進(jìn)行重新選擇。

已有文獻(xiàn)引入平滑和梯度（Smoothing and Gradient，SG）算子替代拉普拉斯算子[6]，SG是平滑度和梯度的結(jié)合，傳統(tǒng)BSCB算法的平滑拉普拉斯算子只是SG算子參數(shù)為某值時的特例。SG算子參數(shù)較多且難以確定，運(yùn)算復(fù)雜導(dǎo)致修補(bǔ)時間表現(xiàn)不佳[7]，若參數(shù)確定不佳反而降低其性能表現(xiàn)，因此諸多文獻(xiàn)對其做了近似處理，文獻(xiàn)[8]提出一種平滑和梯度近似（Approximation of Smoothing and Gradient，ASG）算子來替代SG算子。但是引入ASG算子是以犧牲修復(fù)效果為代價的，ASG算子沒有改變將圖像做各向同性擴(kuò)散的本質(zhì)，所以仍然可能導(dǎo)致修復(fù)圖像紋理變模糊[9]。為避免上述缺陷，文獻(xiàn)[8]在引入ASG算子后對自變量采用Max/Min函數(shù)做選擇，本文用加權(quán)平均函數(shù)做選擇，具體算法如下：

式中：mavg為去掉3個數(shù)中最小值求平均；Mavg為去掉3個數(shù)中最大值求平均。

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

式中：ζ是等照線的方向向量，當(dāng)ut→0時，可達(dá)到擴(kuò)散的目的[10]。

另外，采用式（7）模型來確定等照線的移動軌跡

式中：k是等照線曲率，uζζ是沿著方向的二階偏導(dǎo)數(shù)，式（7）可以保證等照線不會交叉[11]，沿受損圖像邊緣的切線的進(jìn)行光滑擴(kuò)散，最大限度地保留圖像邊緣。

2.3 改進(jìn)修補(bǔ)擴(kuò)散算法

擴(kuò)散是修補(bǔ)的重要步驟，核心區(qū)域選取是擴(kuò)散的基礎(chǔ)，反復(fù)迭代是擴(kuò)散的核心[12]。為了保證擴(kuò)散修復(fù)的過程正確的演化，本文改善核心區(qū)域的選取，優(yōu)化迭代次數(shù)，進(jìn)一步降低噪聲，以獲得更好的修補(bǔ)區(qū)域邊緣銳利性。

如圖4，首先定義區(qū)域直徑：在一個區(qū)域中選擇兩點，使得兩點之間的距離d最大，定義d為此區(qū)域直徑。顯而易見，Ωε就是Ω經(jīng)過擴(kuò)散而來，其中圓的直徑選的即為待修補(bǔ)區(qū)域Ω的直徑，圓心為區(qū)域直徑中心點。

圖4 擴(kuò)散示意圖

采用第1節(jié)中圖2的方向進(jìn)行等照線異向性擴(kuò)散，算法方程為

κ(i,j)表示的是等照線在點(i,j)的曲率[12]，至此，核心區(qū)域選擇完成。

改善后的迭代算式為

式中：In(i,j)是I(i,j,n)的簡寫形式，表示的是第n步所得到的結(jié)果，(i,j)表示的是像素坐標(biāo)，Int(i,j)表示的是對In(i,j)的修正，Δt表示的是迭代的步長，公式的作用域在Ω里面。隨著n的增大[5]，圖像修補(bǔ)的效果越來越明顯，當(dāng)n增加到一定的時候，這里的In(i,j)將不會有太大的變化，此時如果繼續(xù)迭代，修補(bǔ)效果不會增強(qiáng)甚至可能變差，同時極大地延長了修復(fù)時間，所以選擇滿足式（11）的制約條件時迭代停止：

3 實驗結(jié)果

在MATLAB7.0（R14）平臺編輯M文件實現(xiàn)上述算法，選擇分辨率為600×450的兩張位圖（Bitmap，BMP）圖像作為實驗對象。一張為輕微缺損的顏色較單一圖像即圖5b所示的受損圖像，一張為非輕微缺損的顏色較復(fù)雜圖像即圖6b所示的受損圖像，分別用傳統(tǒng)BSCB和改進(jìn)的BSCB算法對其進(jìn)行修補(bǔ)。

圖5 實驗結(jié)果1

圖6 實驗結(jié)果2

圖像修補(bǔ)結(jié)果評價包含主觀評價和客觀評價兩部分[3]。

首先進(jìn)行人眼主觀評價，因為人眼始終是圖像最后的信息判斷受體，所以主觀評價更為重要，若人眼不能判斷出圖像是原始圖像還是修復(fù)后的圖像，則說明此圖像修復(fù)效果為優(yōu)。

觀察圖5所示的實驗結(jié)果1，可見對于顏色復(fù)雜度較低的輕微缺損圖像，傳統(tǒng)和改進(jìn)的BSCB模型算法均有較好的表現(xiàn)，在保持原有分辨率未進(jìn)行放大的情況下，人眼幾乎不能判斷出修補(bǔ)效果的優(yōu)劣，放大以后，能觀察到修補(bǔ)區(qū)域有細(xì)微的模糊表現(xiàn)。

觀察圖6所示的實驗結(jié)果2，對于顏色復(fù)雜度較高的非輕微缺損圖像，傳統(tǒng)BSCB修補(bǔ)算法品質(zhì)惡化嚴(yán)重，拉普拉斯算子考慮了所有的鄰點進(jìn)行同性擴(kuò)散，造成了修補(bǔ)區(qū)域和相鄰區(qū)域的大面積色塊模糊，同時純色初始化導(dǎo)致豐富的顏色信息丟失，修補(bǔ)效果不令人滿意。而改進(jìn)的BSCB算法在隨機(jī)初始化時充分保留了缺損周圍區(qū)域的顏色信息，使得待修補(bǔ)區(qū)域在開始的時候就保留一定的信息特征[13]，引入ASG算子后加權(quán)平均周圍所有點的圖像信息進(jìn)行異向性擴(kuò)散，使修補(bǔ)區(qū)域邊緣銳利性更平滑，表現(xiàn)出較好的修補(bǔ)效果。

客觀評價選用兩個指標(biāo)：峰值信噪比（PeakSignal Noise Ratio，PSNR）測度和修補(bǔ)時間t[13]，PSNR的計算公式為

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

實驗結(jié)果1和實驗結(jié)果2的PSNR評價分別見表1和表2。

表1 實驗結(jié)果1的PSNR評價

表2 實驗結(jié)果2的PSNR評價

測試平臺硬件為Intel i3-2120CPU、4 Gbyte RAM、NVID?IA GeForce 405顯示卡、512 Gbyte顯示內(nèi)存、ST3500413硬盤、容量300 Gbyte，軟件平臺為WindowsXP SP2（5.1.2600）、MATLAB7.0。在該平臺運(yùn)行具修補(bǔ)時間觀測功能的M文件處理上述圖像，得到結(jié)果如表3所示。

表3 實驗結(jié)果1、2的修補(bǔ)時間對比

表1、表2表明改進(jìn)的BSCB算法修補(bǔ)結(jié)果PSNR值更大，更忠于原始圖像，修補(bǔ)效果更好。表3表明對于顏色復(fù)雜度較低的輕微缺損圖像修補(bǔ)時間t，兩種算法相差無異，對于顏色復(fù)雜度較高的非輕微缺損圖像修補(bǔ)時間t，改進(jìn)后的BSCB算法時間增加約10%，但是相對于修補(bǔ)品質(zhì)的優(yōu)化，這個時間增加是可以接受的。

4 結(jié)語

在傳統(tǒng)BSCB圖像修補(bǔ)算法的基礎(chǔ)上，本文提出了一種改進(jìn)的BSCB圖像修補(bǔ)算法。與傳統(tǒng)算法相比，本文的方法對于顏色復(fù)雜度高、缺損區(qū)域較大的圖像修補(bǔ)效果更好。若對相關(guān)子算法的運(yùn)算策略做進(jìn)一步優(yōu)化，如引入快速矩陣算法、多分辨率匹配等，能更好地降低算法的復(fù)雜度，縮短修補(bǔ)時間，增強(qiáng)圖像修補(bǔ)效果。今后將重點研究快速矩陣運(yùn)算策略，進(jìn)而與該匹配方法結(jié)合，在保持圖像修補(bǔ)效果的同時縮短修補(bǔ)時間。

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

[2] 張紅英，彭啟琮.數(shù)字圖像修復(fù)技術(shù)綜述[J].中國圖象圖形學(xué)報，2007，12（1）：1-8.

[3]盧小寶，王維蘭.基于樣本塊的破損唐卡圖像修復(fù)算法的改進(jìn)[J].計算機(jī)應(yīng)用，2010，30（4）：943-946.

[4]胡時琳.自適應(yīng)圖像修復(fù)算法研究[D].重慶：重慶大學(xué)，2012.

[5] 謝愛敏.BSCB圖像修補(bǔ)方法介紹[EB/OL].[2014-03-20].http:// www.pudn.com/downloads333/sourcecode/math/detail1460973.ht?ml.

[6]吳東亞.數(shù)字圖像修復(fù)技術(shù)[M].北京：科學(xué)出版社，2010.

[7] 曾勛勛，陳飛.基于BSCB模型的圖像修補(bǔ)算法[J].福州大學(xué)學(xué)報：自然科學(xué)版，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] 張靜，余燁，葉強(qiáng)強(qiáng)，等.一種改進(jìn)的BSCB修復(fù)模型[J].系統(tǒng)仿真學(xué)報，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]田素云，王小明，趙雪青，等.基于拉普拉斯算子和圖像修補(bǔ)的圖像去噪算法[J].計算機(jī)應(yīng)用，2012，32（10）：2793-2797.

[13] 紀(jì)利娥，楊風(fēng)暴，王志社，等.圖像配準(zhǔn)中特征點檢測算法的探討[J].電視技術(shù)，2013，37（19）：27-31.

代妮娜（1983—），講師，主研數(shù)字信號處理；

蔡 黎（1981—），講師，主研通信與控制技術(shù)；

戴閩魯（1958—），教授，主研數(shù)字電視技術(shù)。

責(zé)任編輯：閆雯雯

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

重慶市教育科學(xué)技術(shù)研究資助項目（KJ121114）；重慶三峽學(xué)院信息與信號處理重點實驗室開放基金項目（SXXY201218）

【本文獻(xiàn)信息】代妮娜，蔡黎，戴閩魯.一種改進(jìn)的BSCB圖像修補(bǔ)算法[J].電視技術(shù)，2015，39（2）.