基于自動(dòng)秩估計(jì)的黎曼優(yōu)化矩陣補(bǔ)全算法及其在圖像補(bǔ)全中的應(yīng)用

劉靜; 劉涵; 黃開(kāi)宇; 蘇立玉

doi:10.11999/JEIT181076

基于自動(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

基金項(xiàng)目: 國(guó)家自然科學(xué)基金(61573276)

詳細(xì)信息

作者簡(jiǎn)介:
劉靜：女，1975年生，教授，博士生導(dǎo)師，從事壓縮感知、圖像融合、雷達(dá)信號(hào)處理方向的研究

劉涵：女，1991年生，碩士生，研究方向?yàn)閴嚎s感知、圖像處理、矩陣補(bǔ)全

黃開(kāi)宇：男，1992年生，博士生，研究方向?yàn)閴嚎s感知、信號(hào)處理、信號(hào)與圖像處理

蘇立玉：男，1996年生，碩士生，研究方向?yàn)閴嚎s感知、圖像處理、張量補(bǔ)全

通訊作者:
劉靜　elelj20080730@gmail.com

中圖分類(lèi)號(hào): TP391.41
計(jì)量
- 文章訪(fǎng)問(wèn)數(shù): 3851
- HTML全文瀏覽量: 1956
- PDF下載量: 103
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-11-23
- 修回日期: 2019-05-07
- 網(wǎng)絡(luò)出版日期: 2019-05-20
- 刊出日期: 2019-11-01

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

Funds: The National Natural Science Foundation of China (61573276)

摘要

摘要: 矩陣補(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)精度顯著提高。
- 圖像補(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.
- Image Completion(IC) /
- Matrix Completion(MC) /
- Automatic rank estimation /
- Riemannian optimization /
- Convolutional Neural Network (CNN)

HTML全文

圖 1 基于自動(dòng)秩估計(jì)的黎曼優(yōu)化矩陣補(bǔ)全算法的圖像補(bǔ)全

下載: 全尺寸圖片幻燈片

圖 2 低秩矩陣構(gòu)建示意圖

下載: 全尺寸圖片幻燈片

圖 3 黎曼流形上的共軛梯度法

下載: 全尺寸圖片幻燈片

圖 4 30%采樣率下各算法圖像補(bǔ)全結(jié)果

下載: 全尺寸圖片幻燈片

表 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
10	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
20	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
30	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
40	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
50	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
60	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
70	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
80	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
90	House	46.1068/0.9810	41.9691/0.9442	40.3322/0.8943	42.0364/0.9707	38.1441/0.7449

下載: 導(dǎo)出CSV

參考文獻(xiàn)(18)

臧芳. 一種利用低秩矩陣填充技術(shù)恢復(fù)氣象數(shù)據(jù)的方法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2017, 34(9): 322–327. doi: 10.3969/j.issn.1000-386x.2017.09.063

ZANG 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.030

YANG 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/JEIT170449

CHEN 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.005260

CHEN 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪(fǎng)問(wèn)統(tǒng)計(jì)