Analysis of Artifacts in Shell-Based Image Inpainting: Why They Occur and How to Eliminate Them
Authors
Hocking, L. Robert
Holding, Thomas
Schönlieb, Carola-Bibiane
Publication Date
2020-03-16Journal Title
Foundations of Computational Mathematics
ISSN
1615-3375
Publisher
Springer US
Volume
20
Issue
6
Pages
1549-1651
Language
en
Type
Article
This Version
VoR
Metadata
Show full item recordCitation
Hocking, L. R., Holding, T., & Schönlieb, C. (2020). Analysis of Artifacts in Shell-Based Image Inpainting: Why They Occur and How to Eliminate Them. Foundations of Computational Mathematics, 20 (6), 1549-1651. https://doi.org/10.1007/s10208-020-09450-3
Description
Funder: University of Cambridge
Abstract
Abstract: In this paper we study a class of fast geometric image inpainting methods based on the idea of filling the inpainting domain in successive shells from its boundary inwards. Image pixels are filled by assigning them a color equal to a weighted average of their already filled neighbors. However, there is flexibility in terms of the order in which pixels are filled, the weights used for averaging, and the neighborhood that is averaged over. Varying these degrees of freedom leads to different algorithms, and indeed the literature contains several methods falling into this general class. All of them are very fast, but at the same time all of them leave undesirable artifacts such as “kinking” (bending) or blurring of extrapolated isophotes. Our objective in this paper is to build a theoretical model in order to understand why these artifacts occur and what, if anything, can be done about them. Our model is based on two distinct limits: a continuum limit in which the pixel width h→0 and an asymptotic limit in which h>0 but h≪1. The former will allow us to explain “kinking” artifacts (and what to do about them) while the latter will allow us to understand blur. Both limits are derived based on a connection between the class of algorithms under consideration and stopped random walks. At the same time, we consider a semi-implicit extension in which pixels in a given shell are solved for simultaneously by solving a linear system. We prove (within the continuum limit) that this extension is able to completely eliminate kinking artifacts, which we also prove must always be present in the direct method. Finally, we show that although our results are derived in the context of inpainting, they are in fact abstract results that apply more generally. As an example, we show how our theory can also be applied to a problem in numerical linear algebra.
Keywords
Article, Image processing, Image inpainting, Partial differential equations, Stopped random walks, Numerical analysis, 68U10, 65M12, 65M15, 65F10, 60G50, 60G40, 35F15, 60G42, 35Q68
Identifiers
s10208-020-09450-3, 9450
External DOI: https://doi.org/10.1007/s10208-020-09450-3
This record's URL: https://www.repository.cam.ac.uk/handle/1810/313058
Rights
Attribution 4.0 International (CC BY 4.0)
Licence URL: https://creativecommons.org/licenses/by/4.0/
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.