An overview of image restoration based on variational regularization

Abstract

Image restoration is a complicated process in which the original information can be recovered from the degraded image model caused by lots of factors. Mathematically, image restoration problems are ill-posed inverse problems. In this paper image restoration models and algorithms based on variational regularization are surveyed. First, we review and analyze the typical models for denoising, deblurring and inpainting. Second, we construct a unified restoration model based on variational regularization and summarize the typical numerical methods for the model. At last, we point out eight diffcult problems which remain open in this field.

Keywords

Regularization / image restoration / inverse problem / total variation / wavelet

References

[1] Alliney S. A property of the minimum vectors of a regularizing functional defined by means of the absolute norm. IEEE Trans Signal Processing 1997; 45(4): 913–917

[2] AmbrosioLFuscoNPallaraD. Functions of Bounded Variation and Free Discontinuity Problems. New York: Clarendon Press, 2000

[3] Aubert G, Aujol J F. Modeling very oscillating signals: application to image processing. Appl Math Optim 2005; 51(2): 163–182

[4] Aubert G, Aujol J F. A variational approach to remove multiplicative noise. SIAM J Appl. Math. 2008; 68(4): 925–946

[5] Aujol J F. Dual norms and image decomposition models. Int. J. Comput. Vision 2005; 63(1): 85–104

[6] Aujol J F, Gilboa G, Chan T F, Osher S J. Structure-texture image decomposition modeling, algorithms and parameter selection. Int J Comput Vis 2005; 67(1): 111–136

[7] Ballester C, Bertalmio M, Caselles V, Sapiro G, Verdera J. Filling-in by joint interpolation of vector fields and grey levels. IEEE Trans Image Processing 2001; 10(8): 1200–1211

[8] Banham M R, Katsaggelos A K. Digital image restoration. IEEE Signal Processing Mag 1997; 14(2): 24–41

[9] Bardsley J M, Luttman A. Total variation-penalized Poisson likelihood estimation for ill-posed problems. Advances in Computational Mathematics, Special Volume on Mathematical Methods for Image Processing 2009; 31(13): 35–59

[10] Bardsley J M. An efficient computational method for total variation-penalized Poisson likelihood estimation. Inverse Problems and Imaging 2008; 2(2): 167–185

[11] BertalmioMSapiromGCasellesVBallesterC. Image inpainting. In: Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques, New Orleans, USA, July 2000, 417‒424

[12] BoydSVandenbergheL. Convex Optimization. Cambridge University Press, 2004

[13] Bresson X, Chan T F. Fast dual minimization of the vectorial total variation norm and applications to color image processing. Inverse Problems and Imaging 2008; 2(4): 455–484

[14] BressonXChanT F. Non-local unsupervised variational image segmentation models. UCLA CAM Report, 2008

[15] Cai J F, Osher S J, Shen Z W. Convergence of the linearized Bregman iteration for l₁-norm minimization. Math Comput 2009; 78(268): 2127–2136

[16] Cai J F, Chan R H, Shen Z W. A framelet-based image inpainting algorithm. Appl Comput Harmon Anal 2008; 24(2): 131–149

[17] CaiJ FDongBOsherS JShenZ W. Image restoration: total variation; wavelet frames; and beyond. UCLA CAM Report, 2011

[18] CaiJ FJiHLiuC QShenZ W. Blind motion deblurring from a single image using sparse approximation. In: IEEE Conf Computer Vision and Pattern Recognition, CVPR 2009

[19] Cai J F, Ji H, Liu C Q, Shen Z W. Blind motion deblurring using multiple images. J Computational Physics 2009; 228(14): 5057–5071

[20] Cai J F, Osher S J, Shen Z W. Linearized Bregman iterations for compressed sensing. Math Comput 2009; 78(267): 1515–1536

[21] Cai J F, Osher S J, Shen Z W. Linearized Bregman Iterations for frame based image deblurring. SIAM J Imaging Sciences 2009; 2(1): 226–252

[22] Cai J F, Osher S J, Shen Z W. Split Bregman methods and frame based image restoration. Multiscale Model Simul 2009; 8(2): 337–369

[23] Candès E, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans Information Theory 2006; 52(2): 489–509

[24] Carasso A S. Linear and nonlinear image deblurring: a documented study. SIAM J Numer Anal 1999; 36(6): 1659–1689

[25] Carasso A S. Singular integrals, image smoothness, and the recovery of texture in image deblurring. SIAM J Appl Math 2004; 64(5): 1749–1774

[26] CarterJ L. Dual Methods for Total Variation Based Image Restoration, Ph D thesis. Los Angeles, CA: UCLA, 2001

[27] Chambolle A. An algorithm for total variation minimization and applications. Journal of Mathematical Imaging and Vision 2004; 20(12): 89–97

[28] Chan R H, Ho C W, Nikolova M. Salt-and-pepper noise removal by median type noise detectors and detail preserving regularization. IEEE Trans Image Processing 2005; 14(10): 1479–1485

[29] Chan T F, Esedoglu S. Aspects of total variation regularized function approximation. SIAM J Appl Math 2005; 65(5): 1817–1837

[30] Chan T F, Shen J. Variational image inpainting. Communications on Pure and Applied Mathematics 2005; 58(5): 579–619

[31] Chan T F, Shen J H. Nontexture inpainting by curvature-driven diffusions. J Visual Commun Image Rep 2001; 12(4): 436–449

[32] Chan T F, Shen J H. Mathematical models for local nontexture inpaintings. SIAM J Appl Math 2002; 62(3): 1019–1043

[33] ChanT FShenJ H. Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods. Philadelphia: SIAM, 2005

[34] ChanT FShenJ H. Theory and computation of variational image deblurring. In: IMS Lecture Notes, 2006, 93‒131

[35] Chan T F, Wong C K. Total variation blind deconvolution. IEEE Trans Image Processing 1998; 7(3): 370–375

[36] Chan T F, Golub G H, Mulet P. A nonlinear primal-dual method for total variation based image restoration. SIAM J Sci Comp 1999; 20(6): 1964–1977

[37] Chan T F, Shen J H, Zhou H M. Total variation wavelet inpainting. Journal of Mathematical Imaging and Vision 2006; 25(1): 107–125

[38] ChenTHuangT SYinW TZhouX S. A new coarse-to-fine framework for 3D brain MR image registration. In: Computer Vision for Biomedical Image, Lecture Notes in Computer Science, 2005, 3765: 114‒124

[39] Cohen A, Dahmen W, DeVore R. Compressed sensing and best k-term approximation. J American Mathematical Society 2009; 22(1): 211–231

[40] Combettes P L, Wajs V R. Signal recovery by proximal forward backward splitting. SIAM J Multiscale Modeling and Simulation 2005; 4(4): 1168–1200

[41] CostanzinoN. EN161 Project Presentation Ⅲ: Structure Inpainting via Variational Methods, 2004

[42] Dai W, Sheikh M, Milenkovic O, Baraniuk R G. Compressed sensing DNA microarrays. EURASIP J Bioinformatics and Systems Biology 2009; 162824

[43] Darbon J, Sigelle M. Image restoration with discrete constrained total variation part I: fast and exact optimization. J Math Imaging Vis 2006; 26(3): 261–276

[44] Daubechies I, Defrise M, De Mol C. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Comm Pure and Applied Math 2004; 57(11): 1413–1457

[45] Daubechies I, Teschke G. Variational image restoration by means of wavelets: simultaneous decomposition, deblurring and denoising. Applied and Computational Harmonic Analysis 2005; 19(1): 1–16

[46] DeVore R A. Nonlinear approximation. Acta Numerica 1998; 7: 51–150

[47] Donoho D. Compressed sensing. IEEE Trans Information Theory 2006; 52(4): 1289–1306

[48] Eckstein J, Bertsekas D P. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming 1992; 55(13): 293–318

[49] EkelandITemamR. Convex Analysis and Variational Problems. Philadelphia: SIAM, 1999

[50] Esedogl S, Shen J H. Digital inpainting based on the Mumford-Shah-Euler image model. European J Appl Math 2002; 13(4): 353–370

[51] EsserEZhangX QChanT F. A general framework for a class of first order primal-dual algorithms for TV minimization. UCLA CAM Report (09–67), 2009

[52] EvansL CGariepR F. Measure Theory and Fine Properties of Functions. Boca Raton, FL: CRC Press, 1992

[53] Fish D A, Brinicombe A M, Pike E R, Walker J G. Blind deconvolution by means of the Richardson-Lucy algorithm. J Opt Soc Am A 1996; 12(1): 58–65

[54] Fu H Y, Ng M K, Nikolova M, Barlow J L. Efficient minimization methods of mixed l₂-l₁ and l₁-l₁ norms for image restoration. SIAM J Scientific Computing 2006; 27(6): 1881–1902

[55] Gabay D, Mercier B. A dual algorithm for the solution of non-linear variational problems via finite element approximations. Comp Math Appl 1976; 2(1): 17–40

[56] GanL. Block compressed sensing of natural images. In: Proc Int Conf Digital Signal Processing, Cardiff, UK, 2007

[57] Garnett J B, Le T M, Meyer Y, Vese L A. Image decompositions using bounded variation and generalized homogeneous Besov spaces. Appl Comput Harmon Anal 2007; 23(1): 25–56

[58] Geman S, Geman D. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans Pattern Anal Mach Intell 1984; 6(6): 721–741

[59] Gilboa G, Sochen N, Zeevi Y. Texture preserving variational denoising using an adaptive fidelity term. IEEE Trans Image Processing 2006; 15(8): 2281–2289

[60] Gilles J, Meyer Y. Properties of BV-G structures + textures decomposition models: application to road detection in satellite images. IEEE Trans Image Processing 2010; 19(11): 2793–2800

[61] GlowinskiRLe TallecP. Augmented Lagrangians and Operator-Splitting Methods in Nonlinear Mechanics. Philadelphia: SIAM, 1989

[62] Goldfarb D, Yin W T. Second-order cone programming methods for total variation based image restoration. SIAM J Scientific Computing 2006; 27(2): 622–645

[63] Goldstein T, Osher S J. The split Bregman method for L₁-regularized problems. SIAM J Imaging Sci 2009; 2(2): 323–343

[64] Grasmair M. Generalized Bregman distances and convergence rates for non-convex regularization methods. Inverse Problems 2010; 26(11): 115014

[65] HamzaA BKrimH. A variational approach to maximum a posteriori estimation for image denoising. In: Energy Minimization Methods in Computer Vision and Pattern Recognition. Lecture Notes in Computer Science, 2001, 19–34

[66] Hamza A B. Krim H, Unal B. Unifying probabilistic and variational estimation. IEEE Signal Process Mag 2002; 19(5): 37–47

[67] Huang Y, Ng M K, Wen Y W. A fast total variation minimization method for image restoration. SIAM J Multiscale Modeling and Simulation 2008; 7(2): 774–795

[68] Hubel D H, Wiesel T N. Receptive fields, binocular intersection and functional architecture in the cat’s visual cortex. J Physiology 1962; 160(1): 106–154

[69] Ito K, Kunisch K. Semi-smooth Newton methods for variational inequalities of the first kind. Math Modelling and Numerical Analysis 2003; 37(1): 41–62

[70] JiaoY LFanQ B. An Efficient Model for Distinguishing Between Texture and Noise. Tech Report, School of Math, Stat, Wuhan University, Nov 2010

[71] JohnsonC. Numerical Solution of Partial Differental Equations by the Finite Element Method. UK: Cambridge University Press, 1987

[72] KanizsaG. Organization in Vision. New York: Praeger, 1979

[73] Krishnan D, Lin P, Yip A M. A primal-dual active-set method for non-negativity constrained total variation deblurring problems. IEEE Trans Image Processing 2007; 16(11): 2766–2777

[74] Krishnan D, Pham Q V, Yip A M. A primal-dual active-Set algorithm for bilaterally constrained total variation deblurring and piecewise constant Mumford-Shah segmentation problems. Advances in Comput Math 2009; 31(13): 237–266

[75] Kunisch K, Hintermüller M. Total bounded variation regularization as a bilaterally constrained optimization problem. SIAM J Appl Math 2004; 64(4): 1311–1333

[76] LangeK L. Optimization. New York: Springer-Verlag, 2004

[77] Le T M, Vese L A. Image decomposition using total variation and div(BMO), Multiscale Modeling and Simulation. SIAM Interdis Journal 2005; 4(2): 390–423

[78] LeVequeR J. Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-state and Time-dependent Problems (Classics in Applied Mathematics). SIAM, 2007

[79] Lu D Y, Fan Q B. Characterizations of L_p(R) using tight wavelet frames. Wuhan University J of Natural Sciences 2010; 15(6): 461–466

[80] Lu D Y, Fan Q B. Gabor frames generated by multiple generators. Scientia Sinica Mathematica 2010; 40(7): 693–708

[81] Lu D Y, Fan Q B. A class of tight framelet packets. Czechoslovak Mathematical Journal 2011; 61(3): 623–639

[82] Lustig M, Donoho D, Pauly J M. Sparse MRI: the application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine 2007; 58(6): 1182–1195

[83] Malgouyres F, Zeng T. A predual proximal point algorithm solving anon negative basis pursuit denoising model. Int Journal of Computer Vision 2009; 83(3): 294–311

[84] MallatS. A Wavelet Tour of Signal Processing, 3rd Ed. Academic Press, 2008

[85] Marr D, Hildreth E. Theory of edge detection. Proc Roy Soc London, Ser B 1980; 207(1167): 187–217

[86] MaurelPAujolJ FPeyréG. Locally parallel textures modeling with adapted Hilbert spaces. In: Lecture Notes in Computer Science, 2009, 5681: 429‒442

[87] MeyerY. Wavelets and Operators. UK: Cambridge University Press, 1992

[88] MeyerY. Oscillating Patterns in Image Processing and Nonlinear Evolution Equations. University Lecture Series, Vol 22, Providence, RI: American Mathematical Society, 2001

[89] Micchelli C A, Shen L.X, Xu Y S. Proximity algorithms for image models: denoising. Inverse Problems 2011; 27(4): 045009

[90] MorozovV A. Methods for Solving Incorrectly Posed Problems. New York: Springer-Verlag, 1984

[91] NealenAAlexaM. Hybrid texture synthesis. In: Proceedings of the Eurographics Symposium on Rendering, 2003, 97‒105

[92] Ng M K, Qi L Q, Tang Y F, Huang Y M. On semismooth Newton’s methods for total variation minimization. Journal of Mathematical Imaging and Vision 2007; 27(3): 265–276

[93] Nikolova M. A variational approach to remove outliers and impulse noise. Journal of Mathematical Imaging and Vision 2004; 20(1-2): 99–120

[94] Nikolova M. Model distortions in Bayesian map reconstruction. Inverse Problems and Imaging 2007; 1(2): 399–422

[95] OliveiraM MBowenBMcKennaRChangY S. Fast digital image inpainting. In: Proceedings of the International Conference on Visualization, Imaging and Image Processing (VⅡP 2001), Marbella, Spain, Sep 3‒5, 2001

[96] Osher S, Burger M, Goldfarb D, Xu J J, Yin W T. An iterative regularization method for total variation based image restoration. Multiscale Model Simul 2005; 4(2): 460–489

[97] OsherS JFedkiwR P. Level Set Methods and Dynamic Implicit Surfaces. New York: Springer-Verlag, 2003

[98] Osher S J, Mao Y, Dong B, Yin W T. Fast linearized Bregman iteration for compressed sensing and sparse denoising. Communications in Mathematical Sciences 2010; 8(1): 93–111

[99] Osher S J, Solé A, Vese L A. Image decomposition and restoration using total variation minimization and the H₋₁ norm. Multiscale Modeling and Simulation 2003; 1(3): 349–370

[100] Peyré G. Texture synthesis with grouplets. IEEE Trans on Pattern Analysis and Machine Inte 2010; 32(4): 733–746

[101] Peyré G. A review of adaptive image representations. IEEE Journal of Selected Topics in Signal Processing 2011; 5(5): 896–911

[102] Pruessner A, O’Leary D P. Blind deconvolution using a regularized structured total least norm algorithm. SIAM J Matrix Anal Appl 2003; 24(4): 1018–1037

[103] PuetterR C. Pixons and Bayesian image reconstruction. In: Proceedings of SPIE, 1994, 23(2): 112‒131

[104] RabbatMHauptJSinghANowakRD. Decentralized compression and predistribution via randomized gossiping. In: Proc Int Conf on Information Processing in Sensor Networks, Nashville, Tennessee, 2006

[105] RahmanTTaiX COsherS J. A TV-Stokes denoising algorithm. In: Lecture Notes in Computer Science, Berlin: Springer-Verlag, 2007, 4485: 473‒483

[106] Rudin L I, Osher S J, Fatemi E. Nonlinear total variation based noise removal algorithms. Physica D 1992; 60: 259–268

[107] Scherzer O. Scale space methods for denoising and inverse problem. Advances in Imaging and Electron Physics 2003; 128: 445–530

[108] ScherzerO. Handbook of Mathematical Methods in Imaging. Berlin: Springer-Verlag, 2010

[109] ScherzerOGrasmairMGrossauerHHaltmeierMLenzenF. Variational Methods in Imaging. New York: Springer-Verlag, 2009

[110] ShikhminA. Synthesizing natural textures. In: Proceedings of 2001 ACM Symposium on Interactive 3D Graphics, 2001, 217‒226

[111] Snyder D L, Hammoud A M, White R L. Image recovery from data acquired with a charged-coupled-device camera. J Opt Soc Am A 1993; 10(5): 1014–1023

[112] SongB. Topics in Variational PDE Image Segmentation, Inpainting and Denoising. Ph D thesis, Los Angeles, CA: University of California, 2003

[113] StarckJ LMurtaghFFadiliJ M. Compressed sensing. In: Sparse Image and Signal Processing: Wavelets, Curvelets, Morphological Diversity, Cambridge University Press, 2010

[114] StoecklerJWellandG V. Beyond Wavelet. New York: Academic Press, 2003

[115] TaiX COsherS JHolmR. Image inpainting using a TV-Stokes equation. In: Image Processing Based on Partial Differential Equations, Heidelberg: Springer-Verlag, 2007, 3‒22

[116] TakharDLaskaJWakinM BDuarteM FBaronDSarvothamSKellyK FBaraniukR G. A new compressive imaging camera architecture using optical-domain compression. In: Proc Computational Imaging IV at SPIE Electronic Image, San Jose, California, 2006

[117] TikhonovA NArseninV Y. Solutions of Ill-Posed Problems. Washington D C: John Wiley and Sons, 1977

[118] TriebelH. Theory of Function Spaces Ⅱ. Monographs in Mathematics, Vol 84, Boston: Birkhäuser, 1992

[119] Tsai A, Yezzi A R, Willsky A S. Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification. IEEE Trans Image Processing 2001; 10(8): 1169–1186

[120] Tseng P. Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J Control and Optimization 1991; 29(1): 119–138

[121] Vese L A, Osher S J. Modeling textures with total variation minimization and oscillating patterns in image processing. J Sci Comput 2003; 19: 553–572

[122] VogelC R. Computational Methods for Inverse Problems. Frontiers Appl Math, Vol 23, Philadelphia: SIAM, 2002

[123] WangWGarofalakisM NRamchandranK. Distributed sparse random projections for refinable approximation. In: Proc Int Conf Information Processing in Sensor Networks, Cambridge, Massachusetts, 2007

[124] Weiss P, Blanc-Féraud L, Aubert G. Efficient schemes for total variation minimization under constraints in image processing. SIAM J Scientific Computing 2009; 31(3): 2047–2080

[125] Woiselle A, Starck J L, Fadili J. 3-D data denoising and inpaint- ing with the low redundancy fast curvelet transform. Journal of Mathematical Imaging and Vision 2011; 39(2): 121–139

[126] Wu C L, Tai X C. Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models. SIAM Journal on Imaging Sciences 2010; 3(3): 300–313

[127] YamauchiHHaberJSeidelH P. Image restoration using multiresolution texture synthesis and image inpainting. In: Proceedings of Computer Graphics International Conference, Japan, 2003, 120‒125

[128] Ye J C. Compressed sensing shape estimation of star-shaped objects in Fourier imaging. IEEE Signal Processing Letters 2007; 14(10): 750–753

[129] Yin W T, Goldfarb D, Osher S J. A comparison of three total variation based texture extraction models. J Visual Communication and Image Representation 2007; 18(3): 240–252

[130] YosidaK. Functional Analysis: Reprint of the 1980 Edition. Berlin: Springer-Verlag, 1995

[131] Zhang H Y, Peng Q C, Wu Y D. Wavelet inpainting based on p-Laplace operator. Acta Automatica Sinica 2007; 33(5): 546–549

[132] Zhang H Y, Wu B, Peng Q C, Wu Y D. Digital image inpainting based on p-harmonic energy minimization. Chinese Journal of Electronics 2007; 3: 525–530

[133] Zhang T, Fan Q B. Wavelet characterization of dyadic BMO norm and its application in image decomposition for distinguishing between texture and noise. Int Journal of Wavelet, Multiresolution and Information Processing 2011; 9(3): 445–457

[134] Zhang T, Fan Q B, Gao Q L. Wavelet characterization of Hardy space and its application in variational image decomposition. Int Journal of Wavelet, Multiresolution and Information Processing 2010; 8(1): 71–87

[135] Zhang X Q, Burger M, Osher S J. A unified primal-dual algorithm gramework based on Bregman iteration. J Sci Comput 2011; 46(1): 20–46

[136] ZhouM Y. Deconvolution and Signal Recovery. Beijing: National Defence Industry Press, 2001 (in Chinese)

[137] ZhuM QChanT F. An efficient primal-dual hybrid gradient algorithm for total variation image restoration. UCLA CAM Report (08–34), 2008

[138] Zhu M Q, Wright J, Chan T F. Duality based algorithms for total variation regularized image restoration. Comput Optim Appl 2008; 47(3): 377–400

[139] ZiemerW P. Weakly Differentiable Functions: Sobolev Spaces and Functions of Bounded Variation. Graduate Texts in Mathematics, Vol 120, New York: Springer-Verlag, 1989

RIGHTS & PERMISSIONS

2024 Higher Education Press 2024