193 Pages
English

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

-

Gain access to the library to view online
Learn more

Informations

Published by
Published 01 January 2010
Reads 18
Language English
Document size 1 MB

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 characteristics of problem (1.1). Because we
paint from every boundary point intoW, the characteristics, which are the
brush strokes, are supposed to meet somewhere; the locations where they
meet are contained in the exceptional setS of equation (1.1).4 Chapter 1 Introduction
Eventually, the continuous description was the key to improve the quality
(compared to [Tel04]) of the inpainting. Ideally, in order to obtain an aes-
thetic inpainting, the vector field c would need to reflect the full expertise
of our restorer, which, clearly, is impossible. But at least the vector field c
should be adapted to and hence depend on the image u. This consideration
aims for a quasi-linear model
c[u](x),ru(x) = 0 , x2WnS ,h i
(1.3)
uj = u ,WnW 00
within the continuous framework; for the discrete algorithm, that means
that the weights need to depend on u. For the improved algorithm, in
[BM07], the vector c[u](x) – and thus the weight – includes an estimation
of the tangent vector, which is tangent to the level line of u going through
x. This is because brush strokes are supposed to continue level lines of u0
which have been interrupted byW .0
By applying structure tensor analysis to the image we estimate approximate
tangent information or so-called coherence information. The structure tensor
S is a positive semi-definite 2 2-matrix. Its set-up, basically, consists of
the following two steps:
Z
v(y)= k (y, h) u(h) dh ,1
B(y)
Z
TS(x)= k (x, y)rv(y)rv(y) dy .2
B(x)
The approximate tangent, then, is the eigenvector of S w.r.t. the minimal
eigenvalue. The benefit and the robustness of this estimator have been re-
+vealed in different works, e.g. [Wei98] and [AMS 06]. A precise descrip-
tion of the structure tensor and its analytical properties is given in chapter
6. Our new weight for the discrete algorithm, then, weights those pixels
that lie close to the approximate tangent much stronger; thus, the transport
effect is mainly along the approximate tangent.
Practical results of [BM07]
In [BM07], we gave a complete description of the novel algorithm and have
compared it to other methods. The inpainting result shown in figure 1.1 has
been computed by our improved method. The higher quality, compared to
Telea’s method, is clearly visible if one compares figures 1.1 and 1.2. For
Telea’s choice of the weight, the transport field c of the corresponding PDE
is exactlyrd. But, the distance-to-boundary map d depends only on the
geometry ofW and says nothing about the image.
By the structure tensor analysis, our method is computationally more ex-
pensive than Telea’s, but, compared to the other works cited above, we