何?凱，?？』?，沈成南，盧雯霞

?

基于SSIM的自適應樣本塊圖像修復算法

何?凱，?？』郏虺赡?，盧雯霞

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

現(xiàn)有基于樣本塊的圖像修復算法，大多通過人工設定樣本塊大小來達到最佳修復效果，缺乏自適應性；此外，對圖像不同紋理和結(jié)構(gòu)區(qū)域采用相同大小的樣本塊，也不利于獲得整體最優(yōu)修復效果．為解決上述問題，本文提出一種基于改進結(jié)構(gòu)相似性的自適應樣本塊大小選取算法，在傳統(tǒng)的SSIM算法的基礎上增加了梯度信息，并通過結(jié)合樣本塊亮度、對比度和結(jié)構(gòu)3個模塊來衡量結(jié)構(gòu)差異，以此確定不同結(jié)構(gòu)和紋理區(qū)域的最優(yōu)樣本塊大小，提高算法適應性，改善修復效果．仿真實驗結(jié)果表明，當圖像存在復雜的結(jié)構(gòu)和紋理信息時，本文算法仍然能夠獲得理想的修復效果．

圖像修復；紋理合成；自適應樣本塊；SSIM算法；梯度信息

圖像修復是計算機圖像和視覺研究領(lǐng)域的熱點之一，在文物保護、影視制作、老照片修復、目標移除等方面都得到了廣泛的應用．其核心思想是利用圖像中已知的紋理和結(jié)構(gòu)信息，按照一定的修復順序和匹配準則對缺損區(qū)域進行修補，以保證圖像的視覺完整性．圖像修復算法可以大致分為兩大類：基于偏微分方程的圖像修復算法和基于樣本塊的紋理合成算法．前者適用于小區(qū)域圖像修復，后者可用于較大破損區(qū)域的修復，能夠獲得比較自然的紋理和結(jié)構(gòu)修復效果．

本文主要針對第2類算法開展相關(guān)研究．目前，國內(nèi)外學者已經(jīng)提出了許多紋理合成算法，例如：Luo等[1]對經(jīng)典的Criminisi算法[2]進行了改進，于2009年提出了基于深度圖像的圖像修復算法，將深度圖像繪制和視點變化技術(shù)引入圖像修復領(lǐng)域．2010年，Xu等[3]提出利用待修復塊和鄰域塊的非零相似稀疏性來獲得結(jié)構(gòu)可信度，改進了修復順序；此外，在信息填充過程中，將所得候選塊的線性組合作為填充信息填充到破損區(qū)域．同年，Anamandra等[4]對優(yōu)先權(quán)函數(shù)公式做了修改，加入了梯度及其對應的對數(shù)值，取得了不錯的圖像修復效果．2011年，Li等[5]采用小波變換法來檢測圖像的不完整凸結(jié)構(gòu)，并運用線性擬合對基于樣本塊的紋理合成算法進行了改進．Cao等[6]使用結(jié)構(gòu)張量來確定修復順序和匹配準則，并利用K-最近鄰域算法，有效減少了搜索最優(yōu)匹配塊的計算量．Smith等[7]設計了具有互斥鑒別特性的字典對來改進稀疏形態(tài)成分分解法，可以更好地提取圖像的紋理和結(jié)構(gòu)信息．Huang等[8]為解決因場景透視而產(chǎn)生的結(jié)構(gòu)不連續(xù)問題，引入了仿射變換矩陣，利用圖像中的消失點和線等信息，實現(xiàn)樣本塊的幾何變換，有效提高了結(jié)構(gòu)圖像的修復效果．

此外，Zhou等[9]加強了數(shù)據(jù)項與結(jié)構(gòu)信息之間的聯(lián)系，對數(shù)據(jù)項做了加權(quán)處理，在結(jié)構(gòu)邊緣的保持方面取得了較好的處理效果．Sairam等[10]利用信息地圖技術(shù)確定樣本塊修復準則，通過紋理生成技術(shù)解決圖像丟失信息問題，取得了較好的修復效果．He?等[11]在KD-tree的基礎上進一步完善了塊匹配傳播效果，提高了算法運行效率．Li等[12]改進了置信度計算公式，并提出了一種修復塊相鄰區(qū)域內(nèi)的搜索方法，能有效縮小搜索范圍，提高運行效率．2013年，謝瓊等[13]提出了一種新的基于模式相似性的修復算法，利用了紋理的亮度變化規(guī)律和空間域的特性來確定最優(yōu)匹配塊，獲得了不錯的修復效果．Rodriguez-Sánchez等[14]利用角點冗余檢測，借助非下采樣輪廓波變換來改進置信度計算公式，并在獲取最優(yōu)匹配塊的過程中使用了累計色散的方法，改善了修復效果．

此外，Zhou等[15]根據(jù)已知的鄰域結(jié)構(gòu)信息，提出了一種自適應確定樣本塊大小的算法，提高了算法的自適應性．2012年，孟春芝等[16]對該算法進行了改進，通過計算基于破損區(qū)域領(lǐng)域中完好部分的梯度值變化來確定最優(yōu)樣本塊大小，提高了準確性，但算法需要考慮0°～360°梯度域數(shù)值，運算效率受到限制．為解決上述問題，本文提出一種基于改進SSIM算法的自適應樣本塊大小選取方法，在原有亮度、對比度和結(jié)構(gòu)3個模塊的指標的基礎上增加了梯度信息，以此來衡量結(jié)構(gòu)相似度．仿真實驗結(jié)果表明，本文方法可以獲得更加自然的結(jié)構(gòu)修復效果．

1?基于樣本塊修復算法

基于樣本塊的圖像修復算法主要包含以下3個步驟．

步驟1?確定待修復樣本塊的優(yōu)先級．

?(1)

?(2)

步驟2?搜尋最佳匹配塊并進行信息填充．

在信息完好區(qū)域?qū)ふ遗c待修補塊相似度最高的樣本塊，并將其復制到破損區(qū)域當中．

步驟3?更新置信度．

更新像素點的置信度，進行下一次迭代，直到圖像修復完成為止．

2?本文算法

傳統(tǒng)基于樣本塊的圖像修復算法，需要根據(jù)實驗結(jié)果手動調(diào)整樣本塊大小，以獲得最優(yōu)修復效果．樣本塊偏小，算法效率低，也不利于保持圖像的整體結(jié)構(gòu)；反之，容易出現(xiàn)結(jié)構(gòu)斷裂的現(xiàn)象，紋理修復效果不理想．此外，采用固定大小樣本塊對不同的結(jié)構(gòu)和紋理區(qū)域進行處理，缺乏適應性，當圖像結(jié)構(gòu)和紋理情況復雜時，不利于獲得理想的修復效果．為此，本文提出一種基于改進SSIM算法的自適應樣本塊大小確定方法，可以根據(jù)不同的結(jié)構(gòu)和紋理區(qū)域自適應選取樣本塊大小，提高了算法適應性，可以獲得理想的圖像修復效果．

2.1?結(jié)構(gòu)相似性度量

結(jié)構(gòu)信息能夠反映圖像之間的差異，可以用于圖像識別．其中，結(jié)構(gòu)相似度(SSIM)[17]可以獲取符合人眼視覺系統(tǒng)的圖像結(jié)構(gòu)信息，得到了廣泛應用．傳統(tǒng)SSIM定義為

?(3)

?(4)

?(5)

?(6)

2.2?樣本塊大小自適應選取

本文嘗試將待修復樣本塊大小選取問題轉(zhuǎn)化為結(jié)構(gòu)相似性度量問題，利用改進后的SSIM算法實現(xiàn)樣本塊大小的自適應選?。糞SIM算法通常利用結(jié)構(gòu)分量來表征局部區(qū)域的結(jié)構(gòu)差異，本文在原有SSIM算法的基礎上引入梯度信息，以實現(xiàn)圖像局部邊緣及紋理的量化表征．由于破損區(qū)域存在信息缺失，因此，本文利用破損塊對應的原圖像塊來計算相關(guān)梯度信息．

?(7)

?(8)

結(jié)合梯度信息，本文定義區(qū)域結(jié)構(gòu)相似度的?RSS為

(9)

當待修復區(qū)域的結(jié)構(gòu)變化比較單一時，相鄰尺寸樣本塊之間結(jié)構(gòu)結(jié)構(gòu)相似度較高，RSS值較大，此時應選取較大的樣本塊進行修復，以保證修復效率；而當待修復區(qū)域結(jié)構(gòu)信息比較復雜時，相鄰尺寸樣本塊之間的結(jié)構(gòu)相似度較低，RSS較小，此時應選取較小的樣本塊，以保證結(jié)構(gòu)的有效延續(xù)．為此，本文定義樣本塊大小選取方法為

?(10)

在實際修復過程中，當源匹配塊位于圖像邊緣時，此時可能存在樣本塊不完整的情況，為此，本文定義源匹配塊與待匹配塊之間的誤差限制準則為

?(11)

2.3?本文算法流程

本文算法流程如下．

步驟4?根據(jù)最小絕對差平方和算法(SSD)[2]在圖像信息完好區(qū)域搜索最優(yōu)匹配塊，計算匹配誤差．

3?實驗結(jié)果及分析

為了對算法性能進行比較，選取了幾幅具有不同結(jié)構(gòu)和紋理類型的自然場景圖像，利用Non-Local算法[18]、Parabola算法[19]和Meng算法[16]分別進行處理．Non-Local算法通過引入變分框架來對圖像進行修復；Parabola算法改進了置信度與數(shù)據(jù)項的權(quán)重系數(shù)和置信度更新公式；Meng算法運用梯度域進行自適應修復；其圖像效果分別如圖1所示．

從圖1可以看出，采用變分框架的Non-Local算法，雖然成功修復了海水輪廓，但由于樣本塊大小無法自適應選取，在連接處出現(xiàn)了折疊和模糊．Parabola算法雖然在一定程度上抑制了置值度函數(shù)迅速下降的情況，但當破損區(qū)域較大時，出現(xiàn)了明顯的斷層．Meng算法能夠自適應選擇樣本塊，修復效果優(yōu)于前面2種算法，但仍然存在人工痕跡．本文算法基于圖像結(jié)構(gòu)相似度，并結(jié)合梯度信息，海水紋理擴散更加合理，結(jié)構(gòu)修復效果也更加自然．

圖1?圖像Beach修復效果比較

圖2破損圖像包含大區(qū)域復雜結(jié)構(gòu)和紋理信息．從圖中可以看出，利用Non-Local算法的變分模型恢復的臺階邊緣不夠清晰；與之類似，Parabola算法在結(jié)構(gòu)傳播方面也存在問題；Meng算法依據(jù)梯度域評測圖像結(jié)構(gòu)相似度，在紋理和結(jié)構(gòu)保持方面不夠理想；而本文算法不僅完整的恢復了臺階結(jié)構(gòu)，紋理修復效果也更加自然合理，取得了理想的處理效果．

圖2?圖像Stairs修復效果比較

由表1可以看出，Non-Local算法的處理時間最短，本文方法其次，且明顯優(yōu)于另外2種算法；然而，利用Non-Local算法對結(jié)構(gòu)進行修復，容易出現(xiàn)模糊和斷層現(xiàn)象，相比之下，本文算法不僅運算速度較快，修復效果也更加自然合理，整體效果最優(yōu)．

表1?圖像修復時間

Tab.1?Time of image inpainting

4?結(jié)?語

本文提出了一種基于改進結(jié)構(gòu)相似度測量的自適應樣本塊圖像修復算法，可以根據(jù)圖像局部結(jié)構(gòu)信息，自適應確定樣本塊大小，提高了算法的適應性和修復效果．仿真實驗結(jié)果表明，本文算法對于復雜的結(jié)構(gòu)和紋理圖像，仍然能夠獲得理想的修復效果．

［1］ Luo K，Li D，F(xiàn)eng Y. Depth-aided inpainting for disocclusion restoration of multi-view images using depth-image-based rendering[J].：，2009，10(12)：1738-1749.

［2］ Criminisi A，Perez P，Toyama K. Object removal by exemplar-based inpainting[C]//2003. Wisconsin，USA，2003：721-728.

［3］ Xu Zongben，Sun Jian. Image inpainting by patch propagation using patch sparsity[J].，2010，13(9)：1200-1212.

［4］ Anamandra S H，Chandrasckaran V. Exemplar-based color image inpainting using a simple and effective gradient function[C]//. Las Vegas，USA，2010：140-145.

［5］ Li S，Zhao M. Image inpainting with salient structure completion and texture propagation[J].，2011，32(9)：1256-1266.

［6］ Cao F，Gousseau Y，Masnou S，et al. Geometrically guided exemplar-based inpainting[J].，2009，4(4)：1143-1179.

［7］ Smith L N，Elad M. Improve dictionary learning：Multiple dictionary updates and coefficient reuse[J].，2013，20(1)：9-28.

［8］ Huang J B，Kang S B. Image completion using planar structure guidance[J].，2014，33(4)：129-1-129-10.

［9］ Zhou Yatong，Li Lin. Research on weighted priority of exemplar-based image inpainting[J].，2012，29(1)：166-170.

［10］ Sairam V，Sarma R R，Balasubramanian S，et al. A unified framework for geometry and exemplar based image inpainting[C]//2. Paris，F(xiàn)rance，2014：511-515.

［11］ He Kaiming，Sun Jian. Computing nearest-neighbor fields via propagation-assisted KD-trees[C]//2012. Providence，USA，2012：111-118.

［12］ Li Zhangming，Hu Wenjin. A novel method for exemplar-based image inpainting[J].，2012，9(3)：761-769.

［13］ 謝?瓊，張紅英，彭?博. 基于模式相似性的圖像修復算法[J]. 現(xiàn)代電子技術(shù)，2013，36(2)：94-96.

Xie Qiong，Zhang Hongying，Peng Bo. Image inpainting algorithm based on pattern similarity[J].，2013，36(2)：94-96(in Chinese).

［14］ Rodriguez-Sanche Z，Garcfa J A，F(xiàn)dez-Valdivia J. Image inpainting with nonsubsampled Contourlet transform[J].，2013，34(13)：1508-1518.

［15］ Zhou H L，Zheng J M. Adaptive patch size determination for patch-based image completion [C] //201017. Hong Kong，China，2010：421-424.

［16］ 孟春芝，何?凱，焦青蘭. 自適應樣本塊大小的圖像修復方法[J]. 中國圖像圖形學報，2012，17(3)：337-341.

Meng Chunzhi，He Kai，Jiao Qinglan. Image completion method with adaptive patch size[J].，2012，17(3)：337-341(in Chinese).

［17］ Wang Z，Bovik A C，Sheikh H T，et al. Image quality assessment：From error cisbility to structural similarity [J].，2004，13(4)：600-612.

［18］ Vadim F，Gabriele F，Pablo A，et al. Variational framework for non-local inpainting[J].，2015，5：362-386.

［19］ Nan A，Xi X. An improved Criminisi algorithm based on a new priority function and updating confidence[C]//2014 7. Dalian，China，2014：885-889.

(責任編輯：王曉燕)

Image Inpainting Algorithm with Adaptive Patch Using SSIM

He Kai，Niu Junhui，Shen Chengnan，Lu Wenxia

(School of Electrical and Information engineering，Tianjin University，Tianjin 300072，China)

The current exemplar-based algorithms lack adaptability due to manually determining the size of block．In addition，using a patch with the constant size is not suitable to obtain the optimal effect in different structure and texture regions．To address this problem，this paper puts forward an adaptive patch size selection method using improved structure similarity(SSIM)．The gradient information is added to the traditional SSIM and is combined with the brightness，contrast ratio，and structure of patch to measure the structural difference．On this basis，the optimal size of patch in different structure or texture regions is determined，thus improving the adaptability，as well as the inpainting effect．The simulation results demonstrate the effectiveness of the proposed method even when complex structure or texture exists.

image inpainting；texture synthesis；adaptive patch；SSIM algorithm；gradient information

10.11784/tdxbz201704066

TP391

A

0493-2137(2018)07-0763-05

2017-04-23；

2017-09-26.

何?凱（1972—），男，博士，副教授

何?凱，hekai@tju.edu.cn.

國家自然科學基金資助項目(61271326).

the National Natural Science Foundation of China(No.,61271326).