基于非凸低秩約束的圖像修復(fù)方法

孫艷敏，郭 強，張彩明

基于非凸低秩約束的圖像修復(fù)方法

孫艷敏1,2，郭 強1,2，張彩明2,3

(1. 山東財經(jīng)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，山東 濟南 250014；2.山東省數(shù)字媒體技術(shù)重點實驗室，山東 濟南 250014；3. 山東大學(xué)軟件學(xué)院，山東 濟南 250101)

受傳輸干擾或存儲不當?shù)纫蛩氐挠绊?，現(xiàn)實應(yīng)用中獲取的某些圖像通常會存在像素缺失現(xiàn)象，這給圖像的后續(xù)分析與處理帶來了一定影響。解決該問題的常用方法是對圖像進行低秩修復(fù)。利用低秩特性進行修復(fù)的方法大多以秩函數(shù)建模，由于矩陣秩函數(shù)是非凸離散的，該模型的求解是一個NP難問題，所以通常利用核范數(shù)對矩陣的秩進行凸松弛。但是，基于核范數(shù)的修復(fù)方法與基于秩函數(shù)極小化的方法之間存在一定偏差，因此提出非凸低秩約束的圖像修復(fù)方法。即采用log函數(shù)代替核范數(shù)對秩進行約束，能夠克服核范數(shù)無法很好逼近秩最小化的問題。此外，為有效求解上述非凸模型，將目標函數(shù)轉(zhuǎn)化為增廣拉格朗日函數(shù)，利用交替方向乘子法求解圖像修復(fù)模型。實驗結(jié)果表明，該修復(fù)方法能夠處理不同情況下的像素缺失問題，且修復(fù)性能明顯好于現(xiàn)有低秩修復(fù)方法。

圖像修復(fù)；核范數(shù)；交替方向乘子法；非凸低秩約束；增廣拉格朗日函數(shù)

圖像修復(fù)是圖像處理和計算機視覺領(lǐng)域研究的熱點問題[1]，其目標是根據(jù)圖像中的已知區(qū)域提取可用圖像信息來恢復(fù)破損區(qū)域或去除圖像中的多余物體，以便獲得符合人眼視覺要求或接近真實圖像[2]。該技術(shù)在物體移除、影視特效以及藝術(shù)作品修復(fù)等領(lǐng)域具有廣泛的應(yīng)用。

圖像修復(fù)方法通常是在修復(fù)過程中引入關(guān)于圖像內(nèi)在的結(jié)構(gòu)信息和先驗屬性，利用數(shù)學(xué)理論建立先驗?zāi)Ｐ?，并依?jù)先驗?zāi)Ｐ颓蠼馊笔^(qū)域的像素。常用的修復(fù)算法大致可分為4類：基于偏微分方程(partial differential equations，PDE)的修復(fù)算法[3-5]、基于樣本塊的修復(fù)算法[6]、基于稀疏表示的修復(fù)算法[7]以及基于深度學(xué)習(xí)的修復(fù)算法[8-9]?；谄⒎值男迯?fù)算法的主要思想是利用物理學(xué)中的擴散方程將待修復(fù)區(qū)域周圍的信息傳播到修復(fù)區(qū)域中，從而達到修復(fù)的目的。該方法主要適用于修復(fù)包含小尺度破損區(qū)域的圖像如劃痕和文字等，但當修復(fù)的面積較大時，修復(fù)效果會明顯變差。其代表性算法包括TV算法[3]，BSCB算法[4]和CDD算法[5]等。為了彌補PDE修復(fù)算法的不足，基于樣本塊的修復(fù)算法應(yīng)運而生。其實現(xiàn)修復(fù)的原理是在待修復(fù)圖像的已知像素區(qū)域內(nèi)按照某種規(guī)則搜索一個或多個圖像塊，將得到的圖像塊作為待修復(fù)塊的估計進行填補，如此往復(fù)直到待修復(fù)區(qū)域填充完畢。這種方法雖然在較大區(qū)域的修復(fù)上較前者效果更好，但當圖像本身的紋理特征不規(guī)則時，修復(fù)效果會明顯下降。不同于以上2種方法，基于稀疏表示的修復(fù)算法則假定圖像待修復(fù)區(qū)域和完好無損區(qū)域具備相同稀疏特性，對完好區(qū)域進行稀疏表示獲得表示系數(shù)，再通過重構(gòu)算法對圖像破損區(qū)域進行重構(gòu)，進而恢復(fù)成完整的圖像。在修復(fù)過程中這類算法不僅能夠改善圖像修復(fù)質(zhì)量，而且能夠使修補的圖像更加清晰。此外，深度學(xué)習(xí)近來也被應(yīng)用到圖像修復(fù)中。借助于深度學(xué)習(xí)較強的特征學(xué)習(xí)能力，在海量圖像數(shù)據(jù)的支撐下，通過學(xué)習(xí)可對一些大尺度破損的圖像進行較好的修復(fù)。但其存在訓(xùn)練時間長，且對計算機的硬件配置要求較高，網(wǎng)絡(luò)模型缺乏理論解釋等問題。

隨著稀疏表示理論的發(fā)展，低秩表示成為近年來學(xué)術(shù)界研究的熱點[10-11]。其是稀疏表示在矩陣上的擴展[12]，能夠利用矩陣內(nèi)樣本點之間的內(nèi)在關(guān)系[13-15]獲得數(shù)據(jù)的全局性特征。受到低秩表示在挖掘數(shù)據(jù)全局信息方面具有很大優(yōu)勢的啟發(fā)，以及圖像本身具有的近似低秩特性[16-18]，本文假設(shè)原始圖像可以由一個低秩矩陣表示[19]?；谠摷僭O(shè)，圖像修復(fù)的過程可以轉(zhuǎn)換為一個低秩矩陣填充問題。

低秩矩陣填充可采用矩陣雙線性因子分解[20-24]和矩陣秩最小化[25-29]2種策略進行。假設(shè)破損的矩陣為∈×n，為已知元素的位置構(gòu)成的集合?；陔p線性因子分解的填充算法通過求解以下模型可對缺失元素進行估計，即

其中，為矩陣的秩。該方法將目標矩陣分解為2個低秩矩陣的乘積形式，求解過程中可避免復(fù)雜的矩陣奇異值分解，從而使得算法具有較低的計算復(fù)雜度。但是其必須預(yù)先估計矩陣的秩，這在一定程度上限制了該方法的可用性。

與基于雙線性因子分解算法不同的是，基于秩最小化的填充算法通過式(2)得到矩陣的近似低秩估計

其中，()為矩陣的秩，即非零奇異值的個數(shù)。該方法無需知道矩陣的具體結(jié)構(gòu)信息。因為當矩陣滿足強不相干性且符合隨機一致采樣時，通過極小化矩陣的秩，能夠以大概率對矩陣進行復(fù)原[25]。但是由于秩函數(shù)()的離散特性，矩陣的秩極小化是一個NP-hard問題。通常用求解核范數(shù)最小化(nuclear norm minimization，NNM)問題的方法來對其進行凸松弛[14,23,30]，進而式(2)可以轉(zhuǎn)化為

其中，||||*表示矩陣的核范數(shù)，即矩陣的所有奇異值之和。為了求解該模型，文獻[31]提出了一種奇異值閾值方法(singular value thresholding，SVT)。但是該方法在求解NNM問題時，忽略了奇異值的物理意義而同等地收縮處理所有奇異值，導(dǎo)致在求解NNM問題時通常得到的是對原始秩最小化問題的次優(yōu)解。事實上大的奇異值通常對應(yīng)于數(shù)據(jù)的主要信息，應(yīng)該被較小地收縮來保持數(shù)據(jù)的主要內(nèi)容。文獻[32]中的加權(quán)核范數(shù)極小化法(weighted nuclear norm minimization，WNNM)則根據(jù)奇異值的物理意義，通過賦予奇異值不同的權(quán)重來提高矩陣填充精度，但需要根據(jù)經(jīng)驗手動確定權(quán)重，使得該方法不能精確近似矩陣的秩函數(shù)。為了避免耗時的迭代收縮，文獻[33]提出了一種利用低秩近似(low rank approximation，LRA)和截斷奇異值的簡單圖像修復(fù)方法。此外，文獻[34]認為基于矩陣NNM方法在求解過程中往往會更多地關(guān)注較大的奇異值，忽略較小的奇異值，這將導(dǎo)致所得到的矩陣雖然具有低秩性但卻不能很好地逼近真實解。因此，上文提出了基于截斷式矩陣核范數(shù)正則化(TNNR)的矩陣填充算法，其僅懲罰最小的-個奇異值(其中是矩陣的秩)。雖然TNNR在數(shù)據(jù)集上取得了很好的效果，但其在建立模型的過程中需要對矩陣的秩進行預(yù)估計，這一過程在真實場景中難以實現(xiàn)。

盡管核范數(shù)能夠較好地逼近非凸的秩函數(shù)，且文獻[25]給出了一定的理論保證，但其與秩函數(shù)的最佳逼近函數(shù)仍有一定差距，這使得在實際應(yīng)用中其所獲結(jié)果往往不是最優(yōu)的。其原因為矩陣的每一個非零奇異值對秩函數(shù)來說是同等重要的，而核范數(shù)定義為全部非零奇異值之和，并且同時最小化，這樣就使得每一個奇異值具有了不相同的貢獻。為了克服上述問題，本文提出了一種非凸矩陣填充算法來進行圖像修復(fù)。與基于核范數(shù)的模型相比，其能夠更好地逼近原始的秩極小化問題，這是因為非凸松弛可以對不同奇異值進行不平衡懲罰，從而有利于對數(shù)據(jù)中主要信息的度量和刻畫。此外，為了求得算法的一個最優(yōu)解，本文采用了交替方向乘子法來求解該模型。

1 相關(guān)工作

為了更精準地逼近秩函數(shù)，學(xué)者們提出引入一些更加緊致的非凸函數(shù)來松弛秩函數(shù)。文獻[26]采用Schatten-p(0<≤1)范數(shù)來作為秩函數(shù)的逼近函數(shù)，將低秩矩陣填充問題建模為

其中

當參數(shù)=1時，Schatten-p范數(shù)等價于核范數(shù)，即核范數(shù)是Schatten-p范數(shù)的一個特例。當越趨近于0時，Schatten-p范數(shù)對秩函數(shù)的逼近能力越強。該模型可以采用拉格朗日乘子法進行求解。數(shù)值實驗結(jié)果表明，采用Schatten-p范數(shù)比采用核范數(shù)進行矩陣填充獲得的效果更好。

文獻[35]則用高斯函數(shù)

來逼近秩函數(shù)，其中，s為變量；為參數(shù)。將低秩矩陣填充問題建模為

該模型可充分利用高斯函數(shù)可微的性質(zhì)，采用梯度投影算法進行求解。受高斯函數(shù)的啟發(fā)，文獻[36]則利用光滑雙曲正切函數(shù)

建立光滑非凸優(yōu)化模型，同樣可采用梯度投影算法進行求解。對低秩矩陣填充問題和圖像修復(fù)問題的實驗結(jié)果表明，該算法取得了更好的結(jié)果。此外，也可采用非凸光滑的logdet(+T)函數(shù)作為秩函數(shù)()的包絡(luò)來對矩陣填充問題建模[37]，該模型求解可以采用交替方向乘子法。

不同于上述非凸矩陣填充模型的圖像修復(fù)方法，本文基于log函數(shù)的放縮性和泰勒展開函數(shù)的逼近性導(dǎo)出了一種簡單有效的方法。

2 本文方法

2.1 動機分析

本文采用log函數(shù)近似秩函數(shù)主要從以下2個方面考慮：

(1) 從物理意義上講，圖像中較大的奇異值與圖像的主要成分相關(guān)，因此較大奇異值需要被較小地約束以保留主要成分。但是矩陣核范數(shù)卻將具有不同重要性的奇異值同等對待，這導(dǎo)致基于矩陣核范數(shù)的修復(fù)方法不能很好地保留圖像主要成分。直觀上的做法是，不同的奇異值應(yīng)該根據(jù)重要性被不同程度地約束。一種策略是用加權(quán)核范數(shù)的形式，但是這種形式會引入更多的權(quán)重參數(shù)且需要手動確定權(quán)重，這使得加權(quán)核范數(shù)不能更精確近似秩函數(shù)。而本文采用奇異值的對數(shù)來保證較大奇異值的重要性，其在求解時對奇異值的收縮值僅與各個奇異值相關(guān)，這是更加合理的。

(2) 從數(shù)學(xué)意義上講，由于秩函數(shù)是奇異值的0范數(shù)，是非凸不連續(xù)的函數(shù)，而核范數(shù)是奇異值的1范數(shù)，其最小化容易導(dǎo)致過懲罰的問題。于是，出現(xiàn)了許多利用非凸連續(xù)函數(shù)來逼近0范數(shù)的方法，例如：l范數(shù)[38-39](0<<1)、平滑截斷絕對值偏差[40]、MCP函數(shù)[41]以及指數(shù)型罰函數(shù)[42]等。這些非凸近似函數(shù)較1范數(shù)具有更好的性能，且更適合用于圖像修復(fù)。

圖1 l1范數(shù)和函數(shù)對l0范數(shù)逼近程度比較

2.2 基于log函數(shù)的修復(fù)模型

通過以上分析，理論上可采用以下非凸低秩的正則化模型對圖像進行修復(fù)

其中

>1為常數(shù)；()為矩陣的第個奇異值?？紤]到自然圖像會受到噪聲干擾，需引入噪聲正則項以增加模型魯棒性，即

其中，為正則化參數(shù)；為數(shù)據(jù)的噪聲矩陣。

2.3 模型的優(yōu)化求解過程

由于||||log的非凸性，式(11)難以直接求解，因此本文利用一階泰勒展開式[43]來線性逼近式||||log，將其代入泰勒展開式()=(0)+?(0) (-0)，得

通過引入輔助變量=及拉格朗日乘子矩陣和，將式(11)轉(zhuǎn)換為有關(guān)增廣拉格朗日函數(shù)的無約束最小化模型，即

其中，和為正的懲罰權(quán)重參數(shù)。此外，為了方便起見，記

由于式(13)中的變量是可分離的，所以利用交替最小化方法[44]來求解。具體地，在一次迭代中，首先固定，，，，，并利用式(15)更新，得

由于式(15)的目標函數(shù)是可微的，因此+1有如下閉式解

然后，固定，，，，，利用下式更新，得

根據(jù)文獻[43]引理1，可得

類似地，固定，，，，，利用式(19)更新，則有

由于式(19)中的目標函數(shù)是可微的，故通過使其一階導(dǎo)數(shù)等于零可得

其中，是指標集的補集。

其次，固定，，，，，利用式(20)更新，有

由于式(21)的目標函數(shù)是可微的，易得+1的解為

最后，固定，，，，利用下式更新增廣拉格朗日乘子，為

根據(jù)上述的求解過程，可得本文算法：

輸入：破損圖像Y，指標集W。初始化：X=0，N=0，Z=0，P=0，Q=0和m=b=1e-8，k=100。輸出：修復(fù)圖像X。步驟1. 通過式(15)更新Xk+1。步驟2. 通過式(17)更新Zk+1。步驟3. 通過式(19)更新Yk+1。步驟4. 通過式(21)更新Nk+1。步驟5. 通過式(23)更新pk+1。步驟6. 通過式(24)更新Qk+1。步驟7. 通過m=tm，b=tb更新乘數(shù)m和b。步驟8. 重復(fù)執(zhí)行步驟1～7，直到滿足收斂條件：。步驟9. 結(jié)束。

需要說明的是，為避免迭代收斂過程過于緩慢，本文通過利用文獻[45]的方法來加速收斂過程，即每一次迭代中的和分別是上一次迭代的倍，即=，=，其中?[1.1, 1.2]。

3 實驗結(jié)果與分析

通過將本文方法與WNNM-MC[32]，TCTR[45]，MC-NC[46]，LRMC[47]和LRTC-TNN[47]5種方法進行比較分析，以驗證本文方法的有效性。實驗所用計算機配置為：Intel Core i7-6700 CPU @3.40 GHz，8 GB內(nèi)存，軟件平臺為MATLAB R2018a。

參數(shù)設(shè)置下：=0.01max(((T)))，=1。其他5種修復(fù)算法的實現(xiàn)代碼均從作者主頁上獲取，相關(guān)參數(shù)采用默認值。對修復(fù)后圖像的質(zhì)量從主觀的視覺效果以及客觀的量化指標2方面進行評價。本文采用峰值信噪比(peak signal-to-noise ratio，PSNR)和特征相似度均值(feature similarity index mersure，F(xiàn)SIM)這2種常用的定量標準來量化修復(fù)后圖像的質(zhì)量。原始測試圖像如圖2所示。

①②③ ④⑤⑥ ⑦⑧⑨

3.1 隨機丟失像素修復(fù)性能比較

3.1.1 無噪聲數(shù)據(jù)的實驗結(jié)果

表1為在不同像素缺失率(=0.1, 0.3, 0.5)下，采用不同方法所得修復(fù)圖像的PSNR和FSIM值。從中可以看出，本文方法的量化性能明顯優(yōu)于WNNM-MC和MC-NC，略好于LRMC，LRTC-TNN和TCTR。本文方法的平均PSNR值分別比WNNM-MC，MC-NC，LRMC，LRTC-TNN和TCTR高出2.56 dB，3.17 dB，1.17 dB，0.14 dB和0.12 dB。

為比較不同方法修復(fù)圖像的視覺效果，圖3為在像素缺失率(=0.5)的情況下，各種修復(fù)方法對圖2中不同測試圖像的修復(fù)結(jié)果?？梢钥闯觯捎肨CTR方法修復(fù)后的圖像含有非常明顯的瑕疵點，尤其是圖像的邊緣部分，未能將圖像邊緣信息有效地恢復(fù)，而本文方法的視覺效果則明顯好于TCTR。產(chǎn)生上述問題的原因在于，TCTR每次對固定秩為的矩陣執(zhí)行SVD。雖然該算法可以縮短運行時間，但其忽略了現(xiàn)實圖像的秩是一變量的事實。

表1 不同方法修復(fù)結(jié)果PSNR/FSIM比較(無噪聲)

圖3 不同算法對缺失率a=0.5的圖像修復(fù)效果圖

3.1.2 含噪聲數(shù)據(jù)的實驗結(jié)果

表2為在不同噪聲水平(=5,10,15)下，采用不同方法所得修復(fù)圖像的PSNR和FSIM值。從表2可以發(fā)現(xiàn)，噪聲降低了所有方法的性能，而且在大多數(shù)情況下，基于非凸松弛的方法可獲得較好的結(jié)果。

表2 不同方法修復(fù)結(jié)果PSNR/FSIM比較(有噪聲)

為進一步比較修復(fù)圖像的視覺效果，圖4為在=0.5，=15情況下，不同修復(fù)方法對測試圖像的修復(fù)結(jié)果。由于實驗使用的圖片分辨率較低，因此無法較好地觀察到復(fù)原區(qū)域與原始圖片對應(yīng)區(qū)域之間的細節(jié)差異，于是圖5給出了不同修復(fù)方法對測試圖像的局部細節(jié)修復(fù)結(jié)果。不難看出，采用LRMC修復(fù)后的圖像整體過于模糊。如圖5(f)的第3行圖像所示，圖像細節(jié)特征丟失嚴重。產(chǎn)生上述問題的原因在于，基于NNM模型的算法忽略了奇異值的物理意義而同等地收縮所有奇異值。此外采用WNNM算法進行圖像修復(fù)雖然效果較好，但需要引入額外的權(quán)重參數(shù)。而本文利用奇異值的對數(shù)來保證較大奇異值的重要性，并在求解時要求奇異值的收縮值僅與各個奇異值相關(guān)，沒有引入額外的權(quán)重參數(shù)，這是更加合理的收縮算法。

3.2 像素塊丟失修復(fù)性能比較

3.2.1 無噪聲數(shù)據(jù)的實驗結(jié)果

本文隨機選取圖像的某一個30×30的方形區(qū)域作為缺失區(qū)域，將其數(shù)量定義為，并將處理后得到的圖像作為破損圖像來驗證本文算法的有效性。各方法的FSIM和PSNR見表3，以及相應(yīng)的視覺效果如圖6所示。根據(jù)表中相應(yīng)的PSNR和FSIM值可以看出，MC-NC在PSNR平均值方面優(yōu)于本文算法0.13 dB，而在FSIM平均值方面則兩者相同，說明從客觀的量化指標進行評價，本文方法與MC-NC相當。

圖4 不同算法對缺失率a=0.5，噪聲水平t=15的圖像修復(fù)效果圖

圖5 不同算法對缺失率a=0.5，噪聲水平t=15的圖像修復(fù)細節(jié)效果圖

表3 不同方法修復(fù)結(jié)果PSNR/FSIM比較(無噪聲，30×30)

圖6 不同算法對缺失率k=2的圖像修復(fù)效果圖

從圖6主觀視覺效果方面而言，本文方法所獲得的修復(fù)結(jié)果不僅與MC-NC相當，并且明顯優(yōu)于其他相關(guān)方法，尤其是對于含有大量冗余信息的圖像，本文方法的修復(fù)效果較好。需要說明的是，如圖6(c)所示，盡管MC-NC方法可以獲得最佳的視覺效果，但在實際運行中需要進行耗時的逐行更新。此外，TCTR不適合修復(fù)隨機丟失像素以及丟失較大區(qū)域的圖像，從定量標準和視覺效果兩方面來說，TCTR的修復(fù)性能最差。

3.2.2 含噪聲數(shù)據(jù)的實驗結(jié)果

表4為固定=2時，在不同噪聲水平(=5,10,15)下，不同算法取得的PSNR和FSIM值。可以看出，平均MC-NC取得了最高的PSNR值，而本文算法取得了最高的FSIM值?？傮w而言，本文算法具有相對較好的修復(fù)果。

表4 不同方法修復(fù)結(jié)果PSNR/FSIM比較(有噪聲，30×30，k=2)

圖7為在=2，=10的情況下，各種修復(fù)方法對不同測試圖像的修復(fù)結(jié)果，為進一步從視覺上觀察到補全區(qū)域與原始圖片對應(yīng)區(qū)域之間的細節(jié)差異，圖8給出了圖像的局部細節(jié)修復(fù)結(jié)果。從圖8中不難看出，本文方法和MC-NC的視覺效果要遠好于TCTR，LRMC和LRTC-TNN，略好于WNNM-MC。WNNM-MC盡管具有較高的量化指標，但其結(jié)果存在一定程度的模糊，如圖8(e)所示。此外，從圖8(g)中可以發(fā)現(xiàn)，LRTC-TNN無法有效地修復(fù)缺失的像素塊，這是由于其對參數(shù)較為敏感。

綜上所述，本文方法不僅具有較高的PSNR和FSIM，以及較強的魯棒性，而且其修復(fù)的圖像具有很好的視覺效果，能夠有效地保持圖像細節(jié)。

4 結(jié) 論

本文提出了一種基于非凸正則化項的矩陣填充模型，并結(jié)合交替方向乘子法對其進行求解，實驗結(jié)果表明，在不同缺失率下以及不同噪聲影響下，本文算法均能獲得較好的修復(fù)效果。由于迭代過程中涉及到矩陣的奇異值分解，使得算法的計算復(fù)雜度較高，如何提高算法的計算效率是下一步研究工作的主要內(nèi)容。

圖7 不同算法對缺失率k=2，噪聲水平t=10的圖像修復(fù)效果圖

圖8 不同算法對缺失率k=2，噪聲水平t=10的圖像修復(fù)細節(jié)效果圖

[1] GUILLEMOT C, LE M O. Image inpainting: overview and recent advances[J]. IEEE Signal Processing Magazine, 2014, 31(1): 127-144.

[2] 馮象初, 王斯琪, 李小平. 圖像修復(fù)問題的低秩對偶逼近算法[J]. 西安電子科技大學(xué)學(xué)報, 2016, 43(4): 172-177.

FENG X C, WANG S Q, LI X P. Low-rank and dual approximation method for image inpainting problems[J]. Journal of Xidian University, 2016, 43(4): 172-177 (in Chinese).

[3] 張桂梅, 李艷兵. 結(jié)合紋理結(jié)構(gòu)的分數(shù)階TV模型的圖像修復(fù)[J]. 中國圖象圖形學(xué)報, 2019, 24(5): 700-713.

ZHANG G M, LI Y B. Image inpainting of fractional TV model combined with texture structure[J]. Journal of Image and Graphics, 2019, 24(5): 700-713 (in Chinese).

[4] 尹芳, 陳田田. 均場退火算法在單幅灰度圖像高光檢測與恢復(fù)中的應(yīng)用[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2017, 29(5): 829-837.

YI F, CHEN T T. Application of mean field annealing in specular detection and recovery for a grayscale image[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(5): 829-837 (in Chinese).

[5] 竇立云, 徐丹, 李杰, 等. 基于雙樹復(fù)小波的圖像修復(fù)[J]. 計算機科學(xué), 2017, 44(S1): 179-182, 191.

DOU L Y, XU D, LI J, et al. Image inpainting based on dual-tree complex wavelet transform[J]. Computer Science, 2017, 44(S1): 179-182, 191 (in Chinese).

[6] 陶兆勝, 張敬寒, 王磊, 等. 基于邊緣特征和像素結(jié)構(gòu)相似度的圖像修復(fù)算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2019, 31(10): 1768-1776.

TAO Z S, ZHANG J H, WANG L, et al. Image inpainting algorithm based on edge feature and pixel structure similarity[J]. Journal of Computer-Aided Design & Computer Graphics, 2019, 31(10): 1768-1776 (in Chinese).

[7] 高成英, 徐仙兒, 羅燕媚, 等. 基于稀疏表示的物體圖像修復(fù)[J]. 計算機學(xué)報, 2019, 42(9): 1953-1965.

GAO C Y, XU X E, LUO Y M, et al. Object image inpainting based on sparse representation[J]. Chinese Journal of Computers, 2019, 42(9): 1953-1965 (in Chinese).

[8] LI J Y, WANG N, ZHANG L F, et al. Recurrent feature reasoning for image inpainting[C]//2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2020: 7760-7768.

[9] ZHAO L, MO Q H, LIN S H，et al. UCTGAN: diverse image inpainting based on unsupervised cross-space translation[C]// 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2020: 5741-5750.

[10] UDELL M, HORN C, ZADEH R B, et al. Generalized low rank models[J]. Foundations and Trends in Machine Learning, 2016, 9(1): 1-118.

[11] 郭強, 張彩明, 張云峰, 等. 基于最小方差估計的圖像低秩去噪[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2015, 27(12): 2237-2246.

GUO Q, ZHANG C M, ZHANG Y F, et al. Low-rank image denoising based on minimum variance estimator[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(12): 2237-2246 (in Chinese).

[12] CAI T T, ZHANG A. Sparse representation of a polytope and recovery of sparse signals and low-rank matrices[J]. IEEE Transactions on Information Theory, 2014, 60(1): 122-132.

[13] 張倩侃, 計忠平, 付曉峰. 二次聯(lián)合稀疏表示和低秩近似的淺浮雕優(yōu)化[J]. 中國圖象圖形學(xué)報, 2020, 25(6): 1245-1259.

ZHANG Q K, JI Z P, FU X F. Bas-relief optimization based on twice-joint sparse representation and low-rank approximation[J]. Journal of Image and Graphics, 2020, 25(6): 1245-1259 (in Chinese).

[14] LIU G C, LIN Z C, YAN S C, et al. Robust recovery of subspace structures by low-rank representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(1): 171-184.

[15] LU X Q, WANG Y L, YUAN Y, et al. Graph-regularized low-rank representation for destriping of hyperspectral images[J]. IEEE Transactions on Geoscience and Remote Sensing, 2013, 51(7): 4009-4018.

[16] 劉成士, 趙志剛, 李強, 等. 加強的低秩表示圖像去噪算法[J]. 計算機工程與應(yīng)用, 2020, 56(2): 216-225.

LIU C S, Z Z G, LI Q, et al. Enhanced low-rank representation image denoising algorithm[J]. Computer Engineering and Applications, 2020, 56(2): 216-225 (in Chinese).

[17] 白宏陽, 馬軍勇, 熊凱, 等. 圖像修復(fù)中的加權(quán)矩陣補全模型設(shè)計[J]. 系統(tǒng)工程與電子技術(shù), 2016, 38(7): 1703-1708.

BAI H Y, MA J Y, XIONG K, et al. Design of weighted matrix completion model in image inpainting[J]. Systems Engineering and Electronics, 2016, 38(7): 1703-1708 (in Chinese).

[18] HE W, ZHANG H Y, ZHANG L P, et al. Hyperspectral image denoising via noise-adjusted iterative low-rank matrix approximation[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2015, 8(6): 3050-3061.

[19] JI H, LIU C Q, SHEN Z W, et al. Robust video denoising using low rank matrix completion[C]//2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York: IEEE Press, 2010: 1791-1798.

[20] WEN Z W, YIN W T, ZHANG Y. Solving a low-rank factorization model for matrix completion by a nonlinear successive over relaxation algorithm[J]. Mathematical Programming Computation, 2012, 4(4): 333-361.

[21] HE W, ZHANG H Y, ZHANG L P, et al. Total-Variation-Regularized low-rank matrix factorization for hyperspectral image restoration[J]. IEEE Transactions on Geoscience and Remote Sensing, 2016, 54(1): 178-188.

[22] XU Y Y, YIN W T, WEN Z W, et al. An alternating direction algorithm for matrix completion with nonnegative factors[J]. Frontiers of Mathematics in China, 2012, 7(2): 365-384.

[23] ZHOU P , LU C Y, LIN Z C , et al. Tensor factorization for low-rank tensor completion[J]. IEEE Transactions on Image Process, 2018, 27(3): 1152-1163.

[24] SHANG F H, CHENG J, LIU Y Y, et al. Bilinear factor matrix norm minimization for robust PCA: Algorithms and applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 40(9): 2066-2080.

[25] CANDES E J, RECHT B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9(6): 717-772.

[26] NIE F P, WANG H, HUANG H, et al. Joint schatten p-norm and lp-norm robust matrix completion for missing value recovery[J]. Knowledge and Information Systems, 2015, 42(3): 525-544.

[27] NIE F, HUANG H, DING C, et al. Low-rank matrix recovery via efficient schatten p-norm minimization[C]//The 26th AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2012: 655-661.

[28] LU C Y, ZHU C B, XU C Y, et al. Generalized singular value thresholding[C]//The 29th AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2015: 1805-1811.

[29] LARSSON V, OLSSON C. Convex low rank approximation[J]. International Journal of Computer Vision, 2016, 120(2): 194-214.

[30] DAI Y H, LI H D, HE M Y, et al. A simple prior-free method for non-rigid structure-from-motion factorization[J]. International Journal of Computer Vision, 2014, 107(2): 101-122.

[31] CAI J F, CANDèS E J, SHEN Z W, et al. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956-1982.

[32] GU S H, XIE Q, MENG D Y, et al. Weighted nuclear norm minimization and its applications to low level vision[J]. International Journal of Computer Vision, 2017, 121(2): 183-208.

[33] GUO Q, GAO S S, ZHANG X F, et al. Patch-based image inpainting via two-stage low rank approximation[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(6): 2023-2036.

[34] LIU Q, LAI Z H, ZHOU Z W, et al. A truncated nuclear norm regularization method based on weighted residual error for matrix completion[J]. IEEE Transactions on Image Processing, 2015, 25(1): 316-330.

[35] GHASMEI H, MALEK M M, BABAIE Z M, et al. SRF: matrix completion based on smoothed rank function[C]//2011 IEEE International Conference on Acoustics, Speech and Signal Processing. New York: IEEE Press, 2011: 3672-3675.

[36] GENG J, WANG L S, WANG Y F, et al. A non-convex algorithm framework based on DC programming and DCA for matrix completion[J]. Numerical Algorithms, 2015, 68(4): 903-921.

[37] KANG Z, PENG C, CHENG J, et al. LogDet rank minimization with application to subspace clustering[EB/OL]. [2020-09-11]. https://www.hindawi.com/journals/cin/2015/824289/.

[38] TAHERI O, VOROBYOV S A. Sparse channel estimation with lp-norm and reweighted l1-norm penalized least mean squares[C]//2011 IEEE International Conference on Acoustics, Speech, and Signal Processing. New York: IEEE Press, 2011:2864-2867.

[39] XU Z B, ZHANG H, WANG Y, et al. L1/2 regularization[J]. Science China (Information Sciences), 2010, 53(6): 1159-1169.

[40] FAN J, LI R. Variable selection via nonconcave penalized likelihood and its oracle properties[J]. Journal of the American Statistical Association, 2001, 96(456): 1348-1360.

[41] CAO W F, WANG Y, YANG C, et al. Folded-concave penalization approaches to tensor completion[J]. Neurocomputing, 2015, 152(25): 261-273.

[42] GAO C X, WANG N Y, YU Q R, et al. A feasible nonconvex relaxation approach to feature selection[C]//The 25th AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2011: 356-361.

[43] DONG W S, SHI G M, LI X, et al. Compressive sensing via nonlocal low-rank regularization[J]. IEEE Transactions on Image Processing, 2014, 23(8): 3618-3632.

[44] LU C Y, FENG J S, YAN S C, et al. A unified alternating direction method of multipliers by majorization minimization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 40(3): 527-541.

[45] LU C Y, FENG J S, LIN Z C, et al. Exact low tubal rank tensor recovery from Gaussian measurements[C]//The 27th International Joint Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2018: 2504-2510.

[46] NIE F P, HU Z X, LI X L. Matrix completion based on non-convex low-rank approximation[J], IEEE Transactions on Image Processing, 2019, 28(5): 2378-2388.

[47] LU C. A library of ADMM for sparse and low-rank Optimization. National University of Singapore, June 2016[EB/OL]. [2020-10-15]. https://github.com/canyilu/ LibADMM-toolbox.

Image inpainting using non-convex and low-rank constraint

SUN Yan-min1,2, GUO Qiang1,2, ZHANG Cai-ming2,3

(1. School of Computer Science and Technology, Shandong University of Finance and Economics, JinanShandong 250014, China; 2. Shandong Key Laboratory of Digital Media Technology, JinanShandong 250014, China; 3. School of Software, Shandong UniversityJinanShandong 250101, China)

Due to transmission interference or improper storage, there exist some missing pixels in the images obtained in the real scene, which causes obstacles to the subsequent processing and analysis of the images. The key solution for missing pixels is to recover the image with low rank prior. However, since the rank function is discrete, the model that minimizes the rank is an NP-hard problem. In order to address this issue, a commonly used method is to employ an image-inpainting algorithm based on the nuclear norm. Unlike the methods based on the nuclear norm minimization, this paper proposed an image-inpainting algorithm using non-convex low-rank constraints, which replaced the traditional nuclear norm with a log function and overcame the inability of the nuclear norm to approach the rank minimization. In addition, to optimize the non-convex model, the augmented Lagrangian multiplier method was adopted to derive an alternating minimization algorithm. Experimental results demonstrate that the proposed method can deal with different missing pixel rates, and can far outperform other low-rank inpainting methods in inpainting.

image inpainting; nuclear norm; alternating direction method of multiplier; non-convex and low-rank constraints; augmented Lagrangian method

TP 391

10.11996/JG.j.2095-302X.2021030414

A

2095-302X(2021)03-0414-12

2020-12-02；

2020-12-26

2 December，2020；

26 December，2020

國家自然科學(xué)基金項目(61873145，U1609218)；山東省省屬高校優(yōu)秀青年人才聯(lián)合基金(ZR2017JL029)

National Natural Science Foundation of China (61873145, U1609218);Supported by Youth Foundation of Shandong Province of China (ZR2017JL029)

孫艷敏(1993-)，女，山東濟南人，碩士研究生。主要研究方向為數(shù)字圖像修復(fù)。E-mail：1689980961@qq.com

SUN Yan-min (1993-), female, master student. Her main research interest covers digital image inpainting. E-mail：1689980961@qq.com

郭 強(1979–)，男，山東濟南人，教授，博士。主要研究方向為圖形圖像處理、計算機視覺等。E-mail：guoqiang@sdufe.edu.cnE-mail：guoqiang@sdufe.edu.cn

GUO Qiang(1979-), male, professor, Ph.D. His main research interests cover graphic image processing, computer vision, etc.