Abstract
We present a simple framework for solving different ill-posed inverse problems in image processing by means of constrained total variation minimizations. We argue that drawbacks commonly attributed to total variation algorithms (slowness and incomplete fit to the image model) can be easily bypassed by performing only a few number of iterations in our optimization process. We illustrate this approach in the context of computerized tomography, that comes down to inverse a Radon transform obtained by illuminating an object by straight and parallel beams of x-rays. This problem is ill-posed because only a finite number of line integrals can be measured, resulting in an incomplete coverage of the frequency plane and requiring, for a direct Fourier reconstruction, frequencies interpolation from a polar to a Cartesian grid. We introduce a new method of interpolation based on a total variation minimization constrained by the knowledge of frequency coefficients in the polar grid, subject to a Lipschitz regularity assumption. The experiments show that our algorithm is able to avoid Gibbs and noise oscillations associated to the direct Fourier method, and that it outperforms classical reconstruction methods such as filtered backprojection and Rudin-Osher-Fatemi total variation restoration, in terms of both PSNR and visual quality.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)
Chambolle, A., Lions, P.L.: Image recovery via total variation minimization and related problems. Numer. Math. 76, 167–188 (1997)
Acar, R., Vogel, C.: Analysis of total variation penalty methods for ill-posed problems. Inverse Problems 10, 1217–1229 (1994)
Li, Y., Santosa, F.: A computational algorithm for minimizing total variation in image restoration. IEEE Trans. on Image Proc. 5, 987–995 (1996)
Vogel, C., Oman, M.: Iterative method for total variation denoising. SIAM J. Sci. Comput. 17, 227–238 (1996)
Dobson, D.C., Vogel, C.R.: Convergence of an iterative method for total variation denoising. SIAM J. Numer. Anal. 34, 1779–1791 (1997)
Vogel, C., Oman, M.: Fast, robust total variation-based reconstruction of noisy, blurred images. IEEE Trans. on Image Proc. 7, 813–824 (1998)
Chan, T., Golub, G., Mulet, P.: A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20, 1964–1977 (1999)
Dibos, F., Koepfler, G.: Global total variation minimization. SIAM J. Numer. Anal. 37, 646–664 (2000)
Darbon, J., Sigelle, M.: Exact optimization of discrete constrained total variation minimization problems. In: Klette, R., Žunić, J. (eds.) IWCIA 2004. LNCS, vol. 3322, pp. 548–557. Springer, Heidelberg (2004)
Combettes, P., Luo, J.: An adaptive level set method for nondifferentiable constrained image recovery. IEEE Trans. on Image Proc. 11, 1295–1304 (2002)
Durand, S., Froment, J.: Reconstruction of wavelet coefficients using total variation minimization. SIAM J. Sci. Comput. 24, 1754–1767 (2003)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20, 89–97 (2004)
Alter, F., Durand, S., Froment, J.: Deblocking DCT-based compressed images with weighted total variation. In: Proc. of ICASSP 2004, Montréal, vol. 3 (2004)
Coifman, R., Sowa, A.: Combining the calculus of variations and wavelets for image enhancement. Applied and Comput. Harmonic Ana. 9, 1–18 (2000)
Chan, T.F., Zhou, H.: Total variation improved wavelet thresholding in image compression. In: Proc. of ICIP 2000 (2000)
Malgouyres, F.: Combining total variation and wavelet packet approaches for image deblurring. In: Proc. of IEEE work. on VLSM 2001, Vancouver, Canada, pp. 57–64 (2001)
Malgouyres, F.: Minimizing the total variation under a general convex constraint for image restoration. IEEE Trans. on Image Proc. 11, 1450–1456 (2002)
Aliney, S.: A property of the minimum vectors of a regularizing functional defined by means of the absolute norm. IEEE Trans. on Signal Proc. 45, 913–917 (1997)
Nikolova, M.: Minimization of cost-functions with non-smooth data-fidelity terms to clean impulsive noise. In: Rangarajan, A., Figueiredo, M.A.T., Zerubia, J. (eds.) EMMCVPR 2003. LNCS, vol. 2683, pp. 391–406. Springer, Heidelberg (2003)
Nikolova, M.: Minimization of cost-functions involving nonsmooth data-fidelity terms. application to the processing of outliers. SIAM J. Numer. Anal. 40, 965–994 (2002)
Gousseau, Y., Morel, J.M.: Are natural images of bounded variation? SIAM J. Math. Anal. 33, 634–648 (2001)
Meyer, Y.: Oscillating patterns in image processing and in some nonlinear evolution equations. In: The Fifteenth Dean Jacquelines B. Lewis Memorial Lectures, vol. 22. American Mathematical Society, Providence (2001)
Osher, S., Solé, A., Vese, L.: Image decomposition and restoration using total variation minimization and the H − 1 norm. SIAM Multiscale Model. Simul. 1, 349–370 (2003)
Vese, L., Osher, S.: Image denoising and decomposition with total variation minimization and oscillatory functions. J. Math. Imaging Vis. 20, 7–18 (2004)
Aujol, J., Aubert, G., Blanc-Féraud, L., Chambolle, A.: Image decomposition into a bounded variation component and an oscillating component. J. Math. Imaging Vis. 22 (2005)
Aujol, J., Chambolle, A.: Duals norms and image decomposition models. Int. Jour. of Computer Vision 63, 85–104 (2005)
Alter, F., Durand, S., Froment, J.: Adapted total variation for artifact free decompression of JPEG images. J. Math. Imaging Vis. 23 (2005)
Shepp, L., Logan, B.: The Fourier reconstruction of a head section. IEEE Trans. Nucl. Sci. 21, 21–43 (1974)
Guichard, F., Malgouyres, F.: Total variation based interpolation. In: Proc. of EUSIPCO 1998, vol. 3, pp. 1741–1744 (1998)
Polyak, B.: Introduction to Optimization. Optimization Software (1987)
Combettes, P.L.: Convex set theoretic image recovery by extrapolated iterations of parallel subgradient projections. IEEE Trans. on Image Proc. 6, 493–506 (1997)
Durand, S., Malgouyres, F., Rougé, B.: Image deblurring, spectrum interpolation and application to satellite imaging. ESAIM: COCV Control, Opt. and Cal. of Var. 5, 445–475 (2000)
Moisan, L.: Extrapolation de spectre et variation totale pondérée. In: Proc. of Gretsi 2001, Toulouse, France (2001)
Durand, S., Froment, J.: Artifact free signal denoising with wavelets. In: Proc. of ICASSP 2001, Salt Lake City, vol. 6 (2001)
Donoho, D., Johnstone, I.: Ideal spatial adaptation via wavelet shrinkage. Biometrika 81, 425–455 (1994)
Wallace, G.: The JPEG still picture compression standard. Communications of the ACM 34, 31–44 (1991)
Kak, A., Slaney, M.: Principles of Computerized Tomographic Imaging. SIAM, Philadelphia (2001)
Gottlieb, D., Gustafsson, B., Forssén, P.: On the direct Fourier method for computer tomography. IEEE Trans. Medical Imaging 19, 223–232 (2000)
Waldén, J.: Analysis of the direct Fourier method for computer tomography. IEEE Trans. Medical Imaging 19, 211–222 (2000)
Averbuch, A., Coifman, R., Donoho, D., Israeli, M., Waldén, J.: Fast slant stack: A notion of radon transform for data in a cartesian grid which is rapidly computable, algebraically exact, geometrically faithful and invertible. SIAM J. Sci. Comput. (to appear)
Bronstein, M., Bronstein, A., Zibulevsky, M., Azhari, H.: Reconstruction in ultrasound diffraction tomography using non-uniform FFT. IEEE Trans. Medical Imaging 21, 1395–1401 (2002)
Fessler, J., Sutton, B.: Nonuniform fast Fourier transforms using min-max interpolation. IEEE Trans. on Signal Proc. 51, 560–574 (2003)
Jonsson, E., Huang, S., Chan, T.: Total variation regularization in positron emission tomography. UCLA CAM Report 98-48, University of California, Los Angeles, CA (1998), http://www.math.ucla.edu/~chan/papers.html
Candès, E., Guo, F.: New multiscale transforms, minimum total variation synthesis: Applications to edge-preserving image reconstruction. Signal Processing 82, 1519–1543 (2002)
Capricelli, T.D., Combettes, P.L.: Parallel block-iterative reconstruction algorithms for binary tomography. In: Special issue of Electronic Notes in Discrete Mathematics: Workshop on discrete tomography and its applications, June 13-15, Elsevier, New York City (2005) (to appear)
Lee, N.Y., Lucier, B.J.: Wavelet methods for inverting the radon transform with noisy data. IEEE Trans. on Image Proc. 10, 79–94 (2001)
Chan, T., Marquina, A., Mulet, P.: High-order total variation-based image restoration. SIAM J. Sci. Comput. 22, 503–516 (2000)
Dobson, D., Santosa, F.: Recovery of blocky images from noisy and blurred data. SIAM J. Appl. Math. 56, 1181–1199 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, XQ., Froment, J. (2005). Constrained Total Variation Minimization and Application in Computerized Tomography. In: Rangarajan, A., Vemuri, B., Yuille, A.L. (eds) Energy Minimization Methods in Computer Vision and Pattern Recognition. EMMCVPR 2005. Lecture Notes in Computer Science, vol 3757. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11585978_30
Download citation
DOI: https://doi.org/10.1007/11585978_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30287-2
Online ISBN: 978-3-540-32098-2
eBook Packages: Computer ScienceComputer Science (R0)