First order quasi-linear PDEs with BV boundary data and applications to image inpainting [Elektronische Ressource] / Thomas März

Thomas März <[e-mail]>

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2010
• Nombre de lectures: 18
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Technische Universität München
Zentrum Mathematik
First Order Quasi-Linear PDEs with BV
Boundary Data and Applications to
Image Inpainting
Thomas März
Vollständiger Abdruck der von der Fakultät für Mathematik der Technis-
chen Universität München zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Dr. Bernhard Hanke
Prüfer der Dissertation: 1. Univ.-Prof. Dr. Folkmar Bornemann
2. Univ.-Prof. Dr. Bernd Schmidt
3. Univ.-Prof. Dr. Simon Masnou
Universität Lyon / Frankreich
(schriftliche Beurteilung)
Die Dissertation wurde am 19.11.2009 bei der Technischen Universität Mün-
chen eingereicht und durch die Fakultät für Mathematik am 30.03.2010
angenommen.Acknowledgements
This thesis would not have been realized without the support of several
people.
I would like to express my deep gratitude to my mentor, Prof. Dr. F. Borne-
mann, for his support, his advice and the freedom he allowed me.
Thanks to the Graduiertenkolleg Angewandte Algorithmische Mathematik
(funded by the Deutsche Forschungsgemeinschaft) of the Technische Uni-
versität München; I was a scholarship holder of the Graduiertenkolleg for
eight months.
Many thanks to the former and to the actual staff of the Chair of Scientific
Computing for numerous discussions and helpful suggestions.
Special thanks to Gordana Kelava, Esther Frömmer, Christian Ludwig, Eva
Perreiter, and Wolfgang Erb for proof reading earlier drafts of this thesis.
Finally, I want to thank the members of my family for their support.
iiiContents
1 Introduction 1
1.1 Inpainting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of the General Framework . . . . . . . . . . . . . . 5
1.2.1 The Linear Problem . . . . . . . . . . . . . . . . . . . 6
1.2.2 The Quasi-Linear Problem . . . . . . . . . . . . . . . . 11
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Basics: Functions of Bounded Variation 13
2.1 Measure Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Functions of Bounded Variation . . . . . . . . . . . . . . . . . 17
2.2.1 Definition and Characterization . . . . . . . . . . . . 17
2.2.2 Topologies on the Space BV . . . . . . . . . . . . . . . 18
2.2.3 Fine Properties of BV-Functions . . . . . . . . . . . . 21
2.2.4 BV-Functions of One Variable and BV-Sections . . . . 25
3 The Linear Problem 31
3.1 The Problem and its Requirements . . . . . . . . . . . . . . . 31
3.2 A Customized Coordinate System . . . . . . . . . . . . . . . 38
3.3 Existence of a Solution . . . . . . . . . . . . . . . . . . . . . . 51
3.4 Uniqueness and Stability . . . . . . . . . . . . . . . . . . . . . 69
4 The Quasi-Linear Problem 79
4.1 The Fixed Point Formulation and its Requirements . . . . . . 80
4.2 Existence of a Fixed Point . . . . . . . . . . . . . . . . . . . . 84
4.3 Uniqueness and Stability under Volterra-Type Dependence 87
4.3.1 PDE Coefficients with Vype and
Additional Requirements . . . . . . . . . . . . . . . . 87
4.3.2 Uniqueness of the Fixed Point . . . . . . . . . . . . . 90
4.3.3 Continuous Dependence of the Fixed Point . . . . . . 103
vvi CONTENTS
5 Extensions 109
5.1 Extended Concept of Time Functions . . . . . . . . . . . . . . 109
5.2 n-Connected Domains . . . . . . . . . . . . . . . . . . . . . . 120
6 Image Inpainting Based on Coherence Transport 123
6.1 The Generic Algorithm and its Continuous Formulation . . 123
6.2 Two Linear Models . . . . . . . . . . . . . . . . . . . . . . . . 131
6.2.1 Transport Along Normals . . . . . . . . . . . . . . . . 131
6.2.2 Guided Transport . . . . . . . . . . . . . . . . . . . . . 132
6.3 A Quasi-Linear Model . . . . . . . . . . . . . . . . . . . . . . 135
6.3.1 Guidance by Coherence Information . . . . . . . . . . 135
6.3.2 Structure Tensor with Volterra-Type Dependence . . 138
6.3.3 Properties of the Transport Field . . . . . . . . . . . . 148
6.3.4 Existence, Uniqueness and Continuous Dependence 156
6.4 Distance-To-Boundary Map as Time . . . . . . . . . . . . . . 161
7 Experiments on Different Orders 167
7.1 Order by Harmonic Interpolation . . . . . . . . . . . . . . . . 170
7.2 Order by Modified Distance to Boundary . . . . . . . . . . . 174
7.3 Order by Distance to Skeleton . . . . . . . . . . . . . . . . . . 176
7.4 Order by to Boundary and Natural Images . . . . . 178
Miscellaneous Symbols and Notations 181
Bibliography 185Chapter 1
Introduction
As image processing has become an active field of mathematical research,
the task of digital image inpainting has also been approached by mathemati-
cal methods in the last few years. The questions that we study in this work
emerged during the analysis of our image inpainting method Image Inpaint-
ing Based on Coherence Transport published in [BM07].
1.1 Inpainting
Image inpainting serves the purpose of touching-up damaged or unwanted
portions of a picture. In mathematical image processing images are consid-
ered as functions of type
w :W !R ,0
2defined on a typically rectangular image domainW = [a, b][c, d]R .0
The value w(x)2R often represents an intensity of light which is percep-
tible as a gray color.
From the mathematician’s point of view inpainting is a problem of data
interpolation. Apart fromW we are given a subdomainW W which0 0
marks the damage or the portion which has to be touched-up. And, the
”good” part of the image, which is to be kept, is given as a function
u :WnW!R ,0 0
defined on the data domainWnW, while u is undefined onW. Now, the0 0
task is to search for a function u : W!R, defined on the missing partW,
which interpolates the data u .0
Clearly, the interpolation problem, as stated above, might have many solu-
tions, but the very important side condition on an acceptable solution u is
that the completed image u¯,
u¯ := u 1 + u1 ,0 WnW W0
12 Chapter 1 Introduction
(a) vandalized image (courtesy of [Tel04, figure 8.i]) (b) inpainting interstage 1
(c) inpainting interstage 2 (d) inpainted result
Figure 1.1: Scratch removal by inpainting; using the method of [BM07]
defined on the whole image domain W , should look nice, i.e., u should0
interpolate the data u in a visually plausible manner.0
In order to achieve the latter goal, different approaches to the inpainting
problem have been made: for example, [CS02], [CKS02], [MM98], [Mas02],
and [Tsc05] have shown that variational principles and PDE methods are
fruitful here. But, the resulting PDEs in these works are typically non-linear
and of a high order (up to order 4); thus, the numerical algorithms are
iterative by nature and computationally expensive.
In the works cited above, the authors started with continuous models and
discretized them to obtain algorithms for digital image inpainting. In the
article [BM07], we approached the problem from the opposite direction:
our point of departure was the discrete inpainting problem. For discrete or
digital images the functions w :W !R are simply matrices andW ish 0,h 0,h
the set of matrix coordinates; the subscript h indicates discrete objects.
The simple idea behind the generic algorithm (see [BM07, section 2] and
chapter 6) is to fill the inpainting domain W by traversing its pixels –h
the points of W – in a fixed order from the boundary inwards by usingh
weighted means of given or already calculated image values. Thus, the al-
gorithm implements a process with processing order given by the distance-
to-boundary map, which is the time of first arrival. See figure 1.1, which1.1 Inpainting 3
(a) vandalized image (b) inpainted
Figure 1.2: Scratch removal by inpainting; using Telea’s method
illustrates some stages of this process. Such a single-pass method was first
utilized by Telea (see [Tel04]). Owing to the simple structure of the algo-
rithm, his method performs extremely fast, but produces a blurry fill-in,
which, moreover, shows peculiar transport patterns (see figure 1.2).
Analytical results of [BM07]
In order to better understand the geometrical effects of the generic algo-
rithm, we put it in a continuous framework. By the high-resolution vani-
shing-viscosity limit (see [BM07, section 3]) we have shown that the generic
algorithm, for a special class of weights, is consistent with the transport
equation
hc(x),ru(x)i= 0 , x2WnS ,
(1.1)
uj = u ,0WnW0
a PDE of first order. Hereby, the vector field c depends on the weights used
to compute the weighted means. Moreover, the exceptional setS is the
skeleton of the distance-to-boundary map d(x)= dist(x,¶W). The skeleton
S comprises the locations of ridges d; these are the points where the time of
the first arrival cannot be uniquely associated with a point on the boundary.
By equations (1.1), we can give the following rationale: imagine a restorer
doing brush strokes in the missing areaW. Assuming on the one hand that
he only uses color given by the data u on¶W and on the other that brush0
strokes go along trajectories x(t) – of a vector field c – which constantly
carry a single color, we end up with the dynamical system
0x = c(x) , x(0)= x 2 ¶W ,0
(1.2)0u = 0 , u(0)= u (x ) ,0 0
which describes exactly the characteristic