Abstract
In Part II of this paper we extend the results obtained in Part I for total variation minimization in image restoration towards the following directions: first we investigate the decomposability property of energies on levels, which leads us to introduce the concept of levelable regularization functions (which TV is the paradigm of). We show that convex levelable posterior energies can be minimized exactly using the level-independant cut optimization scheme seen in Part I. Next we extend this graph cut scheme to the case of non-convex levelable energies.We present convincing restoration results for images corrupted with impulsive noise. We also provide a minimum-cost based algorithm which computes a global minimizer for Markov Random Field with convex priors. Last we show that non-levelable models with convex local conditional posterior energies such as the class of generalized Gaussian models can be exactly minimized with a generalized coupled Simulated Annealing.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Abbreviations
- KAP:
-
Kluwer Academic Publishers
- compuscript:
-
Electronically submitted article
References
R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms and Applications. Prentice Hall, 1993.
S. Alliney, “An algorithm for the minimization of mixed l 1 and l 2 norms with application to bayesian estimation,” IEEE Transactions on Signal Processing, Vol. 42, No. 3, pp. 618–627, 1994.
J. Besag, “On the statistical analysis of dirty pictures,” Journal of the Royal Statistics Society, Vol. 48, pp. 259–302, 1986.
A. Blake and A. Zisserman, Visual Reconstruction. MIT Press, 1987.
C. Bouman and K. Sauer, “A generalized Gaussian image model for edge-preserving MAP estimation,” IEEE Transactions on Transactions on Signal Processing, Vol. 2, No. 3, pp. 296–310, 1993.
S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.
Y. Boykov and V. Kolmogorov, “An experimental comparison of Min-Cut/Max-Flow algorithms for energy minimization in vision,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, No. 9, 1124–1137, 2004.
Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 11, pp. 1222–1239, 2001.
D. Coupier, A. Desolneux, and B. Ycart, “Image denoising by statistical area thresholding,” Journal of Mathematical Imaging and Vision, Vol. 22, No. 2–3, pp. 183–197, 2005.
S. Geman and D. Geman, “Stochastic relaxation, Gibbs distributions, and the bayesian restoration of images,” IEEE Pattern Analysis and Machine Intelligence, Vol. 6, No. 6, pp. 721–741, 1984.
G. Giorgi, A. Guerraggio, and J. Thierfelder, Mathematics of Optimization: Smooth and Nonsmooth Case. Elsevier Science, 2004.
D. Greig, B. Porteous, and A. Seheult, “Exact maximum a posteriori estimation for binary images,” Journal of the Royal Statistics Society, Vol. 51, No. 2, pp. 271–279, 1989.
F. Guichard and J. Morel, “Mathematical morphology “almost everywhere,”” in Proceedings of ISMM, 2002, pp. 293–303.
H. Ishikawa, “Exact optimization for Markov random fields with convex priors,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 25, No. 10, pp. 1333–1336, 2003.
S. Iwata, L. Fleischer, and S. Fujishige, “A combinatorial strongly polynomial algorithm for minimizing submodular functions,” Journal of the ACM, Vol. 48, No. 4, pp. 761–777, 2001.
V. Kolmogorov and R. Zabih, “What energy can be minimized via graph cuts?” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, No. 2, pp. 147–159, 2004.
M. Nikolova, “Local strong homogeneity of a regularized extimator,” SIAM Journal on Applied Mathematics, Vol. 61, pp. 633–658, 2000.
M. Nikolova, “A variational approach to remove outliers and impulse noise,” Journal of Mathematical Imaging and Vision, Vol. 20, pp. 99–120, 2004.
S. Osher, A. Solé, and L. Vese, “Image decomposition and restoration using total variation minimization and the H −1 norm,” J. Mult. Model. and Simul., Vol. 1, No. 3, 2003.
I. Pollak, A. Willsky, and Y. Huang, “Nonlinear evolution equations as fast and exact solvers of estimation problems,” IEEE Transactions on Signal Processing, Vol. 53, No. 2, pp. 484–498, 2005.
L. Rudin, S. Osher, and E. Fatemi, “Nonlinear total variation based noise removal algorithms,” Physica D., Vol. 60, pp. 259–268, 1992.
K. Sauer and C. Bouman, “Bayesian estimation of transmission tomograms using segmentation based optimization,” IEEE Transactions on Nuclear Science, Vol. 39, No. 4, pp. 1144–1152, 1992.
B. Zalesky, “Efficient determination of Gibbs estimators with submodular energy functions,” http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:math/0304041, 2003.
Author information
Authors and Affiliations
Corresponding author
Additional information
Jérôme Darbon was born in Chenôve, France in 1978. From 1998 to 2001, he studied computer science at Ecole Pour l’Informatique et les Techniques Avancées (EPITA), France. He received the M.Sc. degree in applied mathematics from E.N.S. de Cachan, France, in 2001. In 2005, he received the Ph.D. degree from Ecole Nationale des Télécommunications (ENST), Paris, France. He is currently a postdoc at the Department of Mathematics, University of California, Los Angeles, hosted by Prof. T.F. Chan. His main research interests include fast algorithms for exact energy minimization and mathematical morphology.
Marc Sigelle was born in Paris on 18th March 1954. He received an engeneer diploma from Ecole Polytechnique Paris 1975 and from Ecole Nationale Supérieure des Télécommunications Paris in 1977. In 1993 he received a Ph.D. from Ecole Nationale Supérieure des Télécommunications. He worked first at Centre National d’Etudes des Télécommunications in Physics and Computer algorithms. Since 1989 he has been working at Ecole Nationale Supérieure des Télécommunications in image and more recently in speech processing. His main subjects of interests are restoration and segmentation of signals and images with Markov Random Fields (MRF’s), hyperparameter estimation methods and relationships with Statistical Physics. His interests concerned first reconstruction in angiographic medical imaging and processing of remote sensed satellital and synthetic aperture radar images, then speech and character recognition using MRF’s and bayesian networks. His most recent interests concern a MRF approach to image restoration with Total Variation and its extensions.
Rights and permissions
About this article
Cite this article
Darbon, J., Sigelle, M. Image Restoration with Discrete Constrained Total Variation Part II: Levelable Functions, Convex Priors and Non-Convex Cases. J Math Imaging Vis 26, 277–291 (2006). https://doi.org/10.1007/s10851-006-0644-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-006-0644-3