基于压缩传感重建算法的研究
|
摘要
压缩传感是一种新型的稀疏采样方法。相对于经典的香农采样有两点不同,第一随机采样代替了一致均匀采样;第二在重建算法上,香农采样采用的是插值法来重建原始信号,而压缩采样是利用最优化算法,通过寻找最稀疏的采样,来重建原始信号。因此节省了先采样后压缩的过程,也就是说压缩传感整合了采样和压缩,节省了不必要的存储,对于实际工程有潜在的应用。
本文研究了压缩传感的重建算法,压缩传感的重建算法有两个主要部分,分别是信号的稀疏矩阵表示和测量矩阵。这里我们给出了几种稀疏矩阵的实例,首次提出用分数傅里叶变换作为稀疏表示的方法,并且分析了可行性,给出了测量矩阵满足的条件,并且归类举例说明了几种符合条件的测量矩阵模型。
虽然压缩传感还是比较新的压缩理论,但是关于压缩传感的重建算法已经涌现了许多。为了提高压缩传感算法的实时性,有些人提出了分块压缩传感算法,但是分块压缩传感,对于每一块图像用的测量矩阵是相同的,也就是说每一块的重要程度,只与图像的像素数有关,但是没有考虑除像素外的其他因素。一幅图像的重要部分应该是图像的边缘部分,这是符合人的视觉特点的,而每一块图像的边缘比例是不一样的,所以重要程度自然不一样。因此本文基于人眼视觉的特点,提出了一种新的压缩传感重建算法,即加权分块压缩传感算法,并且将其应用到正交匹配追踪算法和全变差最小化算法。为了说明算法的有效性,我们进行了大量的数值实验。实验表明,加权分块压缩算法,相比图像未经过分块的压缩传感重建算法,实时性明显提高;相比分块压缩传感重建算法,图像重建后的峰值信噪比提高了近一分贝,处理效果也显著提高了。
Compressed sensing is a new type of sparse sampling. There are two different aspects from the classical Shannon sampling. Firstly, it is random sampling instead of uniform sampling. Secondly, the interpolation is used in Shannon sampling while the algorithm of optimization in mathematic is used in the compressed sensing. It means the compressed sensing reconstructs the original signal by searching the least sparse sampling points. Hence it saves the process of compressing after sampling, that is to say, it integrates with the two processes. So it saves much more storage and will have potential application in the engineering.
In this paper, we principally invest the algorithm of the compressed sensing, which includes two major parts, the sparse matrix and the measurement matrix respectively. We give some examples of the sparse matrix. Specially, we propose the fractional Fourier transform as the sparse representation of the original signal creatively and analyze its feasibility. Also we give the condition meeting the measurement matrix and exemplify some model of the measurement matrix.
As a new theory, the reconstructed algorithm of compressed sensing emerges a lot recently. Some authors proposed the block compressed sensing in order to improve the real-time. However it used the same measurement matrix in every block of the image. It means the value of every block is not distinction except the amounts of the pixel. For an image, the edge is the important part, which is also the sensitive to mankind vision. The proportion of the edge in each block is different as so as the importance of each block. In this paper, we propose the weighted block compressed sensing based on mankind vision. Then we apply it to the orthogonal matching pursuit and minimization total variation. In order to verify the effectiveness of the algorithm, we perform a lot of numerical simulation. We show that the new method can improve the real-time comparing with the algorithm of compressed sensing without blocking and the PSNR nearly one decibel comparing with the algorithm of the block compressed sensing respectively.
本文研究了压缩传感的重建算法,压缩传感的重建算法有两个主要部分,分别是信号的稀疏矩阵表示和测量矩阵。这里我们给出了几种稀疏矩阵的实例,首次提出用分数傅里叶变换作为稀疏表示的方法,并且分析了可行性,给出了测量矩阵满足的条件,并且归类举例说明了几种符合条件的测量矩阵模型。
虽然压缩传感还是比较新的压缩理论,但是关于压缩传感的重建算法已经涌现了许多。为了提高压缩传感算法的实时性,有些人提出了分块压缩传感算法,但是分块压缩传感,对于每一块图像用的测量矩阵是相同的,也就是说每一块的重要程度,只与图像的像素数有关,但是没有考虑除像素外的其他因素。一幅图像的重要部分应该是图像的边缘部分,这是符合人的视觉特点的,而每一块图像的边缘比例是不一样的,所以重要程度自然不一样。因此本文基于人眼视觉的特点,提出了一种新的压缩传感重建算法,即加权分块压缩传感算法,并且将其应用到正交匹配追踪算法和全变差最小化算法。为了说明算法的有效性,我们进行了大量的数值实验。实验表明,加权分块压缩算法,相比图像未经过分块的压缩传感重建算法,实时性明显提高;相比分块压缩传感重建算法,图像重建后的峰值信噪比提高了近一分贝,处理效果也显著提高了。
Compressed sensing is a new type of sparse sampling. There are two different aspects from the classical Shannon sampling. Firstly, it is random sampling instead of uniform sampling. Secondly, the interpolation is used in Shannon sampling while the algorithm of optimization in mathematic is used in the compressed sensing. It means the compressed sensing reconstructs the original signal by searching the least sparse sampling points. Hence it saves the process of compressing after sampling, that is to say, it integrates with the two processes. So it saves much more storage and will have potential application in the engineering.
In this paper, we principally invest the algorithm of the compressed sensing, which includes two major parts, the sparse matrix and the measurement matrix respectively. We give some examples of the sparse matrix. Specially, we propose the fractional Fourier transform as the sparse representation of the original signal creatively and analyze its feasibility. Also we give the condition meeting the measurement matrix and exemplify some model of the measurement matrix.
As a new theory, the reconstructed algorithm of compressed sensing emerges a lot recently. Some authors proposed the block compressed sensing in order to improve the real-time. However it used the same measurement matrix in every block of the image. It means the value of every block is not distinction except the amounts of the pixel. For an image, the edge is the important part, which is also the sensitive to mankind vision. The proportion of the edge in each block is different as so as the importance of each block. In this paper, we propose the weighted block compressed sensing based on mankind vision. Then we apply it to the orthogonal matching pursuit and minimization total variation. In order to verify the effectiveness of the algorithm, we perform a lot of numerical simulation. We show that the new method can improve the real-time comparing with the algorithm of compressed sensing without blocking and the PSNR nearly one decibel comparing with the algorithm of the block compressed sensing respectively.
引文
[1] Candès E J, Romberg J, Tao T. Robust Uncertainty Principles Exact Signal Reconstruction from Highly Incomplete Frequency Information[J]. IEEE Transactions on Information Theory, 2006,52(2):489-509.
[2] Donoho D L, Compressed Sensing[J]. IEEE Transactions on Information Theory, 2006,52(4):1289-1306.
[3] Baraniuk R G. Compressive Sensing[J]. IEEE Signal Processing Magazine, 2007,24(4):118-124.
[4] Shonnon C E. Communication in the Presence of Noise[J]. Proceedings of the IEEE, 1984,72(9):1192-1201.
[5] Pennec E L, Mattat S. Image Compression with Geometrical Wavelets[C]. International Conference of Image Processing, Vancouver, Canada, 2000:661-664.
[6] Candes E J, Donoho D. Curvelets a Surprise Effective Nonadaptive Represension for Object with Edge. Curves and Surfaces[M], Vanderbilt University Press, Nashville TN, 2000:105-120.
[7] Candes E J, Wakin M B.“People Hearing Without Listening”: An Intruduction To Compressive Sampling[R]. California Institute of Technology, 2007:1-19.
[8] Jafarpour S, Pezeshki A, Calderbank R. Expriments with Compressively Sampled Images and a New Debluring-denoising Algorithm[C].Tenth IEEE International Symposium on Multimedia, 2008:66-73.
[9] Fira M, Garas L. Basis Pursuit for ECG Compression[C]. IEEE, 2009:1-4.
[10] Duval V, Aujol J F, Gousseau Y. The TVL1 Model: A Geometric Point of View[J]. Society for Industrial and Applied Mathematics, 2009:154-189.
[11] Chen S B, Donoho D L, Michael A S. Atomic Decomposition Pursuit[J]. Society for Industrial and Applied Mathematics, 2001,43(1):129-159.
[12] Mallat S G, Zhang Z. Matching Pursuits with Time-frequency Dictionaries[J]. IEEE Trans, Signal Process, 1993,41(12):3397-3415.
[13] Wang H Y, Vieira J, Ferreira P, et al. Batch Algorithms of Matching Pursuit and Orthogonal Matching Pursuit with Applications to Compressed Sensing[C]. Proceedings of the 2009 IEEE, 2009:824-829.
[14] Tropp J A, Gilbert A C. Signal Recovery From Random Measurements ViaOrthogonal Matching Pursuit[J]. IEEE Trans. Inf. Theory, 2007,53(12):4655-4666.
[15] Blumensath T, Davies M E. Gradient Pursuits[J], IEEE Trans. On Signal Processing, 2008,56(6):2370-2382.
[16] Zhou C M, Zhao R Z, Hu S H. An Improved Gradient Pursuit Algorithm for Signal Reconstruction Based on Compressed Sensing[C]. Wireless Communications Networking and Mobile Computing, 2010:1-4.
[17] Golub G H, Loan F V, Matrix Computations[M]. Baltimore, Jones Hopkins Univ. Press, 1996.
[18] Zhu L, Qiu C T. Newton Pursuit Algorithm for Sparse Signal Reconstruction in Compressed Sensing[C]. Computer Science and Information Technology, 2010:463-466.
[19] Duarte M F, Davenport M A, Takhar D, et al. Single-pixel Imaging via Compressive Sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2):83-91.
[20] Divekar A, Ersoy O. Image Fusion via Compressed Sensing[C]. IEEE, 2009:1-6.
[21] Orsdemir A, Altun H O, Sharma G, et al. On the Security and Robustness of Encryption via Compressed Sensing[C]. Military Communications Conference, 2008:1-7.
[22] Lusting M, Donoho D L, Pauly J. Rapid MR Imaging with Compressed Sensing and Randomly Under-sampled 3DFT Trajectories[C]. In proc. Annual Meeting of ISMRM, Seattle, WA, 2006:1.
[23] Lusting M, Santos J, Lee J, et al. Application of Compressed Sensing for MR Imaging(R). Signaux (SPARS), Rennes, France, 2005:1-4.
[24] Trzasko J, Manduca A. Highly Undersampled Magnetic Resonance Image Reconstruction via Homotopic l 0-minimization[J]. IEEE Trans. Med. Imaging, 2009,28(1):106-121.
[25] Ma S Q, Yin W T, Zhang Y, et al. An Efficient Algorithm for Compressed MR Imaging using Total Variation and Wavelets [C]. IEEE, 2008:1-8.
[26] Zheng J, Jacobs E L. Video Compressive Sensing using Spatial Domain Sparsity[J]. Optical Engineering, 2009,48(8):1-10.
[27] Shi G M, Lin J, Chen X Y, et al. UWB Echo Signal Detection with Ultra-Low Rate Sampling Based on Compressed Sensing[J]. IEEE Transactions on Circuits and Systems, 2008,55(4):379-383.
[28] Gan L. Block Compressed Sensing of Natural Images[C]. Proc. Of the 2007.15th Intl. Conf. on Digital Signal Processing(DSP 2007). IEEE, 2007:403-406.
[29] Starck J L, Bobin J. Astronomcal Data Analysis and Sparsity from Wavelets to Compressed Sensing[J]. Proceedings of the IEEE, 2010,98(6):1021-1031.
[30] Donoho D L. Denoising by Soft-thresholding[J]. IEEE Trans. Inform. Theroy, 1995,41(3):613-627.
[31] Majumdar A, Ward R K. Compressive Color Imaging with Group-Sparriy on Analysis Prior[C]. Proceeding of 2010 IEEE 17th International Conference on Image Processing, 2010:1337-1341.
[32]陶然,邓兵,王越.分数阶傅里叶变换及其应用[M].清华大学出版社,2009.
[33] Mallat S. A Wavelet Tour of Signal Processing[M]. Academic press,1998.
[34]李林,孔令富,练秋生.基于轮廓波维纳滤波的图像压缩传感重构,仪器仪表学报,2009,30(10):2051-2057.
[35] Pei S C, Yeh M H, Tseng C C. Discrete Fractional Fourier Transform Based on Orthogonal Projections[J]. IEEE Transction on Signal Processing, 1999,47(5):1335-1348.
[36] Marim M M, Elsa D, Angelini J C, et al. Compressed Sensing in Microscopy with Random Projections in the Fourier Domain[C]. ICIP, IEEE, 2009:2121-2125.
[37] Elad M. Optimized Projections for Compressed Sensing[J], IEEE Trans, Signal Process, 2007,55(12):5695-5702.
[38] Candes E J, Tao T, Decoding by Linear Programming[J]. IEEE Transactions on Information Theory, 2005,51(12):4203-4215.
[39] Candes E J, Romberg J, Tao T. Stable Signal Recovery from Incomplete and Inaccurate Measurements[J]. Communications on Pure and Applied Mathematics, 2006,59(8):1207-1223.
[40] Candes E J, Romberg J. Sparsity and Incoherence in Compressive Sampling[J]. Inverse Prob, 2007,23(3): 969–986.
[41] Gan L, Do T, Tran T D. Fast Compressive Imaging using Scrambled Block Hadamard Ensemble[C]. EUSIPCO, 2008:2-6.
[42] HE Z X, Ogawa T, Haseyama M. The Simplest Measurement Matrix for Compressed Sensing of Natural Images[C]. Proceedings of 2010 IEEE 17thInternational Conference on Image Processing, 2010:4301-4305.
[43] Li Z, Wu F, Wright J. On the Systematic Measurement Marix for Compressed Sensing in the Presence of Gross Errors[C]. IEEE Computer Society, 2010:356-366.
[44] Yu L, Barbot J P, Zheng G, et al. Toeplitz-Structured Chaotic Sensing Matrix for Compressive Sensing[C]. Communication Systems Networks and Digital Signa, 2010:229-233.
[2] Donoho D L, Compressed Sensing[J]. IEEE Transactions on Information Theory, 2006,52(4):1289-1306.
[3] Baraniuk R G. Compressive Sensing[J]. IEEE Signal Processing Magazine, 2007,24(4):118-124.
[4] Shonnon C E. Communication in the Presence of Noise[J]. Proceedings of the IEEE, 1984,72(9):1192-1201.
[5] Pennec E L, Mattat S. Image Compression with Geometrical Wavelets[C]. International Conference of Image Processing, Vancouver, Canada, 2000:661-664.
[6] Candes E J, Donoho D. Curvelets a Surprise Effective Nonadaptive Represension for Object with Edge. Curves and Surfaces[M], Vanderbilt University Press, Nashville TN, 2000:105-120.
[7] Candes E J, Wakin M B.“People Hearing Without Listening”: An Intruduction To Compressive Sampling[R]. California Institute of Technology, 2007:1-19.
[8] Jafarpour S, Pezeshki A, Calderbank R. Expriments with Compressively Sampled Images and a New Debluring-denoising Algorithm[C].Tenth IEEE International Symposium on Multimedia, 2008:66-73.
[9] Fira M, Garas L. Basis Pursuit for ECG Compression[C]. IEEE, 2009:1-4.
[10] Duval V, Aujol J F, Gousseau Y. The TVL1 Model: A Geometric Point of View[J]. Society for Industrial and Applied Mathematics, 2009:154-189.
[11] Chen S B, Donoho D L, Michael A S. Atomic Decomposition Pursuit[J]. Society for Industrial and Applied Mathematics, 2001,43(1):129-159.
[12] Mallat S G, Zhang Z. Matching Pursuits with Time-frequency Dictionaries[J]. IEEE Trans, Signal Process, 1993,41(12):3397-3415.
[13] Wang H Y, Vieira J, Ferreira P, et al. Batch Algorithms of Matching Pursuit and Orthogonal Matching Pursuit with Applications to Compressed Sensing[C]. Proceedings of the 2009 IEEE, 2009:824-829.
[14] Tropp J A, Gilbert A C. Signal Recovery From Random Measurements ViaOrthogonal Matching Pursuit[J]. IEEE Trans. Inf. Theory, 2007,53(12):4655-4666.
[15] Blumensath T, Davies M E. Gradient Pursuits[J], IEEE Trans. On Signal Processing, 2008,56(6):2370-2382.
[16] Zhou C M, Zhao R Z, Hu S H. An Improved Gradient Pursuit Algorithm for Signal Reconstruction Based on Compressed Sensing[C]. Wireless Communications Networking and Mobile Computing, 2010:1-4.
[17] Golub G H, Loan F V, Matrix Computations[M]. Baltimore, Jones Hopkins Univ. Press, 1996.
[18] Zhu L, Qiu C T. Newton Pursuit Algorithm for Sparse Signal Reconstruction in Compressed Sensing[C]. Computer Science and Information Technology, 2010:463-466.
[19] Duarte M F, Davenport M A, Takhar D, et al. Single-pixel Imaging via Compressive Sampling[J]. IEEE Signal Processing Magazine, 2008, 25(2):83-91.
[20] Divekar A, Ersoy O. Image Fusion via Compressed Sensing[C]. IEEE, 2009:1-6.
[21] Orsdemir A, Altun H O, Sharma G, et al. On the Security and Robustness of Encryption via Compressed Sensing[C]. Military Communications Conference, 2008:1-7.
[22] Lusting M, Donoho D L, Pauly J. Rapid MR Imaging with Compressed Sensing and Randomly Under-sampled 3DFT Trajectories[C]. In proc. Annual Meeting of ISMRM, Seattle, WA, 2006:1.
[23] Lusting M, Santos J, Lee J, et al. Application of Compressed Sensing for MR Imaging(R). Signaux (SPARS), Rennes, France, 2005:1-4.
[24] Trzasko J, Manduca A. Highly Undersampled Magnetic Resonance Image Reconstruction via Homotopic l 0-minimization[J]. IEEE Trans. Med. Imaging, 2009,28(1):106-121.
[25] Ma S Q, Yin W T, Zhang Y, et al. An Efficient Algorithm for Compressed MR Imaging using Total Variation and Wavelets [C]. IEEE, 2008:1-8.
[26] Zheng J, Jacobs E L. Video Compressive Sensing using Spatial Domain Sparsity[J]. Optical Engineering, 2009,48(8):1-10.
[27] Shi G M, Lin J, Chen X Y, et al. UWB Echo Signal Detection with Ultra-Low Rate Sampling Based on Compressed Sensing[J]. IEEE Transactions on Circuits and Systems, 2008,55(4):379-383.
[28] Gan L. Block Compressed Sensing of Natural Images[C]. Proc. Of the 2007.15th Intl. Conf. on Digital Signal Processing(DSP 2007). IEEE, 2007:403-406.
[29] Starck J L, Bobin J. Astronomcal Data Analysis and Sparsity from Wavelets to Compressed Sensing[J]. Proceedings of the IEEE, 2010,98(6):1021-1031.
[30] Donoho D L. Denoising by Soft-thresholding[J]. IEEE Trans. Inform. Theroy, 1995,41(3):613-627.
[31] Majumdar A, Ward R K. Compressive Color Imaging with Group-Sparriy on Analysis Prior[C]. Proceeding of 2010 IEEE 17th International Conference on Image Processing, 2010:1337-1341.
[32]陶然,邓兵,王越.分数阶傅里叶变换及其应用[M].清华大学出版社,2009.
[33] Mallat S. A Wavelet Tour of Signal Processing[M]. Academic press,1998.
[34]李林,孔令富,练秋生.基于轮廓波维纳滤波的图像压缩传感重构,仪器仪表学报,2009,30(10):2051-2057.
[35] Pei S C, Yeh M H, Tseng C C. Discrete Fractional Fourier Transform Based on Orthogonal Projections[J]. IEEE Transction on Signal Processing, 1999,47(5):1335-1348.
[36] Marim M M, Elsa D, Angelini J C, et al. Compressed Sensing in Microscopy with Random Projections in the Fourier Domain[C]. ICIP, IEEE, 2009:2121-2125.
[37] Elad M. Optimized Projections for Compressed Sensing[J], IEEE Trans, Signal Process, 2007,55(12):5695-5702.
[38] Candes E J, Tao T, Decoding by Linear Programming[J]. IEEE Transactions on Information Theory, 2005,51(12):4203-4215.
[39] Candes E J, Romberg J, Tao T. Stable Signal Recovery from Incomplete and Inaccurate Measurements[J]. Communications on Pure and Applied Mathematics, 2006,59(8):1207-1223.
[40] Candes E J, Romberg J. Sparsity and Incoherence in Compressive Sampling[J]. Inverse Prob, 2007,23(3): 969–986.
[41] Gan L, Do T, Tran T D. Fast Compressive Imaging using Scrambled Block Hadamard Ensemble[C]. EUSIPCO, 2008:2-6.
[42] HE Z X, Ogawa T, Haseyama M. The Simplest Measurement Matrix for Compressed Sensing of Natural Images[C]. Proceedings of 2010 IEEE 17thInternational Conference on Image Processing, 2010:4301-4305.
[43] Li Z, Wu F, Wright J. On the Systematic Measurement Marix for Compressed Sensing in the Presence of Gross Errors[C]. IEEE Computer Society, 2010:356-366.
[44] Yu L, Barbot J P, Zheng G, et al. Toeplitz-Structured Chaotic Sensing Matrix for Compressive Sensing[C]. Communication Systems Networks and Digital Signa, 2010:229-233.