張 麗，孔 旭，孫忠貴

（聊城大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山東聊城 252000）

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

0 引言

通過(guò)矩陣已知元素來(lái)恢復(fù)出未知元素的問(wèn)題通常稱為矩陣補(bǔ)全（Matrix Completion，MC）問(wèn)題。隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展，矩陣補(bǔ)全已成為信號(hào)與圖像處理研究的熱點(diǎn)問(wèn)題，可廣泛應(yīng)用于圖像修復(fù)［1］、多標(biāo)記圖像分類［2］、系統(tǒng)辨識(shí)［3］、推薦系統(tǒng)［4］和半監(jiān)督聚［5］類等諸多領(lǐng)域中。

矩陣補(bǔ)全問(wèn)題可建模為仿射秩最小化問(wèn)題：

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

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

對(duì)于第一類方法，盡管該類方法在矩陣補(bǔ)全中得到了廣泛的應(yīng)用，但是核函數(shù)不能準(zhǔn)確地近似秩函數(shù)。自然的想法是在矩陣補(bǔ)全的過(guò)程中直接采用秩函數(shù)；然而，現(xiàn)實(shí)中待補(bǔ)全矩陣的秩往往是未知的，因此，在采用第二類方法進(jìn)行矩陣補(bǔ)全時(shí)，也會(huì)遇到一定的問(wèn)題。

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

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

1 低秩矩陣逼近的補(bǔ)全算法

如果已知待補(bǔ)全矩陣秩的大小，可以將問(wèn)題（1）建模如下：

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

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

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

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

2 NL-LRMA算法

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

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

由于矩陣的秩等于矩陣的非奇異值的個(gè)數(shù)，所以低秩矩陣的奇異值大部分為0。對(duì)自然圖像的數(shù)值矩陣進(jìn)行奇異值分解，并取不同的奇異值與對(duì)應(yīng)的酉矩陣進(jìn)行重構(gòu)圖像，如圖2所示。

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

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

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

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

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

圖4 相似塊組矩陣Yj的構(gòu)造過(guò)程Fig.4 Formation process of similar patch group matrix Yj

算法2 NL-LRMA算法。

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 參數(shù)設(shè)定

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

3.2 實(shí)驗(yàn)結(jié)果對(duì)比

針對(duì)不同的采樣率R，將NL-LRMA 算法與其他經(jīng)典的補(bǔ)全算法分別應(yīng)用到10 幅256 × 256 大小的標(biāo)準(zhǔn)灰度圖像的恢復(fù)中，10 幅灰度圖像如圖5 所示，恢復(fù)結(jié)果的PSNR 值如表1所示?？梢钥闯?，在該圖像集上，本文所提算法的平均PSNR值要比其他算法的平均PSNR 值高出4～7 dB，并且基于非局部的兩個(gè)補(bǔ)全算法（NL-LRMA和NL-WNNM）明顯優(yōu)于相應(yīng)的未使用非局部的補(bǔ)全算法。

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

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

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

此外，圖7分別展示了兩幅自然圖像在采樣率R為0.1時(shí)不同算法的圖像恢復(fù)結(jié)果?？梢钥闯?，本文算法在低采樣率時(shí)也有很好的恢復(fù)效果。

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

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

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

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

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

4 結(jié)語(yǔ)

本文提出了一種基于非局部自相似性和低秩矩陣逼近的補(bǔ)全算法，并將算法應(yīng)用于自然圖像的恢復(fù)。由于低秩矩陣逼近的矩陣補(bǔ)全算法應(yīng)用于近似低秩的自然圖像中恢復(fù)效果不佳，受自然圖像的非局部自相似性和低秩矩陣逼近算法的啟發(fā)，利用圖像的非局部自相似性，在缺失圖像上通過(guò)塊匹配方法可得到一個(gè)低秩的非局部相似塊組矩陣，進(jìn)而可利用低秩矩陣逼近算法對(duì)低秩矩陣進(jìn)行估計(jì)，將估計(jì)好的矩陣進(jìn)行重組，從而可達(dá)到恢復(fù)圖像的目的。實(shí)驗(yàn)結(jié)果表明，所提算法在灰度圖像以及RGB 圖像的恢復(fù)方面不僅具有較高的峰值信噪比值，而且使得所恢復(fù)圖像具有良好的視覺(jué)效果。