Image inpainting

ABSTRACT

Inpainting, the technique of modifying an image in an undetectable form, is as ancient as art itself. The goals and applications of inpainting are numerous, from the restoration of damaged paintings and photographs to the removal/replacement of selected objects. In this paper, we introduce a novel algorithm for digital inpainting of still images that attempts to replicate the basic techniques used by professional restorators. After the user selects the regions to be restored, the algorithm automatically fills-in these regions with information surrounding them. The fill-in is done in such a way that isophote lines arriving at the regions' boundaries are completed inside. In contrast with previous approaches, the technique here introduced does not require the user to specify where the novel information comes from. This is automatically done (and in a fast way), thereby allowing to simultaneously fill-in numerous regions containing completely different structures and surrounding backgrounds. In addition, no limitations are imposed on the topology of the region to be inpainted. Applications of this technique include the restoration of old photographs and damaged film; removal of superimposed text like dates, subtitles, or publicity; and the removal of entire objects from the image like microphones or wires in special effects.

REFERENCES

• 1: S. Walden. The Ravished Image. St. Martin's Press, New York, 1985.
• 2: G. Emile-Male. The Restorer's Handbook of Easel Painting. Van Nostrand Reinhold, New York, 1976.
• 3: D. King. The Commissar Vanishes. Henry Holt and Company, 1997.
• 4: A.C. Kokaram, R.D. Morris, W.J. Fitzgerald, P.J.W. Rayner. Detection of missing data in image sequences. IEEE Transac-tions on Image Processing 11(4), 1496-1508, 1995.
• 5: A.C. Kokaram, R.D. Morris, W.J. Fitzgerald, P.J.W. Rayner. Interpolation of missing data in image sequences. IEEE Trans-actions on Image Processing 11(4), 1509-1519, 1995.
• 6: C. Braverman. Photoshop retouching handbook. IDG Books Worldwide, 1998.
• 7: Anil N. Hirani , Takashi Totsuka, Combining frequency and spatial domain information for fast interactive image noise removal, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.269-276, August 1996 [doi>10.1145/237170.237264]
• 8: Alexei A. Efros , Thomas K. Leung, Texture Synthesis by Non-Parametric Sampling, Proceedings of the International Conference on Computer Vision-Volume 2, p.1033, September 20-25, 1999
• 9: David J. Heeger , James R. Bergen, Pyramid-based texture analysis/synthesis, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.229-238, September 1995 [doi>10.1145/218380.218446]
• 10: E. Simoncelli and J. Portilla. Texture characterization via joint statistics of wavelet coefficient magnitudes. 5th IEEE Int'l Conf. on Image Processing, Chicago, IL. Oct 4-7, 1998.
• 11: M. Nitzberg , D. Mumford , T. Shiota, Filtering, Segmentation, and Depth, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 12: S. Masnou and J.M. Morel. Level-lines based disocclusion. 5th IEEE Int'l Conf. on Image Processing, Chicago, IL. Oct 4-7, 1998.
• 13: C. Kenney and J. Langan. A new image processing primitive: reconstructing images from modified flow fields. University of California Santa Barbara Preprint, 1999.
• 14: P. Perona , J. Malik, Scale-Space and Edge Detection Using Anisotropic Diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.629-639, July 1990 [doi>10.1109/34.56205]
• 15: Luis Alvarez , Pierre-Louis Lions , Jean-Michel Morel, Image selective smoothing and edge detection by nonlinear diffusion. II, SIAM Journal on Numerical Analysis, v.29 n.3, p.845-866, June 1992 [doi>10.1137/0729052]
• 16: Stanley Osher , James A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, Journal of Computational Physics, v.79 n.1, p.12-49, Nov. 1988 [doi>10.1016/0021-9991(88)90002-2]
• 17: A. Marquina and S. Osher. Explicit algorithms for a new time dependent model based on level set motion for nonlinear de-bluring and noise removal. UCLA CAM Report 99-5, January 1999.
• 18: Leonid I. Rudin , Stanley Osher , Emad Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, v.60 n.1-4, p.259-268, Nov. 1, 1992
• 19: S. Osher, personal communication, October 1999.
• 20: Hong-Kai Zhao , T. Chan , B. Merriman , S. Osher, A variational level set approach to multiphase motion, Journal of Computational Physics, v.127 n.1, p.179-195, Aug. 1996 [doi>10.1006/jcph.1996.0167]
• 21: A. Bertozzi The mathematics of moving contact lines in thin liquid films. Notices Amer. Math. Soc., Volume 45, Number 6, pp. 689-697, June/July 1998.
• 22: Jack Tumblin , Greg Turk, LCIS: a boundary hierarchy for detail-preserving contrast reduction, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.83-90, July 1999 [doi>10.1145/311535.311544]
• 23: T. Chan and J. Shen, "Mathematical models for local deter-ministic inpaintings," UCLA CAM TR 00-11, March 2000.
• 24: C. Ballester, M. Bertalmio, V. Caselles, G. Sapiro, and J. Verdera, "Filling-in by joint interpolation of vector fields and grey levels," University of Minnesota IMA TR, April 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
anisotropic diffusion, image restoration, inpainting, isophotes