改進TV-H-1模型的圖像修復方法

何仕文，劉　琳，張永強，楊劍哲，石大明，程丹松

(哈爾濱工業大學 計算機科學與技術學院，150001 哈爾濱)

?

改進TV-H-1模型的圖像修復方法

何仕文，劉琳，張永強，楊劍哲，石大明，程丹松

(哈爾濱工業大學 計算機科學與技術學院，150001 哈爾濱)

摘要:為改善現存圖像修復算法在修復時存在的“灰度跳變”現象，同時降低運行復雜度，提出一種基于偏微分方程模型(稱為Isophote-TV-H-1模型)和改進Criminisi算法的數字圖像修復算法.首先利用圖像分解模型(TV-H-1)獲得缺損圖像的結構部分和紋理部分；然后用Isophote-TV-H-1模型和改進的Criminisi算法分別對缺損圖像的結構部分和紋理部分進行修復；最后將修復后的結構部分和紋理部分進行疊加得到最終的修復結果.實驗結果表明，本模型與TV模型相比，能夠較好地修復缺損區域中的紋理信息；與Criminisi算法相比，本模型通過對相似度度量方法的改進，有效地抑制了圖像修復過程中的誤差傳播，并利用局部搜索(圖像局部相似性)來替代傳統的窮盡搜索，進而提高算法的效率.同傳統的基于圖像分解的圖像復原算法以及TV模型相比，本模型能解決“灰度跳變”問題，獲得更好的修復結果.

關鍵詞:全變分；TV-H-1；圖像分解；圖像修復;Criminisi算法

圖像修復(image inpainting)是計算機圖像處理中的一個熱點問題,是利用當前圖像中已知信息對圖像中缺損部分按照某種約束實現“合理”填充，使圖像恢復完整.該技術主要應用于文物保護和修復、圖像/視頻編碼及傳輸、游戲設計和電影特效制作等領域.圖像修復方法可以分為兩類[1]：一類是基于幾何結構(geometry-oriented)的方法; 另一類是基于紋理合成(texture-oriented)的方法.其中基于幾何結構的方法有文獻[2]提出的基于擴散理論的BSCB模型，該方法是沿修復邊界的等照度線方向來修復信息損失區域.此外文獻[3-4]將圖像去噪領域中的TV(total variational)模型、文獻[5]將Navier-stokes方程也應用到圖像修復領域.總體來說，基于幾何結構的模型是通過迭代求解偏微分方程來實現對圖像的修復，但是迭代求解偏微分方程時，只利用了缺損區域附近點的幾何結構信息和灰度信息，具有很強的局部性，所以該類算法只對圖像的小區域缺損(斑點、刮痕、覆蓋文字等)具有較好的修復效果；同時由于該類模型對修復區域的光滑性有較強的約束，所以會導致修復區域過于光滑，進而丟失圖像待修復區域中的紋理信息，這也局限了該類模型的應用范圍.而基于紋理合成方法則是依據一定的準則，在已知圖像區域(樣本區)搜索最佳匹配像塊來填充缺損區域，其中Criminisi算法[6-7]是最成功的算法之一.Criminisi算法利用待修復點鄰域的幾何結構信息來確定修復優先級，這使得該算法除了具有基于樣本塊紋理合成技術的修復效率和質量外，還可以保持缺損區域周圍的幾何結構.文獻[8-12]分別對Criminisi算法中的填充修復順序、優先權計算、置信度更新方式等問題進行了改進.由于對于每一個點的修復都需要在整個樣本區中搜索最佳匹配像塊，所以該類方法具有很好的全局性，即Criminisi算法對圖像缺損較大的區域修復效果較好，但是由于該類算法在圖像修復過程中可能利用原本缺損區域中的填充樣本來修復缺損區域，所以會導致誤差傳播，降低圖像保持幾何結構的能力.由于自然圖像中通常同時包含結構部分(圖像中的光滑部分和邊緣)和紋理部分，所以針對圖像缺損區域修復的理想狀況是在修復圖像結構部分的同時也能夠有效地修復區域內的紋理部分[13].基于圖像分解的圖像修復技術[13-17]首先通過圖像分解方法將缺損圖像分解為結構部分和紋理部分；然后利用基于偏微分方程模型的方法來修復結構部分、利用紋理合成方法來修復圖像的紋理部分；最后通過疊加兩部分的修復結果，獲得較高質量的修復圖像.

但是以上方法在修復時會存在“灰度跳變”和運行復雜度高等問題，所以本文在現有圖像修復技術的基礎上，提出了一個基于改進TV-H-1模型的改進圖像修復方法.該方法首先利用文獻[18]的圖像分解算法對缺損圖像進行分解，獲得圖像的結構部分和紋理部分;然后對結構部分和紋理部分分別進行修復：在對結構部分進行修復時，為了解決TV模型在修復圖像過程中會產生“灰度跳變”的現象，提出基于偏微分方程(PDEs)和等照度線方向的圖像修復方法，記為Isophotes-TV-H-1模型，對結構部分進行修復，同時為了解決Isophotes-TV-H-1模型計算量較大的問題，利用快速行進法(fast march method)對圖像缺損區域進行預填充，從而減少迭代次數，提高Isophotes-TV- H-1模型的效率；在進行紋理部分修復時，根據自然圖像具有很強局部相似性的特點，對Criminisi算法進行兩方面的改進： 1)利用局部搜索代替窮盡搜索，進而減少搜索時間，提高算法的效率；2)對Criminisi算法中待修復目標塊與參與匹配的樣本塊之間的相似度進行改進，使得尋找到的最佳匹配塊變得更加合理.通過實驗對比可知，本文提出的模型相比于TV修復模型、Criminisi算法和基于圖像分解的圖像修復技術算法[16]具有更好的修復效果.

1本文模型

本文在對傳統圖像修復算法進行分析后，提出了基于偏微分方程模型(稱為Isophote-TV-H-1模型)和改進Criminisi算法的數字圖像修復方法.

1.1圖像分解原理

對于一幅圖形f，一般認為圖像可以分解為

f=u+v.

式中:u∈BV(Ω)主要包含圖像f的低頻信息，即結構部分;v∈BV(Ω)包含圖像f的高頻信息，如圖像中的紋理、振蕩、噪聲部分.針對v部分，在文獻[20]中定義了G空間概念，表達式為:

利用最速下降法求解該能量泛函的最優解，假設u為能量泛函的最優解，w∈BV(Ω),令u1=(u+εw)∈BV(Ω)，那么當ε=0時，u1為式(1)的最優解，對E(u1)關于ε求極值點，可得

(2)

對式(2)用變分原理及Green公式可變成如下的初邊值問題:

(3)

通過Gauss-Jacobi迭代算法求解式(3)的解，可獲得圖像的結構部分u.

1.2結構部分修復算法

1.2.1基于快速行進法的圖像預填充

對于結構部分，由于結構部分中只存在光滑區域和邊緣，所以結構部分可以視為一個幾乎處處連續的函數，根據Taylor展開式定理，I(y)在x點處的展開式為

舍去高階項o(|y-x|2)即可以得到如下結果

(4)

(5)

式中W(p,q)為權重.式(5)的含義為：缺損點P處的初始值為其ε鄰域初始值的加權平均.為了保證缺損區域點的初始值按照由邊界向內部逐漸延伸順序，本文借鑒求解水平集函數的快速行進法[21](fast march method).本文算法與文獻[21]方法的不同之處:1)文獻[21]的更新算法并不能完全保證修復順序是由邊界向內部延伸;2)本文算法和文獻[21]的缺損值估計方法也不相同，在本文中權重W(p,q)主要考慮ε鄰域內已知點q處的T(q)的大小，即T(q)越大越接近缺損區域，其權重越大，反之權重越小，它的表達式如

基于以上不同，本文對T的更新方法進行了修改，修改后的表達式如

式中:qw、qs、qe、qn分別為q的四鄰域點,solve(·,·)用于確定q點處T的可能更新值.

1.2.2基于改進TV-H-1模型的圖像修復

分析TV模型對應PDE的數值差分格式，對于缺損區域中的點(i,j)，其值的更新是鄰域4個點p∈{(i+1,j),(i-1,j),(i,j+1),(i,j-1)}值的加權組合，并且相對應的權值wp分別為

即數值同梯度值呈反比，而TV-H-1模型對于缺損區域待修復點(i,j)，其值的更新是由其鄰域12個點值的加權組合，通過分析可知：由于TV模型只利用其鄰域4個點更新中心點信息，而TV-H-1模型利用其鄰域12個點的信息來更新中心點，所以TV-H-1模型的修復結果在缺損區域的邊界具有更好的連接性，從而緩解了“灰度跳變”現象.對于圖像的已知區域，本文希望能夠盡量保持不變，但是無論是TV模型還是TV-H-1模型，由于每個點的值都會用周圍鄰域點來進行加權更新，所以會使圖像變得模糊.因此本文對TV-H-1模型進行改進，改進后的表達式為

(6)

根據文獻[3]可以得到式(6)的不動點迭代 (fixed-point iteration)離散差分格式為

把它改寫為Gauss-Jacobi迭代形式后的表達式如

(7)

當λ=0時，表達式(7)為式(6)的Gauss-Jacobi迭代格式.

盡管該改進模型能夠在解決“灰度跳變”問題的同時保持已知信息，但是該模型中的加權權重只與梯度信息相關，并沒有利用等照度線(isophote)的方向信息，所以為了更有效地傳播信息，并模擬人工修復圖像的工作機制，本文將向量Ip與等照度線方向的夾角考慮到結構修復模型，從而使信息沿著等照度線方向傳播.修改權重后的表達式如

(8)

綜上所述，本文提出的Isophote-TV-H-1模型具有以下優點：1)相比于TV模型，利用更多鄰域點信息，解決了“灰度跳變”問題；2)能夠保持已知區域信息；3)引入等照度線方向信息，模擬人工修復的工作機理，提高信息的傳播效率.同時針對Isophote-TV-H-1模型計算量大的問題，本文在對結構部分進行直接修復之前，利用改進的快速行進法對缺損區域值進行預估，這樣可以明顯減少式(8)的迭代次數.

1.3紋理部分修復算法

1.3.1圖像局部相似性

首先利用統計的方法，對Berkeley大學圖像數據庫BSDS300中圖像的局部相似性進行分析，具體過程如下：

1)確定塊的大小(2pSize+1)×(2pSize+1)，在本文實驗中pSize = 10;

2)在每幅圖像中隨機選擇塊的中心坐標，記為(x0,y0)，確定大小為(2pSize+1)×(2pSize+1)的塊patch;

3)對每一幅原圖像、結構圖像及紋理圖像，取所有可能的大小為(2pSize+1)×(2pSize+1)的圖像塊Mpatch，Mpatch的中心坐標的距離為(x,y)，計算塊patch和Mpatch塊的Manhattan距離，并計算兩個塊中心坐標的Euclidean距離Dis;

4)計算各中心距離為Dis的塊patch和Mpatch的平均距離.

利用上述統計方法，本文統計原圖像、結構圖像及紋理圖像的中心距離-圖像塊平均距離的關系如圖1所示，對圖1進行分析可以得到如下結論：1) 原圖像、結構圖像和紋理圖像的中心距離在0~150時，塊間平均距離較小；當超過該距離之后，塊間平均距離逐漸增大，這說明自然圖像具有很強的局部相似性；2) 當3類圖像在中心點間距為300~400之間時，塊間平均距離有下降的趨勢，這說明自然圖像不僅具有局部相似性，同時也具有全局冗余，即相似塊分布在整幅圖像中.對于這兩個結果的可能解釋是：在獲取的自然圖像中，存在很多面積較大的物體，同時在同一場景中可能存在多個相似物體，并且每個物體間相隔一段距離.

圖1　中心距離-圖像塊平均距離

1.3.2基于局部搜索的Criminisi算法

通過對統計原圖像、結構圖像及紋理圖像的中心距離-圖像塊平均距離的關系的分析，本文獲得圖像具有局部相似性的結論，因此對Criminisi算法中的搜索策略進行改進，利用紋理圖像的局部相似性，在搜索最佳匹配塊時，利用局部搜索方法替代全局搜索，在保證修復效果的前提下提高Criminisi算法的效率.在本文實驗中，只在距離缺損區域邊界為B(B=30)范圍內進行最佳匹配塊的搜索.此外，由于馬爾可夫隨機場模型是紋理圖像的一種客觀認識，它體現了紋理的局部性和穩定性，即一個像素點或像素塊的亮度都可以由它們的鄰域像素唯一確定，而與圖像的其他部分無關[12].針對Criminisi算法中，每個已知點對相似度的貢獻率都是完全相同的情況，本文把其改為與距離相關的加權相似度貢獻方式，其相似度定義為

式中：dist(xp,p)表示點xp距離中心點p的距離，在本文中距離度量使用Manhattan距離；xp∈(ψp∩Φ)表示xp為ψp中的已知點.相比于Criminisi算法中的相似度，在本文定義的相似度計算中，特征點距離中心點p越近，對相似度的影響越大，否則會變得越小.

2實驗結果

本文分別對Lena、 Barbara等圖像進行圖像修復實驗，并將實驗結果與TV修復模型、Criminisi算法和文獻[16]算法的修復結果進行對比.實驗結果分別如圖2，3所示，在圖2中，待修復圖像(Lena)包含光滑區域，同時也包含豐富的紋理，并且缺損區域1,4位于光滑區域，缺損區域2,3位于紋理區域.觀察缺損區域2,3的修復結果，TV模型的修復結果過于光滑，丟失了紋理信息，而Criminisi算法、文獻[16]和本文模型較好地修復了缺損區域中的紋理；但是文獻[16]的修復結果在缺損區域和已知區域的邊界存在比較明顯的“灰度跳變”現象，如區域2，同樣的現象也出現在缺損區域1.Criminisi算法在區域2和4的修復結果上，由于誤差放大，修復區域結果也并不理想，而本文方法則取得了較好的處理結果.對圖3中結果進行分析可得，TV模型對于缺損區域的邊緣修復效果較差；而Criminisi算法、文獻[16]算法、本文模型對缺損區域內的邊緣有更好的修復效果；然而本文模型相比于文獻[16]的算法，對缺損區域內的邊緣有更強的修復能力；與Criminisi算法相比，盡管Criminisi算法能夠較好地修復缺損區域中的邊緣和紋理，但是由于誤差的傳播，該算法在修復缺損區域過程中會引入“新”的邊緣；而本文模型則能夠較好地控制誤差傳播，獲得較好的修復結果.觀察其他圖像的處理結果也可以得到同圖2，3所示類似的結論.

圖2　Lena對比試驗

為了精確地評價各模型的修復效果，本文分別計算每幅圖像修復后的信噪比(signal noise ratio, SNR)和峰值信噪比(peak signal noise ratio,PSNR)，SNR和PSNR的定義為

式中：M、N分別為圖像的行數和列數；u0、u分別為修復前、后的圖像.SNR和PSNR的比較結果見表1, 2.從表1, 2中可以看出本文模型具有最高的SNR和PSNR.表3為TV模型、Criminisi算法、文獻[16]算法和本文模型修復圖像所用時間的比較，從表3中可以看出本文的Isophotes-TV-H-1模型在修復紋理圖像方面比Criminisi算法更有效率，平均能提高40%，同時本文模型在處理結構圖像方面也具有較高的修復效率.

圖3　Barbara對比試驗

表1TV模型、Criminisi算法、文獻[16]、本文模型SNR對比結果

圖像TVCriminisi文獻[16]本文模型Lena52.602949.751051.849854.4841Wall15.942021.728716.768323.4339Baboon31.649324.825531.373932.3833Barbara48.846835.278445.856149.2610Building37.677141.887339.976342.7213Monkey27.125822.951927.026327.2088

表2TV模型、Criminisi算法、文獻[16]、本文模型PSNR對比結果

圖像TVCriminisi文獻[16]本文模型Lena42.894541.660042.569343.7127Wall24.768027.280525.125928.0349Baboon32.766629.931632.649833.2193Barbara37.354633.454837.536438.0575Building36.389038.213937.388538.5802Monkey33.303932.048733.248633.4614

表3　TV模型、Criminisi算法、文獻[16]、本文模型修復時間的對比結果

注：cpu處理時間為s.

3結論

1)通過實驗對比可知，與TV模型相比，本文模型能夠較好地修復紋理缺損區域中的紋理；與Criminisi算法相比，本文模型通過對相似度度量方法進行改進，能夠有效抑制圖像修復過程中的誤差放大，同時利用局部搜索策略替代Criminisi算法中的窮盡搜索，進而提高算法的處理效率.

2)通過同文獻[16]算法和TV模型的實驗對比，可以看出本文方法能夠緩解上述算法處理時出現的“灰度跳變”問題，并取得較好的修復結果.

參考文獻

[1] ARIAS P, FACCIOLO G, CASELLES V, et al. A variational framework for exemplar-based image inpainting[J]. International Journal of Computer Vision, 2011, 93(3): 319-347.

[2] BERTALMIO M, SAPIRO G, CASELLES V, et al. Image inpainting[C]//Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press/Addison-Wesley Publishing Co., 2000: 417-424.

[3] SHEN Jianhong, CHAN T F. Mathematical models for local non-textureinpaintings[J]. SIAM Journal on Applied Mathematics, 2002, 62(3): 1019-1043.

[4] RUDIN L I, OSHER S, FATEMI E. Nonlinear total variation based noise removal algorithms[J]. Physica D: Nonlinear Phenomena, 1992, 60(1/2/3/4): 259-268.

[5] BERTALMIO M, BERTOZZI A L, SAPIRO G. Navier-stokes, fluid dynamics, and image and video inpainting[C]// Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York: IEEE, 2001, 1(1): 355-362.

[6] CRIMINISI A, PEREZ P, TOYAMA K. Object removal by exemplar-based inpainting[C]// Proceedings 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York: IEEE, 2003, 2(2): 721-728.

[7] CRIMINISI A, PéREZ P, TOYAMA K. Region filling and object removal by exemplar-based image inpainting[J]. IEEE Transactions on Image Processing, 2004, 13(9): 1200-1212.

[8] SUN Jian，YUAN Lu，JIA Jiaya，et al. Image completion withstructure propagation[J]. ACM Transactions on Graphics，2005，24(3)：861-868.

[9] 翟東海,肖杰,魚江,等. 基于自適應模板的圖像修復算法[J]. 計算機應用,2013,33(10):2891-2894.

[10]王梅,趙彩,郭勇. 基于重構樣本區域的數字圖像修復算法研究[J]. 軟件導刊,2014,13(2):71-73.

[11]張巧煥,唐向宏,任澍. 區域自適應的圖像修復算法[J]. 計算機工程與應用,2013,49(21):160-163,171.

[12]張申華,王克剛,祝軒. 局部特征信息約束的改進Criminisi算法[J]. 計算機工程與應用,2014,50(8):127-130.

[13]賈淵，劉鵬程，牛四杰. 偏微分方程圖像處理及程序設計[M]. 北京：科學出版社，2012：160-176.

[14]STARCK J L, ELAD M, DONOHO D L. Image decomposition via the combination of sparse representations and a variational approach[J]. IEEE Transactions on Image Processing, 2005, 14(10): 1570-1582.

[15]沈民奮，陳家亮，代龍泉,等. 基于圖像分解和圖像分割的數字圖像修復[J]. 電子測量與儀器學報，2009,23(9)：11-17.

[16]林云莉，趙俊紅，朱雪峰,等. 基于圖像分解的圖像復原技術[J]. 計算機工程，2010,36(10)：187-192.

[17]王阿川,侯暢,宋宏光,等. 基于圖像分解的單板節子缺陷圖像修補方法研究[J]. 林業機械與木工設備,2013,41(8):50-54.

[18]OSHER S, SOLé A, VESE L. Image decomposition and restoration using total variation minimization and the H-1norm[J]. Multiscale Modeling & Simulation, 2003, 1(3): 349-370.

[19]MEYER Y. Oscillating patterns in image processing and nonlinear evolution equations: the fifteenth Dean Jacqueline B. Lewis memorial lectures[M]. New York: American Mathematical Society, 2001.

[20]VESE L A, OSHER S J. Modeling textures with total variation minimization and oscillating patterns in image processing[J]. Journal of Scientific Computing, 2003, 19(1): 553-572.

[21]TELEA A. An image inpainting technique based on the fast marching method[J]. Journal of Graphics Tools, 2004,9(1): 23-24.

[22]徐晨，李敏，張維強，等. 后小波與變分理論及其在圖像修復中的應用[M]. 北京：科學出版社，2013:183-184.

[23]CHAN T F, SHEN Jianhong. Non-textureinpainting by curvature-driven diffusions[J]. Journal of Visual Communication and Image Representation, 2001, 12(4): 436-449.

(編輯張紅)

An improved image inpainting method based on TV-H-1model

HE Shiwen, LIU Lin, ZHANG Yongqiang, YANG Jianzhe, SHI Daming, CHENG Dansong

(School of Computer Science and Technology, Harbin Institute of Technology, 150001 Harbin, China)

Abstract:Intensity discontinuity and high computational complexity are drawbacks in some existing methods of image inpainting. To tackle these problems, a method based on PDE model(Isophote-TV-H-1model) and improved Criminisi algorithm is proposed in this paper. Firstly, the damaged image is decomposed into cartoon and texture with the TV-H-1model. Secondly, the Isophote-TV-H-1model and the improved Criminisi algorithm are used to recover the cartoon and texture of the damaged image, respectively. Finally the recovered texture is superimposed on the recovered cartoon to get the result image. The experimental results demonstrate that the proposed model recovers the texture of the damaged region better than the TV model. Comparing with Criminisi algorithm, the proposed model suppresses the error propagation through improving the similarity measurement method, as well as improves the efficiency by employing the local search.

Keywords:total variation; TV-H-1; image decomposition; image inpainting; criminisi algorithm

中圖分類號:TP391

文獻標志碼:A

文章編號:0367-6234(2016)02-0167-06

通信作者:程丹松, cdsinhit@hit.edu.cn.

作者簡介:何仕文(1989—)，男，碩士研究生；石大明(1971—)，男，教授，博士生導師.

基金項目:國家自然科學基金 (61440025，61402133); 國家博士后科學基金(20100480998); 國防科工局重大專項(公開)(50-Y20A08-0508-15/16); 哈爾濱市科技創新人才專項資金 (2013RFQXJ110).

收稿日期:2014-09-23.

doi：10.11918/j.issn.0367-6234.2016.02.029