Régularité et parcimonie pour les problèmes inverses en imagerie
Algorithmes et comparaisons
OPEN ACCESS
This article is a survey on regularization techniques for inverse problems based on l1 criteria. We split these criteria in two categories : those which promote regularity of the signal (e.g. total variation) and those which express the fact that a signal is sparse in some dictionnary. In the first part of the paper, we give guidelines to choose a prior and propose a comparative study of these two priors on standard transforms such as total variation, redundant wavelets, and curvelets. In the second part of the paper, we give a sketch of different first order algorithms adpated to the minimization of these l1-terms.
RÉSUMÉ
Dans cet article, nous nous intéressons à la régularisation de problèmes inverses reposant sur des critères l1. Nous séparons ces critères en deux catégories : ceux qui favorisent la régularisation des signaux (à variation totale bornée par exemple) et ceux qui expriment le fait qu'un signal admet une représentation parcimonieuse dans un dictionnaire. Dans une première partie, nous donnons quelques éléments de comparaisons théoriques et pratiques sur les deux a priori, pour aider le lecteur à choisir l'un ou l'autre en fonction de son problème. Pour cette étude, nous utilisons les transformées communément utilisées telles que la variation totale, les ondelettes redondantes ou les curvelets. Dans une deuxième partie, nous proposons un état des lieux des algorithmes de premier ordre adaptés à la minimisation de ces critères.
inverse problems, imaging, l1-criteria, regularity, sparsity, fast algorithms, experimental comparisons
MOTS-CLÉS
problèmes inverses, imagerie, critères l1, régularité, parcimonie, algorithmes rapides, comparaisons expérimentales
Aujol J.-F. (2009). « Some first-order algorithms for total variation based image restoration », Journal of Mathematical Imaging and Vision, vol. 34, n° 3, p. 307-327, juillet.
Bect J., Blanc-Féraud L., Aubert G., Chambolle A. (2004). « A l1-unified variational framework for image restoration », Proc. European Conference on Computer Vision, Prague, République tchèque, p. 1-13, mai.
Boyd S., Vandenberghe L. (2004). Convex Optimization, Cambridge University Press, mars.
Candès E., Demanet L., Donoho D., Ying L. (2006). « Fast Discrete Curvelet Transforms », Multiscale Modeling & Simulation, vol. 5, n° 3, p. 861-899.
Chambolle A. (2004). « An algorithm for total variation minimization and applications », Journal of Mathematical Imaging and Vision, vol. 20, n° 1, p. 89-97.
Chambolle A., DeVore R. A., Lee N.-Y., Lucier B. J. (1996). « Nonlinear Wavelet Image Processing: Variational Problems, Compression, and Noise Removal through Wavelet Shrinkage », IEEE Trans. Image Processing, vol. 7, p. 319-335.
Chaux C., Pesquet J.-C., Pustelnik N. (2009). « Nested iterative algorithms for convex constrained image recovery problems », SIAM Journal on Imaging Sciences, Juin.
Chen S. S., Donoho D. L., Saunders M. A. (1998). « Atomic Decomposition by Basis Pursuit », SIAM Journal on Scientific Computing, vol. 20, n° 1, p. 33-61.
Combettes P. L. (2009). « Iterative construction of the resolvent of a sum of maximal monotone operators », Journal of Convex Analysis, vol. 16, n° 4, p. 727-748.
Combettes P. L., Pesquet J.-C. (2007). « A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery », IEEE Journal of Selected Topics in Signal Processing, décembre.
Combettes P. L., Pesquet J.-C. (2010). Proximal Splitting Methods in Signal Processing, Springer-Verlag, New York.
Combettes P. L., Wajs V. R. (2005). « Signal Recovery by Proximal Forward-Backward Splitting », Multiscale Modeling & Simulation, vol. 4, n° 4, p. 1168-1200.
Daubechies I. (1992). Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.
Daubechies I., Defrise M., Mol C. D. (2004). « An iterative thresholding algorithm for linear inverse problems with a sparsity constraint », Communications on Pure and Applied Mathematics, vol. 57, n° 11, p. 1413-1457.
Donoho D. (1995). « De-noising by soft-thresholding », IEEE transactions on Information Theory, vol. 41, n° 3, p. 613-627.
Douglas J., Rachford H. (1956). « On the numerical solution of heatconduction problems in two or three space variables », Trans.Amer.Math.Soc., décembre.
Dupé F., Fadili J., Starck J. (2009). « A proximal iteration for deconvolving Poisson noisy images using sparse representations », IEEE Transactions on Image Processing, vol. 18, n° 2, p. 310-321.
Elad M., Milanfar P., Rubinstein R. (2007). « Analysis versus synthesis in signal priors », Inverse Problems, vol. 23, n° 3, p. 947-968.
Figueiredo M. A. T., Nowak R. D. (2003). « An EM algorithm for wavelet-based image restoration », IEEE Transactions on Image Processing, vol. 12, n° 8, p. 906-916, août.
Fuchs J. (2005). « Recovery of exact sparse representations in the presence of bounded noise », IEEE Transactions on Information Theory, vol. 51, n° 10, p. 3601-3608.
Gaetan C., Guyon X. (eds) (2008). Modélisation et statistique spatiales, Springer.
Geman S., Geman D. (1984). « Stochastic relaxation, Gibbs distributions, and the Bayesian relation of images », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 6, p. 721-741.
Gibson J. D., Bovik A. (eds) (2000). Handbook of Image and Video Processing, Academic Press, Inc., Orlando, FL, USA.
Glowinski R. (1984). Numerical Methods for Nonlinear variation al Problems, SpringerVerlag.
Golub G., Van Loan C. (1996). Matrix computations, Johns Hopkins Univ Pr.
Hamza B., Krim H. (2001). « Image denoising : A nonlinear robust statistical approach », IEEE Transactions on Signal Processing, vol. 49, n° 12, p. 3045-3054.
He B., Liao L.-Z., Han D., Yang H. (2002). « A new inexact alternating directions method for mo-notone variational inequalities », Journal on Mathematical Programming, vol. 92, n° 1, p. 103-118.
Idier J. (ed.) (2001). Approche bayésienne pour les problèmes inverses, Traité IC2, Série traitement du signal et de l’image, Hermès, Paris, novembre.
Kirsch A. (1996). An introduction to the mathematical theory of inverse problems, Springer Verlag.
Le Pennec E., Mallat S. (2005). « Sparse geometric image representations with bandelets », IEEE Transactions on Image Processing, vol. 14, n° 4, p. 423-438.
Lions P., Mercier B. (1979). « Splitting algorithms for the sum of two nonlinear operators », SIAM Journal on Numerical Analysis, vol. 16, n° 6, p. 964-979.
Lucy L. (1974). « An iterative technique for rectification of observed distributions », The Astronomical Journal, vol. 79, n° 6, p. 745-765.
Nemirovsky A. (1992). « Information-based complexity of linear operator equations », Journal of Complexity, vol. 8, n° 2, p. 175.
Nesterov Y. (2004). Introductory lectures on convex optimization. A basic course, Kluwer.
Nesterov Y. (2005). « Smooth minimization of non smooth functions », Mathematical Programming, Ser. B.
Nesterov Y. (2007). « Gradient methods for minimizing composite objective function », CORE Discussion Paper 2007/76.
Nesterov Y. (2009). « Primal-dual subgradient methods for convex problems », Mathematical Programming, Ser. B.
Nesterov Y., Nemirovsky A. (1994). Interior-Point polynomial methods in convex programming, vol. 13, SIAM Studies in Applied Mathematics.
Ng M., Weiss P., Yuang X. (2009). « Solving Constrained Total-Variation Image Restoration and Reconstruction Problems via Alternating Direction Methods », ICM Research Report.
Nikolova M. (2004). « A variational approach to remove outliers and impulse noise », Journal of Mathematical Imaging and Vision, vol. 20, n° 1, p. 99-120.
Polyak B. (1987). Introduction to optimization, Optimization Software, Publications Division, New York.
Rockafellar R. (1997). Convex analysis, Princeton university press.
Rudin L. I., Osher S., Fatemi E. (1992). « Nonlinear total variation based noise removal algorithms », Physica D, vol. 60, p. 259-268.
Selesnick I. W., Baraniuk R. G., Kingsbury N. G. (2005). « The Dual-Tree Complex Wavelet Transform », IEEE Signal Processing Magazine, vol. 22, n° 6, p. 123-151, Nov.
Selesnick I. W., Figueiredo M. A. T. (2009). « Signal restoration with overcomplete wavelet trans-forms: comparison of analysis and synthesis priors », vol. 7446, SPIE.
Weiss P. (2009). Algorithmes rapides d’optimisation convexe. Application à la reconstruction d’images et à la détection de changements, Thèse de doctorat à l’université de Nice Sophia-Antipolis.
Weiss P., Blanc-Féraud L., Aubert G. (2009). « Efficient schemes for total variation minimization under constraints in image processing », SIAM journal on Scientific Computing, vol. 31, n° 3, p. 2047-2080.