基于全变分模型压缩传感图像重构的快速算法
|
摘要
数字图像处理是利用计算机对图像信息进行加工以满足人的视觉心理或应用需求的行为.图像重构是为了提高图像的质量,建立模型,采用某种数值方法,重构或重建原始图像.本文提出求解基于全变分正则化优化模型压缩传感图像重构的交替极小化算法和交替方向算法,分析算法的收敛性,通过数值仿真试验验证算法的有效性.
第一章,简单介绍问题的研究背景和研究意义;介绍压缩传感和全变分模型的基本理论;回顾求解l1-范数优化问题和全变分模型的已有算法;给出求解可分离凸优化问题交替方向法的基本知识;列出本文所用到的一些符号.
第二章,提出基于全变分模型压缩传感图像重构的两种算法.所提算法分别是交替极小化原始问题罚函数和增广拉格朗日函数.利用全变分模型特征,线性化拟合项并加临界点项确保子问题具有显式解.所提两种算法迭代形式简单,每步迭代仅需计算两次矩阵向量内积和一次收缩算子.在一定条件下,分析算法全局收敛性.数值试验验证所提算法的有效性.
第三章,结合Xiao-Yang-Yuan提出的算法和第二章所提算法,提出交替线性化的杂交算法.在每步迭代中,本章所提算法交替线性化增广拉格朗日函数的二次拟合项.数值仿真试验表明,本章所提算法提高了效率.
第四章,给出本文的总结,并提出一些值得继续探讨的方向.
In order to improve the quality of the image, the task of image reconstruction isto construct model, use some numerical methods, restore or recovery the original image.In this thesis, we propose alternating minimization algorithm and alternating directionalgorithm for recovering the compressive sensing image based on total variation regular-ization optimization model. We analyze the algorithms’ convergence properties and dosome numerical experiments to show the efciency of each algorithm.
In chapter1, we introduce the background and signifcance of the thesis. We briefyreview the theory of compressive sensing and total variation, and recall some recent algo-rithm for solving1-norm and total variation regularized minimization problems. More-over, we give the preliminaries of alternating direction algorithm for convex separableminimization problems, and list some notations which used in this thesis.
In chapter2, based on the total variation model, we proposed double algorithms forthe compressive sensing image restoration. Both algorithms minimize the penalty functionand augmented Lagrangian function respectively. We linearize the ftting term and adda proximal point term to ensure that both subproblems have closed-form solutions. Theiterative form of both algorithms is very simple and requires a shrinkage and two matrix-vector produce at each iteration. With some mild conditions, we show that both algorithmconverges globally. Moreover, we also do some numerical experiments which show thatboth proposed algorithm are promising.
In Chapter3, combining the Xiao-Yang-Yuan’s algorithm with the proposed algo-rithm in the previous chapter, we develop a hybrid linearized algorithm. At each iteration,the proposed algorithm alternatively linearized the quadratic ftting term of the aug-mented Lagrangian function. The performance comparisons illustrate that the proposedalgorithm is superior to the algorithm in the previous section.
In Chapter4, we give a summary of this thesis and list some further research topics.
第一章,简单介绍问题的研究背景和研究意义;介绍压缩传感和全变分模型的基本理论;回顾求解l1-范数优化问题和全变分模型的已有算法;给出求解可分离凸优化问题交替方向法的基本知识;列出本文所用到的一些符号.
第二章,提出基于全变分模型压缩传感图像重构的两种算法.所提算法分别是交替极小化原始问题罚函数和增广拉格朗日函数.利用全变分模型特征,线性化拟合项并加临界点项确保子问题具有显式解.所提两种算法迭代形式简单,每步迭代仅需计算两次矩阵向量内积和一次收缩算子.在一定条件下,分析算法全局收敛性.数值试验验证所提算法的有效性.
第三章,结合Xiao-Yang-Yuan提出的算法和第二章所提算法,提出交替线性化的杂交算法.在每步迭代中,本章所提算法交替线性化增广拉格朗日函数的二次拟合项.数值仿真试验表明,本章所提算法提高了效率.
第四章,给出本文的总结,并提出一些值得继续探讨的方向.
In order to improve the quality of the image, the task of image reconstruction isto construct model, use some numerical methods, restore or recovery the original image.In this thesis, we propose alternating minimization algorithm and alternating directionalgorithm for recovering the compressive sensing image based on total variation regular-ization optimization model. We analyze the algorithms’ convergence properties and dosome numerical experiments to show the efciency of each algorithm.
In chapter1, we introduce the background and signifcance of the thesis. We briefyreview the theory of compressive sensing and total variation, and recall some recent algo-rithm for solving1-norm and total variation regularized minimization problems. More-over, we give the preliminaries of alternating direction algorithm for convex separableminimization problems, and list some notations which used in this thesis.
In chapter2, based on the total variation model, we proposed double algorithms forthe compressive sensing image restoration. Both algorithms minimize the penalty functionand augmented Lagrangian function respectively. We linearize the ftting term and adda proximal point term to ensure that both subproblems have closed-form solutions. Theiterative form of both algorithms is very simple and requires a shrinkage and two matrix-vector produce at each iteration. With some mild conditions, we show that both algorithmconverges globally. Moreover, we also do some numerical experiments which show thatboth proposed algorithm are promising.
In Chapter3, combining the Xiao-Yang-Yuan’s algorithm with the proposed algo-rithm in the previous chapter, we develop a hybrid linearized algorithm. At each iteration,the proposed algorithm alternatively linearized the quadratic ftting term of the aug-mented Lagrangian function. The performance comparisons illustrate that the proposedalgorithm is superior to the algorithm in the previous section.
In Chapter4, we give a summary of this thesis and list some further research topics.
引文
[1]李董辉,童小娇,万中,数值最优化算法与理论,北京,科学出版社,2010.
[2] Cande`s E., Romberg J., Tao T., Robust uncertainty principles: Exact signal reconstructionfrom highly incomplete frequence information, IEEE Transactions on Information Theory,2006,52:489-509.
[3] Chen S. S., Basis pursuit, PhD thesis, Stanford University, Department of Statistics,1995.
[4] Chen S. S., Donoho D. L., Saunders M. A., Atomic decomposition by basis pursuit, SIAMReview,2001,1:129–159.
[5] Donoho D., For most large underdetemined systems of linear equations the minimal l1-normsolution is also the sparsest solution, Communications on Pure and Applied mathematics,2006,59:907-934.
[6] Cande`s E., Romberg J., Tao T., Stable signal recovery from imcomplete and inaccurateinformation, Communications on Pure and Applied Mathematics,2005,59:1207-1233.
[7] Donoho D., Compressed sensing, IEEE Transactions on Information Theory,2006,52:1289-1306.
[8] Zhang Y., On the theory of compresssed sensing via l1-minimization: simple derivationsand extensions, TR08-11, CAAM, Rice University.
[9] Lustig M., Donoho D., Pauly J. M., Sparse MRI: the application of compressed sensing forrapid MR Imaging, Magnetic Resonance in Medicine,2007,58:1182-1195.
[10] Figueriedo M., Nowak R., Wright S. J., Gradient projection for sparse reconstruction,Application to compressed sensing and other inverse problems, IEEE Journal of SelectedTopics in Signal Processing: Special Issue on Convex Optimization Methods for SignalProcessing,2007,1:586-597.
[11] Berg E. V. D., Friedlander M. P., Probing the pareto frontier for basis pursuit solutions,SIAM Journal on Scientifc Computing,2008,31:890-912.
[12] Mol C. De., Defrise M., A note on wavelet-based inversion algorithms, Contemporary Math-ematics,2002,313:85-96.
[13] Figreiredo M., Nowak R., An EM algorithm for wavelet-based image restoration, IEEETransactions Image Processing,2003,12:906-916.
[14] Starck J. L., Nguyen M., Murtagh F., Wavelets and curvelets for image deconvolution: acombined approach, Signal Processing,2003,83:2279-2283.
[15] Daubechies I., Defrise M., Mol C. De., An iterative thresholding algorithm for linear inverseproblems with a sparsity constraint, Communications on Pure and Applied Mathematics,2004,57:1413-1457.
[16] Elad M., Why simple shrinkage is still relevant for redundant representations, IEEE Trans-actions on Information Theory,2006,52:5559-5569.
[17] Bioucas-Dias J., Figueiredo M., A New TwIST: Two-step iterative thresholding algorithmfor image restoration, IEEE Transactions Image Processing,2007,16:2292-3004.
[18] Beck A., Teboulle A., A fast itertive shrinkage-thresholding algorithm for linear inverseproblems, SIAM Journal on Imaging Sciences,2009,2:183-202.
[19] Hale E. T., Yin W., Zhang Y., A fxed-point continuation method for l1-regularized min-imization with applications to compressed sensing, SIAM Journal on Optimization,2008,19:1107-1130.
[20] Osher S., Burger M., Goldfarb D. et al., An iterated regularization method for totalvariation-based image restoration, Multiscale Modeling and Simulation,2005,4:460-489.
[21] Osher S., Mao Y., Dong B. et al., Fast linearized Bregman iteration for compressed sensingand spase denoising, TR08-07, CAAM, Rice University.
[22] Darhon J., Osher S., Fast discrete optimization for sparse approximations, deconvolutions,UCLA CAAM Report08-37,2008.
[23] Yin W., Osherm S., Goldfard D. et al., Bregman iterative algorithms for l1-minimizationwith applications to compressed sensing, SIAM Journal on Imaging Sciences,2008,1:143-168.
[24] Combettes P. L., Pesquet J. C., Proximal thresholding algorithm for minimization overorthonormal bases, SIAM Journal on Optimization,2008,18:1351-1376.
[25] Yang J., Zhang Y., Alternating direction algorithms for1-problems in compressive sensing,TR09-37, CAAM, Rice University.
[26] Afonsok M. V., Bioucas-Dias J., Figueiredo M. A. T., Fast image recovery using variablesplitting and constrained optimizationm, IEEE Transactions Image Processing, submitted.
[27] Afonsok M. V., Bioucas-Dias J., Figueiredo M. A. T., A fast algorithm for the constrainedformulation of compressive image reconstruction and other linear inverse problems, sub-mitted.
[28] Rudinm L., Osherm S., Fatemi E., Nonlinear total variation based noise removal algorithms,Physica D,1992,60:259-268.
[29] Wang Y., Yang J., Yin W. et al., A new alternating minimization algorithm for totalvariation image reconstruction, SIAM Journal on Scientifc Computing,2008,1:248-272.
[30] Yang J., Yin W., Zhang Y. et al., A fast algorithm for edge-preserving variational multi-channel image restoration, SIAM Journal on Imaging Sciences,2009,2:569-592.
[31] Yang J., Zhang Y., Yin W., A efcient TVL1algorithm for deblurring multichannel imagescorrupted by impulsive noise, SIAM Journal on Scientifc Computing,2009,31:2842-2865.
[32] Yang J., Zhang Y., Yin W., A fast TVL1-L2minimization algorithm for signal reconstruc-tion from partial Fourier data, IEEE Journal of Selected Topics in Signal Processing,2010,4:288-297.
[33] He B., Liao L. Z., Han D. et al., A new inexact alteratin directions method for monotonevariational inequalities, Mathematical Programming,2002,92:103-118.
[34] He B.,Yang H., Wang S., Alternating direction method with self-adaptive penalty param-eters for monotone variational inequalities, Journal of Optimization Theory and Applica-tions,2000,106:337-356.
[35] Xiao Y., Yang J., Fast algorithm for total variation image restoration from random projec-tions, http://arxiv.org/abs/1001.1774v1.
[36]张峥嵘,孙玉宝,黄丽丽等,全变差图像恢复的交替方向乘子法,[J]计算机工程和应用,2010,46:8-12.
[37] Gabay D., Mercier B., A dual algoithm for the solution of nonliear variational problemsvia fnite element approximation, Computers&Mathematics with Applications,1976,2:17-40.
[38] Barzilai J., Borwein J. M., Two point step size gradient method, IMA Journal MumericalAnalysis,1988,8:141-148.
[2] Cande`s E., Romberg J., Tao T., Robust uncertainty principles: Exact signal reconstructionfrom highly incomplete frequence information, IEEE Transactions on Information Theory,2006,52:489-509.
[3] Chen S. S., Basis pursuit, PhD thesis, Stanford University, Department of Statistics,1995.
[4] Chen S. S., Donoho D. L., Saunders M. A., Atomic decomposition by basis pursuit, SIAMReview,2001,1:129–159.
[5] Donoho D., For most large underdetemined systems of linear equations the minimal l1-normsolution is also the sparsest solution, Communications on Pure and Applied mathematics,2006,59:907-934.
[6] Cande`s E., Romberg J., Tao T., Stable signal recovery from imcomplete and inaccurateinformation, Communications on Pure and Applied Mathematics,2005,59:1207-1233.
[7] Donoho D., Compressed sensing, IEEE Transactions on Information Theory,2006,52:1289-1306.
[8] Zhang Y., On the theory of compresssed sensing via l1-minimization: simple derivationsand extensions, TR08-11, CAAM, Rice University.
[9] Lustig M., Donoho D., Pauly J. M., Sparse MRI: the application of compressed sensing forrapid MR Imaging, Magnetic Resonance in Medicine,2007,58:1182-1195.
[10] Figueriedo M., Nowak R., Wright S. J., Gradient projection for sparse reconstruction,Application to compressed sensing and other inverse problems, IEEE Journal of SelectedTopics in Signal Processing: Special Issue on Convex Optimization Methods for SignalProcessing,2007,1:586-597.
[11] Berg E. V. D., Friedlander M. P., Probing the pareto frontier for basis pursuit solutions,SIAM Journal on Scientifc Computing,2008,31:890-912.
[12] Mol C. De., Defrise M., A note on wavelet-based inversion algorithms, Contemporary Math-ematics,2002,313:85-96.
[13] Figreiredo M., Nowak R., An EM algorithm for wavelet-based image restoration, IEEETransactions Image Processing,2003,12:906-916.
[14] Starck J. L., Nguyen M., Murtagh F., Wavelets and curvelets for image deconvolution: acombined approach, Signal Processing,2003,83:2279-2283.
[15] Daubechies I., Defrise M., Mol C. De., An iterative thresholding algorithm for linear inverseproblems with a sparsity constraint, Communications on Pure and Applied Mathematics,2004,57:1413-1457.
[16] Elad M., Why simple shrinkage is still relevant for redundant representations, IEEE Trans-actions on Information Theory,2006,52:5559-5569.
[17] Bioucas-Dias J., Figueiredo M., A New TwIST: Two-step iterative thresholding algorithmfor image restoration, IEEE Transactions Image Processing,2007,16:2292-3004.
[18] Beck A., Teboulle A., A fast itertive shrinkage-thresholding algorithm for linear inverseproblems, SIAM Journal on Imaging Sciences,2009,2:183-202.
[19] Hale E. T., Yin W., Zhang Y., A fxed-point continuation method for l1-regularized min-imization with applications to compressed sensing, SIAM Journal on Optimization,2008,19:1107-1130.
[20] Osher S., Burger M., Goldfarb D. et al., An iterated regularization method for totalvariation-based image restoration, Multiscale Modeling and Simulation,2005,4:460-489.
[21] Osher S., Mao Y., Dong B. et al., Fast linearized Bregman iteration for compressed sensingand spase denoising, TR08-07, CAAM, Rice University.
[22] Darhon J., Osher S., Fast discrete optimization for sparse approximations, deconvolutions,UCLA CAAM Report08-37,2008.
[23] Yin W., Osherm S., Goldfard D. et al., Bregman iterative algorithms for l1-minimizationwith applications to compressed sensing, SIAM Journal on Imaging Sciences,2008,1:143-168.
[24] Combettes P. L., Pesquet J. C., Proximal thresholding algorithm for minimization overorthonormal bases, SIAM Journal on Optimization,2008,18:1351-1376.
[25] Yang J., Zhang Y., Alternating direction algorithms for1-problems in compressive sensing,TR09-37, CAAM, Rice University.
[26] Afonsok M. V., Bioucas-Dias J., Figueiredo M. A. T., Fast image recovery using variablesplitting and constrained optimizationm, IEEE Transactions Image Processing, submitted.
[27] Afonsok M. V., Bioucas-Dias J., Figueiredo M. A. T., A fast algorithm for the constrainedformulation of compressive image reconstruction and other linear inverse problems, sub-mitted.
[28] Rudinm L., Osherm S., Fatemi E., Nonlinear total variation based noise removal algorithms,Physica D,1992,60:259-268.
[29] Wang Y., Yang J., Yin W. et al., A new alternating minimization algorithm for totalvariation image reconstruction, SIAM Journal on Scientifc Computing,2008,1:248-272.
[30] Yang J., Yin W., Zhang Y. et al., A fast algorithm for edge-preserving variational multi-channel image restoration, SIAM Journal on Imaging Sciences,2009,2:569-592.
[31] Yang J., Zhang Y., Yin W., A efcient TVL1algorithm for deblurring multichannel imagescorrupted by impulsive noise, SIAM Journal on Scientifc Computing,2009,31:2842-2865.
[32] Yang J., Zhang Y., Yin W., A fast TVL1-L2minimization algorithm for signal reconstruc-tion from partial Fourier data, IEEE Journal of Selected Topics in Signal Processing,2010,4:288-297.
[33] He B., Liao L. Z., Han D. et al., A new inexact alteratin directions method for monotonevariational inequalities, Mathematical Programming,2002,92:103-118.
[34] He B.,Yang H., Wang S., Alternating direction method with self-adaptive penalty param-eters for monotone variational inequalities, Journal of Optimization Theory and Applica-tions,2000,106:337-356.
[35] Xiao Y., Yang J., Fast algorithm for total variation image restoration from random projec-tions, http://arxiv.org/abs/1001.1774v1.
[36]张峥嵘,孙玉宝,黄丽丽等,全变差图像恢复的交替方向乘子法,[J]计算机工程和应用,2010,46:8-12.
[37] Gabay D., Mercier B., A dual algoithm for the solution of nonliear variational problemsvia fnite element approximation, Computers&Mathematics with Applications,1976,2:17-40.
[38] Barzilai J., Borwein J. M., Two point step size gradient method, IMA Journal MumericalAnalysis,1988,8:141-148.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |