# Inpainting in Discrete Sobolev Spaces: Structural Information for Uncertainty Reduction
## 1 Introduction
of the unknown are needed (e.g., in [3; 26], the discrete Laplacian is employed as a smoothness estimator); in the second case, the choice is driven by the best match among the available patches in the dataset, usually represented by the given part of the image (in the following sections we will refer to it as to the _training set_\(T_{S}\), borrowing this expression from the neural networks literature). Despite the goodness of the achieved results, inpainting-by-patch methods mask a conceptual weakness due to neglecting the under-the-surface structural information hidden in \(T_{S}\). This structural information is connected with the concept of finite differences [27; 28; 29]. For this reason, introducing a similarity metric that cares about these structural aspects gives support to a better understanding of the logic behind the inpainting process. Sobolev spaces [30], in their discrete versions, have been used in the image processing field with different formalization and aims (see, e.g., [31; 32]). We employ, in the context of image inpainting, the definition of Sobolev spaces to formulate a new, neighborhood dependent functional, described in Section 2: in our method we stay true to the patch-based idea, in a way that is quite different from classical PDE methods, in which higher order derivatives are employed for regularization reasons. To the best of our knowledge, this is the first time that a functional having this form is employed for the solution of the inpainting problem, such that it represents a novelty in the field of the inpainting-by.patch techniques. Figure 1: An example of a damaged image (left) restored (right) using the inpaint-by-patch approach (central scheme). The missing points in \(\Omega\) (in black) are sequentially scrolled to individuate the best correspondence in the undamaged areas of the given image (\(T_{S}\) in the scheme, in white). The values found are then used to fill the missing points. More theoretically, in the seminal paper [29], a comparable approach for noise removal has been introduced in BV spaces, giving origin to a vast literature. Differently from [29], in our case, the finite differences are used as a similarity metric, as in [33] for textural classification purposes. An attempt in this direction has been described in [34], where a quite complete and general variational framework, applicable to super resolution and denoising problems, has been proposed. Like in [34], our results can be extended to other tasks, as image completion, texture synthesis, and image registration (only to cite some), thus providing general operational principles. Another open debate for the solution of the inpainting problem, using the inpainting-by-patch methods, is focused on the scanning order of the missing points. The role of the scanning order is to inpaint first those points where the uncertainty is lower with respect to the others. The pivotal work exploiting the importance of the scanning order is represented by [35], in which a priority index has been introduced. The proposed procedure gave considerable results such that it is still commonly taken as reference for qualitative evaluations. For this reason, in what follows, we have compared our reconstructions to the ones achieved using [35]. Starting from [35], further attempts to improve the final quality have been performed by different authors (see, e.g., [36]), basing their works mostly on numerical considerations. Differently from them, we reformulate a completely new priority index, never used before in the literature, justifying its introduction by uncertainty reduction motivations. An important scenario, for the inpainting problem, is represented by the fast and effective neural networks (NN) solutions. Recently, many inpainting methods have been developed based on deep learning techniques (see, e.g., [37; 38; 39]). The advantages of NN approaches reside in a fast computational time (after the time consuming initial training) with a high rate of success.