基于自動(dòng)秩估計(jì)的黎曼優(yōu)化矩陣補(bǔ)全算法及其在圖像補(bǔ)全中的應(yīng)用
doi: 10.11999/JEIT181076
-
1.
西安交通大學(xué)電子與信息工程學(xué)院 西安 710049
-
2.
西安交通大學(xué)智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實(shí)驗(yàn)室 ??西安 ??710049
Automatic Rank Estimation Based Riemannian Optimization Matrix Completion Algorithm and Application to Image Completion
-
1.
School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China
-
2.
Ministry of Education Key Laboratory for Intelligent Networks and Network Security, Xi’an Jiaotong University, Xi’an 710049, China
-
摘要: 矩陣補(bǔ)全(MC)作為壓縮感知(CS)的推廣,已廣泛應(yīng)用于不同領(lǐng)域。近年來(lái),基于黎曼優(yōu)化的MC算法因重構(gòu)精度高、計(jì)算速度快的特點(diǎn),引起了廣泛關(guān)注。針對(duì)基于黎曼優(yōu)化的MC算法需假設(shè)原矩陣秩固定已知,且隨機(jī)選擇迭代起點(diǎn)的特點(diǎn),該文提出一種基于自動(dòng)秩估計(jì)的黎曼優(yōu)化MC算法。該算法通過(guò)優(yōu)化包含秩正則項(xiàng)的目標(biāo)函數(shù),迭代獲取秩估計(jì)值和預(yù)重構(gòu)矩陣。在估計(jì)所得秩對(duì)應(yīng)的矩陣空間上以預(yù)重構(gòu)矩陣為迭代起點(diǎn),利用基于黎曼流形的共軛梯度法進(jìn)行矩陣補(bǔ)全,從而提高重構(gòu)精度。實(shí)驗(yàn)結(jié)果表明,與幾種經(jīng)典的圖像補(bǔ)全方法相比,該文算法圖像重構(gòu)精度顯著提高。
-
關(guān)鍵詞:
- 圖像補(bǔ)全(IC) /
- 矩陣補(bǔ)全(MC) /
- 自動(dòng)秩估計(jì) /
- 黎曼優(yōu)化 /
- 卷積神經(jīng)網(wǎng)絡(luò)
Abstract: As an extension of Compressed Sensing(CS), Matrix Completion(MC) is widely applied to different fields. Recently, the Riemannian optimization based MC algorithm attracts a lot of attention from researchers due to its high accuracy in reconstruction and computational efficiency. Considering that the Riemannian optimization based MC algorithm assumes a fixed rank of the original matrix, and selects a random initial point for iteration, a novel algorithm is proposed, namely automatic rank estimation based Riemannian optimization matrix completion algorithm. In the proposed algorithm, the estimate of rank is obtained minimizing the objective function that involving the rank regulation, in addition, the iterative starting point is optimized based on Riemannian manifold. The Riemannian manifold based conjugate gradient method is then used to complete the matrix, thereby improving the reconstruction precision. The experimental results demonstrate that the image completion performance is significantly improved using the proposed algorithm, compared with several classical image completion methods. -
表 1 自動(dòng)秩估計(jì)算法偽代碼
算法1 自動(dòng)秩估計(jì)算法 輸入:${\text{A}} = {{\text{A}}_p} \in {\mathbb {R}^{m \times n}}$,索引矩陣${\text{Ω}}$,正則項(xiàng)系數(shù)$\mu $, $\alpha $,初始秩$\hat k$,最大迭代次數(shù)$K$,容錯(cuò)度${\tau _2}$。 初始化:執(zhí)行奇異值分解${\text{A}}{\rm{ = }}{\text{U}}{\text{W}}{{\text{V}}^{\rm{T}}}$,將${\text{U}}$的第$r$列單位化記為${{\text{u}}_r}$,將${\text{V}}$的第$r$行單位化記為${{\text{v}}_r}$, ${\text{w}} = \left\{ {{w_r}} \right\}_{r = 1}^{\min \left( {m,n} \right)}$為${\text{W}}$中奇異值組成的 向量。令${\text{Z}} = {\text{0}}$, ${{\text{P}}_{{\Omega ^c}}}\left( {\text{A}} \right) = {\text{0}}$。 輸出:${\text{Z}} $, $k$。 (1) for $i = 1,2,·\!·\!·,K$ do: (2) ${{\text{A}}_r} = {\text{A}}$; (3) 更新${{\text{u}}_r}$, ${{\text{v}}_r}$, ${w_r}$: for $r = 1,2, ·\!·\!· ,\hat k$ do: 若${w_r} \ne 0$,根據(jù)式(8)、式(9)和式(11)依次更新${{\text{u}}_r}$, ${{\text{v}}_r}$, ${w_r}$, ${{\text{A}}_r} = {{\text{A}}_r} - {w_r}{{\text{u}}_r}{\text{v}}_r^{\rm{T}}$, end; (4) 更新${\text{A}}$:更新${\text{Z}} = {\text{A}} - {{\text{A}}_r}$,令${ {\text{P} }_{ {\varOmega ^c} } }\left( {\text{A} } \right) = { {\text{P} }_{ {\varOmega ^c} } }\left( {\text{Z} } \right)$; (5) 更新$k$:for $k = 1,2, ·\!·\!· ,\min\left( {m,n} \right)$ do: 計(jì)算$f\left( k \right) = {\rm{ } }\mu \left| { { {\text{w} }_r} } \right|_{r = 1}^k + 0.5\parallel {\text{A} } - \sum\limits_{r = 1}^k { {w_r}{ {\text{u} }_r}{ {\text{v} }_r}^{\rm{T} } } \parallel _{\rm F}^2 + \alpha k$,若$f\left( k \right) < f\left( {k + 1} \right)$,則結(jié)束循環(huán), end; (6) $\hat k = k$; (7) 若${{\parallel {{\text{P}}_\Omega }\left( {{\text{A}} - {\text{Z}}} \right){\parallel _{\rm{F}}}} /{\parallel {{\text{P}}_\Omega }\left( {\text{A}} \right){\parallel _{\rm{F}}}}} < {\tau _2}$或${{\parallel {{\text{A}}^{i + 1}} - {{\text{A}}^i}{\parallel _{\rm{F}}}} / {\parallel {{\text{A}}^{i + 1}}{\parallel _{\rm{F}}}}} < {\tau _2}$,則結(jié)束循環(huán); (8) end。 下載: 導(dǎo)出CSV
表 2 基于自動(dòng)秩估計(jì)的黎曼優(yōu)化矩陣補(bǔ)全算法偽代碼
算法2 基于自動(dòng)秩估計(jì)的黎曼優(yōu)化矩陣補(bǔ)全算法 輸入:${{\text{X}} _1}{\rm{ = }}Z \in {{\cal M}_k}$(${\text{Z}} $和$k$源于算法1),容錯(cuò)度${\tau _1}$,切向量${{\text{η}} _0}{\rm{ = }}0$。 輸出:${{\text{X}}^ * }$。 (1) for $i = 1,2, ·\!·\!· ,K$ do: (2) 梯度${\xi _i}: = {\rm{gradf}}\left( {{{\text{X}}_i}} \right)$; % 計(jì)算黎曼梯度 (3) 若$\parallel {\xi _i}\parallel \le {\tau _1}$,則停止迭代,令${{\text{X}}^ * }{\rm{ = }}{{\text{X}}_i}$,否則轉(zhuǎn)(4);% 終止條件 (4) 共軛方向${{\text{η}} _i}: = - {\xi _i} + {\beta _i}{{\cal T}_{{{\text{X}} _{i - 1}} \to {{\text{X}}_i}}}\left( {{{\text{η}}_{i - 1}}} \right)$; % 計(jì)算共軛方向 (5) 步長(zhǎng)${t_i} = {{\rm{argmin}}_t}f\left( {{{\text{X}}_i} + t{{\text{η}} _i}} \right)$; % 計(jì)算步長(zhǎng) (6) 執(zhí)行Armijo回溯以找到滿(mǎn)足$f\left( {{{\text{X}}_i}} \right) - f\left( {{R_{{{\text{X}}_i}}}\left( {0.{5^m}{t_i}{{\text{η}} _i}} \right)} \right) \ge - 0.0001 \times 0.{5^m}{t_i}\left\langle {{\xi _i},{{\text{η}} _i}} \right\rangle $且m≥0的最小整數(shù),計(jì)算${X_{i + 1}}: = {R_{{{\text{X}}_i}}}\left( {0.{5^m}{t_i}{{\text{η}} _i}} \right)$; % 收縮算子 (7) end。 下載: 導(dǎo)出CSV
表 3 基于各算法的補(bǔ)全后圖像PSNR(dB)/SSIM指標(biāo)評(píng)價(jià)
采樣率(%) 圖像補(bǔ)全算法 本文算法 SVP OptSpace SVT IALM 10 Barbara 25.1371/0.1018 27.1138/0.0749 28.4540/0.2703 26.4330/0.1817 27.9684/0.2217 House 25.0207/0.0737 27.0100/0.0845 28.8611/0.3805 26.0756/0.2122 27.3161/0.0319 20 Barbara 29.5855/0.6187 29.4788/0.3705 29.0277/0.3509 27.7929/0.3638 29.0097/0.3175 House 32.1346/0.7750 30.5881/0.4681 29.2989/0.4096 28.0950/0.4569 29.1008/0.0667 30 Barbara 31.8223/0.7775 30.5821/0.5530 29.7224/0.4138 29.0192/0.5193 29.6337/0.4010 House 34.3279/0.8434 32.6125/0.6858 29.8818/0.4437 30.2986/0.6472 29.9081/0.4560 40 Barbara 33.1805/0.8054 31.3704/0.6249 30.4532/0.4922 30.2063/0.6471 30.2152/0.4592 House 36.9926/0.9175 33.4685/0.7449 30.5393/0.4687 32.2618/0.7718 30.6276/0.4546 50 Barbara 34.3090/0.8545 32.3230/0.7045 31.1457/0.5349 31.6388/0.7607 31.0285/0.5060 House 37.9729/0.9342 34.4193/0.7909 31.8817/0.5854 34.2940/0.8575 31.3316/0.4965 60 Barbara 35.5808/0.8932 33.3609/0.7612 32.2731/0.5955 33.4085/0.8552 31.9375/0.5660 House 39.5723/0.9504 35.5242/0.8297 33.5629/0.7099 36.5579/0.9150 32.3391/0.4992 70 Barbara 37.1206/0.9277 34.6884/0.8124 33.4690/0.6453 35.7766/0.9191 33.0595/0.6449 House 41.0744/0.9622 36.8819/0.8690 34.4479/0.7395 39.3028/0.9524 33.4229/0.5724 80 Barbara 39.0801/0.9529 36.4704/0.8665 35.3219/0.7479 38.8081/0.9565 34.7671/0.6462 House 43.1665/0.9728 38.6710/0.9042 37.2815/0.8288 41.8076/0.9234 35.2485/0.6317 90 Barbara 42.3685/0.9699 39.3773/0.9213 38.4127/0.8653 40.6578/0.9357 38.0598/0.7796 House 46.1068/0.9810 41.9691/0.9442 40.3322/0.8943 42.0364/0.9707 38.1441/0.7449 下載: 導(dǎo)出CSV
-
臧芳. 一種利用低秩矩陣填充技術(shù)恢復(fù)氣象數(shù)據(jù)的方法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2017, 34(9): 322–327. doi: 10.3969/j.issn.1000-386x.2017.09.063ZANG Fang. Method of restoring meteorological data using low-rank matrix filling technique[J]. Computer Applications and Software, 2017, 34(9): 322–327. doi: 10.3969/j.issn.1000-386x.2017.09.063 楊國(guó)亮, 魯海榮, 豐義琴, 等. 基于非局部矩陣填充的文物修復(fù)技術(shù)研究[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2016, 33(11): 126–129. doi: 10.3969/j.issn.1000-386x.2016.11.030YANG Guoliang, LU Hairong, FENG Yiqin, et al. On cultural relic images restoration technology based on non-local matrix completion[J]. Computer Applications and Software, 2016, 33(11): 126–129. doi: 10.3969/j.issn.1000-386x.2016.11.030 陳秋實(shí), 楊強(qiáng), 董英凝, 等. 基于矩陣填充的合成寬帶高頻雷達(dá)非網(wǎng)格目標(biāo)分辨技術(shù)研究[J]. 電子與信息學(xué)報(bào), 2017, 39(12): 2874–2880. doi: 10.11999/JEIT170449CHEN Qiushi, YANG Qiang, DONG Yingning, et al. Off-the-grid targets resolution of synthetic bandwidth high frequency radar based on matrix completion[J]. Journal of Electronics &Information Technology, 2017, 39(12): 2874–2880. doi: 10.11999/JEIT170449 CAI T T and ZHANG Anru. 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. doi: 10.1109/TIT.2013.2288639 CAI Jianfeng, CANDES E J, and SHEN Zuowei. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956–1982. doi: 10.1137/080738970 LIN Zhouchen, CHEN Minming, and MA Yi. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. arXiv preprint arXiv: 1009.5055, 2010. VANDEREYCKEN B. Low-rank matrix completion by riemannian optimization[J]. SIAM Journal on Optimization, 2013, 23(2): 1214–1236. doi: 10.1137/110845768 MEKA R, JAIN P, and DHILLON I S. Guaranteed rank minimization via singular value projection[C]. Proceedings of the Neural Information Processing Systems Conference, Vancouver, Canada, 2010: 937–945. KESHAVAN R H and OH S. A gradient descent algorithm on the grassman manifold for matrix completion[J]. arXiv preprint arXiv: 0910.5260, 2009. SHI Qiquan, LU Haiping, and CHEUNG Y. Rank-one matrix completion with automatic rank estimation via L1-norm regularization[J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(10): 4744–4757. doi: 10.1109/TNNLS.2017.2766160 陳蕾, 陳松燦. 矩陣補(bǔ)全模型及其算法研究綜述[J]. 軟件學(xué)報(bào), 2017, 28(6): 1547–1564. doi: 10.13328/j.cnki.jos.005260CHEN Lei and CHEN Songcan. Survey on matrix completion models and algorithms[J]. Journal of Software, 2017, 28(6): 1547–1564. doi: 10.13328/j.cnki.jos.005260 CANDèS E J and RECHT B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9(6): 717–772. doi: 10.1007/s10208-009-9045-5 LI Wei, ZHAO Lei, LIN Zhijie, et al. Non-local image inpainting using low‐rank matrix completion[J]. Computer Graphics Forum, 2015, 34(6): 111–122. doi: 10.1111/cgf.12521 LIU Ping, LEWIS J, and RHEE T. Low-rank matrix completion to reconstruct incomplete rendering images[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(8): 2353–2365. doi: 10.1109/TVCG.2017.2722414 DONG Bin, MAO Yu, OSHER S, et al. Fast linearized Bregman iteration for compressive sensing and sparse denoising[J]. Communications in Mathematical Sciences, 2010, 8(1): 93–111. doi: 10.4310/CMS.2010.v8.n1.a6 LIU Yuanyuan, SHANG Fanhua, WEI Fan, et al. Generalized higher-order orthogonal iteration for tensor decomposition and completion[C]. Proceedings of the 27th International Conference on Neural Information Processing Systems, Montreal, Canada, 2014: 1763–1771. HORE A and ZIOU D. Image quality metrics: PSNR vs. SSIM[C]. Proceedings of the 20th International Conference on Pattern Recognition, Istanbul, Turkey, 2010: 2366–2369. ÖZIÇ M Ü and ÖZŞEN S. A new model to determine asymmetry coefficients on MR images using PSNR and SSIM[C]. Proceedings of 2017 International Artificial Intelligence and Data Processing Symposium, Malatya, Turkey, 2017: 1–6. -