基于改進(jìn)匹配區(qū)域的虛擬化圖像修復(fù)算法

文/封嘯 何金鑫 高溪 戴磊

在圖像修復(fù)領(lǐng)域，經(jīng)典的圖像修復(fù)算法有兩類:第一類是圖像潤飾（inpainting）方法，由Bertalmio[4]等人提出通過修復(fù)邊界的等照度線方向傳播信息的各項異性擴(kuò)散的三階PDEs 模型(BSCB 模型)，Chan等將圖像去噪中的（TV）模型應(yīng)用于圖像修復(fù)，提出了整體變分模型以及基于曲率驅(qū)動擴(kuò)散模型等，但當(dāng)面臨修復(fù)較大區(qū)域或紋理較強(qiáng)的破損區(qū)域問題時，修復(fù)效果不理想。第二類是基于紋理合成的圖像修復(fù)方法，以Criminisi [5]等人提出的結(jié)合待修復(fù)點的幾何結(jié)構(gòu)以及相關(guān)領(lǐng)域的置信度，計算出修復(fù)的順序從而實現(xiàn)模擬人工修復(fù)圖像的過程，基于塊的紋理合成修復(fù)模型，通過全局搜索來匹配樣本塊，然后借助復(fù)制對圖像缺損區(qū)域進(jìn)行填充，實現(xiàn)圖像由邊緣缺損逐步向內(nèi)修復(fù)的算法。本文針對第二類算法的不足進(jìn)行了改進(jìn)。

1 算法簡介

1.1 原始的Criminisi算法

如圖1所示，此算法先通過計算目標(biāo)區(qū)域中沿輪廓線截取的方形模板Ψp的優(yōu)先級，它的優(yōu)先級大小由下面兩部分構(gòu)成：第一部分是該模板中的數(shù)據(jù)值，第二部分是該模板的置信值，最終的該模板的優(yōu)先級就由這2部分共同構(gòu)成。計算出最高優(yōu)先級后對該區(qū)域進(jìn)行擴(kuò)散紋理和結(jié)構(gòu)處理，方法是從源區(qū)域取樣，尋找和該模板最匹配的模板，然后將相應(yīng)的像素點復(fù)制填充到目標(biāo)區(qū)域的待修復(fù)模板中。隨著模板內(nèi)剩余像素的填充完畢，重新更新該模板內(nèi)像素的置信值。算法重復(fù)以上過程，直到填充全部完成。

1.2 原始算法存在的問題

Criminisi原始算法的缺點主要體現(xiàn)在以下兩個方面：

（1）算法對于優(yōu)先級的計算：隨著目標(biāo)區(qū)域修復(fù)算法填充的進(jìn)行,對模板數(shù)據(jù)的值沒有進(jìn)行更新，從而導(dǎo)致模板數(shù)據(jù)會隨著修補過程不斷降低，這便導(dǎo)致后面修補過程中計算出的置信值不可靠。因此產(chǎn)生錯誤的填充順序,最終使修復(fù)效果不盡人意。

（2）該算法采用全局搜索算法來尋找最優(yōu)匹配塊，這不僅產(chǎn)生大量多余運算影響修復(fù)速度，還會產(chǎn)生錯誤的修復(fù)順序。

1.3 原始算法改進(jìn)

我們對算法進(jìn)行了如下幾點的改進(jìn)，其主要分為以下兩個步驟：

1.3.1 計算優(yōu)先級（改進(jìn)Criminisi算法公式）針對原始Criminisi算法中計算模板優(yōu)先級只是簡單的由模板數(shù)據(jù)值和模板置信值的乘積構(gòu)成，未能充分反映模板中紋理信息和結(jié)構(gòu)信息的分布情況對圖像恢復(fù)造成的影響，改進(jìn)算法特設(shè)置了分段函數(shù)針對不同的情況分別處理。

公式1中，C(p)和D(p)分別表示模板的置信度值和數(shù)據(jù)值，α和β為調(diào)節(jié)參數(shù)，取α=0.382，β=0.618。公式2中，C(q)表示模板內(nèi)像素點的置信值，np是輪廓線在p點的單位法向量，是在點p的等照度線的強(qiáng)度和方向。

圖1：基于紋理合成的圖像修復(fù)

公式1中的分段函數(shù)表示當(dāng)數(shù)據(jù)項為零時,只要置信度項足夠高,模板也可以得到優(yōu)先修復(fù)；當(dāng)數(shù)據(jù)項不為零且置信度項值大于等于0.5時，變乘為加，讓數(shù)據(jù)項占主導(dǎo)因素,即采用結(jié)構(gòu)優(yōu)先的修復(fù)方法；當(dāng)數(shù)據(jù)項不為零且置信度項值小于0.5時，仍采用Criminisi算法的優(yōu)先級計算方法，可使兩項相互抑制，保證修復(fù)順序從外向內(nèi)逐漸擴(kuò)散。

1.3.2 匹配區(qū)域和最佳匹配塊的改進(jìn)

使用來自整個圖像的已知信息執(zhí)行Criminisi算法下的匹配，以確定具有輪廓線上具有最高優(yōu)先級的模板的最佳匹配塊。搜索空間由模板組成，模板由已知區(qū)域的像素組成。這個過程很耗時。與要恢復(fù)的模板相關(guān)的源圖像的信息僅存在于特定區(qū)域中。基于紋理局部性和穩(wěn)定性的馬爾可夫隨機(jī)場模型，新算法將匹配區(qū)域縮小到S×S方形鄰域，其中像素點將被恢復(fù)為中心像素。匹配鄰域S×S的大小可以由損壞區(qū)域的形狀確定。重復(fù)測試和驗證大量圖像可以將受損區(qū)域的大小保持在m×n之內(nèi)。新算法設(shè)置K = min（m，n）和S =2×K + 1。

在Criminisi算法中，搜索最佳匹配塊的順序是從上到下，從左到右。該算法在匹配區(qū)域中搜索要恢復(fù)的塊的候選塊。實現(xiàn)SSD計算以識別最佳匹配塊。給定與將要恢復(fù)的塊的最小SSD相同的匹配過程創(chuàng)建多個候選塊。如果最佳匹配塊與要恢復(fù)的塊相距很遠(yuǎn)，則僅確保與塊中的已知像素的特征一致以進(jìn)行恢復(fù)。其余部分的特征可能與預(yù)期結(jié)果不一致。一旦復(fù)制了錯誤匹配塊，以下匹配塊搜索將導(dǎo)致差的再現(xiàn)過程。圖2顯示了具有5×5測量的類似塊。圖2（b）和圖2（c）中的任何塊都可用于恢復(fù)圖2（a）。圖2（c）的修復(fù)效果應(yīng)該是最好的，因此圖2（c）是真正的最佳匹配塊。

Criminisi算法中的匹配使用SSD計算。不考慮圖像紋理，僅考慮將要恢復(fù)的塊的對應(yīng)像素與所選擇的匹配塊之間的色差，不包括對應(yīng)位置的梯度差。提出以下匹配函數(shù)來解決問題：

在公式（5）中，表示最佳匹配塊并表示要恢復(fù)的塊。在公式（6）中，表示待恢復(fù)塊與匹配塊之間的距離，m表示待修復(fù)塊中的像素數(shù)，Vip待恢復(fù)塊中第i個像素的顏色值，Vip表示匹配塊中第i個像素的顏色值，Iip表示待恢復(fù)塊中第i個像素的梯度值，Iiq'表示匹配塊中第i個像素的梯度值。新的匹配功能確保了兩個塊的顏色和紋理的最小差異。

2 系統(tǒng)實現(xiàn)流程

2.1 項目實施的具體步驟

（1）標(biāo)記確定待修復(fù)圖像中的待修復(fù)區(qū)域，本算法采用手工標(biāo)記；

（2）選取待修復(fù)區(qū)域和已知區(qū)域交界的輪廓線；

（3）計算輪廓線上模板的數(shù)據(jù)值和置信度值，引入Sobel算子，優(yōu)化數(shù)據(jù)值和置信度值的計算；

（4）引入調(diào)節(jié)參數(shù)，根據(jù)模板的數(shù)據(jù)值和置信度值計算模板的優(yōu)先級，確定具有最高優(yōu)先級的待修復(fù)模塊；

（5）在待修復(fù)模塊鄰近的已知區(qū)域內(nèi)，按照與待修復(fù)模塊中心點的距離遠(yuǎn)近，由近及遠(yuǎn)的搜索所有匹配塊，尋找與待修復(fù)模塊最相似的最優(yōu)匹配塊；

（6）在待修復(fù)模塊的相應(yīng)位置用最優(yōu)的匹配塊所對應(yīng)的像素點填充，然后依據(jù)最優(yōu)匹配塊對應(yīng)的SSD值和設(shè)定的顏色閾值的大小關(guān)系的不同，更新新填充像素點的置信度值；

（7）對待修復(fù)區(qū)域重復(fù)步驟（2）～（6），直到待修復(fù)區(qū)域全部填充完畢。

2.2 效果展示

圖3、圖4為本文章法修復(fù)效果對比圖。

2.3 實驗結(jié)果分析

本修復(fù)系統(tǒng)采用VisualC++6.0作為開發(fā)平臺，表1中分別對圖3、圖4中缺失像素的個數(shù)以及兩種算法修復(fù)所需要的時間進(jìn)行統(tǒng)計，圖像修復(fù)效果如圖3、圖4所示，在改進(jìn)其優(yōu)先級計算和最優(yōu)匹配塊搜索的基礎(chǔ)上，明顯看出本文所使用的算法恢復(fù)效果良好，基本沒有瑕疵，在還原背景區(qū)域時，沒有出現(xiàn)斷層區(qū)，以及紋理扭曲、色素差不匹配等問題。

3 結(jié)論

本文在基于Criminisi算法上，針對其所存在的問題，通過引入顏色直方圖以及待修復(fù)塊周邊像素的信息，對Criminisi算法的優(yōu)先級計算方式、樣本塊大小和相似性度量等方面進(jìn)行了部分改進(jìn)。最終得出實驗結(jié)果，本文的算法在視覺修復(fù)效果上要優(yōu)于Criminisi算法,更加與人類視覺系統(tǒng)的特征相吻合;另外本算法只是在局部進(jìn)行運算,所以大大的減少了修復(fù)所需要的時間。此算法對于破損區(qū)域復(fù)雜、結(jié)構(gòu)性很強(qiáng)、紋理不太明顯的圖片上，其修復(fù)效果依然會存在一定的修復(fù)誤差。針對不同類型的圖像修復(fù),本文算法的通用性仍存在不足。如何更好的建立算法的通用性和自適應(yīng)性,這是今后的工作需要進(jìn)一步研究的問題。

表1：原始算法與改進(jìn)后算法修復(fù)時間對比

圖2：類似的樣本塊

圖3：文物瓷盤的修復(fù)效果

圖4：海濱風(fēng)光的修復(fù)效果