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.

Key words： 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