基于非局部自相似性和低秩矩陣逼近的補全算法

張 麗，孔 旭，孫忠貴

（聊城大學數學科學學院，山東聊城 252000）

（?通信作者電子郵箱kongxu@lcu.edu.cn）

0 引言

通過矩陣已知元素來恢復出未知元素的問題通常稱為矩陣補全（Matrix Completion，MC）問題。隨著計算機技術的迅速發展，矩陣補全已成為信號與圖像處理研究的熱點問題，可廣泛應用于圖像修復［1］、多標記圖像分類［2］、系統辨識［3］、推薦系統［4］和半監督聚［5］類等諸多領域中。

矩陣補全問題可建模為仿射秩最小化問題：

其中：X ∈Rn×n，指標集是由采樣矩陣下標組成的集合，PΩ為正交投影算子，當(i，j) ∈Ω 時，Dij為采樣元素，即：

由于秩函數具有非凸性和不連續性，直接求解秩最小化問題屬于NP（Non-deterministic Polynomial）難問題。近年來研究者們提出了許多求解這一問題的近似方法，這些方法主要分為兩類：一類是將秩函數凸松弛到核范數，建立核范數優化模型［6-11］；另一類是假設已知矩陣秩的大小，建立矩陣低秩分解的優化模型［12-15］。關于矩陣補全模型及其算法的綜述可參見文獻［16-17］。

對于第一類方法，盡管該類方法在矩陣補全中得到了廣泛的應用，但是核函數不能準確地近似秩函數。自然的想法是在矩陣補全的過程中直接采用秩函數；然而，現實中待補全矩陣的秩往往是未知的，因此，在采用第二類方法進行矩陣補全時，也會遇到一定的問題。

為了解決此問題，Wang等［18］提出了一種基于低秩矩陣逼近的補全算法，并給出了算法的收斂性。當矩陣秩的大小未知時，該算法通過秩的逐步增加進行更新迭代，給出了秩最小化問題的一種有效求解方法，在低秩的隨機矩陣上的數值實驗也驗證了該算法的有效性和可行性。特別地，當矩陣具有很好的低秩性時，該算法取得了較為理想的補全效果。然而，將上述算法應用到自然圖像恢復時，所得結果并不理想。原因在于低秩矩陣補全問題的解決建立在矩陣可以低秩表示的基礎上，但是自然圖像多數是近似低秩的。

在實際圖像中，同一圖像塊內容通常會在一個非局部范圍內呈周期性展現，同時，基于這種非局部屬性所構建的算法模型也已在圖像處理領域得到了較廣泛的應用［19-27］。進一步，Wang等［25］給出了一個基于上述非局部相似塊的低秩矩陣構建方法，并指出了其潛在的應用前景。結合上述研究基礎，本文提出了一個基于非局部自相似性和低秩矩陣逼近的補全算 法（NonLocal self-similarity and Low-Rank Matrix Approximation，NL-LRMA），并將其用于圖像恢復。實驗結果表明，本文所提算法的主觀視覺效果與客觀量化指標峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）值均優于迭代重加權核范數（Iteratively Reweighted Nuclear Norm，IRNN）［28］、加權核 范 數（Weighted Nuclear Norm Minimization，WNNM）［29］、LRMA（Low-Rank Matrix Approximation）［18］等原有局部算法。

1 低秩矩陣逼近的補全算法

如果已知待補全矩陣秩的大小，可以將問題（1）建模如下：

然而，在實際問題中矩陣X 的秩往往是未知的。針對問題（1），當矩陣秩的大小未知時，Wang等［18］提出了一種低秩矩陣逼近算法（LRMA），該算法通過秩的逐步增加進行更新迭代，直到滿足迭代終止條件，具體見算法1。

算法1 低秩矩陣逼近（LRMA）算法。

其中：lansvd(Yk，rk，L)表示計算矩陣Yk的前rk個較大的奇異值和對應的奇異向量，Xk表示由前r 個奇異值和奇異向量計算所得到的矩陣，maxIter表示最大迭代次數。

LRMA 算法不僅在理論上可保證收斂性，而且具有速度快、補全效果好等優點。特別地，在隨機產生的維數較高的低秩矩陣上該算法具有很好的補全效果，如在隨機產生的秩大小分別為20、30、40 時的較大型數值矩陣（2 000 × 2 000、3 000 × 3 000、4 000 × 4 000）。

2 NL-LRMA算法

為了驗證LRMA 算法在自然圖像恢復中的性能，圖1 給出了利用LRMA 算法分別對兩幅256 × 256 大小的灰度圖像進行恢復的實驗結果。設隨機采樣數目為a，即采樣率為R=a/(256 × 256)。當圖像的采樣率為0.2時，圖像恢復效果如圖1 所示。由圖1 可見，該算法應用于自然圖像恢復時，圖像恢復效果并不理想，這表明LRMA 算法應用在近似低秩的自然圖像時恢復效果較差。

圖1 基于低秩矩陣逼近算法的圖像恢復效果（采樣率R=0.2）Fig.1 Image recovery results of LRMA algorithm（sampling ratio R=0.2）

由于矩陣的秩等于矩陣的非奇異值的個數，所以低秩矩陣的奇異值大部分為0。對自然圖像的數值矩陣進行奇異值分解，并取不同的奇異值與對應的酉矩陣進行重構圖像，如圖2所示。

圖2 自然圖像的奇異值分解和基于奇異值分解的重構圖像Fig.2 Singular value decomposition of natural images and reconstruction images based on singular value decomposition

從圖2 可以看出，隨著奇異值的增加，重構后的圖像與原始圖越來越接近。前40 個奇異值包含了圖像的大部分信息，且由前40 個奇異值及其相應的正交矩陣重構的圖像的秩為40，大約占原始圖像秩的1/8，由此可以看出自然圖像是近似低秩的。

針對上述LRMA 算法在低秩數值矩陣上具有很好的補全效果而在近似低秩的自然圖像時恢復效果不佳的問題，受圖像的非局部自相似性和LRMA 算法的啟發，本文提出了一種基于非局部自相似性和低秩矩陣逼近的補全算法。

主要步驟如下：首先輸入n × n 缺失圖像X，任取一個p ×p 的局部塊yj；其次利用圖像的非局部自相似性，通過塊匹配方法［27］搜索其N 個非局部相似塊yjl(1 ≤l ≤N)，將每個非局部相似塊yjl向量化，并將所有向量化后所得向量疊加到矩陣Yj中；再次通過LRMA 算法從Yj估計出最后將估計好的矩陣進行重組，得到恢復圖像算法流程可見圖3，具體的算法見算法2。對于圖3中的塊匹配過程，也就是利用圖像的非局部自相似性，構造非局部相似塊組矩陣Yj的過程，如圖4所示，方框代表非局部相似塊。

圖3 算法2流程Fig.3 Flowchart of algorithm 2

圖4 相似塊組矩陣Yj的構造過程Fig.4 Formation process of similar patch group matrix Yj

算法2 NL-LRMA算法。

3 實驗結果與分析

在本章將提出的NL-LRMA算法應用于圖像恢復，并比較該算法與經典的圖像恢復算法（IRNN［28］、WNNM［29］、NLWNNM（NonLocal self-similarity and Weighted Nuclear Norm Minimization）［29］和LRMA［18］）的圖像恢復效果，其中NLWNNM 代表基于非局部自相似性和WNNM 結合的算法。本文實驗采用Matlab R2018b 編程，運行環境為Windows 10，Intel Core i7-7700 CPU 3.60 GHz，8 GB內存。

3.1 參數設定

本文算法中有幾個參數（c、ε、p、N 和maxIter），依據文獻［14］中的理論分析結果，參數c和誤差精度ε分別設定為0.98和1E-3。在塊匹配過程中，圖像局部塊的大小p × p 和非局部相似塊的個數N的設置對算法的性能影響較大：如果p和N設置過小，會使非局部相似塊組矩陣包含的信息比較少；反之，p設置過大，會使得圖像中的非局部相似塊較少，N設置過大，會使非局部相似塊組矩陣含有冗余信息?；诖?，局部塊的大小可根據采樣率來設置。考慮到結果的準確性和時間性能，根據數值實驗結果，當采樣率R為0.1和0.2時，局部塊的大小p × p 設置為50 × 50，相似塊的個數N 設置為70；當采樣率R 大于等于0.3 時，塊的大小p × p 設置為30 × 30，相似塊的個數N 設置為50。理論上，LRMA 算法是收斂的，但是，通過實驗發現若maxIter設置過大則實驗時間比較長，若設置值過小則圖像恢復效果欠佳。綜合考慮到實驗的執行時間和圖像恢復效果兩方面的因素，當圖像的大小為256 × 256 時，maxIter 設置為50；當圖像的大小為512 × 512 時，maxIter 設置為100。對于IRNN 算法［24］，本文對原始代碼的參數進行了一些微調，使其達到比較好的恢復效果。為了客觀評價圖像的恢復效果，采用峰值信噪比（PSNR）來衡量。設X為原圖像，為恢復圖像，則PSNR的定義為：

3.2 實驗結果對比

針對不同的采樣率R，將NL-LRMA 算法與其他經典的補全算法分別應用到10 幅256 × 256 大小的標準灰度圖像的恢復中，10 幅灰度圖像如圖5 所示，恢復結果的PSNR 值如表1所示。可以看出，在該圖像集上，本文所提算法的平均PSNR值要比其他算法的平均PSNR 值高出4～7 dB，并且基于非局部的兩個補全算法（NL-LRMA和NL-WNNM）明顯優于相應的未使用非局部的補全算法。

圖5 10幅灰度圖像Fig.5 Ten grayscale images

為進一步說明基于NL-LRMA 算法的優越性，本文以512×512 的Lena 灰度圖像為例，針對不同采樣率R，給出所提算法與其他經典補全算法PSNR值的對比曲線，如圖6所示。

圖6 不同算法的PSNR值的曲線圖Fig.6 Curves of PSNR values of different algorithms

此外，圖7分別展示了兩幅自然圖像在采樣率R為0.1時不同算法的圖像恢復結果。可以看出，本文算法在低采樣率時也有很好的恢復效果。

總之，由圖6 和圖7 可以看出，本文中所提的算法不僅使恢復圖像具有較高的PSNR值，而且具有更好的視覺效果。

本文所提算法不僅適用于灰度圖像的恢復，也容易推廣到RGB 圖像的恢復，其中一個簡單的實現方式是將其分別應用于R、G、B 通道；同時，為了提升NL-LRMA 算法的性能，本文先采用LRMA 算法對待恢復圖像進行預處理，再使用NLLRMA 算法進行圖像恢復。以Lena 圖像為例，圖8 展示了各算法的恢復效果，可以看出，本文算法在Lena 圖像恢復中也有很好的效果。

圖7 不同算法的灰度圖像恢復結果（采樣率R=0.1）Fig.7 Recovery results of different algorithms on gray scale image（sampling ratio R=0.1）

圖8 不同算法在Lena圖像上的恢復結果（采樣率R=0.2）Fig.8 Recovery results of different algorithms on Lena image（sampling ratio R=0.2）

表1 不同圖像恢復算法的峰值信噪比結果 單位：dBTab.1 PSNR results of different image recovery algorithms unit：dB

4 結語

本文提出了一種基于非局部自相似性和低秩矩陣逼近的補全算法，并將算法應用于自然圖像的恢復。由于低秩矩陣逼近的矩陣補全算法應用于近似低秩的自然圖像中恢復效果不佳，受自然圖像的非局部自相似性和低秩矩陣逼近算法的啟發，利用圖像的非局部自相似性，在缺失圖像上通過塊匹配方法可得到一個低秩的非局部相似塊組矩陣，進而可利用低秩矩陣逼近算法對低秩矩陣進行估計，將估計好的矩陣進行重組，從而可達到恢復圖像的目的。實驗結果表明，所提算法在灰度圖像以及RGB 圖像的恢復方面不僅具有較高的峰值信噪比值，而且使得所恢復圖像具有良好的視覺效果。