# Inpainting in Discrete Sobolev Spaces: Structural Information for Uncertainty Reduction
## 1 Introduction  
In the literature, the so called \"inpainting problem\" consists of filling zones of \"missing\" information in an image, i.e., in a two-dimensional discrete set [1]. Focusing on the specific two dimensional image case, to have satisfactory results, the inpainted area has to be not \"eye-distinguishable\" from the rest of the given image by a human observer. This subjective way to evaluate the achieved results does not take into account the ground truth, in all of those cases when the to-be-inpainted areas are created deleting zones of the complete starting image (Even if in practical cases ground truth images are never available, it is possible to create specific tests where the area to reconstruct is expected to be exactly the part that has been deleted from the pristine image. This kind of test is useful, e.g., to verify the correct behavior of the reconstruction algorithms). To tackle the inpainting problem different solutions have been proposed. On one hand, partial differential equations (PDE)-based approaches have been used. These methods involve the introduction of derivatives in the mathematical models (or their equivalent finite differences in the discrete case), working in the so called Sobolev spaces [2; 3; 4; 5; 6; 7], i.e., in mathematical spaces where the norm of the Lebesgue spaces is extended to the derivatives of the function itself. PDE-based approaches achieve good results when the damaged regions are small in size; otherwise, their reconstructions appear blurred. Moreover, these methods usually need a considerable execution time [8; 9; 10; 11]. On the other hand, an interesting promising technique was introduced by [12; 13]: for each missing point in the to-be-inpainted area, a suitable neighborhood of the point is scrolled all over the known image data and the correct value is chosen maximizing a similarity measure between the neighborhood and the known signal (see, e.g., [12; 13; 14; 15; 16; 17; 18; 19; 20]). The quality of the reconstructions by this method is conditioned by the choice of anappropriate similarity measure. Furthermore, despite its conceptual simplicity, this method provides very good results in a relatively affordable execution time [21; 22; 23; 24]. The inpainting procedures based on this idea are referred as \"inpainting-by-patch\" or exemplar-based techniques, see Figure 1.  
In [15], a mathematical formalization describing the behavior of the algorithm introduced in [12; 13] has been provided through a functional, named \"Inpainting Energy\" (\(E_{I}\)). The logic behind \(E_{I}\) is to quantify the difference between a neighborhood of the missing points (reconstructed one by one) and the known part of the signal itself. Another even earlier work (see [25]), following in some sense a similar approach, used the correlation function in place of \(E_{I}\): here the problem was the rigid registration of two similar images and the goal was the maximization of their similarity. However, we will show in Section 3 that the \"deterministic\" \(E_{I}\) hides a strong probabilistic character: it is equivalent to finding, in the given image, which point has the highest probability to match the chosen neighborhood, considering a content-driven, patch-based similarity. Both PDE-based methods and exemplar-based ones have the common goal, hidden by distinct mathematical formulations, to reduce the uncertainty in the choice of the missing points. In the first case, boundary conditions together with constraints on the structure (From here on, when we use the word _structure_, we will refer to the _shape_) of the three dimensional structure of the image function (in effect a surface immersed in a 3D space) and not to the geometry of the isophotes, as is usual in the image inpainting contest.