一種基于分水嶺分割的快速圖像修復(fù)算法

屠 昕，鈕圣虓，陳更生，許 薇

(復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室，上海 201203)

一種基于分水嶺分割的快速圖像修復(fù)算法

屠 昕，鈕圣虓，陳更生，許 薇

(復(fù)旦大學(xué) 專用集成電路與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室，上海 201203)

為快速準(zhǔn)確地對破損圖像進(jìn)行修復(fù)，提高傳統(tǒng)算法的修復(fù)質(zhì)量和速度，本文提出了一種改進(jìn)的基于分水嶺分割的快速圖像修復(fù)算法．首先針對傳統(tǒng)算法在修復(fù)速度上的不足，采用改進(jìn)的匹配區(qū)域搜索方法以縮小搜索區(qū)域，然后通過分水嶺分割結(jié)果篩選匹配塊以進(jìn)一步加速圖像修復(fù)，最后利用分水嶺分割結(jié)果提出了新的分類修復(fù)方法來改進(jìn)圖像修復(fù)質(zhì)量．實(shí)驗(yàn)結(jié)果表明，相較于現(xiàn)有算法，本文提出的算法在修復(fù)質(zhì)量上有明顯的改進(jìn)，并且修復(fù)速度平均提升了40%左右．

圖像修復(fù)； 匹配區(qū)域縮??； 分水嶺分割； 分類比較

圖像修復(fù)，是在保證圖像的質(zhì)量和自然效果不受破壞的前提下，利用圖像中未損壞的信息對圖像中遺失信息進(jìn)行修補(bǔ)或者對圖像中特定的信息進(jìn)行移除的圖像處理技術(shù)，在圖像輪廓修復(fù)、氣象云圖處理、物聯(lián)網(wǎng)等許多領(lǐng)域都有廣泛的應(yīng)用．

圖像修復(fù)技術(shù)主要分為兩類．一類是基于Bertalmio等[1]提出的基于偏微分方程的方法，通過對破損區(qū)域的邊界進(jìn)行不同方向的擴(kuò)散來對圖像進(jìn)行修復(fù)．在其基礎(chǔ)上，Chan等[2]提出基于全變分的修復(fù)方法，改進(jìn)了對有噪聲圖像的修復(fù)．該類算法的缺點(diǎn)是運(yùn)算量大，不適合修復(fù)大面積的破損．另一類方法是最早由Efros[3]提出的基于紋理合成的圖像修復(fù)方法，通過對紋理的適當(dāng)采樣來對破損區(qū)域進(jìn)行填補(bǔ)，適合大區(qū)域的圖像修補(bǔ)．紋理合成的方法容易導(dǎo)致修復(fù)后的圖像結(jié)構(gòu)信息出現(xiàn)斷裂．

Criminisi[4]在紋理合成的基礎(chǔ)之上結(jié)合邊界擴(kuò)散算法的優(yōu)點(diǎn)提出了基于樣本塊的圖像修復(fù)算法，利用破損區(qū)域的邊界信息確定修復(fù)優(yōu)先級，在圖像未破損的已知區(qū)域(源區(qū)域)中尋找與待修復(fù)區(qū)域的紋理信息最為接近的樣本塊來填充破損區(qū)域(目標(biāo)區(qū)域)，獲得了較好的圖像修復(fù)質(zhì)量．在Criminisi算法的基礎(chǔ)上，Wen等[5]通過優(yōu)化修復(fù)塊的優(yōu)先級計(jì)算公式在修復(fù)結(jié)構(gòu)信息時(shí)取得了更好的效果，但并沒有對修復(fù)速度做出改進(jìn)；劉奎等[6]提出了一種利用結(jié)構(gòu)張量來決定目標(biāo)區(qū)域修復(fù)順序的改進(jìn)算法，但是同樣沒有對修復(fù)速度做出優(yōu)化．Masnou[7]通過對圖像中的等照度線進(jìn)行匹配和連接來改進(jìn)Criminisi算法中修復(fù)結(jié)構(gòu)信息時(shí)產(chǎn)生的誤差．Frederic等[8]在Masnou算法的基礎(chǔ)上通過使用歐拉曲線替代直線來修復(fù)圖像的等照度線，使得修復(fù)效果更加自然．基于等照度線的改進(jìn)算法缺點(diǎn)在于增加了修復(fù)時(shí)間，而且難以保證等照度線斷點(diǎn)的正確匹配．

在提升修復(fù)速度方面，Hui等[9]則通過預(yù)先對源區(qū)域中的樣本塊進(jìn)行分類來加快匹配速度．王昊京等[10]通過放縮圖像的方法顯著地提升了Criminisi算法的修復(fù)速度，但是修復(fù)質(zhì)量也隨著縮放倍數(shù)的提升出現(xiàn)了明顯的下降．而Anupam等[11]針對Criminisi算法在修復(fù)質(zhì)量和時(shí)間上同時(shí)進(jìn)行了改進(jìn)，相較于前述的幾種算法取得了更為理想的處理效果，但仍然在修復(fù)時(shí)間、修復(fù)效果等方面存在不足．

針對目前圖像修復(fù)算法存在的各種不足之處，本文首先改進(jìn)了Anupam算法中的匹配區(qū)域搜索算法以減少每次填充過程中的匹配次數(shù)，并利用分水嶺分割的結(jié)果對匹配塊進(jìn)行篩選，通過減少需要比較的匹配塊數(shù)量來對算法進(jìn)行加速；同時(shí)基于分水嶺算法的分類匹配結(jié)果，提出了一種改進(jìn)的分類修復(fù)算法，針對不同類型的待填充塊采取不同的填充策略，以提高圖像修復(fù)的質(zhì)量．實(shí)驗(yàn)結(jié)果表明，相比上述各類已有的算法，本文算法不僅能夠快速有效地修復(fù)大面積破損區(qū)域，圖像修復(fù)的質(zhì)量更高，修復(fù)效果也更加自然．

1 基于樣本塊的圖像修復(fù)算法

1.1Criminisi算法

圖1 Criminisi算法修復(fù)過程示意圖Fig.1 Diagram of the inpainting process of Criminisi algorithm

Criminisi算法的主要思想是在確定了破損區(qū)域后，通過匹配最接近的樣本塊來對圖像的破損區(qū)域進(jìn)行修復(fù)．如圖1所示，Ω為待修復(fù)的破損區(qū)域，φ為未破損的源區(qū)域，I為整幅圖像(I=Ω∪φ)，δΩ為破損區(qū)域和源區(qū)域的邊界．Criminisi算法分為3個(gè)步驟：

步驟1.計(jì)算破損部分邊界上的修復(fù)優(yōu)先級．

由于修復(fù)順序會影響修復(fù)效果，為了確定邊界δΩ上各點(diǎn)的修復(fù)順序，Criminisi算法首先計(jì)算δΩ邊界上所有像素點(diǎn)的優(yōu)先級，找出優(yōu)先級最高的點(diǎn)p和以其為中心的樣本塊Ψp．為了保證破損區(qū)域較小且包含結(jié)構(gòu)區(qū)域的樣本塊優(yōu)先合成，式(1) 定義了修復(fù)優(yōu)先級：

P(p)=C(p)×D(p)，

(1)

其中：C(p)為信任項(xiàng)，D(p)為數(shù)據(jù)項(xiàng).具體定義如式(2)和式(3)所示：

(2)

(3)

式(2)中，Ψp為圖1中以p點(diǎn)為中心的待修復(fù)塊的像素點(diǎn)的集合，Ψp∩φ為黑色方框里的已知區(qū)域，即Ψp中位于源區(qū)域的部分．|Ψp|表示整個(gè)待填充塊中像素點(diǎn)的個(gè)數(shù)．C(p)為像素點(diǎn)p通過Ψp中所有像素點(diǎn)q的信任項(xiàng)C(q)所求得的對應(yīng)信任項(xiàng)，對于位于源區(qū)域的像素點(diǎn)q其信任項(xiàng)為1，對于位于破損區(qū)域的像素點(diǎn)q其信任項(xiàng)為0．C(q)越大表示對應(yīng)的Ψp破損程度越小，越值得被優(yōu)先修復(fù)．

步驟2.尋找最佳匹配塊Ψq．

在找到優(yōu)先級最高的待填充塊Ψp之后，需要在圖像的源區(qū)域φ中尋找與Ψp最接近的匹配塊Ψq，并用Ψq來對Ψp中的破損區(qū)域進(jìn)行填充．其中Ψq的選擇條件如式(4)所示，其中d(Ψp,Ψq)表示樣本塊Ψp中未破損區(qū)域與匹配塊Ψq對應(yīng)區(qū)域之間的歐式距離[4]：

(4)

步驟3.填充待修復(fù)區(qū)域并更新邊界．

在找到與Ψp最接近的匹配塊Ψq之后，Ψp中的破損區(qū)域被Ψq中的對應(yīng)區(qū)域填充．在填充完成后，更新破損區(qū)域的邊界δΩ．以更新后的邊界為新的邊界，重復(fù)步驟1～3的計(jì)算直到破損區(qū)域被全部修復(fù)．

圖2 相似塊的誤匹配示意圖Fig.2 Diagram of the false match of similar patches

Criminisi算法的優(yōu)點(diǎn)是一方面能夠保證圖像紋理的修復(fù)質(zhì)量，另一方面能維持原圖的結(jié)構(gòu)信息基本不變．但是，按照Criminisi算法來對圖像進(jìn)行修復(fù)，存在2個(gè)問題： 1) 在選定填充塊的過程中只考慮了匹配塊與待填充塊對應(yīng)的已知部分的相似度，沒有考慮匹配塊中用來作為填充區(qū)域的部分對修復(fù)結(jié)果的影響，導(dǎo)致修復(fù)結(jié)果易產(chǎn)生誤差(如圖2所示)；2) 每次找到用于填充的目標(biāo)樣本塊之前，都要對源區(qū)域進(jìn)行全局搜索，嚴(yán)重影響了算法的效率．

1.2Anupam算法

圖2中，為了修復(fù)樣本塊p，Criminisi算法首先在已知區(qū)域中尋找最接近的匹配塊進(jìn)行修復(fù)．由于樣本塊A先于樣本塊B的搜索順序，在A和B擁有同樣差異的情況下，盡管樣本塊B更符合視覺填充的效果，但B始終被算法所忽略，造成誤匹配．針對這種誤匹配情況，Anupam算法通過比較匹配塊中與待修復(fù)塊缺損區(qū)域?qū)?yīng)的部分和待修復(fù)塊中已知部分平均值的均方誤差(Mean Square Error, MSE)來判斷填充部分與待修復(fù)塊已知部分的差異大小，修正選擇結(jié)果，判斷的條件如下所示：

(5)

(6)

其中：fp∈φ∩Ψ表示待修復(fù)塊已知區(qū)域中點(diǎn)p的顏色；#{p|p∈φ∩Ψ}為待修復(fù)塊已知區(qū)域中像素的數(shù)量，M為待填充區(qū)域中已知顏色的平均值，fp∈φ-Ψ表示待修復(fù)塊破損區(qū)域中的點(diǎn)p在匹配塊中對應(yīng)位置的顏色，#{p|p∈φ-Ψ}表示待修復(fù)塊破損區(qū)域中像素的數(shù)量；V表示由匹配塊中對應(yīng)破損區(qū)域位置的顏色與待修復(fù)塊中已知部分的平均值M計(jì)算得到的MSE．V越小說明用于填充的顏色均值越接近待修復(fù)塊已知區(qū)域的顏色均值．改進(jìn)后，當(dāng)根據(jù)式(4)再次搜索到擁有同樣差異的樣本塊時(shí)，則繼續(xù)計(jì)算2個(gè)樣本塊與待修復(fù)塊的差異V，并選擇V值更小的樣本塊進(jìn)行修復(fù)．改進(jìn)后的修復(fù)結(jié)果對比如圖3所示．

圖3 修復(fù)結(jié)果比較示意圖Fig.3 Diagram of the comparison of inpainting results

Anupam算法在修正誤匹配、改進(jìn)修復(fù)效果的同時(shí)，對修復(fù)速度也進(jìn)行了改進(jìn)．由于實(shí)際情況下最終搜索到的匹配塊大多分布在距離待填充塊較近的區(qū)域，而Criminisi算法采用的全圖搜索方式會遍歷眾多距離較遠(yuǎn)的區(qū)域，存在大量的冗余計(jì)算．Anupam算法將Criminisi算法中的全圖搜索方式改為局部搜索的方式來減少匹配次數(shù)，局部搜索的范圍由(startX,startY)和(endX,endY)所給出的矩形框加以限定，其坐標(biāo)定義如式(7)～(10)所示：

(7)

(8)

(9)

(10)

其中：h和w表示圖像的高和寬；m和n表示樣本塊中包含的列數(shù)和行數(shù)；Dx和Dy為常量，分別表示搜索范圍在X和Y方向上的最小直徑；c表示樣本塊的邊長．

與Criminisi算法相比，Anupam算法在修復(fù)時(shí)考慮了填充部分對修復(fù)的影響，所以修復(fù)效果更好，同時(shí)因?yàn)榭s小了搜索區(qū)域，修復(fù)速度得到了明顯提升．但是該算法的改進(jìn)同時(shí)也使匹配塊的選取更傾向于顏色均值接近的區(qū)域，弱化了結(jié)構(gòu)信息對選取的影響，導(dǎo)致在修復(fù)結(jié)構(gòu)區(qū)域時(shí)依舊存在誤差．另外經(jīng)過該算法縮小后的搜索區(qū)域，依然含有大量始終未被使用的匹配塊，算法的效率仍然有較大的提升空間，尤其當(dāng)破損區(qū)域較大時(shí)，通過該算法計(jì)算出的搜索區(qū)域接近整張圖片的大?。?/p>

2 基于分水嶺分割的快速圖像修復(fù)算法流程

針對Criminisi算法和Anupam算法在圖像修復(fù)質(zhì)量、修復(fù)速度上存在的不足之處，本文提出了一種基于分水嶺分割的快速圖像修復(fù)算法，進(jìn)行了3個(gè)方面的改進(jìn)： 1) 在Anupam算法的基礎(chǔ)上利用改進(jìn)的匹配區(qū)域搜索，進(jìn)一步縮小了搜索區(qū)域，加快了修復(fù)速度；2) 提出了一種樣本塊篩選方法，通過分水嶺算法對圖像進(jìn)行分割，判斷樣本塊和待修復(fù)塊是否屬于同一個(gè)區(qū)域，根據(jù)篩選結(jié)果選擇是繼續(xù)進(jìn)行匹配運(yùn)算還是直接忽略該樣本塊繼續(xù)尋找下一個(gè)樣本塊；3) 本文利用分水嶺分割的結(jié)果，提出了一種分類修復(fù)紋理區(qū)域和結(jié)構(gòu)區(qū)域的新的匹配方法來改進(jìn)Anupam算法在修復(fù)結(jié)構(gòu)上的誤差．算法的整體流程如圖4所示．

圖4 Anupam算法和本文改進(jìn)算法的流程圖Fig.4 Flow charts of Anupam algorithm and the proposed algorithm

2.1改進(jìn)的匹配區(qū)域搜索

由于Criminisi算法在修復(fù)過程中選中的匹配塊大部分集中于修復(fù)邊界的周圍， Anupam算法通過在待修復(fù)塊周圍劃定矩形區(qū)域的方式縮小搜索區(qū)域，達(dá)到提升修復(fù)速度的目的．但是Anupam算法在劃定搜索區(qū)域時(shí)，為了保證每個(gè)待修復(fù)塊都能找到對應(yīng)的匹配塊，分別使用樣本塊中心點(diǎn)對應(yīng)的行和列中的待修復(fù)像素?cái)?shù)量作為修復(fù)區(qū)域?qū)捄透叩陌霃剑虼藢τ谖挥谝恍﹫D像邊緣區(qū)域的待修復(fù)塊，Anupam算法所采用的矩形框會包含大量無用的區(qū)域．

為了修復(fù)破損區(qū)域，首先需要在圖像中搜索與待修復(fù)塊最接近的樣本塊．由于Criminisi算法采用全圖搜索的方式，所以非常耗時(shí)．但是根據(jù)馬爾科夫隨機(jī)場(Markov Random Filed, MRF)模型的假設(shè)，一張圖像具有局部統(tǒng)計(jì)特征，圖像中某一點(diǎn)的特征與其附近的鄰域有關(guān)，因此可以用局部搜索來代替全局搜索．根據(jù)文獻(xiàn)[12]中的統(tǒng)計(jì)結(jié)果，相似塊大部分位于破損區(qū)域附近，因此本文在Anupam算法的基礎(chǔ)上通過改進(jìn)匹配區(qū)域的方法來加速搜索.

圖5 改進(jìn)的匹配區(qū)域搜索過程示意圖Fig.5 Diagram of the searching process of modified matching area

表1給出了分別使用Anupam算法和本節(jié)中改進(jìn)的匹配區(qū)域搜索方法進(jìn)行修復(fù)的耗時(shí)對比(原圖見圖6第一列)．可以看出，本文的改進(jìn)方法使得Anupam算法取得了40%左右的平均加速比．

表1 2種方法的修復(fù)速度和搜索結(jié)果的相似比例

為了進(jìn)一步驗(yàn)證改進(jìn)的匹配區(qū)域?qū)π迯?fù)質(zhì)量影響，本文引入文獻(xiàn)[13]中的感知哈希值(圖像指紋)作為相似性的評測標(biāo)準(zhǔn)，針對每個(gè)待修復(fù)塊，通過同時(shí)在Anupam算法的匹配區(qū)域和改進(jìn)區(qū)域中分別搜索匹配塊并計(jì)算對應(yīng)的哈希值來進(jìn)行驗(yàn)證．根據(jù)標(biāo)準(zhǔn)，如果感知哈希值不相同的數(shù)據(jù)位數(shù)小于5，就說明2張圖像相似；如果大于10，就說明這2張圖像不同[13]．根據(jù)表1中的結(jié)果顯示，針對同樣的待修復(fù)塊，2種算法選中的匹配塊有高度的相似性．由此可以推測出，改進(jìn)后的加速算法可以獲得與Anupam算法基本一致的圖像修復(fù)質(zhì)量．圖6顯示了經(jīng)過本節(jié)算法改進(jìn)后的修復(fù)效果和原算法的結(jié)果對比，從圖中可以看出改進(jìn)前后的修復(fù)質(zhì)量基本沒有變化．因此改進(jìn)的匹配區(qū)域搜索算法在不影響修復(fù)質(zhì)量的同時(shí)可以大幅提高圖像的修復(fù)速度．

從左至右依次為原圖、待修復(fù)圖、本文實(shí)現(xiàn)的Anupam算法結(jié)果、本節(jié)算法的修復(fù)結(jié)果.圖6 修復(fù)結(jié)果對比示意圖Fig.6 Diagram of the comparison of inpainting results

2.2利用分水嶺分割結(jié)果的匹配塊篩選

由于Crminisi算法在搜索匹配塊的過程中會遇到大量與待填充塊明顯不符合的樣本塊，為了能夠快速地分辨出這些樣本塊，可以先對圖像進(jìn)行分割操作，將顏色相近的區(qū)域用同一種顏色表示，然后在匹配的過程中通過判斷是否屬于同一顏色區(qū)域來快速剔除明顯不符合的匹配塊．文獻(xiàn)[14]提出了一種通過模糊聚類對圖像進(jìn)行分割的算法，但是使用模糊聚類對圖像進(jìn)行分割需要預(yù)先設(shè)定圖像的聚類數(shù)目，并且在進(jìn)行分類的過程中會由于樣本集的選取不理想導(dǎo)致分割結(jié)果不理想，當(dāng)存在遠(yuǎn)離各聚類中心的像素時(shí)，由于模糊聚類的約束條件會使得該像素對各聚類的隸屬度都相當(dāng)大，最終影響迭代的結(jié)果．此外模糊聚類的計(jì)算時(shí)間較長，因而不利于實(shí)際應(yīng)用．文獻(xiàn)[15]提出了一種通過k- means聚類對圖像進(jìn)行分割的算法，和文獻(xiàn)[14]中的改進(jìn)一樣，使用k- means聚類分割圖像必須事先指定要生成的聚類數(shù)目，而且對選取的初值敏感，對于不同的初值，可能產(chǎn)生不同結(jié)果．k- means聚類同樣對于孤立的像素敏感，個(gè)別孤立像素的存在會極大影響分類結(jié)果．

鑒于上述分析，本文基于分水嶺分割的結(jié)果，提出了一種新的匹配塊篩選方法，通過比較分水嶺分割結(jié)果來篩選掉不合適的匹配塊，進(jìn)一步加快了修復(fù)速度．分水嶺分割是一個(gè)迭代標(biāo)注過程，該過程首先把圖像當(dāng)作測地學(xué)上的拓?fù)涞孛玻椿叶葘γ總€(gè)像素從低到高進(jìn)行排序，然后對海拔高度上的局部極小值執(zhí)行膨脹操作，在膨脹的過程中判斷和標(biāo)注出局部極小值在不同高度的影響域．如圖7(a)所示，為了得到2個(gè)集水盆間的分水嶺，需要對連通區(qū)域進(jìn)行多次膨脹．在每一次膨脹的過程中每個(gè)點(diǎn)都必須滿足結(jié)構(gòu)化元素的中心只能位于當(dāng)前連通分量的條件，結(jié)果如圖中的第1次膨脹邊界所示．在下一次膨脹時(shí)，由于膨脹邊界上的部分像素點(diǎn)造成了不同連通分量的集合聚合，如圖中的第2次膨脹邊界所示．為了劃分出不同的連通分量，這些點(diǎn)就被標(biāo)記為分水嶺[16]．使用分水嶺分割圖像的好處在于能夠在自適應(yīng)地對微弱邊緣做出良好響應(yīng)的同時(shí)，保證分割邊界的封閉連續(xù)．

圖7 分水嶺分割圖像示意圖Fig.7 Diagram of the watershed segmentation image

圖7(c)、圖7(d)和圖7(e)為分別對LENA圖(圖7(b))使用模糊聚類、k- means聚類和分水嶺分割的結(jié)果，其中模糊聚類分割耗時(shí)4.891s，k- means聚類耗時(shí)173ms，而分水嶺分割耗時(shí)21.499ms，明顯優(yōu)于其他2種算法．從圖7(c)～(e)中可以看到，使用分水嶺分割得到的結(jié)果在整體顏色區(qū)域的識別上有著更優(yōu)秀的效果，既保證集水盆擁有封閉連續(xù)的邊緣，又保留了圖像大致的結(jié)構(gòu)信息，從而為之后分析圖像的局部特征提供了可能．為了消除分水嶺分割中由于灰度的微小變化產(chǎn)生的過度分割，梯度圖像中用于提取圖像邊緣信息的分割閾值設(shè)為20．

在得到分水嶺分割結(jié)果后，圖像被分割成不同的單一顏色區(qū)域．之后匹配塊的搜索由式(11)加以篩選：

?Ψafor ?q：R(p)=R(q),q∈Ψa,p∈Ψp∩φ，

(11)

其中：Ψa表示搜索中有效的候選樣本塊；R(p)表示待修復(fù)塊已知區(qū)域中的p點(diǎn)在分割圖像中包含的顏色區(qū)域集合；R(q)表示候選的樣本塊Ψa中的q點(diǎn)在分割圖像中包含的顏色區(qū)域集合．通過式(11)的限制，只有搜索到擁有和待匹配塊相同顏色區(qū)域的樣本塊才進(jìn)行誤差計(jì)算，否則直接忽略該樣本塊．篩選過程如圖8(見第64頁)所示，Ω為待修復(fù)區(qū)域，φ為未破損區(qū)域，A、B為不同顏色的匹配區(qū)域，中心位于p的方框?yàn)榇迯?fù)塊．如圖8(a)所示，當(dāng)待修復(fù)塊中的顏色只包含區(qū)域A中的顏色時(shí)，區(qū)域B被忽略，只搜索區(qū)域A中的樣本塊；如圖8(b)所示，當(dāng)待修復(fù)塊中的顏色只包含區(qū)域B中的顏色時(shí)，區(qū)域A被忽略，只搜索區(qū)域B中的樣本塊；如圖8(c)所示，當(dāng)待修復(fù)塊中的顏色同時(shí)包含2種以上的顏色時(shí)，只搜索同時(shí)包含對應(yīng)顏色區(qū)域的樣本塊．通過篩選匹配區(qū)域，當(dāng)再次搜索到差異較大的區(qū)域時(shí)，匹配操作的算法復(fù)雜度則由計(jì)算歐幾里得距離時(shí)的O(8n)下降到遍歷樣本塊中顏色種類的O(n)，從而大大節(jié)約了修復(fù)時(shí)間，其中8表示計(jì)算歐式距離時(shí)每個(gè)點(diǎn)需要執(zhí)行的算術(shù)運(yùn)算次數(shù)，n表示樣本塊中的像素個(gè)數(shù)．

圖8 匹配塊篩選示意圖Fig.8 Diagram of filtering the matching patches

篩選匹配區(qū)域的實(shí)例如圖9(見第64頁)所示，圖9(c)中的小方框?yàn)榇迯?fù)塊，大方框?yàn)榘凑誂nupam算法劃分出的匹配區(qū)域，本文采用的基于分水嶺分割的匹配塊篩選，篩選后的匹配區(qū)域被限制在圖9(d)中的著色部分，因?yàn)檫@個(gè)區(qū)域的顏色和待修復(fù)區(qū)域中的顏色相同．通過對比圖9(c)和圖9(d)，可以看出經(jīng)過篩選后，需要匹配的區(qū)域明顯減少．

圖9 分水嶺分割篩選搜索區(qū)域的過程示意圖Fig.9 Diagram of the process of narrowing the searching area by watershed segmentation

表2給出了修復(fù)耗時(shí)的比較．可以看出，與Anupam算法相比，采用分水嶺分割結(jié)果篩選匹配塊的改進(jìn)方法，可以取得25%左右的平均加速比，明顯降低了圖像修復(fù)時(shí)間．當(dāng)破損區(qū)域所跨越的源區(qū)域中顏色對比越明顯，使用這種方法的加速效果越為突出．圖10顯示了加速前后圖像修復(fù)質(zhì)量的對比結(jié)果，可以看出，圖像修復(fù)的質(zhì)量基本保持一致．

表2 修復(fù)速度比較

從左至右依次為原圖、待修復(fù)圖、Criminisi算法結(jié)果、Anupam算法結(jié)果、本節(jié)算法的修復(fù)結(jié)果.圖10 修復(fù)結(jié)果對比示意圖Fig.10 Diagram of the comparison of inpainting results

2.3利用分水嶺分割結(jié)果的分類修復(fù)

圖11 相似塊的誤匹配示意圖Fig.11 Diagram of false match of similar patches

Anupam算法針對Criminisi算法在進(jìn)行修復(fù)時(shí)只考慮對已知部分進(jìn)行比較而造成的誤差，提出了一種比較樣本塊間MSE的改進(jìn)方法，改進(jìn)效果如圖3所示．盡管該算法在一定程度上解決了相似塊的誤匹配問題，但是Anupam算法在修復(fù)含有結(jié)構(gòu)信息的待填充塊時(shí)會造成新的誤差．產(chǎn)生這種錯(cuò)誤主要是因?yàn)楫?dāng)樣本塊間的歐式距離相等時(shí)，MSE就成了選取匹配塊的決定因素，從而導(dǎo)致了結(jié)構(gòu)信息在修復(fù)時(shí)出現(xiàn)斷裂．如圖11所示，當(dāng)同時(shí)存在與待填充塊p中已知區(qū)域歐式距離相等的樣本塊A和樣本塊B時(shí)，由于樣本塊A中存在與待填充塊p中已知部分的平均值一致的部分，使得樣本塊A與待填充塊p的MSE較小，導(dǎo)致在修復(fù)結(jié)構(gòu)區(qū)域時(shí)會去選取樣本塊A來填充，而不是結(jié)構(gòu)上更加一致的樣本塊B．

在圖2中，出現(xiàn)錯(cuò)誤匹配是因?yàn)闆]有考慮待填充塊中未知區(qū)域的紋理信息，而在圖11中，出現(xiàn)錯(cuò)誤匹配是由于忽略了圖像的結(jié)構(gòu)信息，因而得到了錯(cuò)誤的匹配結(jié)果．為了能夠快速分辨待填充塊是由單一紋理構(gòu)成的區(qū)域還是包含結(jié)構(gòu)變化的區(qū)域，并進(jìn)行針對性修復(fù)，本文提出了一種利用分水嶺分割結(jié)果的分類修復(fù)方法．

由于分水嶺算法在區(qū)分顏色邊緣時(shí)具有良好的效果，能夠在識別出物體邊緣同時(shí)，保證識別結(jié)果的封閉連續(xù)，本文首先根據(jù)之前的分水嶺分割算法得到一張分割結(jié)果，用來快速劃分近似的顏色區(qū)域．如圖12所示，(a)為原圖，(b)為待修復(fù)圖，(c)為經(jīng)過分水嶺分割后的效果，(d)為待修復(fù)區(qū)域中的2個(gè)樣本塊．其中，(d)中標(biāo)識為1的樣本塊為結(jié)構(gòu)變化區(qū)域，標(biāo)識為2的樣本塊為單一顏色區(qū)域．

圖12 分水嶺分割分類結(jié)果示意圖Fig.12 Diagram of the results of watershed segmentation classification

在得到如圖12(c)所示的分水嶺分割結(jié)果后，為了分辨出待填充塊是由單一顏色構(gòu)成的紋理區(qū)域還是由多種顏色構(gòu)成的結(jié)構(gòu)區(qū)域，首先在分水嶺分割結(jié)果中找到與待填充塊對應(yīng)的區(qū)域并統(tǒng)計(jì)其中的顏色數(shù)目，當(dāng)含有多種顏色時(shí)，說明該區(qū)域內(nèi)可能存在結(jié)構(gòu)變化，否則是單一顏色的紋理區(qū)域．在識別出結(jié)構(gòu)變化的區(qū)域之后，為了降低Anupam算法在修復(fù)結(jié)構(gòu)時(shí)因?yàn)榫档囊攵斐傻恼`差，本文在式(6)的基礎(chǔ)上引入了顏色梯度變化的差異比較來進(jìn)一步修正匹配的準(zhǔn)確度．由于圖像的變化情況可以用圖像分布的梯度來反應(yīng)，所以通過比較顏色梯度的變化，能夠更加準(zhǔn)確地識別出擁有相同結(jié)構(gòu)的區(qū)域來進(jìn)行修復(fù)．具體過程如下：

步驟1.首先得到分水嶺分割結(jié)果，尋找優(yōu)先級最高的待填充塊.

步驟2.在找到優(yōu)先級最高的待填充塊Ψp后，首先按照式(4)計(jì)算出d(Ψp,Ψq)，如果同時(shí)存在點(diǎn)q和q′使得d(Ψp,Ψq)=d(Ψp,Ψq′)，則使用式(12)和式(13)來進(jìn)一步分類尋找最匹配的填充塊Ψq：

Ψq=argmind′(Ψp,Ψq),

(12)

(13)

式(13)中d′(Ψp,Ψp)為分類匹配后得到的差異結(jié)果．為了對填充塊Ψp進(jìn)行有針對性的匹配，本文根據(jù)待填充塊Ψp在分水嶺分割結(jié)果中包含的顏色數(shù)量來選擇相應(yīng)的匹配方法，具體可分為下列兩種情況：

a.如圖12(d)的樣本塊2，當(dāng)Ψp在分水嶺分割結(jié)果中只包含一種顏色時(shí)，表示Ψp處于單一的紋理區(qū)域中．在計(jì)算匹配塊間距離時(shí)，引入V(Ψp,Ψq)做修正．V(Ψp,Ψq)為匹配塊間的MSE，計(jì)算方式如式(6)所示．V(Ψp,Ψq)越小，說明2個(gè)樣本塊顏色的平均值越接近，越有可能屬于同一區(qū)域．

b.如圖12(d)的樣本塊1，當(dāng)包含多種顏色時(shí)，表示在Ψp中可能存在結(jié)構(gòu)變化．在計(jì)算匹配塊間差異時(shí)，引入g(Ψp,Ψq)來修正結(jié)構(gòu)區(qū)域的修復(fù)結(jié)果．g(Ψp,Ψq)為匹配塊和待填充塊中對應(yīng)的已知部分在顏色梯度上差值的平方和，g(Ψp,Ψq)值越小，說明2個(gè)樣本塊間的結(jié)構(gòu)越接近，反之，差異越大說明2個(gè)樣本塊在結(jié)構(gòu)上差異越大．g(Ψp,Ψq)的計(jì)算方式如式(14)所示，其中Rp，Gp，Bp分別表示在RGB顏色空間中利用Sobel算子求得的點(diǎn)p處的顏色梯度，p′為待修復(fù)塊中的點(diǎn)p在匹配塊Ψq中對應(yīng)的像素點(diǎn)：

(14)

步驟3.在找到最合適的匹配塊后，用匹配塊中的已知部分對待填充塊中缺失的部分進(jìn)行填充，同時(shí)依照待填充塊和選中的匹配塊的坐標(biāo)，對分水嶺分割圖像中的對應(yīng)部分進(jìn)行相應(yīng)的填充．之后更新邊界δΩ的優(yōu)先級并重復(fù)步驟1～3來繼續(xù)尋找優(yōu)先級最高的待填充塊進(jìn)行修復(fù)．

該方法在修復(fù)圖像的過程中，既保證了同一紋理區(qū)域在尋找匹配塊時(shí)的準(zhǔn)確性，同時(shí)也保證了修復(fù)結(jié)構(gòu)區(qū)域時(shí)，圖像缺失的結(jié)構(gòu)信息得到延伸．修復(fù)結(jié)果的對比如圖13所示，其中圖(d)為Anupam算法的修復(fù)結(jié)果，方框圈出的結(jié)構(gòu)區(qū)域出現(xiàn)了明顯的誤差．而使用本節(jié)算法的結(jié)果如圖13(e)所示，由于在修復(fù)時(shí)采取了分類修復(fù)方法，因此結(jié)構(gòu)區(qū)域得到了更好的修復(fù)．

圖13 修復(fù)結(jié)果對比示意圖Fig.13 Diagram of the comparison of inpainting results

3 實(shí)驗(yàn)結(jié)果分析

本文所用算法工作均在如下硬件測試平臺完成： 操作系統(tǒng)為Ubuntu13.04，CPU為AMD A4- 5000 APU with RadeonTMHD Graphics，主頻為1.5GHz．實(shí)驗(yàn)中用到的測試圖片來自于Berkeley大學(xué)的BSR_bsds500測試集和參考文獻(xiàn)．

3.1算法耗時(shí)比較

表3為Criminisi算法、Anupam算法和本文算法的整體耗時(shí)的結(jié)果比較．其中第5列給出了本文整體算法改進(jìn)后的修復(fù)耗時(shí)．可以看出，經(jīng)過本文算法的改進(jìn)，圖像修復(fù)速度平均提高了40%左右．其中圖14(c)由于圖像尺寸較小且破損區(qū)域占比相對較大，因此按照本文2.1節(jié)中改進(jìn)的算法劃分出的區(qū)域與Anupam算法劃分出的搜索區(qū)域接近，加速效果不及其他圖標(biāo)的明顯．

表3 3種算法修復(fù)耗時(shí)比較

但如表3中最后一列所示，第2章中通過第2.1節(jié)對匹配區(qū)域搜索和第2.2節(jié)對匹配塊篩選的改進(jìn)，分別獲得了40%左右和25%左右的算法平均加速比，而最終的加速比只在40%左右，主要是因?yàn)闉楦訙?zhǔn)確地識別出擁有相同結(jié)構(gòu)的區(qū)域來進(jìn)行后續(xù)的修復(fù)，本文第2.3節(jié)的改進(jìn)部分在Anupam算法的基礎(chǔ)上增加了分類匹配和梯度差異計(jì)算，部分增加了修復(fù)耗時(shí)，因此導(dǎo)致了整體改進(jìn)耗時(shí)沒有單獨(dú)使用2.1節(jié)和2.2節(jié)的優(yōu)化修復(fù)耗時(shí)短．

3.2主觀視覺比較

圖14為修復(fù)結(jié)果對比，從圖14(a)和圖14(b)中可以看出在修復(fù)有明顯邊界區(qū)域區(qū)分的修復(fù)區(qū)域時(shí)，本文算法在加快修復(fù)速度的同時(shí)保持了原算法的修復(fù)效果．此外，在修復(fù)圖14(c)中擁有復(fù)雜背景的破損區(qū)域時(shí)，本文算法改進(jìn)了Anupam算法在結(jié)構(gòu)區(qū)域處的修復(fù)誤差(紅框圈出部分)．在修復(fù)圖14(d)中邊界模糊的破損區(qū)域時(shí)，本文算法同樣改進(jìn)了結(jié)構(gòu)區(qū)域處的修復(fù)誤差(紅框圈出部分)．從修復(fù)結(jié)果中可以看出，經(jīng)過本文算法修復(fù)的破損圖片在主觀視覺效果上更加自然平滑，圖像修復(fù)的質(zhì)量更高．

從左至右依次為原、待修復(fù)圖、Criminisi算法結(jié)果、Anupam算法結(jié)果、改進(jìn)后的修復(fù)結(jié)果.圖14 修復(fù)結(jié)果對比示意圖Fig.14 Diagram of the comparison of inpainting results

3.3客觀標(biāo)準(zhǔn)評價(jià)

為了更加客觀的評價(jià)圖像的修復(fù)結(jié)果，本文使用文獻(xiàn)[15]提到的峰值信噪比PSNR值(圖像在每個(gè)顏色通道上的峰值與噪聲方差之比，Peak Singal to Noise Ratio)和MSE來衡量圖像的修復(fù)質(zhì)量．圖15顯示了分別使用Anupam算法和本文算法對加入隨機(jī)劃痕后的圖片進(jìn)行修復(fù)的對比結(jié)果．分別對2種算法結(jié)果的PSNR和MSE值進(jìn)行計(jì)算和比較，結(jié)果如表4和表5所示．

從左至右依次為原圖、待修復(fù)圖、Anupam算法結(jié)果、本文算法結(jié)果.圖15 修復(fù)結(jié)果對比示意圖Fig.15 Diagram of the comparison of inpainting results

PSNR越高、MSE越小，說明修復(fù)圖和原圖間的差異越小，相應(yīng)的圖像修復(fù)的質(zhì)量也越好．由表4和表5可以看出，本文算法的修復(fù)結(jié)果優(yōu)于Anupam算法．

表4 Anupam算法和本文中提出的算法的PSNR結(jié)果比較

表5 Anupam算法和本文中提出的算法的MSE結(jié)果比較

4 結(jié) 語

本文在Criminisi算法和Anupam算法的基礎(chǔ)上對傳統(tǒng)的圖像修復(fù)算法進(jìn)行了改進(jìn)．首先通過改進(jìn)的匹配區(qū)域搜索算法縮小了搜索區(qū)域，使修復(fù)的平均耗時(shí)縮短了40%左右．進(jìn)而提出了利用分水嶺分割結(jié)果篩選匹配塊的改進(jìn)方法，進(jìn)一步提高了25%左右的修復(fù)速度．最后通過利用分水嶺分割結(jié)果的分類修復(fù)算法來改進(jìn)圖像結(jié)構(gòu)信息的修復(fù)，改進(jìn)了原算法在修復(fù)結(jié)構(gòu)區(qū)域時(shí)產(chǎn)生的誤差，完整再現(xiàn)了圖像缺損部分的精細(xì)結(jié)構(gòu)，修復(fù)效果更加自然平滑．實(shí)驗(yàn)和分析結(jié)果表明，較之傳統(tǒng)算法，本文提出的基于分水嶺分割的快速圖像修復(fù)算法在平均提升了40%左右的修復(fù)速度的同時(shí)，有效地提升了圖像修復(fù)的質(zhì)量，對于大區(qū)域破損圖像的修復(fù)具有更好的適用性．

[1] BERTALMIO M, GUILLERMO S, VINCENT C,etal. Image inpainting[C]∥Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York, USA： ACM Press/Addison- Wesley Publishing Co, 2000： 417- 424.

[2] CHAN T, SHEN F. Mathematical models for local non- texture inpainting[J].SIAMJournalonAppliedMathematics, 2002,62(3)： 1019- 1043.

[3] EFROS A, LEUNG T. Texture synthesis by non- paramet ric sampling[C]∥Proceedings of IEEE International Conference on Computer Vision. Kerkyra, Greece： IEEE Press, 1999： 1033- 1038.

[4] CRIMINISI A P, PEREZ P, TOYAMA K. Region filling and object removal by exemplar- based image inpainting[J].IEEETransactionsonImageProcessing, 2004,13(9)： 1200- 1212.

[5] CHENG W H, HSIEH C W, LIN S K,etal. Robust algorithm for exemplar- based image inpainting[C]∥Proceedings of the International Conference on Computer Graphics, Imaging and Vision (CGIV 2005). Beijing, China： [s.n.], 2005： 64- 69.

[6] 劉 奎,蘇本躍,王一賓.基于樣例的圖像修復(fù)改進(jìn)算法[J].計(jì)算機(jī)工程,2012,38(7)： 193- 194.

[7] MASNOU S. Disocclusion： A variational approach using level lines[J].IEEETransactionsonImageProcessing, 2002,11(2)： 68- 76.

[8] CAO F, GOUSSEAU Y, MASNOU S,etal. Geometrically guided exemplar- based inpainting[J].SIAMJImagingSciences, 2009,4(4)： 1143- 1179.

[9] HUI Q W, QING C, CHENG H H,etal. FAST exemplar- based image inpainting approach[C]∥Proceedings of International Conference on Machine Learning and Cybernetics, ICMLC 2012, International Conference. Xi’an, China： IEEE Computer Society Press, 2012： 1743- 1747.

[10] 王昊京,王建立,王鳴浩，等.采用雙線性插值收縮的圖像修復(fù)方法[J].光學(xué)精密工程,2010,8(5)： 1234- 1241.

[11] ANUPAM, GOYAL P, DIWAKAR S. Fast and enhanced algorithm for exemplar based image inpainting[C]∥2010 Fourth Pacific- Rim Symposium on Image and Video Technology. Singapore： IEEE Press, 2010： 325- 330.

[12] PARK C, KIM B. Distance weighted bounding for fast exemplar- based inpainting[J].InternationalJournalofSoftwareEngineeringandItsApplications, 2015,9(2)： 143- 150.

[13] KRAWETZ N. Looks like it.[EB/OL]. http：∥www.hackerfactor.com/blog/index.php?/archives/432- Looks- Like- It.html.

[14] 王宇新,賈 棋,劉天陽,等.遮擋物體移除與圖像紋理修補(bǔ)方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2008,20(1)： 43- 49.

[15] 朱 霞,李 宏,張 衛(wèi).一種基于顏色區(qū)域分割的圖像修復(fù)算法[J].計(jì)算機(jī)工程,2008,34(14)： 191- 193.

[16] HARIS K, EFSTRATIADIS S N, MAGLAVERAS N,etal. Hybrid image segmentation using watersheds and fast region merging[J].IEEETransactionsonImageProcessing, 1998,7(12)： 1684- 1699.

Abstract： In order to repair damaged image quickly and precisely, an algorithm based on Watershed Transform is proposed in this paper. Based on the results of watershed segmentation calculation, the new algorithm has three aspects of improvements. Firstly, a new method of searching area reduction is used to reduce the cost of patch matching. Secondly, a new filtering method of matching patches is applied to further improve the inpainting speed. Finally, a new method of classification inpainting is proposed to improve the image processing quality. Experimental results show that the algorithm proposed in this paper obtains an improvement of about 40% in run- rate together with a large improvement of inpainting quality as well, compared with the existing algorithm.

Keywords： inpainting; searching area reduction; watershed segmentation; classification matches

AFastInpaintingMethodBasedonWatershedSegmentation

TU Xin, NIU Shengxiao, CHEN Gengsheng, XU Wei

(StateKeyLaboratoryofASIC&System,FudanUniversity,Shanghai201203,China)

TP391

A

0427- 7104(2017)01- 0057- 14

2016- 02- 16

上海市科技創(chuàng)新行動計(jì)劃(14511108002)

屠 昕(1990—)，男，碩士研究生；許 薇，女，工程師，通信聯(lián)系人，E- mail： xuwei@fudan.edu.cn.