一種基于MRF 的快速圖像修復(fù)算法

何 凱，沈成南，劉 坤，高圣楠

(天津大學(xué)電氣自動化與信息工程學(xué)院，天津 300072)

圖像修復(fù)技術(shù)是計算機(jī)視覺領(lǐng)域的研究熱點(diǎn)，在文物保護(hù)、影視制作、老照片修復(fù)、目標(biāo)移除等方面都得到了廣泛的應(yīng)用．?dāng)?shù)字圖像修復(fù)技術(shù)大致可以分為2 類：①基于偏微分方程的小區(qū)域圖像修復(fù)技術(shù)；②基于樣本塊的較大破損區(qū)域的紋理合成技術(shù)．

基于偏微分方程的圖像修復(fù)，主要是利用熱擴(kuò)散方程來建立圖像的偏微分方程，通過結(jié)合圖像待修復(fù)區(qū)域附近的已知信息，按照一定的規(guī)則向待修復(fù)區(qū)域擴(kuò)散，其代表算法主要有：BSCB 模型[1]，curvature driven diffusions(CDD)模型[2]，TV-Stocks 模型[3]，以及Mumford-Shah 模型[4]．

基于樣本塊的紋理合成，是利用圖像破損區(qū)域附近完好的紋理信息，對待修復(fù)區(qū)域進(jìn)行塊匹配和復(fù)制，以達(dá)到圖像修復(fù)的目的．紋理合成算法能夠較好地解決紋理模糊問題，得到了廣泛應(yīng)用，其代表算法為Criminisi 算法[5]．各國學(xué)者在其基礎(chǔ)上作了許多改進(jìn)，如Siadati 等[6]利用圖像的結(jié)構(gòu)張量檢測圖像結(jié)構(gòu)；Li 等[7]利用改進(jìn)的全變差算法，根據(jù)破損像素和鄰域像素之間的距離方向定義擴(kuò)散系數(shù)，保持了圖像的完整性；何凱等[8]通過改進(jìn)SSIM 來衡量結(jié)構(gòu)相似度，可自適應(yīng)選取樣本塊大小，實(shí)現(xiàn)了圖像結(jié)構(gòu)的有效修復(fù)．Smith 等[9]提出利用具有互斥鑒別特性的字典對來改進(jìn)稀疏形態(tài)成分分解法，能更好地提取圖像的紋理和結(jié)構(gòu)信息；Huang 等[10]引入了仿射變換矩陣，利用圖像中的消失點(diǎn)和消失線等信息，實(shí)現(xiàn)了樣本塊的幾何變換．此外，Newson 等[11]在變分框架下提出了一種改進(jìn)的最近鄰搜索算法，可以比較紋理的相似度．

傳統(tǒng)基于樣本塊的紋理合成方法通常按照一定的順序來進(jìn)行修復(fù)，容易產(chǎn)生錯誤的紋理或結(jié)構(gòu)傳播．為此，Komodakis 等[12]提出基于MRF 的全局優(yōu)化方法來解決這個問題；該方法采用優(yōu)先級置信度傳播(priority-belief propagation，p-BP)，即按照節(jié)點(diǎn)的優(yōu)先級順序，通過計算該節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)之間的消息值，來更新相鄰節(jié)點(diǎn)的優(yōu)先級，并根據(jù)每個節(jié)點(diǎn)候選塊的置信度來確定最優(yōu)候選塊；該算法較好地解決了結(jié)構(gòu)傳播的問題，但算法計算量大，執(zhí)行效率較低．Ruzic 等[13]在p-BP 的基礎(chǔ)上引入了基于上下文感知的方法，并利用上下文的相似性來搜索候選塊，在一定程度上改善了修復(fù)效果，但算法復(fù)雜度仍然較高．He 等[14]在MRF 的框架中利用塊偏移量的統(tǒng)計量來解決圖像修復(fù)問題．Meur 等[15]提出在不同尺度上使用MRF 框架，利用迭代的方法逐層進(jìn)行修復(fù)，可在一定程度上減少置信度傳播所需要的時間，但修復(fù)結(jié)果容易產(chǎn)生模糊現(xiàn)象．

本文提出了一種基于MRF 的快速圖像修復(fù)算法，利用低分辨率圖像的“預(yù)修復(fù)”結(jié)果，來粗略估計破損區(qū)域中MRF 內(nèi)部節(jié)點(diǎn)的初始值，并利用改進(jìn)的置信度計算公式對MRF 節(jié)點(diǎn)的候選塊進(jìn)行篩選，最后利用MRF 來確定最優(yōu)匹配塊．

1 傳統(tǒng)基于MRF的圖像修復(fù)算法

傳統(tǒng)基于MRF 的圖像修復(fù)模型如圖1 所示，其中，源區(qū)域?yàn)棣?，破損區(qū)域?yàn)棣?；與Ω有交集的塊所包含的節(jié)點(diǎn)共同組成節(jié)點(diǎn)集合ζ，并由MRF 邊緣ε組成一個4 鄰域系統(tǒng)．

圖1 MRF圖像修復(fù)模型Fig.1 MRF-based image inpainting model

2 本文算法

傳統(tǒng)基于MRF 的圖像修復(fù)模型中，在初次迭代之前，只有部分節(jié)點(diǎn)(破損區(qū)域邊緣附近)可以計算其初始信息；而計算其余節(jié)點(diǎn)與相鄰節(jié)點(diǎn)的消息傳遞時，則需要遍歷整幅圖像中所有候選塊，計算量很大．為此，本文在p-BP 算法[12]基礎(chǔ)上，提出一種快速算法，即在初次迭代前，先對高金字塔頂層的低分辨率圖像進(jìn)行預(yù)處理，以獲取內(nèi)部節(jié)點(diǎn)的粗略初始值；再利用改進(jìn)的置信度計算公式，以及紋理復(fù)雜度來確定候選塊數(shù)量，對MRF 節(jié)點(diǎn)的候選塊進(jìn)行篩選；最后利用MRF 算法確定最優(yōu)匹配塊．

2.1 候選塊篩選

設(shè)原始圖像I為金字塔底層的高分辨率圖像0G，對其進(jìn)行下采樣，得到頂層低分辨率圖像GK，K代表金字塔層數(shù)．利用自適應(yīng)樣本塊修復(fù)算法[8]對圖像GK進(jìn)行修復(fù)，得到預(yù)修復(fù)圖像；由于圖像GK尺寸很小，算法時間消耗很少，可近似忽略不計．對圖像進(jìn)行上采樣，獲得初始修復(fù)圖像(尺寸與0G相同)．設(shè)預(yù)處理圖像為I′，預(yù)處理示意圖及其結(jié)果如圖2 所示．

圖2 預(yù)處理示意圖及其結(jié)果Fig.2 Preprocessing illustration and its result

預(yù)處理圖像I′可以為內(nèi)部節(jié)點(diǎn)提供粗略的初始信息，相當(dāng)于給定了消息傳遞之前的約束條件，有助于大大加快相鄰節(jié)點(diǎn)間的消息傳遞及收斂速度．

根據(jù)預(yù)處理結(jié)果圖I′，提出的改進(jìn)置信度計算公式為

將節(jié)點(diǎn)p所有候選塊的初始置信度值按降序排列，置信度最高的設(shè)為第一候選塊．為了避免同一節(jié)點(diǎn)擁有大量相似的候選塊，本文利用SSD 值對不同類別的候選塊進(jìn)行判別．代表塊之間的相似程度，其中xN、xM分別代表第N個被選中的候選塊和第M個待比較的候選塊；tprune為相似度閾值，代表預(yù)定義的SSD 均值)，若則認(rèn)為屬于不同類別，此時保留xM為第N+1 個被選中的候選塊．候選塊數(shù)量L由圖像本身的紋理復(fù)雜度決定，本文利用圖像塊直方圖的2 階矩[16]對其進(jìn)行描述，即

式中Lmax表示最大候選塊數(shù)量．對于內(nèi)部節(jié)點(diǎn)，其候選塊數(shù)量設(shè)為Lmax．在消息傳遞過程中，從節(jié)點(diǎn)p發(fā)送給其相鄰節(jié)點(diǎn)q 的消息定義為

對于每一個節(jié)點(diǎn)p，其候選塊的置信度可由式(4)定義，當(dāng)所有消息值穩(wěn)定或達(dá)到了預(yù)先設(shè)定的迭代次數(shù)，即可找到每一個節(jié)點(diǎn)候選塊中置信度最大的樣本塊，即

2.2 算法流程

本文算法流程歸納如下．

步驟1采用自適應(yīng)樣本塊算法[8]對高斯金字塔頂層圖像進(jìn)行修復(fù)，得到預(yù)處理圖像I′．

步驟2計算任意節(jié)點(diǎn)p的初始置信度，計算節(jié)點(diǎn)p的候選塊數(shù)量L，并利用 SSDN,M確定節(jié)點(diǎn)p的L個初始候選塊．

步驟3計算每個節(jié)點(diǎn)的優(yōu)先級將所有節(jié)點(diǎn)標(biāo)記為未訪問，設(shè)置迭代次數(shù)k，其中

步驟4執(zhí)行前向消息傳遞．在未訪問的節(jié)點(diǎn)中選取優(yōu)先級最高的節(jié)點(diǎn)p，將其標(biāo)記為已訪問，計算該節(jié)點(diǎn)與所有相鄰節(jié)點(diǎn)q的消息更新當(dāng)前相鄰節(jié)點(diǎn)q的置信度和優(yōu)先級[12]，直至所有節(jié)點(diǎn)都被訪問為止．

步驟5執(zhí)行后向消息傳遞．按照步驟4 中的相反順序，將節(jié)點(diǎn)p標(biāo)記為未訪問，再次計算節(jié)點(diǎn)p與其所有相鄰節(jié)點(diǎn)q的消息更新當(dāng)前相鄰節(jié)點(diǎn)q的置信度和優(yōu)先級，直至所有節(jié)點(diǎn)都標(biāo)記為未訪問．

步驟6重復(fù)步驟4、5 直至完成k次迭代；對所有節(jié)點(diǎn)p，利用式(9)，完成修復(fù)．

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

本實(shí)驗(yàn)平臺采用Matlab，計算機(jī)配置為CPU 處理器Core i7-6700，主頻3.40 GHz，內(nèi)存8.00 GB．采樣過程中選用最近鄰插值法，以減少預(yù)處理的時間消耗．本文圖片分辨率介于240 ×160～400 ×360之間，參數(shù)選取為300 000}

將本文方法分別與p-BP 算法[12]、Meur 算法[15]和Non-Local 算法[11]進(jìn)行比較；其中，p-BP 算法是在傳統(tǒng)MRF 模型下的經(jīng)典修復(fù)算法，Meur 算法是在改進(jìn)MRF 框架下的多尺度超分辨率修復(fù)算法，Non-Local 算法是在變分框架下的最新改進(jìn)算法．

為了對本文算法修復(fù)效果進(jìn)行量化評價，選取了4 幅圖像，人工標(biāo)記破損區(qū)域，分別采用經(jīng)典算法與本文算法進(jìn)行處理，并采用峰值信噪比(PSNR)對幾種算法的修復(fù)效果進(jìn)行量化評估，如圖3 所示．從圖中可以看出，對上述幾幅圖像，采用本文算法進(jìn)行修復(fù)，其PSNR 都高于傳統(tǒng)算法，修復(fù)后圖像視覺效果也更為合理，修復(fù)效果最佳．

圖3 不同算法修復(fù)效果比較Fig.3 Comparison of different inpainting methods

為進(jìn)一步分析本文算法性能，選取了2 幅具有不同紋理和結(jié)構(gòu)的自然場景圖像，對物體移除后圖像進(jìn)行修復(fù)，各種算法修復(fù)效果對比結(jié)果如圖4、圖5 所示．從圖4 中可以看出，p-BP 算法較好地修復(fù)了水平粗欄桿，但在豎直細(xì)欄桿(紅色圓圈表示)處出現(xiàn)了斷裂；Meur 算法和Non-Local 算法在水平粗欄桿和豎直細(xì)欄桿處的修復(fù)結(jié)果產(chǎn)生了扭曲及斷裂現(xiàn)象；而本文方法則比較理想地恢復(fù)了兩部分的欄桿結(jié)構(gòu)．將圖5 中紅色矩形區(qū)域放大后可以看出：p-BP 算法成功修復(fù)了灌木叢的結(jié)構(gòu)，但在灰色墻壁的結(jié)構(gòu)中有明顯的斷層；Meur 算法在修復(fù)灰色墻壁和灌木叢時均出現(xiàn)了模糊；Non-Local 算法合理修復(fù)了灰色墻壁的部分結(jié)構(gòu)，但在墻壁和灌木叢交接處出現(xiàn)了結(jié)構(gòu)不連續(xù)；而本文算法則有效改善了p-BP 算法中的部分?jǐn)鄬蝇F(xiàn)象，修復(fù)結(jié)果更為理想．

圖4 圖像“Horse”修復(fù)效果比較Fig.4 Comparison of inpainting results of the image“Horse”

圖5 圖像Statue”修復(fù)效果比較Fig.5 Comparison of inpainting results of the image“Statue”

表1 不同算法修復(fù)時間對比Tab.1 Comparison of different inpainting methods in terms of time

由此可以看出，與傳統(tǒng)基于MRF 算法相比，本文算法的修復(fù)結(jié)果有了一定程度的提高，可以獲得更加自然合理的修復(fù)效果．為了驗(yàn)證本文算法的魯棒性，還對另外4 幅圖像進(jìn)行了修復(fù)，效果如圖6 所示．從圖6 中可以看出，對不同結(jié)構(gòu)和紋理的圖像，本文算法比傳統(tǒng)算法的修復(fù)效果更為理想．

表1 列出了傳統(tǒng)基于MRF 算法(p-BP)、Meur算法、Non-Local 算法，以及本文算法的運(yùn)行時間對比結(jié)果(本文算法的運(yùn)行時間包含了第2.1 節(jié)中預(yù)處理所需時間)．結(jié)合表1 和上述修復(fù)效果可以看出，p-BP 算法時間消耗過大；Meur 算法雖然大大減少了算法的時間消耗，但容易產(chǎn)生模糊現(xiàn)象；Non-Local算法的運(yùn)行速度最快，但容易出現(xiàn)結(jié)構(gòu)斷層現(xiàn)象，修復(fù)效果不夠理想；而本文算法在保證修復(fù)效果自然合理的同時，平均運(yùn)行時間比p-BP 算法減少了75%以上，也少于Meur 算法，大大提高了運(yùn)算效率．

圖6 本文算法修復(fù)效果Fig.6 Inpainting results of the proposed method

4 結(jié) 語

本文提出了一種基于MRF 的快速圖像修復(fù)算法，通過對低分辨率圖像進(jìn)行“預(yù)修復(fù)”來獲取內(nèi)部節(jié)點(diǎn)的粗略初始值，并利用改進(jìn)的置信度計算公式對MRF 節(jié)點(diǎn)的候選塊進(jìn)行篩選，提高了所有節(jié)點(diǎn)交互運(yùn)算的效率，有效減少了算法的時間消耗，同時，修復(fù)效果上也得到了一定程度的改善．仿真實(shí)驗(yàn)結(jié)果證明了本文方法的有效性．