6 41 x y R M. y = Φx 1) 1),, y x., x, Φ Restricted isometry property, RIP), x ). min x 0, s. t. y = Φx ) x R N, Ψ = [ψ 1 ψ N ], N x = ψ n θ n = ΨΘ 3)

Size: px

Start display at page:

Download "6 41 x y R M. y = Φx 1) 1),, y x., x, Φ Restricted isometry property, RIP), x ). min x 0, s. t. y = Φx ) x R N, Ψ = [ψ 1 ψ N ], N x = ψ n θ n = ΨΘ 3)"

侑澜董
7 years ago
Views:

1 41 Vol. 41, No. 015 ACTA AUTOMATICA SINICA February, 015 1, 1, 1, 1, 1, Compressed sensing, CS),,,.,,.,.,,,,,,,.., 015, 41): 61 7 DOI /j.aas.015.c14010 Image Reconstruction Algorithm of Compressed Sensing Based on Nonlocal Similarity Model SHEN Yan-Fei 1, LI Jin-Tao 1, ZHU Zhen-Min 1, ZHANG Yong-Dong 1, DAI Feng 1, Abstract In this paper, an image reconstruction algorithm of compressed sensing CS) is proposed based on nonlocal similarity model. Instead of using the traditional sparse property of D image blocks, the sparse representation of 3D similar image block group is exploited to increase the sparse degree of reconstructed image and improve the performance of the compressed sensing reconstruction algorithm. The texture and structure features are well preserved in the reconstructed image. In the solution of our proposed algorithm, the constrained optimization problem is transformed into an unconstrained optimization problem by augmented Lagrangian method, and the linear technique, which is based on Taylor expansion, is employed to reduce the computational burden and accelerates our proposed algorithm. Experimental results show that the subjective and objective performance of our proposed reconstruction algorithm is superior to the state of art reconstruction algorithms. Key words Compressed sensing CS), image reconstruction, nonlocal similarity, sparse representation Citation Shen Yan-Fei, Li Jin-Tao, Zhu Zhen-Min, Zhang Yong-Dong, Dai Feng. Image reconstruction algorithm of compressed sensing based on nonlocal similarity model. Acta Automatica Sinica, 015, 41): 61 7 Compressed sensing, CS),,,. : 1) Manuscript received April 1, 014; accepted August 1, , ), YZ0131) Supported by National Natural Science Foundation of China , ) and Instrument Developing Project of the Chinese Academy of Sciences YZ0131) Recommended by Associate Editor ZHANG Chang-Shui Institute of Computing Technology, Chinese Academy of Sciences, Beijing Beijing Key Laboratory of Mobile Computing and Pervasive Device, Beijing ,,,, ; ),,, ; 3),,. : N x R N, x K K N), x, K/N. x Φ Φ R M N, M N), ), 1),

2 6 41 x y R M. y = Φx 1) 1),, y x., x, Φ Restricted isometry property, RIP), x ). min x 0, s. t. y = Φx ) x R N, Ψ = [ψ 1 ψ N ], N x = ψ n θ n = ΨΘ 3) n=1, Θ, Ψ x, y = ΦΨΘ 4), A = ΦΨ, A RIP, Φ Ψ.,,. : [1].,,,,, [ 3].,, : [4 6] [7 8] [9] [10] [11 13].,,., [14] Total variation, TV) [15] [16] [17], TV,.,, TV [18 19], 5) : T V X) = min T V X), s. t. Y = ΦX 5) X i+1 X + X +1 X 6) T V X) = X i+1,j X ) + X +1 X ) 7), i, j), 6) 7). TV,. TV, ), TV : Second-order cone programming, SOCP) [0] l- Magic [1] Two-step iterative threshold, TwIST) [] NESTA [3] RecPF [4] TVAL3 [5] [6], TV,,,.,,, [7]. [8], Buades Non-local means) [17],, :,,... [17], y = Φx,

3 : 63.,,,,., [9].. 1,,.,, 1., : [30] [31]., [17]. Fig. 1 1 Redundant information in the nature image V = {V x, y) x, y) Z},, V x 0, y 0 ), : ˆV x 0, y 0 ) = 1 cx, y) x,y) Ω ωx, y)vx, y) 8) cx, y) = x,y) Ω ωx, y) 9), Ω V x 0, y 0 ), ωx, y) V x 0, y 0 ) Ω V x, y)., V x 0, y 0 ), Nx 0, y 0 ), ωx, y) = exp Nx ) 0, y 0 ) Nx, y),α h 10), α, h,,α. 10),,,. [3 33],,, Shrinkage thresholding, ST),.,,. ), ;,,,, ),., 5 : 1) ; ) ; 3) ; 4) ; 5).,,,. K-means [34] [35] [36] [37].,,

4 64 41,.,,.,,.,. P, k 1 k, P SP ) = {Q : dp, Q) th 1 } 11), DCT Haar, ;, : SP ) rec = T 1 3DγT 3D SP )))) 14), T 3D, γ, λ hard 3D σ. { 0, x λ hard 3D σ γ = x, 15), th 1, P Q th 1,. dp, Q), : dp, Q) = P Q k 1 k 1),,,,,,. Dabov Hard threshold, HT) [3], P Q,, : dp, Q) = γt DP )) γt D Q)) k 1 k 13), T D, DCT, γ, λ hard D σ, λ hard D σ, σ, σ 40, λ hard D σ = 0,,.,,,,,,,, n n, P k 1 k, Q P,., ;, Fig. The current image block, the matching image block and the search window,,,,.,,,,,. NP hard, P, : W hard P = { N hard P ) 1, N hard P 1 1, 16),, V = W P hard SP ) rec W hard P 17)

5 : 65,,., TV;, DCT ).,,.,. X, N N, A, Y = AX + Ω, Ω. Y X,,, Y = AX + Ω, X,. N,N X = min SP ) W S SP )) X s.t. Y AX ε, P X 18), P i, j), SP ) P, W S. 18) 1, W S SP )), SP ) W S SP )), Y AX ε. W S,,, : N,N X = min SP ) W S SP )) X s.t. Y AX ε, X = U, P U 19) 19) N,N LX, U) = SP ) W S SP )) α T Y AX) + β Y AX γ T X U) + θ X U 0), β θ Y AX X U, α T γ T. LX, U) 18), 0), k. X k+1, U k+1) = min L X k, U k) 1) X,U α k+1 = α k β Y AX k+1) ) γ k+1 = γ k θ X k+1 U k+1) 3), 1), ADM X U, U X ; X U,..1 X k U U k, X k+1 X k+1 = min α T Y AX) + β X Y AX γ T X U k ) + θ ) X U k 4) 4), : X k+1 β = min X Y AX α β θ X U k γ ) θ + 5),, : βa T AX k+1 Y + α β ) + θxk+1 U k γ θ ) = 0 6) X k+1 = βa T A + θi ) 1 βa T Y αa T + θu k + γ ) 7), I,, βa T A + θi) 1,,,,,., Y AX α/β,

6 66 41, Y AX α/β k X k, : Y AX α β = Y AX k α β + g k X X k ) + ρ X X k 8), g k Y AX α/β Xk, g k = A T AX k Y + α/β), ρ, 4) X k+1 = min X β Y AXk α β g ) ) k X X k + βρ X X k + θ X U k γ ) 9) θ X k+1, β gk + ρx X k ) ) + θ X U k γ θ θu k + γ β X k+1 = g k + ρβx k βρ + θ + ) = 0 30) 31),.. U X, U, X k+1, U k+1 = min U N,N SP ) W S SP )) γ T X U) + θ X U s.t. Si, j) U 3), : U k+1 = min U N,N ) SP ) W S SP )) + θ X U γ ) θ s.t. Si, j) U 33), 1 U P. 1,, 33) P k+1 = min P SP ) W S SP )) + ) 34) θ SP ) SW ), W X γ/θ, P,., U k+1,, 17) : X 0 = A T Y, U 0 = 0, α 0 = 0, γ 0 = 0, θ, β, τ, k = 0;. while do; 3. 31) X ; 4. X k+1 : SP ) = Q : dp, Q) th 1); 5. 34); 6. P k+1, U k+1 ; 7. ) 3) α k+1 γ k+1 ; 8. k = k + 1; 9. end while; 10. : X k DCT, : 1) ; ) DCT ; 3) DCT. DCT,, DCT,., Peak signal to noise ratio, PSNR), PSNR : 55 PSNR = 10 lg 35) 1 wh ˆx i x i ) wh i=1

7 : 67, x i ˆx i, w h.,, : T 3D k 1 k 1 k step NS max N s λ hard D λ hard 3D,,. 3.1,,,,,. 1.,., DCT DCT + Haar,, Bior 1.5.,, DCT DCT + Haar ;,, Bior 1.5 DCT DCT + Haar,, Bior Table 1 Default parameters set in the proposed CS image reconstruction algorithm T 3D DCT + Haar k 1 k k step 3 NS max 16 λ hard D λ hard 3D.7 N s ,, 3. 5, Haar Bior 1.5 DCT Hadamard DCT + Haar, Boat Baboon, 51 51,.,, Boat Baboon,, Boat Baboon. Table Boat Baboon 3 Fig. 3 Sparse representation for similar image block group db) The performance of CS image reconstruction based on different sparse basises db) DCT Haar Bior 1.5 Hadamard DCT + Haar

8 68 41,,,.,,,,,,,,,,.,, , 3., 4 4,,.,,,,,,,. Table 3 3 db) The performance of CS image reconstruction based on the different block size db) Boat Baboon ,,,,,,,, ;,,,., , 4., 4,,, ,. 4 db) Table 4 The performance of CS image reconstruction based on the different group size of similar image block group db) Boat Baboon ,,.,,, , 4, 8 8, 51 8)/4 1) 51 8)/4 1) = 15,,,,,., , 5.,,,, 3.

9 : 69 5 db) Table 5 The performance of CS image reconstruction based on the different sliding step of similar block db) Boat Baboon ,., , 51 8),.,,.,,., , 6.,,,, ,,,. : Barbara Parrot Peppers Cameraman Monarch Lena MRI-I MRI-II,, YALL1 [38] BCS [39] NESTA [3] BM3D-CS [9].,.,,,. 1, ρ, DCT, ρ 1, 0) β θ 0.5. Table 6 6 db) The performance of CS image reconstruction based on the different size of search windows db) Boat Baboon , NLCSR. 7,, NLCSR. Barbara,, 3 db,., NLCSR BM3D-CS,,, BM3D-CS., YALL1,, TV, NLCSR YALL1, 8 db., 0.3, NLCSR YALL1 BCS NESTA BM3D-CS

10 自 70 Table 7 动化学报 41 卷表 7 在不同采样率下压缩感知图像恢复算法的恢复性能比较 db) The performance comparison of five CS image reconstruction algorithms under different sampling ratios db) Barbara 图像采样率 0.3 BM3D-CS 4.75 YALL1 1.3 Cameraman Lena Peppers 5.40 NESTA BCS NLCSR Monarch 图像 Parrot BM3D-CS YALL NESTA BCS NLCSR 图4 Fig MRI-II 0. 3 采样率 0. 5 MRI-I 在 0.3 采样率时测试图像 Barbara 的恢复图像及其恢复残差 The reconstruction image and its corresponding residual image for test image Barbara under 0.3 sampling ratio 对相同的感知测量数据进行图像恢复, 恢复图像及其恢复残差如图 4 所示, 从图中可以看到, 由本文中的 NLCSR 算法恢复出的图像主观质量最好, 不仅在平滑区域没有混叠信号, 而且对纹理特征也保持得非常好. 从对应的残差图像还可以看到, NLCSR 算法产生的残差图像也是最小的, 特别是纹理区域的残差, 例如 Barbara 测试图像中的纹理区域. 由 YALL1 算法恢复的图像, 在低采样率情况下, 重建图像中有明显的油画效果, 这是基于全变差模型的固有缺陷, 即对图像的过度平滑. 对于基于图像块采样的压缩感知算法 BCS, 尽管作者在重建过程中使用了维纳滤波器进行了去块斑处理, 但其重建图像中还是有明显的块效应. 由 BM3D-CS 算法重建的图像在 PSNR 性能上仅次于本文 NLCSR 算法, 重建图像的主观质量也比较平滑, 但从其残差图像中可以看到在边缘部分重建误差很大. 由 NESTA 算法恢复得到的图像, 如果图像本身比较平滑, 则重建图像质量较好, 而对含有复杂纹理信息的测试图像, 重建误差也仍然较大, 如 Barbara 图像. 因此无论基于 PSNR 的客观评价, 还是基于恢复图像质量的主

11 : 71, NLCSR. 4,,,,.,,,.,. References 1 Qaisar S, Bilal R M, Iqbal W, Naureen M, Sungyoung L. Compressive sensing: from theory to applications, a survey. Journal of Communications and Networks, 013, 155): Guo W H, Qin J, Yin W T. A New Detail-preserving Regularity Scheme. Technical Report, Rice CAAM, Xu Y Y, Yin W T. A fast patch-dictionary method for whole-image recovery. Technical Report, UCLA CAM, Baraniuk R G, Cevher V, Duarte M F, Hegde C. Modelbased compressive sensing. IEEE Transactions on Information Theory, 010, 564): Chen C, Huang J Z. Compressive sensing MRI with wavelet tree sparsity. In: Proceedings of the 6th Annual Conference on Neural Information Processing Systems NIPS). Nevada, USA: NIPS, He L H, Carin L. Exploiting structure in wavelet-based Bayesian compressive sensing. IEEE Transactions on Signal Processing, 009, 579): Lustig M, Donoho D L, Santos J M, Pauly J M. Compressed sensing MRI. IEEE Signal Processing Magazine, 008, 5): Ma S W, Yin W T, Zhang Y, Chakraborty A. An efficient algorithm for compressed MR imaging using total variation and wavelets. In: Proceedings of the 008 Computer Vision and Pattern Recognition CVPR). Anchorage, AK: IEEE, Egiazarian K, Foi A, Katkovnik V. Compressed sensing image reconstruction via recursive spatially adaptive filtering. In: Proceedings of the 007 International Conference on Image Processing ICIP). San Antonio, TX: IEEE, Dong W S, Zhang L, Shi G M, Li X. Nonlocally centralized sparse representation for image restoration. IEEE Transactions on Image Processing, 013, 4): Waters A E, Sankaranarayanan A C, Baraniuk R G. SpaRCS: recovering low-rank and sparse matrices from compressive measurements. In: Proceedings of the 5th Annual Conference on Neural Information Processing Systems NIPS). Granada, Spain: NIPS, Ji H, Liu C Q, Shen Z W, Xu Y H. Robust video denoising using low rank matrix completion. In: Proceedings of the 010 Computer Vision and Pattern Recognition CVPR). San Francisco, CA: IEEE, Otazo R, Candès E, Sodickson D K. Low-rank plus sparse matrix decomposition for accelerated dynamic MRI with separation of background and dynamic components. Magnetic Resonance in Medicine, DOI: /mrm Bioucas D J M, Figueiredo M A T. A new TwIST: twostep iterative shrinkage thresholding algorithms for image restoration. IEEE Transactions on Image Processing, 007, 161): Rudin L, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Physica D, 199, 601 4): Luo J H, Li W Q, Zhu Y M. Reconstruction from limitedangle projections based on δ-u spectrum analysis. IEEE Transactions on Image Processing, 010, 191): Buades A, Coll B, Morel J M. A non-local algorithm for image denoising. In: Proceedings of the 005 Computer Vision and Pattern Recognition CVPR). San Francisco, CA: IEEE, Chan T F, Esedoglu S, Park F, Yip A. Recent Developments in Total Variation Image Restoration. Technical Report, Department of Mathematics, UCLA, Chambolle A, Lions P L. Image recovery via total variation minimization and related problems. Numerische Mathematik, 1997, 76): Goldfarb D, Yin W. Second-order cone programming methods for total variation based image restoration. SIAM Journal on Scientific Computing, 005, 7): Candes E J, Tao T. Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Transactions on Information Theory, 006, 51): Bioucas D J M, Figueiredo M A T. Two-step algorithms for linear inverse problems with non-quadratic regularization. In: Proceedings of the 007 IEEE International Conference on Image Processing ICIP). San Antonio, TX: IEEE, Becker S, Bobin J, Candès E. NESTA: a fast and accurate first-order method for sparse recovery. SIAM Journal on Imaging Sciences, 011, 41): Yang J F, Zhang Y, Yin W T. A fast alternating direction method for TVL1-L signal reconstruction from partial fourier data. IEEE Journal of Selected Topics in Signal Processing, 010, 4): Li C, Yin W, Zhang Y. TVAL3: TV minimization by augmented Lagrangian and alternating direction algorithms. [Online], available: November 7, Yuan X M, Yang J F, Xiao Y H. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems and Imaging, 01, 63): Danielyan A, Katkovnik V, Egiazarian K. BM3D frames and variational image deblurring. IEEE Transactions on Image Processing, 01, 14):

12 Efros A A, Leung T K. Texture synthesis by non-parametric sampling. In: Proceedings of the 1999 IEEE International Conference on Computer Vision ICCV). Kerkyra: IEEE, Afonso M, Bioucas D J, Figueiredo M. Fast image recovery using variable splitting and constrained optimization. IEEE Transactions on Image Processing, 010, 199): Protter M, Elad M, Takeda H, Milanfar P. Generalizing the nonlocal-means to super-resolution reconstruction. IEEE Transactions on Image Processing, 009, 181): Dong W, Yang X, Shi G. Compressive sensing via reweighted TV and nonlocal sparsity regularisation. Electronics Letters, 013, 493): Dabov K, Foi A, Katkovnik V, Egiazarian K. Image denoising by sparse 3D transform-domain collaborative filtering. IEEE Transactions on Image Processing, 013, 168): Maggioni M, Katkovnik V, Egiazarian K, Foi A. A nonlocal transform-domain filter for volumetric data denoising and reconstruction. IEEE Transactions on Image Processing, 013, 1): MacQueen J B. Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical. Berkeley California: Statistics and Probability, Kohonen T. The self-organizing map. Proceedings of the IEEE, 1990, 789): Hoppner F, Klawonn F, Kruse R, Runkler T. Fuzzy Cluster Analysis. Chichester: Wiley, Gersho A. On the structure of vector quantizers. IEEE Transactions on Information Theory, 198, 8): Yang J F, Zhang Y. Alternating direction algorithms for L1- problems in compressive sensing. SIAM Journal on Scientific Computing, 011, 331): Mun S, Fowler J E. Residual reconstruction for blockbased compressed sensing of video. In: Proceedings of the 011 Data Compression Conference DCC). Snowbird, UT: IEEE, ,. jtli@ict.ac.cn LI Jin-Tao Professor at the Institute of Computing Technology, Chinese Academy of Sciences. His research interest covers multimedia technology, virtual reality technology, and pervasive computing technology.).,. zmzhu@ict.ac.cn ZHU Zhen-Min Professor at the Institute of Computing Technology, Chinese Academy of Sciences. His research interest covers pervasive computing technology, multimedia technology, and embedded system technology.).,. zhyd@ict.ac.cn ZHANG Yong-Dong Professor at the Institute of Computing Technology, Chinese Academy of Sciences. His research interest covers video coding, video retrieval, multimedia content analysis and understanding.) syf@ict.ac.cn SHEN Yan-Fei Associate professor at the Institute of Computing Technology, Chinese Academy of Sciences. He received his Ph. D. degree from University of Chinese Academy of Sciences in 014. His research interest covers image processing. Corresponding author of this paper.).,. fdai@ict.ac.cn DAI Feng Associate professor at the Institute of Computing Technology, Chinese Academy of Sciences. His research interest covers video coding and processing, multimedia content analysis and understanding.)

Vol. 36 ( 2016 ) No. 6 J. of Math. (PRC) HS, (, ) :. HS,. HS. : ; HS ; ; Nesterov MR(2010) : 90C05; 65K05 : O221.1 : A : (2016)

Vol. 36 ( 2016 ) No. 6 J. of Math. (PRC) HS, (, ) :. HS,. HS. : ; HS ; ; Nesterov MR(2010) : 90C05; 65K05 : O221.1 : A : (2016) Vol. 36 ( 6 ) No. 6 J. of Math. (PRC) HS, (, 454) :. HS,. HS. : ; HS ; ; Nesterov MR() : 9C5; 65K5 : O. : A : 55-7797(6)6-9-8 ū R n, A R m n (m n), b R m, b = Aū. ū,,., ( ), l ū min u s.t. Au = b, (.)