基于压缩感知理论的图像采样和重构
|
摘要
目前信号处理领域存在两个关键难点：(1)奈奎斯特采样频率过高,对硬件的要求过高；(2)信号处理框架比较单一,先采样后压缩,效率低、浪费存储空间。这在一定程度上制约了信号与信息处理领域的发展。
近年来,诞生了压缩感知(Compressed Sensing)理论。主要针对可压缩信号或者是稀疏信号,将采样与压缩同时进行,这样其采样频率则有可能低于奈奎斯特频率。压缩感知理论的突出优点是可减少采样数据量,节省存储空间,同时保证一定的精度。需要时,可采用适当的重构算法从压缩传感得到的数据中重建出足够的数据点,从而恢复出原始信号。压缩感知是一个将信号采样与压缩合二为一的框架,既节省了存储空间,又降低了对采样等硬件设备的要求。压缩传感与信号的稀疏重构尤其是在图像的压缩与重建方面有着非常大的应用价值。
本文首先研究了压缩感知理论,包括其原理和应用,探讨了目前的主流算法,并且通过实验的方式实现了几种主流的求解稀疏系数的经典算法。接着探讨了用于求解稀疏表达的反馈神经网络方法,对其进行了深入研究,并通过数值试验验证了维度参数和稀疏度对重建性能的影响,同时应用三种反映信号的重建效果的指标更加客观对比出了神经网络的重建方法与现在的一些经典的主流算法的在性能上的优越性。而后将压缩传感理论应用于图像重建中,建立了一个可以进行图像采样压缩和恢复的框架,将神经网络的算法和图像的采样与重构结合起来,针对一些经典算法的重建速度慢和重建质量不高的缺点,将神经网络重建算法应用到图像的采样和重建中去,提高了压缩比和恢复图像的性能。最后把神经网络重建算法和图像处理中的行列均衡的思想结合起来,进一步提升了恢复图像的效果。同时还提出了一种基于单层和多层小波的分区扫描方案,并在实验上验证了方案的可行性,进一步提高了对原始图像的压缩比和恢复效果。
The current signal processing field has the following two key difficulties:(1) the Nyquist sampling frequency is too high, resulting in sampled data is amount too large; (2) data acquisition mode was not advanced enough, which is sampling first and then compressing, resulting in it is not only a waste of sensing element, but also a waste of time and storage space. This appearance restricts, to some extent, the development of signal and information processing.
Presently, the generation of a new compressed sensing theory is founded, for sparse signal or compressible signal. This method can obtain the signal and compress the data properly at the same time, in hence the sampling frequency can be lower than The Nyquist frequency. The prominent advantages are reducing the sampling data, saving storage space and so on, however, containing enough information. When necessary, the appropriate reconstruction algorithms can be used to obtain enough recovered data points from compressed sensing data and reconstruct to the primitive signal. Compressed sensing combining traditional data collection to data compression, is very suited for some conditions required a miniature device to achieve, however, does not need complex data encoding algorithm. Compressed sensing and sparse reconstruction have become a new research direction in the field of applied mathematics and signal processing.
This paper does research on the theory of compressed sensing, especially, understands the principles and specific applications of the compressed sensing theory and discusses the current mainstream algorithms and uses the ways of the experiment to achieve several of the current and classical algorithms. This paper also does research on the methods as the feedback neural network for solving sparse representation problems along with its some improved researches by quantities of experiments. Numerical experiments are conducted to investigate the influence of dimensional parameters and the sparsity level. Additionally, the author uses three distinct indicators which can reflect the performance of the reconstruction more objective to compare performance of the feedback neural network with that of several present main reconstruction methods and gets very perfect result. The compressed sensing theory will be applied to image reconstruction by the framework which links the compressed sensing theory to the image reconstruction. For the current ways'slow pace and low quality of reconstruction shortcomings, applying the neural network in the image reconstruction algorithm can improve the image compression ratio and recovery performance. In the end the author combines the neural network reconstruction algorithms with the ranks equilibrium and blocking idea which is in the image processing to further enhance the recovery effect, meanwhile innovatively raises a kind of scheme for increasing the compression ratio and reconstruction efficiency through reconstructing the signal by different blocks based on singular and multiply image DWT. Numerical experiments are conducted to confirm the availability of the scheme which can virtually increase the compression ratio and performance to image.
近年来,诞生了压缩感知(Compressed Sensing)理论。主要针对可压缩信号或者是稀疏信号,将采样与压缩同时进行,这样其采样频率则有可能低于奈奎斯特频率。压缩感知理论的突出优点是可减少采样数据量,节省存储空间,同时保证一定的精度。需要时,可采用适当的重构算法从压缩传感得到的数据中重建出足够的数据点,从而恢复出原始信号。压缩感知是一个将信号采样与压缩合二为一的框架,既节省了存储空间,又降低了对采样等硬件设备的要求。压缩传感与信号的稀疏重构尤其是在图像的压缩与重建方面有着非常大的应用价值。
本文首先研究了压缩感知理论,包括其原理和应用,探讨了目前的主流算法,并且通过实验的方式实现了几种主流的求解稀疏系数的经典算法。接着探讨了用于求解稀疏表达的反馈神经网络方法,对其进行了深入研究,并通过数值试验验证了维度参数和稀疏度对重建性能的影响,同时应用三种反映信号的重建效果的指标更加客观对比出了神经网络的重建方法与现在的一些经典的主流算法的在性能上的优越性。而后将压缩传感理论应用于图像重建中,建立了一个可以进行图像采样压缩和恢复的框架,将神经网络的算法和图像的采样与重构结合起来,针对一些经典算法的重建速度慢和重建质量不高的缺点,将神经网络重建算法应用到图像的采样和重建中去,提高了压缩比和恢复图像的性能。最后把神经网络重建算法和图像处理中的行列均衡的思想结合起来,进一步提升了恢复图像的效果。同时还提出了一种基于单层和多层小波的分区扫描方案,并在实验上验证了方案的可行性,进一步提高了对原始图像的压缩比和恢复效果。
The current signal processing field has the following two key difficulties:(1) the Nyquist sampling frequency is too high, resulting in sampled data is amount too large; (2) data acquisition mode was not advanced enough, which is sampling first and then compressing, resulting in it is not only a waste of sensing element, but also a waste of time and storage space. This appearance restricts, to some extent, the development of signal and information processing.
Presently, the generation of a new compressed sensing theory is founded, for sparse signal or compressible signal. This method can obtain the signal and compress the data properly at the same time, in hence the sampling frequency can be lower than The Nyquist frequency. The prominent advantages are reducing the sampling data, saving storage space and so on, however, containing enough information. When necessary, the appropriate reconstruction algorithms can be used to obtain enough recovered data points from compressed sensing data and reconstruct to the primitive signal. Compressed sensing combining traditional data collection to data compression, is very suited for some conditions required a miniature device to achieve, however, does not need complex data encoding algorithm. Compressed sensing and sparse reconstruction have become a new research direction in the field of applied mathematics and signal processing.
This paper does research on the theory of compressed sensing, especially, understands the principles and specific applications of the compressed sensing theory and discusses the current mainstream algorithms and uses the ways of the experiment to achieve several of the current and classical algorithms. This paper also does research on the methods as the feedback neural network for solving sparse representation problems along with its some improved researches by quantities of experiments. Numerical experiments are conducted to investigate the influence of dimensional parameters and the sparsity level. Additionally, the author uses three distinct indicators which can reflect the performance of the reconstruction more objective to compare performance of the feedback neural network with that of several present main reconstruction methods and gets very perfect result. The compressed sensing theory will be applied to image reconstruction by the framework which links the compressed sensing theory to the image reconstruction. For the current ways'slow pace and low quality of reconstruction shortcomings, applying the neural network in the image reconstruction algorithm can improve the image compression ratio and recovery performance. In the end the author combines the neural network reconstruction algorithms with the ranks equilibrium and blocking idea which is in the image processing to further enhance the recovery effect, meanwhile innovatively raises a kind of scheme for increasing the compression ratio and reconstruction efficiency through reconstructing the signal by different blocks based on singular and multiply image DWT. Numerical experiments are conducted to confirm the availability of the scheme which can virtually increase the compression ratio and performance to image.
引文
[1]Donoho D. Compressed sensing [J]. IEEE Transactions on Information Theory,2006, 52(4):1289-1306.
[2]Candes E, Romberg J, Tao J. Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information [J]. IEEE Transactions on Information Theory,2006,52(2):489-509.
[3]Baraniuk R. Compressive sensing [J]. IEEE Signal Processing Magazine [J],2007, 24(4):118-121.
[4]Wang W, Garofalakis M, Ramchandran K. Distributed sparse random projections for refinable approximation [A]. Proceedings of the Sixth International Symposium on Information Processing in Sensor Networks (IPSN2007) [C]. New York:Association for Computing Machinery,2007.331-339.
[5]Baron D, Wakin M B, Duarte M. Distributed compressed sensing. IEEE Transactions on Information Theory,2007.6-18
[6]Takhar D, Laska J, Wakin M etc. A new compressive imaging camera architecture using optical domain compression [A]. Proceedings of SPIE [C]. Bellingham WA: International Society for Optical Engineering.2006,60-65.
[7]Takhar D, Bansal V, Wakin W etc. A compressed sensing camera:New theory and an implementation using digital micro mirrors [A]. Electronic Imaging:Computational Imaging [C],2006.
[8]E Candes, Compressive sampling, in Proc. Int. Congress of Mathematics, Madrid, Spain, 2006.8,3:1433-1452
[9]E Candes, J Romberg and T Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math.,2006.8,59(8):1207-1223
[10]E Candes and T Tao, Near optimal signal recovery from random projections:Universal encoding strategies? IEEE Trans. Inform. Theory,2006.12,52(12):5406-5425
[11]D Donoho and Y Tsaig, Extensions of compressed sensing. Signal Processing,2006.3, 86(3):533-548
[12]R Baraniuk, A lecture on compressive sensing, IEEE Signal Processing Magazine, 2007.7,118-121
[13]W Bajwa, J Haupt, G Raz, S Wright and R Nowak, Toeplitz-structured compressed sensing matrices. IEEE Workshop on Statistical Signal Processing (SSP), Madison, Wisconsin,2007.8
[14]E Candes and J Romberg, Sparsity and incoherence in compressive sampling. Inverse Problems,2007,23(3):969-985
[15]方红,章权兵,韦穗,基于亚高斯随机投影的图像重建方法,计算机研究与发展,2008,45(8)：1402-1407
[16]傅迎华,可压缩传感重构算法与QR分解,计算机应用,2008,28(9)：2300-2302
[17]R DeVore, Deterministic constructions of compressed sensing matrices. Journal of Complexity,2007,23(4-6):918-925
[18]D L Donoho. For most large underdetermined system of linear equations the minimal L1-norm solution is also the sparsest solution. Comm. Pure Appl. Math.2006. 86(3):533-548
[19]王建英,尹忠科,张春梅.信号与图像的稀疏分解及初步应用[M].成都：西南交通大学出版社,2006.
[20]Tropp J, Gibert A. Signal recovery from random measurement via orthogonal matching pursuit. Transactions on Information Theory,2007,53(12):4655-4666
[21]Needell D, Vershynin R. Greedy signal recovery and uncertainty principle. In: proceedings of the SPIE. Bellingham, WA:SPIE,2008,68140J-12
[22]Needell D, Vershynin R. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Found. Comput. Math.2008,6.
[23]Donoho D L, Tsaig Y, Drori I, Starck J L. Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit (StOMP). Applied Mathematics and Computation,2006,103(2):430-481
[24]Needell D, Tropp J A. CoSaMP:Iterative signal recovery from incomplete and inaccurate samples. ACM Technical Report 2008-01, California Institute of Technology, Pasadena,2008.7.
[25]Dai W, Milenkovic 0. Subspace pursuit for compressive sensing signal reconstruction.2008 5th International Symposium on Turbo Codes and Related Topics, TURBOCODING 2008,402-407.
[26]T Do Thong, Lu Gan, Nam Nguyen and Trac D Tran, Sparsity adaptive matching pursuit algorithm for practical compressed sensing, Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, California,2008.10
[27]S S Chen, D L Donoho and M A Saunders, Atomic decomposition by basis pursuit, SIAM Journal of Scientific Computing,1998,20(1):33-61
[28]Donoho D L, Elad M, Temlyakov V. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory, 2006,52(1):6-18
[29]Fiqueiredo M A T, Nowak R D, Wright S J. Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing,2007,1(4):586-598.
[30]B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, "Least angle regression, " The Annals of Statistics,2004,32(2):407-499,
[31]P J Garrigues and Laurent EI Ghaoui, An homotopy algorithm for the lasso with online observation. Neural Information Processing Systems, Vancouver, Canada,2008.12
[32]H Zayyani, M Babaie-Zadeh and C Jutten, Bayesian pursuit algorithm for sparse representation. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing (ICASSP), Taipei, Taiwan,2009.4
[33]D Baron, S Sarvoham and R G Baraniuk, Bayesian compressive sensing via belief propagation,2008.6
[34]Lustig M, Donoho D L, Pauly J M. Sparse MRI:The application of compressedsensing for rapid MR imaging [J]. Magnetic Resonance in Medicine,2007,58(6):1182-1195.
[35]Qi D, Sha W. The Physics of Compressive Sensing and Gradient BasedRecovery Algorithms. http://arxiv.org/abs/0906.1487,2009.4
[36]Lobo M, Vandenberghe L, Boyd S, Lebret H. Application of second-order cone programming. Linear Algebra and its Application,1998,284(1-3):193-228
[37]Kingsbury N G. Complex wavelet for shift invariant analysis and filtering of signals. Journal of Applied and Computational Harmonic Analysis,2001, 10(3):234-253
[38]Herrity K K, Gilbert A C, Tropp J A. Sparse approximation via iterative thresholding. In:Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. Washington D. C., USA:IEEE,2006,624-627.
[39]Blumensath T, Davies M E. Iterative thresholding for sparse approximations. Journal of Fourier Analysis and Applications; 2007,14(5-6):629-654.
[40]Haupt J, Nowak R. Compressive sampling for signal detection. In:Proceedings of the IEEE International Conferenceon Acoustics, Speech and Signal Processing. Washington D. C., USA:IEEE,2007,1509-1512.
[41]Justin Romberg, Imaging via compressive sampling. IEEE signal processing magazine, 2008,3(5):718-725
[42]Liu Q, Wang J. A One-Layer Recurrent Neural Network for Non-Smooth Convex Optimization Subject to Linear Equality Constraints [C]. M. Koppen et al. (Eds.): ICONIP 2008, Part Ⅱ:1003-1010. Berlin:Springer-Verlag,2009.
[43]Liu Q, Wang J. A Recurrent Neural Network for Non-smooth Convex Programming Subject to Linear Equality and Bound Constraints [C]. ICONIP 2006, Part Ⅱ:1004-1013. Berlin:Springer-Verlag,2009.
[44]J. J. Hopfield, Neural Networks and Physical Systems with Emergent Collective Computational Abilities[J], Proc. Natl. Sci. Vol.79, pp.2554-2558,1982.
[2]Candes E, Romberg J, Tao J. Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information [J]. IEEE Transactions on Information Theory,2006,52(2):489-509.
[3]Baraniuk R. Compressive sensing [J]. IEEE Signal Processing Magazine [J],2007, 24(4):118-121.
[4]Wang W, Garofalakis M, Ramchandran K. Distributed sparse random projections for refinable approximation [A]. Proceedings of the Sixth International Symposium on Information Processing in Sensor Networks (IPSN2007) [C]. New York:Association for Computing Machinery,2007.331-339.
[5]Baron D, Wakin M B, Duarte M. Distributed compressed sensing. IEEE Transactions on Information Theory,2007.6-18
[6]Takhar D, Laska J, Wakin M etc. A new compressive imaging camera architecture using optical domain compression [A]. Proceedings of SPIE [C]. Bellingham WA: International Society for Optical Engineering.2006,60-65.
[7]Takhar D, Bansal V, Wakin W etc. A compressed sensing camera:New theory and an implementation using digital micro mirrors [A]. Electronic Imaging:Computational Imaging [C],2006.
[8]E Candes, Compressive sampling, in Proc. Int. Congress of Mathematics, Madrid, Spain, 2006.8,3:1433-1452
[9]E Candes, J Romberg and T Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math.,2006.8,59(8):1207-1223
[10]E Candes and T Tao, Near optimal signal recovery from random projections:Universal encoding strategies? IEEE Trans. Inform. Theory,2006.12,52(12):5406-5425
[11]D Donoho and Y Tsaig, Extensions of compressed sensing. Signal Processing,2006.3, 86(3):533-548
[12]R Baraniuk, A lecture on compressive sensing, IEEE Signal Processing Magazine, 2007.7,118-121
[13]W Bajwa, J Haupt, G Raz, S Wright and R Nowak, Toeplitz-structured compressed sensing matrices. IEEE Workshop on Statistical Signal Processing (SSP), Madison, Wisconsin,2007.8
[14]E Candes and J Romberg, Sparsity and incoherence in compressive sampling. Inverse Problems,2007,23(3):969-985
[15]方红,章权兵,韦穗,基于亚高斯随机投影的图像重建方法,计算机研究与发展,2008,45(8)：1402-1407
[16]傅迎华,可压缩传感重构算法与QR分解,计算机应用,2008,28(9)：2300-2302
[17]R DeVore, Deterministic constructions of compressed sensing matrices. Journal of Complexity,2007,23(4-6):918-925
[18]D L Donoho. For most large underdetermined system of linear equations the minimal L1-norm solution is also the sparsest solution. Comm. Pure Appl. Math.2006. 86(3):533-548
[19]王建英,尹忠科,张春梅.信号与图像的稀疏分解及初步应用[M].成都：西南交通大学出版社,2006.
[20]Tropp J, Gibert A. Signal recovery from random measurement via orthogonal matching pursuit. Transactions on Information Theory,2007,53(12):4655-4666
[21]Needell D, Vershynin R. Greedy signal recovery and uncertainty principle. In: proceedings of the SPIE. Bellingham, WA:SPIE,2008,68140J-12
[22]Needell D, Vershynin R. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Found. Comput. Math.2008,6.
[23]Donoho D L, Tsaig Y, Drori I, Starck J L. Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit (StOMP). Applied Mathematics and Computation,2006,103(2):430-481
[24]Needell D, Tropp J A. CoSaMP:Iterative signal recovery from incomplete and inaccurate samples. ACM Technical Report 2008-01, California Institute of Technology, Pasadena,2008.7.
[25]Dai W, Milenkovic 0. Subspace pursuit for compressive sensing signal reconstruction.2008 5th International Symposium on Turbo Codes and Related Topics, TURBOCODING 2008,402-407.
[26]T Do Thong, Lu Gan, Nam Nguyen and Trac D Tran, Sparsity adaptive matching pursuit algorithm for practical compressed sensing, Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, California,2008.10
[27]S S Chen, D L Donoho and M A Saunders, Atomic decomposition by basis pursuit, SIAM Journal of Scientific Computing,1998,20(1):33-61
[28]Donoho D L, Elad M, Temlyakov V. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory, 2006,52(1):6-18
[29]Fiqueiredo M A T, Nowak R D, Wright S J. Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing,2007,1(4):586-598.
[30]B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, "Least angle regression, " The Annals of Statistics,2004,32(2):407-499,
[31]P J Garrigues and Laurent EI Ghaoui, An homotopy algorithm for the lasso with online observation. Neural Information Processing Systems, Vancouver, Canada,2008.12
[32]H Zayyani, M Babaie-Zadeh and C Jutten, Bayesian pursuit algorithm for sparse representation. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing (ICASSP), Taipei, Taiwan,2009.4
[33]D Baron, S Sarvoham and R G Baraniuk, Bayesian compressive sensing via belief propagation,2008.6
[34]Lustig M, Donoho D L, Pauly J M. Sparse MRI:The application of compressedsensing for rapid MR imaging [J]. Magnetic Resonance in Medicine,2007,58(6):1182-1195.
[35]Qi D, Sha W. The Physics of Compressive Sensing and Gradient BasedRecovery Algorithms. http://arxiv.org/abs/0906.1487,2009.4
[36]Lobo M, Vandenberghe L, Boyd S, Lebret H. Application of second-order cone programming. Linear Algebra and its Application,1998,284(1-3):193-228
[37]Kingsbury N G. Complex wavelet for shift invariant analysis and filtering of signals. Journal of Applied and Computational Harmonic Analysis,2001, 10(3):234-253
[38]Herrity K K, Gilbert A C, Tropp J A. Sparse approximation via iterative thresholding. In:Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing. Washington D. C., USA:IEEE,2006,624-627.
[39]Blumensath T, Davies M E. Iterative thresholding for sparse approximations. Journal of Fourier Analysis and Applications; 2007,14(5-6):629-654.
[40]Haupt J, Nowak R. Compressive sampling for signal detection. In:Proceedings of the IEEE International Conferenceon Acoustics, Speech and Signal Processing. Washington D. C., USA:IEEE,2007,1509-1512.
[41]Justin Romberg, Imaging via compressive sampling. IEEE signal processing magazine, 2008,3(5):718-725
[42]Liu Q, Wang J. A One-Layer Recurrent Neural Network for Non-Smooth Convex Optimization Subject to Linear Equality Constraints [C]. M. Koppen et al. (Eds.): ICONIP 2008, Part Ⅱ:1003-1010. Berlin:Springer-Verlag,2009.
[43]Liu Q, Wang J. A Recurrent Neural Network for Non-smooth Convex Programming Subject to Linear Equality and Bound Constraints [C]. ICONIP 2006, Part Ⅱ:1004-1013. Berlin:Springer-Verlag,2009.
[44]J. J. Hopfield, Neural Networks and Physical Systems with Emergent Collective Computational Abilities[J], Proc. Natl. Sci. Vol.79, pp.2554-2558,1982.