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

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

一種改進的BSCB圖像修補算法

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

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

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

圖像修補；BSCB；隨機初始化；平滑和梯度算子；峰值信噪比

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

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

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

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

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

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

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

圖2 區(qū)域識別圖

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

2）擴散方向及等照線。所有點的灰度值都相等或者是近似相等所組成的一條線叫做等照線[4]。修補圖像的過程就是從待修補區(qū)域的邊界?Ω向待修補區(qū)域Ω擴散的過程，擴散依據(jù)就是等照線。如圖2，其中N為擴散的方向，N與邊界?Ω是一致的，圖2中橢圓框內區(qū)域的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，即認為圖像信息已經穩(wěn)定。

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

2 改進后的BSBC模型算法

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

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

改進純色初始化為隨即初始化，具體的步驟如下：在帶修補區(qū)域中任取一目標點O，以O為中心，沿橫、縱方向尋找到與該點距離最近的非污損區(qū)域的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 改進光滑算子的選擇

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

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

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

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

式中：ζ是等照線的方向向量，當ut→0時，可達到擴散的目的[10]。

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

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

2.3 改進修補擴散算法

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

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

圖4 擴散示意圖

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

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

改善后的迭代算式為

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

3 實驗結果

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

圖5 實驗結果1

圖6 實驗結果2

圖像修補結果評價包含主觀評價和客觀評價兩部分[3]。

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

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

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

客觀評價選用兩個指標：峰值信噪比（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%，但是相對于修補品質的優(yōu)化，這個時間增加是可以接受的。

4 結語

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

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

[2] 張紅英，彭啟琮.數(shù)字圖像修復技術綜述[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]吳東亞.數(shù)字圖像修復技術[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].系統(tǒng)仿真學報，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—），講師，主研數(shù)字信號處理；

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

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

責任編輯：閆雯雯

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）.