Diffusion–Shock Inpainting

Abstract

We propose diffusion–shock (DS) inpainting as a hitherto unexplored integrodifferential equation for filling in missing structures in images. It combines two carefully chosen components that have proven their usefulness in different applications: homogeneous diffusion inpainting and coherence-enhancing shock filtering. DS inpainting enjoys the complementary synergy of its building blocks: It offers a high degree of anisotropy along an eigendirection of the structure tensor. This enables it to connect interrupted structures over large distances. Moreover, it benefits from the sharp edge structure generated by the shock filter, and it exploits the efficient filling-in effect of homogeneous diffusion. The second order equation that underlies DS inpainting inherits a continuous maximum–minimum principle from its constituents. In contrast to other attractive second order inpainting equations such as edge-enhancing anisotropic diffusion, we can guarantee this property also for the proposed discrete algorithm. Our experiments show a performance that is comparable to or better than many linear or nonlinear, isotropic or anisotropic processes of second or fourth order. They include homogeneous diffusion, biharmonic interpolation, TV inpainting, edge-enhancing anisotropic diffusion, the methods of Tschumperlé and of Bornemann and März, Cahn–Hilliard inpainting, and Euler’s elastica.

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 741215, ERC Advanced Grant INCOVID).

1 Introduction

Image inpainting [10, 18] aims at restoring images with missing or damaged areas. Many popular methods use partial differential equations (PDEs), since they offer compact and transparent models with sound theoretical foundations. A particularly simple representative is homogeneous diffusion inpainting [6]. It is based on a linear second order PDE that satisfies a maximum–minimum principle and allows to design very efficient algorithms [13]. For inpainting-based compression, it may give very good results, if the data are optimised carefully [17]. However, it cannot produce satisfactory continuations of sharp edges over large distances.

As a rememdy, higher order PDEs have been considered, such as the ones arising from the energy functionals of Euler’s elastica [14, 18, 19] or the Cahn–Hilliard model [2, 5]. From a theoretical perspective, these continuous models are attractive: They offer a low-curved continuation of level lines or the propagation of gradient information. Unfortunately, for such higher order PDEs it is fairly challenging to design good numerical algorithms that are computationally efficient and do not suffer from dissipative artefacts, which lead to a blurred continuation of edges.

An interesting alternative to higher order inpainting PDEs are second order anisotropic integrodifferential methods that implicitly exploit curvature information via a Gaussian convolution inside a diffusion tensor. This idea is pursued in edge-enhancing anisotropic diffusion (EED) [32]. It achieves state-of-the-art results for inpainting-based compression and can propagate structures over large distances [24]. However, current discretisations can violate a maximum–minimum principle. Moreover, although edges remain sharper than for most algorithms for higher order PDEs, they still show some dissipative artefacts.

Our Contribution. The goal of our work is to show that all the above mentioned problems can be addressed with a surprisingly simple combination of two processes with complementary qualities: homogeneous diffusion inpainting [6] and a coherence-enhancing shock filter [30]. While both techniques are well-established, their combination within an inpainting method is novel. The resulting diffusion–shock (DS) inpainting offers the best of two worlds: On the one hand, the coherence-enhancing shock filter is guided by the robust edge information from a structure tensor [11]. Its switch between the hyperbolic PDEs of dilation and erosion creates perfectly sharp shock fronts that can be propagated with basically no directional artefacts. This is illustrated in Fig. 1. On the other hand, the parabolic homogeneous diffusion PDE is a model with maximal simplicity that creates an efficient filling-in mechanism in flat areas. For both processes we use discretisations that offer a high degree of rotation invariance and satisfy a discrete maximum–minimum principle. These properties carry over to DS inpainting. In our experiments we compare DS inpainting with many inpainting PDEs and demonstrate its favourable performance in spite of its simplicity.

Related Work. With the goal of image sharpening, Kramer and Bruckner [16] proposed the first discrete definition of a shock filter, before Osher and Rudin gave the first PDE-based formulation [21]. In both cases, the morphological operations dilation and erosion with a disk-shaped structuring element are applied adaptively, depending on the sign of a second derivative operator. To make the process more robust against noise, Alvarez and Mazorra proposed to presmooth the image before computing this second derivative operator that guides the process [1]. Weickert’s coherence-enhancing shock filter [30] uses the second derivative in direction of the dominant eigenvector of the structure tensor. Welk et al. [34] proved well-posedness results for 1-D semidiscrete and discrete shock filters. It is well-known that several classical image enhancement methods implicitly or explicitly combine a smoothing PDE with a shock filter; see e.g. [15, 29]. Such combinations, however, rarely appear in inpainting applications.

Apart from the already mentioned PDE-based inpainting methods, there some additional ones that play a role in our performance evaluation. Biharmonic interpolation [8] is the fourth order counterpart to homogeneous diffusion inpainting and offers reasonable quality in inpainting-based compression [24]. Total variation (TV) inpainting [26] can be seen as a limit case of Perona–Malik [22] inpainting with a Charbonnier diffusivity [7]. Tschumperlé’s method [28] involves a tensor-driven equation that uses the curvature of integral curves. This also qualifies it as candidate for bridging interrupted structures over large distances.

While many inpainting PDEs are elliptic or parabolic, hyperbolic ones such as the dilations and erosions in shock filters are rarely used within inpainting methods. A recent inpainting model by Novak and Reinić [20] combines a shock filter with the fourth order Cahn–Hilliard PDE. Our DS inpaiting is conceptually simpler: already a second order homogeneous diffusion PDE suffices to achieve the desired filling-in effect. The method of Bornemann and März [3] is closest in spirit to DS inpainting. It uses transport processes that are guided by a structure tensor. In contrast to our work, however, their paper follows a procedural–algorithmic approach without specifying a compact integrodifferential equation. In our experiments we will compare against this method.

Paper Structure. In Sect. 2, we review the concept of coherence-enhancing shock filtering since it is fundamental for our work. Section 3 introduces our proposed DS inpainting model. A corresponding algorithm is discussed in Sect. 4, followed by an experimental evaluation in Sect. 5. Section 6 concludes the paper and gives an outlook to future work.

Fig. 1.

Line elongation with the coherence-enhancing shock filter. Left: Original image, $512\times 384$. Right: Steady state of the shock filter, $\sigma = 2$, $\rho = 5$.

2 Review of Coherence-Enhancing Shock Filtering

Since DS inpainting substantially relies on coherence-enhancing shock filters and their PDE-based definitions of dilation and erosion, we first review these concepts, in order to keep our paper self-contained.

2.1 PDE-Based Morphology

Let $f: \varOmega \rightarrow \mathbb {R}$ denote a greyscale image on a rectangular image domain $\varOmega \subset \mathbb {R}^2$. Mathematical morphology [27] considers a neighbourhood (structuring element) B. The dilation $\delta _B[f]$ replaces f by its supremum within B, and the erosion $\varepsilon _B[f]$ uses an infimum instead:

$$\begin{aligned} \delta _B[f](\boldsymbol{x} ) \;&= \; \sup \{ f(\boldsymbol{x} -\boldsymbol{y})\; \mid \; \boldsymbol{y} \in B \}\,,\end{aligned}$$

(1)

$$\begin{aligned} \varepsilon _B[f](\boldsymbol{x} ) \;&= \; \inf \; \{ f(\boldsymbol{x}+\boldsymbol{y})\; \mid \; \boldsymbol{y} \in B \}\,. \end{aligned}$$

(2)

If B is a disk of radius t, dilation and erosion $u(\boldsymbol{x}, t)$ follow the PDE [4]

$$\begin{aligned} \partial _t u \; = \; \pm |\boldsymbol{\nabla }u|\end{aligned}$$

(3)

with initial image $u(\boldsymbol{x}, 0) = f(\boldsymbol{x})$ and reflecting boundaries. The $+$ sign describes dilation, and the − sign erosion. By $\boldsymbol{\nabla }= (\partial _x, \partial _y)^\top$ we denote the spatial nabla operator, and $|\cdot |$ is the Euclidean norm.

2.2 Coherence-Enhancing Shock Filtering

The dilation PDE propagates the grey values of local maxima, while erosion propagates the grey values of local minima. To enhance the sharpness of images, shock filters locally apply dilation in influence zones of maxima and erosion in influence zones of minima. The sign of a second order derivative operator determines these influence zones. Shocks are formed at its zero crossings. Individual shock filters differ in their second order derivative operator, which may also involve some smoothing to make the filter more robust under noise.

The coherence-enhancing shock filter [30] that we use is governed by the PDE

$$\begin{aligned} \partial _t u \; = \; - {{\,\textrm{sgn}\,}}\big (\partial _{\boldsymbol{w}\boldsymbol{w}}u_\sigma \big ) |\boldsymbol{\nabla }u| \end{aligned}$$

(4)

with initial image $u(\boldsymbol{x}, 0) = f(\boldsymbol{x})$ and reflecting boundary conditions. It involves the second derivative along the dominant eigenvector $\boldsymbol{w}$ (with the larger eigenvalue) of the structure tensor [11]. Let $u_\sigma = K_\sigma *u$ denote the convolution of u with a Gaussian $K_\sigma$ of standard deviation $\sigma$. Then the structure tensor is given by a componentwise convolution of the matrix $\boldsymbol{\nabla } u_\sigma \, \boldsymbol{\nabla } u_\sigma ^\top$ with a Gaussian $K_\rho$:

$$\begin{aligned} \boldsymbol{J}_\rho (\boldsymbol{\nabla }u_\sigma ) \;=\; K_\rho * \left( \boldsymbol{\nabla } u_\sigma \, \boldsymbol{\nabla } u_\sigma ^\top \right) . \end{aligned}$$

(5)

Its eigenvalues describe the average quadratic contrast in the direction of the eigenvectors. Thus, steering the shock filter with $\partial _{\boldsymbol{w}\boldsymbol{w}}u_\sigma$ encourages the formation of coherent, flow-like structures with maximal contrast in direction $\boldsymbol{w}$. This justifies the name of the coherence-enhancing shock filter. For $t\rightarrow \infty$ it leads to a typically non-flat steady state that shows elongated image structures with very sharp edges. In contrast to [30], we use $\boldsymbol{J}_\rho (\boldsymbol{\nabla }u_\sigma )$ instead of $\boldsymbol{J}_\rho (\boldsymbol{\nabla }u)$, which yields better results in our case.

Figure 1 illustrates the performance of this shock filter. Without visible deviations, it elongates the black line over more than 200 pixels in a direction that is not grid aligned. Moreover, the result is extremely sharp without any dissipative artefacts. This quality is hardly ever seen in PDE-based algorithms.

3 Diffusion–Shock Inpainting

Coherence-enhancing shock filtering is designed to propagate information only in coherence direction. The scale of the created structures perpendicular to its propagation direction is determined by the presmoothing scale $\sigma$. Hence, it cannot fill in large homogeneous areas beyond that scale. Here, homogeneous diffusion inpainting [6] may serve as an ideal partner. It is simple, parameter-free, satisfies a maximum–minimum principle, and offers an efficient isotropic filling-in mechanism by solving $\,0 = \varDelta u = \partial _{xx}u + \partial _{yy}u\,$ in inpainting regions.

Therefore, we design our diffusion–shock (DS) inpainting such that it performs a convex combination of both processes: Around edges, the coherence-enhancing shock filter from Subsect. 2.2 dominates, and homogeneous diffusion inpainting is activated in flat regions. Let the locations of the known values be given by a so-called inpainting mask $K\subset \varOmega$. Here we do not alter the grey values. In the inpainting domain $\varOmega \setminus K$, the reconstruction is computed as the steady state ($t\rightarrow \infty$) of the integrodifferential equation

$$\begin{aligned} \partial _t u \; = \; g\left( |\boldsymbol{\nabla }u_\nu |^2\right) \, \varDelta u \;-\; \Big (1-g\left( | \boldsymbol{\nabla }u_\nu |^2\right) \!\Big ) \, {{\,\textrm{sgn}\,}}\big ( \partial _{\boldsymbol{w}\boldsymbol{w}} (u_\sigma ) \big ) \, | \boldsymbol{\nabla }u | \end{aligned}$$

(6)

with Dirichlet data at the boundaries $\partial K$ of the inpainting mask, and reflecting boundary conditions on the image domain boundary $\partial \varOmega$. By $u_\nu =K_\nu *u$ we denote a convolution of u with a Gaussian of standard deviation $\nu$. The weight function $g\!:\mathbb {R}\rightarrow \mathbb {R}$ is a nonnegative decreasing function with $g(0)=1$, and $g(s^2) \rightarrow 0$ for $s^2\rightarrow \infty$. It has the same structure as a diffusivity function in nonlinear diffusion filters [22]. We use the Charbonnier diffusivity [7]

$$\begin{aligned} g\left( s^2\right) \; = \; \frac{1}{\sqrt{1+ s^2/\lambda ^2}} \end{aligned}$$

(7)

with a contrast parameter $\lambda > 0$. Thus, the weight $g\left( |\boldsymbol{\nabla }u_\nu |^2\right)$ secures a smooth transition between the shock term and the homogeneous diffusion term. Its Gaussian scale $\nu$ makes it robust under noise.

4 Numerical Algorithm

Continuous DS inpainting inherits a maximum–minimum principle from its diffusive and morphological components. To obtain an algorithm for DS inpainting that preserves this property, we discretise Eq. (6). We assume the same grid size $h > 0$ in x- and y-direction. Let $\tau >0$ denote the time step size, and let $u_{i,j}^k$ be an equal discrete approximation of $u(\boldsymbol{x},t)$ in pixel (i, j) at time $k\tau$. For simplicity, we use an explicit finite difference scheme. It approximates $\partial _t u$ at time level k with the forward difference

$$\begin{aligned} (\partial _t u)_{i,j}^k \;=\; \frac{u_{i,j}^{k+1}-u_{i,j}^k}{\tau } \end{aligned}$$

(8)

and evaluates the right hand side of (6) at the old time level k. Thus, let us now focus on the space discretisation of the diffusion term and the shock term.

For the homogeneous diffusion term $\varDelta u$ classical central differences are suitable. Welk and Weickert show in [33] that a weighted combination of axial and diagonal central differences with weight $\delta = \sqrt{2}-1$ results in a scheme with good rotation invariance. The corresponding stencil is given by

(9)

With this stencil in space and the forward difference (8) in time we obtain an explicit scheme for the homogeneous diffusion equation $\partial _t u = \varDelta u$. If

$$\begin{aligned} \tau \;\le \; \frac{h^2}{4-2\delta } \;=:\; \tau _D\,, \end{aligned}$$

(10)

one easily verifies that $u_{i,j}^{k+1}$ is a convex combination of data at time level k. This implies stability in terms of the maximum–minimum principle

$$\begin{aligned} \min _{n,m} f_{n,m} \; \le \; u^k_{i,j} \;\le \; \max _{n,m} f_{n,m}\; \qquad \text{ for } \text{ all } \text{ i, } \text{ j, } \text{ and } \text{ for } k \ge 1\text{. } \end{aligned}$$

(11)

A space discretisation of morphological evolutions of type $\partial _t u = \pm |\boldsymbol{\nabla }u|$ is not as straightforward. Typically one uses upwind methods such as the Rouy–Tourin scheme [23]. In order to improve its rotation invariance, we follow Welk and Weickert [33] again, who propose a weighted combination of a Rouy–Tourin scheme in axial and diagonal direction. For the dilation term $|\boldsymbol{\nabla }u|$ this yields

$$\begin{aligned} |\boldsymbol{\nabla }u|_{i,j}^k \;=\; \tfrac{1-\delta }{h} \, \big (&\max \, \lbrace u_{i+1,j}^k \!-\! u_{i, j}^k,\; u_{i-1,j}^k \!-\! u_{i, j}^k,\; 0\rbrace ^2 \nonumber \\ +&\max \, \lbrace u_{i,j+1}^k \!-\! u_{i, j}^k,\; u_{i,j-1}^k \!-\! u_{i, j}^k,\;0\rbrace ^2 \big )^\frac{1}{2} \nonumber \\[1mm] +\;\tfrac{\delta }{\sqrt{2}h} \, \big (&\max \, \lbrace u_{i+1,j+1}^k \!-\! u_{i, j}^k,\; u_{i-1,j-1}^k \!-\! u_{i, j}^k,\; 0\rbrace ^2 \nonumber \\ +&\max \, \lbrace u_{i-1,j+1}^k \!-\! u_{i, j}^k,\; u_{i+1,j-1}^k \!-\! u_{i, j}^k,\;0\rbrace ^2 \big )^\frac{1}{2} \end{aligned}$$

(12)

with some weight $\delta \in [0,1]$. For the erosion term $-|\boldsymbol{\nabla }u|$, we use

$$\begin{aligned} -|\boldsymbol{\nabla }u|_{i,j}^k \;=\; -\tfrac{1-\delta }{h} \, \big (&\max \, \lbrace u_{i,j}^k \!-\! u_{i+1, j}^k,\; u_{i,j}^k \!-\! u_{i-1, j}^k,\; 0\rbrace ^2 \nonumber \\ +&\max \, \lbrace u_{i,j}^k \!-\! u_{i, j+1}^k ,\; u_{i,j}^k \!-\! u_{i, j-1}^k,\;0\rbrace ^2 \big )^\frac{1}{2} \nonumber \\[1mm] -\;\tfrac{\delta }{\sqrt{2}h} \, \big (&\max \, \lbrace u_{i,j}^k \!-\! u_{i+1,j+1}^k,\; u_{i,j}^k \!-\! u_{i-1,j-1}^k,\;0\rbrace ^2 \nonumber \\ +&\max \, \lbrace u_{i,j}^k \!-\! u_{i-1,j+1}^k ,\; u_{i,j}^k \!-\! u_{i+1,j-1}^k ,\;0 \rbrace ^2 \big )^\frac{1}{2} \;. \end{aligned}$$

(13)

It can be shown that an explicit scheme with time discretisation (8) and space discretisation (12) or (13) satisfies the maximum–minimum principle (11) if

$$\begin{aligned} \tau \;\le \; \frac{h}{\sqrt{2}\,(1-\delta ) + \delta } \;=:\; \tau _M\,. \end{aligned}$$

(14)

For approximating rotation invariance well, we follow [33] and set $\delta =\sqrt{2} - 1$.

To go from dilation and erosion to a coherence-enhancing shock filter, we have to discretise $\partial _{\boldsymbol{w} \boldsymbol{w}} u_\sigma$. We compute all Gaussian convolutions in the spatial domain with a sampled and renormalised Gaussian. To guarantee a high approximation quality, it is truncated at five times its standard deviation. In order to implement reflecting boundary conditions, we add an extra layer of mirrored dummy pixels around the image domain. For the first order derivatives within the structure tensor, we enforce this mirror symmetry by imposing zero values at the image boundaries. We approximate $\partial _x u$ and $\partial _y u$ in the structure tensor by means of Sobel operators [9], which offer a high degree of rotation invariance. Since the structure tensor is a symmetric $2 \times 2$ matrix, its normalised dominant eigenvector $\boldsymbol{w} = (c, s)^\top$ can be computed analytically. Moreover, we have

$$\begin{aligned} \left( \partial _{\boldsymbol{w} \boldsymbol{w}} v\right) _{i,j} ^k \;=\; \left( c^2 \, \partial _{xx}v + 2 cs \, \partial _{xy}v + s^2 \, \partial _{yy}v\right) _{i,j}^k. \end{aligned}$$

(15)

All second order derivatives on the right hand side are approximated with their standard central differences.

Putting everything together yields the following explicit scheme for (6):

$$\begin{aligned} \frac{u^{k+1}_{i,j}- u^k_{i,j}}{\tau }\;=\; g_{i,j}^k \cdot \big (\varDelta u\big )_{i,j}^k - (1-g_{i,j}^k)\cdot {{\,\textrm{sgn}\,}}\big ((\partial _{\boldsymbol{w} \boldsymbol{w}} u_\sigma )^k_{i,j}\big ) \, |\boldsymbol{\nabla }u|^k_{i,j} \end{aligned}$$

(16)

with initial condition $u^0_{i,j} = f_{i,j}$. It inherits its stability from the stability results of the schemes for diffusion and morphology:

Theorem 1

(Stability of the DS Inpainting Scheme).

Let the time step size $\tau$ of the scheme (16) be restricted by

$$\begin{aligned} \tau \; \le \; \min \,\{\tau _D, \, \tau _M\} \end{aligned}$$

(17)

with $\tau _D$ and $\tau _M$ as in (10) and (14).

Then the scheme satisfies the discrete maximum–minimum principle

$$\begin{aligned} \min _{n,m} f_{n,m} \; \le \; u^k_{i,j} \;\le \; \max _{n,m} f_{n,m}\; \qquad \text{ for } \text{ all } \text{ i, } \text{ j, } \text{ and } \text{ for } k \ge 1\text{. } \end{aligned}$$

(18)

Proof

If $\tau \le \min \,\{\tau _M, \, \tau _D\}$, it follows from the stability of the diffusion and morphological processes that

$$\begin{aligned} u^{k+1}_{i,j} \;&=\; u^k_{i,j} +\tau g_{i,j}^k \cdot \big (\varDelta u\big )_{i,j}^k - (1-g_{i,j}^k)\cdot \,\tau {{\,\textrm{sgn}\,}}\big ((\partial _{\boldsymbol{w} \boldsymbol{w}}u_\sigma )^k_{i,j}\big ) \, |\boldsymbol{\nabla }u|^k_{i,j}\\&\le \; g_{i,j}^k \max _{n,m} f_{n,m} + (1-g_{i,j}^k) \max _{n,m} f_{n,m} \\ \;&=\;\max _{n,m} f_{n,m} \; . \end{aligned}$$

Analogously, one can show the condition $\, \min \limits _{n,m} f_{n,m} \, \le \, u^k_{i,j}$.    $\square$

Thus, for $\,\delta = \sqrt{2}-1\,$ and $\,h=1\,$ our scheme is stable for $\,\tau \,\le \, \tau _D \,\approx \, 0.31$. Theorem 1 shows an advantage of DS inpainting over EED inpainting [24, 32], for which a discrete maximum–minimum principle cannot be guaranteed so far.

5 Experiments

Let us now evaluate DS inpainting experimentally. We mainly focus on binary images, since their high contrast is especially vulnerable to dissipative artefacts, but also present one experiment with greyscale images. Whenever the mask image is given, the white area denotes the inpainting mask, and the black area depicts the unknown regions. All methods in our evaluation use optimised parameters.

In Fig. 2, we apply DS inpainting to shape completion problems inspired by the experiments for Cahn–Hilliard inpainting in [2]. Our operator connects bars and restores a cross while maintaining the high contrast of the binary images. Compared to the results in [2], DS inpainting offers sharper reconstructions.

Figure 3 shows a more challenging experiment, inspired by [24]. It drives the sparsity of the inpainting data to the extreme by specifying only one or four dipoles. Nevertheless, DS inpainting shows a flawless performance: It creates two sharp half planes from one dipole, and a disk from four dipoles. This demonstrates its ability to bridge large distances and its curvature reducing effect.

Figure 4 shows an exhaustive comparison of DS inpainting with many results from Schmaltz et al. [24]. The goal is to reconstruct a Kaniza-like triangle. Homogeneous diffusion [6], biharmonic interpolation [8], and TV inpainting [26] are unable to produce sharp edges. Tschumperlé’s algorithm [28] connects the corners, but fails to produce correctly oriented sharp edges. The Bornemann–März approach [3], edge-enhancing anisotropic diffusion (EED) [24, 32], and DS inpainting reconstruct a satisfactory triangle. DS inpainting offers the best overall quality with high directional accuracy and no visible dissipative artefacts.

In Fig. 5, we consider the shape completion of a disk and a cat image, and compare DS inpainting with two advanced competitors: Euler’s elastica [19] and EED inpainting [24]. The elastica results have been published in [25], while the cat data and its result for EED go back to [31]. While all methods accomplish their tasks, DS inpainting produces the sharpest edges.

Figure 6 shows that DS inpainting is also a powerful method for the reconstruction of greyscale images from sparse data. In both examples, the data were given by 10% randomly selected pixels of a $256 \times 256$ image. On a PC with an Intel^© Core™i9-11900K CPU @ 3.50 GHz, the runtime was 3.32 seconds for the peppers image and 3.76 seconds for the house image.

Fig. 2.

DS inpainting of $256\times 256$ test images. Parameters: Top: $\sigma = 2$, $\rho =5$, $\nu =3$, and $\lambda = 3$. Bottom: $\sigma = 2$, $\rho =5$, $\nu =2$, and $\lambda = 2$.

Fig. 3.

DS inpainting from dipoles. Top: $128\times 128$ image; $\sigma = 1$, $\rho =2$, $\nu =2$, $\lambda = 1$. Bottom: $127\times 127$ image; $\sigma = 2.65$, $\rho =4$, $\nu =2$, $\lambda = 3$.

Fig. 4.

Comparison of inpainting methods. Top: Input image with known data in the disks and noise in the unknown region, homogeneous diffusion, biharmonic interpolation, and TV inpainting. Bottom: Tschumperlé’s approach, Bornemann–März (BM) method, EED inpainting, DS inpainting with $\sigma = 4.7$, $\rho =6$, $\nu =5.2$, and $\lambda = 3.4$.

Fig. 5.

Comparison of Euler’s elastica, EED, and DS inpainting. The inpainting mask is shown in white. Parameters for DS inpainting: Top: $\sigma = 3.2$, $\rho =3$, $\nu =3$, and $\lambda = 2$; Bottom: $\sigma = 4.2$, $\rho =4.8$, $\nu =4.5$, and $\lambda = 7$.

Fig. 6.

Inpainting of sparse greyscale images (size $256\times 256$, 10 % density, randomly chosen) with DS inpainting. Parameters: Top: $\sigma =2$, $\rho =1.5$, $\nu =5$, and $\lambda =3$; Bottom: $\sigma =2.5$, $\rho =1.8$, $\nu =3.5$, and $\lambda =3$.

6 Conclusions and Future Work

With DS inpainting we have introduced an approach that aims at maximal simplicity while satisfying widely accepted requirements on inpainting methods. These requirements include the ability to bridge large gaps and the potential to offer sharp edges, a high degree of rotation invariance, and stability in terms of a maximum–minimum principle that prevents over- and undershoots.

Interestingly, this was possible by combining two “time-honoured” components: Homogeneous diffusion has been axiomatically introduced to image analysis 61 years ago [12], and coherence-enhancing shock filters have been around for 20 years [30]. This demonstrates that classical methods still offer a huge potential that awaits being explored.

While most PDEs for inpainting are elliptic or parabolic, our results emphasise that the hyperbolic ones deserve far more attention. Hyperbolic PDEs are a natural concept for modelling discontinuities, and shock filters are a prototype for this. While their early representatives [16, 21] produced oversegmentations and were highly sensitive w.r.t. to noise, more advanced variants such as coherence-enhancing shock filters have changed the game: Their performance reflects the high robustness of the structure tensor that guides them.

Last but not least, the fact that DS inpainting is a second order integrodifferential process that offers the full performance of higher order inpainting PDEs questions the necessity of higher order methods in practice. Without doubt, the latter ones are algorithmically far more challenging. As a general principle in science, Occam’s razor suggests to prefer the simplest model that accomplishes a desired task. Our paper adheres to this principle.

In our ongoing work, we are aiming at a deeper understanding of such integrodifferential processes, and we are investigating alternative applications of this promising class of methods.