An Algorithm for Total Variation Inpainting Based on Nonlinear Multi-Grid Methods

Abstract

Image inpainting refers to restoring a damaged image with missing information. The total variation (TV) inpainting model is one such method that simultaneously fills in the regions with available information from their surroundings and eliminates noises. The method works well with small narrow inpainting domains. However there remains an urgent need to develop fast iterative solvers, as the underlying problem sizes are large. In addition one needs to tackle the imbalance of results between inpainting and denoising. When the inpainting regions are thick and large, the procedure of inpainting works quite slowly and usually requires a significant number of iterations and leads inevitably to oversmoothing in the outside of the inpainting domain. To overcome these difficulties, we propose a solution for TV inpainting method based on the nonlinear multi-grid algorithm.

Keywords

Inpainting total variation multi-grid partial differential equations

References

Chan

T. F.

and Shen

, Mathematical models for local non-texture inpaintings, SIAM J. Appl. Math., 62(3), 1019–1043, 2002.

Bertalmio

Sapiro

Caselles

, and Ballester

. Image Inpainting. In Proceedings SIGGRAPH, 2000.

Chan

T. F.

Kang

S. H.

, and Shen

, Euler's elastica and curvature based inpainting, SIAM Journal of Applied Math., 63(2), 564–592, 2002.

Chan

T. F.

and Shen

, Non-texture inpainting by curvature driven diffusions (CDD), J.Visual Comm. Image Rep., 12, 436–449, 2001.

Rudin

Osher

, and Fatemi

. Nonlinear total variation based noise removal algorithms. Physica D, 60, 259–268, 1992.

Chan

T. F.

and Kang

S. H.

. Error analysis for image inpainting, J Math Imaging Vis. Published online: 2006.

Chan

T. F.

Golub

G. H.

and Mulet

, A nonlinear primal dual method for total variation based image restoration, SIAM J.Sci. Comput. 20(6), 1964–1977, 1999.

Vogel

C. R.

and Oman

M. E.

, Iterative methods for total variation denoising, SIAM J. Sci. Statist. Comput. 17, 227–238, 1996.

Vogel

C. R.

and Oman

M. E.

, Fast, robust total variation-based reconstruction of noisy, blurred images. IEEE Trans, Image Process 7, 813–824, 1998.

10.

Briggs

W. L.

Henson

V. E.

, and McCormick

S. F.

. A Multi-grid Turorial, Second Edition. Philadelphia, SIAM, 2000.

11.

Acton

S. T.

. Multi-grid anisotropic diffusion. IEEE Trans, on Image Procc, 7(3), 280–291, 1998.

12.

Chan

T. F.

and Chen

. On a nonlinear multi-grid algorithm with primal relaxation for the image total variation minimization. Numerical Algorithms, 2006.

13.

Kenigsberg

Kimmel

, and Yavneh

. A multi-grid Approach for Fast Geodesic Active Contours, Computer Science Department, Technical Report, 2004.

14.

Frohn-Schauf

Henn

, and Witsch

. Nonlinear multi-grid methods for total variation image denoising, Comput Visual Sci 7, 199–206, 2004.

15.

Hackbush

, Multi-grid methods, Science Press, 1988.

16.

Brandt

. Multi-level adaptive solutions to boundary-value problem. Math. Comp, 37, 333–390, April 1977.

17.

Multi-grid methods for boundary value problems, Numerical recipes in c: The art of scientific computing, Cambridge university Press.

18.

Marquina

and Osher

. Lecture Notes in Computer Science, volume 1682, chapter “A new time dependent model based on level set motion for nonlinear deblurring and noise removal”, pages 429–434, 1999.

19.

Perona

and Malik

, Scale-space and edge detection using anisotropic diffusion, IEEE Trans. Pattern Anal. Machine Intell, 12(7), 629–639, 1990.

20.

Hackbush

and Trottenberg

, Eds. Multi-grid Methods. New York: Springer-Verlag, 1982.

21.

D'Amore

Marcellino

and Murli

. Image sequence inpainting: Towards numerical software for detection and removal of local missing data via motion estimation. Journal of Computational and Applied Mathematics, 198(2), 396–413, 2007.