基于非局部矩陣填充的文物修復技術研究

楊國亮 魯海榮 豐義琴 唐 俊

(江西理工大學電氣工程與自動化學院 江西 贛州 341000)

?

基于非局部矩陣填充的文物修復技術研究

楊國亮 魯海榮 豐義琴 唐 俊

(江西理工大學電氣工程與自動化學院 江西 贛州 341000)

文物圖像包含了豐富的內容，使用傳統偏微分方法很難有效地恢復文物圖像。為了有效恢復原圖像，提出一種基于非局部矩陣填充的文物修復方法。該算法充分利用圖像的冗余信息，在搜索窗口內，通過比較像素點周圍一個矩形鄰域內的多個像素點的相似性，找到一定數量的相似塊轉換為列向量，構成相似塊組矩陣。由于相似塊組矩陣為低秩或者近似低秩的，再通過矩陣填充的原理對損壞像素點進行填充修復。對于文物圖像中出現的不同比例像素點丟失、有劃痕、有文字破損的修復實驗結果表明，該算法能夠很好地保留結構細節信息，擁有較好的視覺特性，使目標輪廓邊緣特征清晰，有效地恢復出文物圖像的原貌，具有良好的修復能力。

矩陣填充 非局部 相似塊 低秩

0 引 言

計算機技術的快速發展，促使了信息化時代的加速進步。近年來，隨著數字圖像應用的日愈廣泛，數字圖像領域逐漸發展了新型的圖像復原技術。

在文物方面，由于歷史原因和許多不可抗拒的因素，許多出土的文物會存在物理和化學上的反應，導致出現在我們面前的文物是缺失、不完整的。文物的缺失和不完整，影響著文物的交流與欣賞，更為重要的是沒能保護祖先留給我們的歷史文化遺產。

長期以來，文物的修復工作主要是由文物工作者進行手工修復。人為手工修復需要工作者具有很高的文物方面的背景知識，憑借自己豐富的經驗和感知力對文物進行修復，這種修復方式一旦完成，其修復結果很難再次更改。同時，修復的結果還與修復工作者個人的審美觀點和認知有關系，這樣，不同的工作者對文物的修復結果也是不一樣的。但是，借助數字圖像修復技術可以很好地解決這一困境。數字圖像修復技術不但可以極大地縮短人工修復周期，而且很大程度上防止了手工修復過程中對文物產生的再次傷害，還能避免人工修復主觀因素的影響，盡可能讓修復的文物信息更加貼近真實，展現出文物的本來面貌。

近些年來，針對圖像的修復問題主要集中在基于偏微分方程PDE、紋理合成方法及其混合的方法。Chan等人提出的整體變分TV(Total Variation)模型也是基于各向異性擴散的，并且它對尖銳的邊緣有很好的修復效果。但該方法在圖像的平滑區域會產生階梯效應，不能滿足人們的視覺連通性準則。文獻[2]提出了基于曲率驅動擴散CDD(Curvature Driven Diffusions)的修復模型，它利用修復點的曲率信息，使用和曲率相關的遞增函數，從破損區域邊緣向內部修復圖像。該方法雖然能夠對較大破損區域進行修復，但是容易使圖像造成一定程度的模糊。上述兩種模型都是利用圖像的邊界梯度來定義圖像的能量函數，從而利用泛函數分析法來求其最小值，所以這兩種模型都稱為偏微分方程的方法。基于偏微分方程的方法是根據圖像中待修復區域的邊緣信息，利用熱擴散機制沿等照線的方向將已知的信息擴散到待修復的區域中。

隨著壓縮感知在圖像處理領域的發展，近年來，基于稀疏表示的圖像修復方法也得到了重視。文獻[3]通過輸入圖像的有效數據和大量樣本來訓練字典，將字典和數據作為先驗知識來對圖像進行修復。該方法需要訓練大量圖像樣本，計算效率不高。文獻[4]把快速算法與基于稀疏表示的圖像修復算法相結合,可以有效地修復小塊缺失紋理的區域。文獻[5]提出了結構稀疏的圖像修復方法，同時考慮了圖像的幾何結構和紋理信息。然而，上述方法并沒有考慮圖像的非局部自相似性和充分利用圖像的相關信息，對先驗信息的表述能力有限。

矩陣填充MC(Matrix Completion)理論[6,7]是繼壓縮感知、稀疏表示后又一熱門研究方向，它旨在將一個低秩的、不完整的矩陣，利用元素間的相關性，完美地恢復出來。而在文物修復中，待修復文物正是由于出現局部的缺失、損壞或者污損，需要使用圖像修復技術進行修復。本文充分利用圖像的冗余信息，將非局部的思想引入到文物修復中，在搜索窗口內，通過比較像素點周圍一個矩形鄰域內的多個像素點的相似性，而非單個像素點的相似性，找到最為相似的一定數量的相似塊，從而構成相似塊組矩陣；再利用矩陣填充的原理對其破損區域進行修復。這樣，本文把非局部的思想和矩陣填充的方法聯合起來進行文物的修復。

本文算法整體流程如圖1所示。

圖1 整體算法流程圖

1 矩陣填充

矩陣填充技術主要用來解決通過矩陣中的已知數據來恢復其未知或者缺失的數據。它是一個非適定性的問題，如果在沒有額外信息調節的約束下，填充的結果有無數多個。然而，當觀測矩陣是低秩或者近似低秩時，則可以使觀測矩陣精確重構出原始矩陣。

當數據矩陣D中含有丟失元素時，可以通過數據矩陣中低秩結構來恢復出所有元素。假設觀測數據矩陣D=m×n，則MC優化模型[7]可以描述為如下問題：

(1)

其中，Ω是矩陣M中被觀察到的元素位置的集合，A為待重建的低秩矩陣，PΩ為一線性投影算子，即：

(2)

由于矩陣的秩函數是非連續、非凸的，直接求解秩的最小化問題比較困難。因此，問題是一個NP難問題，無法直接求解。然而Candes等[8]證明，矩陣填充并不是一個病態問題，問題可以通過將秩松弛到矩陣的核范數來近似求解，即得到凸優化問題：

(3)

其中，E表示在觀測矩陣D中未知的元素，把它簡單設置為0，τ是一個正則化參數。

MC的問題與魯棒主成分分析RPCA問題比較類似，很自然會考慮使用增廣拉格朗日ALM方法來有效求解MC問題，通過構造增廣拉格朗日函數對凸優化問題進行求解秩范數。

(4)

然后采用非精確拉格朗日乘子法求解MC問題，在最小化L(A,E,Y)更新E的時候采用PΩ(E)=0這個約束條件。每一步通過最小化該拉格朗日函數，使用交替方向法求解A、E、Y，則式(4)最小值的求解過程可以轉換為下列算法流程：

算法1:矩陣填充方法Input:輸入觀測矩陣1.初始化μ0=0.1,τ=10,tol=10-6 Y0=zeros(size(D))E0=zeros(size(D)),k=0,ρ>12.Whilenotconvergeddo3.(U,S,V)=svd(D-Ek+1μkYk)4.Ak+1=UΘτ/μk(S)VT,其中,Θτ/μk為奇異值收縮算子5.Ek+1=PΩ(D-Ak+1+1μkYk),其中,Ω是矩陣M中未被觀察到的元素位置的集合6.Yk+1=Yk+μk(D-Ak+1-Ek+1)7.μk+1=ρμk8.k=k+19.EndwhileOutput:A

2 非局部矩陣填充

在自然圖像中，往往會存在這樣的一些圖像塊，雖然它們處在空間域的不同位置，但是它們彼此之間在結構細節部分卻存在一定的相似性，我們稱這種相似性為非局部結構自相似性。

在圖像塊中尋找相似塊時，如果在整個圖像中進行尋找，則算法的計算時間會比較長。這樣，考慮到算法性能和耗費時間問題，選擇限制搜索范圍，改為在一定大小的搜索窗口中進行相似塊的尋找。將找到的相似塊轉化為列向量，組成一個新的相似塊組矩陣。由于相似塊組的每列都是近似相似的，所以這個相似塊組矩陣為低秩或者近似低秩的，則可以利用圖像塊之間的結構相似性特點，通過矩陣填充的方法對缺失部分數據進行填充。

圖2 非局部尋找相似塊

3 算法實現

對于文物圖像的修復可以分為以下四步：

第一步建立搜索窗口。以圖像中的某一個像素點為中心建立大小為30×30的搜索窗口。

第二步在當前搜索窗口中計算相似塊矩陣。對缺失圖像當前窗口進行分塊，利用塊匹配法對圖像塊進行相似塊匹配，取最為相似的前60個相似塊，將匹配后得到的相似塊列向量堆疊成圖像的相似塊組矩陣Dk。

第三步對相似塊組矩陣進行矩陣填充。采用矩陣填充的方法修復受損區域，從而得到恢復后的數據矩陣Dk。

第四步聚合。對缺失圖像中所有搜索窗口，重復第二步和第三步后得到所有恢復后的圖像塊矩陣，然后對恢復后的所有圖像塊矩陣進行聚合就可以獲得修復后的圖像。

算法流程：

算法2:對輸入受損文物圖像進行修復1.輸入待修復文物圖像D;2.建立搜索窗口,在搜索窗口內對Dk分塊并進行相似塊匹配,得到相似塊組矩陣Dk=[Dk1,Dk2,…,Dkm];3.Dk→算法1(對每個相似塊組進行算法1操作);4.對恢復出的相似塊進行聚合,輸出修復后圖像。

本文算法的軟件編程方式采用Matlab編程，其中較為核心的步驟在于矩陣填充中核范數子問題的求解。本文采用非精確拉格朗日乘子法求解，相比于精確拉格朗日乘子法速度更快。在求解過程中采用奇異值分解，對分解出的特征值收縮，重構后的值即為核范數的解。

核心代碼如下：

for k = 1:iterations

%% Step1,update A

V = P.*M-X + (1/mu)*Y;

[U,SigmaY,V] = svd(full(V),‘econ’);

SigmaX = sign(SigmaY).*max(abs(SigmaY)-tau/mu,0);

X2 = U*SigmaX*V′;

A = X2;

%% Step 2,update E

old_E = E;

E = R.*(P.*M-A + (1/mu)*Y);

%% Step 3,update Y,mu

Y = Y + mu*(P.*M-A-E);

mu =ρmu

%% Check stopping criteria

stop_vals(k,1) = norm(P.*M-A-E,‘fro’) / norm(M,‘fro’);

if ( stop_vals(k,1) <= tol)

break;

end

end

4 實驗及結果分析

本實驗的運行平臺為Intel Duo e7500雙核處理器、主頻為2.93 Ghz、內存為2 GB的臺式電腦，使用Windows XP操作系統，通過Matlab R2010a編程實現。

為了衡量經過修復后的圖像品質，通常參考峰值信噪比PSNR和結構相似指數SSIM來衡量算法的去噪效果是否令人滿意。PSNR值越大，代表失真越少，修復效果越好。SSIM取值范圍為0到1之間，其值越大越好，值越大，說明兩幅圖像的結構越相似。

為了驗證本文提出的基于非局部矩陣填充的文物修復方法，采用釋迦牟尼的不同畫像作為測試圖片，圖像來源于網絡，大小都為256×256。對文物圖像進行不同比例的像素丟失修復、有劃痕形式的破損修復和文字去除修復這三個方面的實驗，并采用傳統的TV方法、CDD方法和矩陣填充的方法進行實驗對比。

4.1 不同比例的噪聲點修復

圖 3為原始文物圖像丟失10%像素后通過使用不同方法修復得出的結果圖。圖 3(a)為原始圖；圖 3(b)丟失10%的像素，紋理信息已被損壞，破損程度較為輕微，PSNR=34.066，SSIM=0.189；圖 3(c)為TV方法修復效果，PSNR=29.612，SSIM=0.208；圖 3(d)為CDD修復效果圖，PSNR=43.295，SSIM=0.976；圖 3(e)為MC修復效果圖，PSNR=43.923，SSIM=0.975；圖 3(f)為本文修復效果圖，PSNR=46.241，SSIM=0.990。從實驗結果可以看出，本文算法要比TV、CDD和MC方法PSNR值分別高出16.629、2.946和2.318，SSIM值分別高出0.782、0.014和0.015。除了TV方法不能有效修復圖像外，其他幾種方法修復效果都還不錯。然而本文方法PSNR和SSIM值都要比其他幾種方法的值要高，能夠很好恢復出原始圖像。

圖3 丟失10%的像素不同修復方法的對比

為了更好體現本文算法的修復效果，再對原始文物圖像丟失70%像素做實驗進行對比。圖 4(a)為原始圖；圖 4(b)丟失70%的像素，紋理信息損壞嚴重，破損程度較高，肉眼已無法看清原始圖像的輪廓，PSNR=25.614，SSIM=0.032；圖 4(c)為TV方法修復效果，PSNR=24.095，SSIM=0.356；圖 4(d)為CDD修復效果圖，PSNR=33.194，SSIM=0.719；圖 4(e)為MC修復效果圖，PSNR=33.169，SSIM=0.619；圖 4(f)為本文修復效果圖，PSNR= 35.682，SSIM=0.819。從實驗結果可以看出，TV方法對于不同比例像素點的修復沒有效果；在高比例像素點丟失的情況下，本文方法仍然能夠有效恢復出原始圖像。本文方法的PSNR值要高出CDD、MC方法分別為2.489、2.514，SSIM值要分別高出0.1、0.2。從人眼視覺效果可以看到，本文方法的修復效果圖更為平滑，紋理結果保持效果更好；而CDD方法未能有效修復，噪聲點較多，邊緣還有未能修復的像素點；MC方法也比較模糊，結構紋理丟失嚴重。從該實驗可以看出，經過本文算法的修復，仍能達到人眼可以接受的狀態，能夠有效修復高比例的像素丟失，可以看到較為清晰的邊緣以及豐富的紋理，具有很好的保持結構優勢。

圖4 丟失70%的像素不同修復方法的對比

4.2 有劃痕形式的破損修復

圖 5為劃痕修復實驗。圖 5(a)為原圖；圖 5(b)為有劃痕圖，上面的劃痕損壞嚴重，紋理信息丟失，視覺效果較差，PSNR=31.014，SSIM=0.277；圖 5(c)為TV方法修復效果圖，PSNR=31.642，SSIM=0.634；圖 5(d)為CDD方法修復效果圖，PSNR=38.131，SSIM=0.925；圖 5(e)為MC方法修復效果圖，PSNR=37.923，SSIM= 0.819；圖 5(f)為本文算法，PSNR=41.271，SSIM=0.958。從圖中可以看到，TV方法對于這些劃痕不能修復，人眼可以很明顯地看到還有劃痕。相對于TV方法，CDD方法有了很明顯的改善，能夠很好地去除劃痕，但對于邊界的修復效果不佳，還能看到很明顯的劃痕信息。MC方法相對于CDD方法來說效果要差，還有一些很明顯的劃痕不能去除。而本文算法可以把劃痕較好地修復，從而恢復出原圖像；對于紋理信息豐富的區域，也能夠較好修復劃痕，保持原有的結構信息。從實驗結果數據來看，本文算法的PSNR和SSIM值也是對比方法中最高的，能夠較好地修復劃痕。

圖5 不同方法劃痕修復效果圖

4.3 文字去除修復

為了驗證本文算法的文字去除性能，同樣，我們采用TV、CDD和MC方法進行對比。圖 6(a)為原圖；圖 6(b)為有文字圖，文字區域圖像的紋理信息被覆蓋，破損程度較高，PSNR=37.064，SSIM=0.843；圖 6(c)為TV方法修復圖，PSNR=42.340，SSIM=0.960；圖 6(d)為CDD方法修復圖，PSNR=46.595，SSIM=0.986；圖 6(e)為MC方法修復圖，PSNR=44.877，SSIM=0.968；圖 6(f)為本文算法，PSNR=47.668，SSIM=0.991。從實驗得到的數據結果中可以看到，本文算法修復圖像得到的PSNR和SSIM值在對比方法中是最高的。再通過實驗局部放大的結果可以看到，TV方法修復的的結果會模糊化，CDD方法在人頭邊緣有結構的丟失，使用MC方法在去除文字后有一個很明顯的文字輪廓。而本文方法既可以較好去除文字，且能夠很好保持圖像的邊緣結構，視覺效果更好。

圖6 文字修復實驗對比效果圖

5 結 語

本文將非局部均值引入到矩陣填充的修復算法中，充分利用圖像的冗余信息，在搜索窗口內尋找相似度較高的相似塊，從而轉為列向量構成相似塊組矩陣，利用矩陣填充的原理來修復圖像。通過在不同比例像素的丟失、有劃痕和有文字文物圖像上分別做實驗，并與其他幾種算法進行對比，可以看出：本文算法能夠最大限度保持圖像的基本信息和結構特性，獲得較高的PSNR和SSIM值，在一定程度上可以很好保證恢復圖像取得較高的視覺質量。同樣，本文方法也可以擴展到視頻圖像中污點的去除，以及舊照片、影視特技應用中。

[1] Chan T F，Shen J H.Mathematical Models For Local Nontexture Inpaintings[J]. SIAM Journal on Applied Mathematics,2002, 62(3):1019-1043.

[2] Chan T F, Shen J H. Nontexture inpainting by curvature-driven diffusions[J]. Journal of Visual Communication and Image Representation, 2001,12(4):436-449.

[3] 李民, 李世華, 樂翔,等. 基于學習字典的圖像修復算法[J]. 儀器儀表學報, 2011, 32(9):2041-2048.

[4] Zhao M, Li S T. Hybrid Inpainting Algorithm Based On Sparse Representation And Fast Inpainting Method[J]. International Journal of Digital Content Technology and Its Applications, 2011, 5(7):239-247.

[5] Zongben X, Jian S. Image inpainting by patch propagation using patch sparsity[J]. Image Processing,IEEE Transactions on, 2010, 19(5):1153-1165.

[6] Cai J F, Candès E J, Shen Z W. A Singular Value Thresholding Algorithm for Matrix Completion[J]. SIAM Journal on Optimization, 2010, 20(4):1956-1982.

[7] Lin Z C,Chen M M,Ma Y.The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices[R].UIUC Technical Report UILU-ENG-09-2215,2009.

[8] Candè E J,Recht B. Exact Matrix Completion via Convex Optimization[J]. Foundations of Computational Mathematics, 2009, 9(6):717-772.

[9] Wright J, Ganesh A, Rao S, et al. Robust principal component analysis:Exact recovery of corrupted low-rank matrices via convex optimization[C]//Advances in Neural Information Processing Systems,2009:2080-2088.

[10] Buades A, Coll B, Morel J M. A non-local algorithm for image denoising[C]//Computer Vision and Pattern Recognition,IEEE Computer Society Conference on. IEEE, 2005,2:60-65.

[11] 李民,程建,李小文,等. 非局部學習字典的圖像修復[J]. 電子與信息學報,2011,33(11):2672-2678.

ON CULTURAL RELIC IMAGES RESTORATION TECHNOLOGY BASED ON NON-LOCAL MATRIX COMPLETION

Yang Guoliang Lu Hairong Feng Yiqin Tang Jun

(SchoolofElectricalEngineeringandAutomation,JiangxiUniversityofScienceandTechnology,Ganzhou341000,Jiangxi,China)

Cultural relic images contain rich contents,and they are difficultly to be restored effectively with traditional partial differential methods.In order to effectively restore original images,we propose a non-local matrix completion-based method for cultural relic image restoration.The method makes full use of the redundant information of image,within the search window and by comparing the similarity of multiple pixels in a rectangular neighbourhood around the pixel,it finds a certain number of similar blocks and converts them to column vector so as to construct the similar block group matrix.Since the obtained similar block group matrix is low rank or near to low rank,we then use matrix completion theory to fill and restore the damaged pixels.It is demonstrated by the restoring experimental results covering the pixels missing in different proportions,scratches and words damages occurred in cultural relic images that the proposed method is able to well preserve the detail information of structure,has good visual characteristics and clear edge features of the target profile.It can effectively recover the original appearance of the cultural relic image with good restoring capability.

Matrix completion Non-local Similar block Low rank

2015-08-31。國家自然科學基金項目(51365017,61305019);江西省科技廳青年科學基金項目(20132bab211032)。楊國亮，副教授，主研領域：模式識別與圖像處理，智能控制。魯海榮,碩士生。豐義琴，碩士生。唐俊，碩士生。

TP391.41

A

10.3969/j.issn.1000-386x.2016.11.030