{'fraction_non_alphanumeric': 0.03592249181056021, 'fraction_numerical': 0.010438065626561546, 'mean_word_length': 4.59016139044072, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A nonlocal feature-driven exemplar-based approach for image inpainting

We present a nonlocal variational image completion technique which admits simultaneous inpainting of multiple structures and textures in a unified framework. The recovery of geometric structures is achieved by using general convolution operators as a measure of behavior within an image. These are combined with a nonlocal exemplar-based approach to exploit the self-similarity of an image in the selected feature domains and to ensure the inpainting of textures. We also introduce an anisotropic patch distance metric to allow for better control of the feature selection within an image and present a nonlocal energy functional based on this metric. Finally, we derive an optimization algorithm for the proposed variational model and examine its validity experimentally with various test images.


Introduction
Inpainting is a process through which lost, deteriorated, or undesirable portions of images and videos may be replaced with a visually plausible interpolation. The applications are plentiful and inpainting is an active area of research in image processing. The majority of image inpainting methods can be categorized into two groups: geometry-oriented and texture-oriented.
In geometry-oriented inpainting, such as in [3,15,25,26], some regularity in a functional representation of the image is assumed. The inpainting takes place by interpolating from the boundary of the inpainting region with the regularity assumptions imposed on the image. This is typically accomplished by solving a boundaryvalue partial differential equation, where the boundary is the set of pixels immediately surrounding the inpainting region and the solution domain is the inpainting region. These methods have been quite successful when the inpainting region is small, such as when removing scratches, text, or minor blemishes [4,25]. Geometric objects such as curves have also been successfully propagated into the inpainting region in numerous works, e.g. [26,8]. Due to the fact that typically only the region immediately surrounding the inpainting region is utilized to inform the inpainting algorithm in geometryoriented methods, often times a large portion of the information in the intact section of the image is not utilized.
Alternatively, in many texture-oriented methods, the goal is to exploit the self-similarity inherent in many images. The value at a pixel in the inpainting region is typically determined by comparing the neighborhood around the pixel, often called a patch, and the neighborhoods of pixels in the intact/desirable region of the image. When the patches are determined to be similar through some criterion, the pixel in the inpainting region is assigned characteristics from pixels in the intact/desirable region of the image. These approaches are often referred to as exemplar-based methods and nonlocality is an intrinsic property. There has been extensive study into such models such as in [13,1]. Exemplarbased methods are celebrated for their ability to recover textures and repetitive structures; however, recreating geometry when a specific example of the structure is not in the known image is limited and not well-understood [1].
A synthesis of these two paradigms has been considered in multiple works such as [8,1]; however, many such algorithms are driven by similarities in pixel magnitudes rather than underlying features. Many images have self-similarity in features that would be ignored by an inpainting technique that focused solely on differences in pixel color. For example, in an image with a black cat and a white cat, one could utilize the selfsimilarity in structure and texture in one cat to reconstruct a region missing from the other cat. In the continuum framework, derivatives are the tools necessary to measure and understand function behavior. When discontinuous or discrete systems are considered such as in images and data sets, classical derivatives are not well-defined; however, generalizations of such operations exist in the form of nonlocal operators [11,19]. Much like their local counterparts, the nonlocal operators can provide measures of structure and texture on discontinuous or discrete domains. In this work we utilize general nonlocal operators to explore a method of exemplar-based inpainting executed in selected feature domains.
Introducing nonlocal operators into the image processing field has been immensely successful, e.g. nonlocal total variation [13] and nonlocal means [6]; however, even in these seminal works, similarity comparisons between patches is largely dependent on color or intensity differences rather than true textural and structural differences. As a potential remedy, in [1] a framework capable of considering structural and textural differences was developed. Their method is a generalization of the method proposed in [13], although their method was a marked improvement as it did not require a priori determining which pixels were self-similar. In addition, rather than solely considering patch differences based entirely on pixel color/intensity, patch differences dependent on the gradient of the image were additionally utilized. In this work we delve further into this framework and consider a general convolution operator which allows us to focus on the types of distinguishing features we wish to utilize in the inpainting process.
The organization of this paper is as follows. In Section 2 we formulate the image inpainting problem and review various inspirational works for the model developed in this paper. In Section 3 we present our model as well as an algorithm with which it may be solved. We continue in Section 4 with examples of our model applied to various damaged images. We conclude our discussion with Section 5.
2 Problem formulation and related works.
In this section we formalize the image inpainting problem and review several inspirational works for the model developed in this paper.
We begin by defining Ω ⊂ R 2 to be an image domain on which we define a functionû : Ω → [0, 1], corresponding to the initial image 1 . In the inpainting problem, one typically desires to provide a plausible replacement ofû on an unknown or undesirable region, O ⊂ Ω, of an image. We refer to O as the inpainting region of the image defined on Ω. Filling in the inpainting region is most certainly an ill-posed problem as there are typically multiple plausible ways to fill in the missing region. For example, in Figure 1, a region containing the entire chair is removed from the image and one could inpaint the unknown/removed region with a chair with any number of color possibilities or even with no chair at all. Consequently, the goal of inpainting is not a true recovery of the inpainting region, but rather to produce a satisfactory replacement. More precisely, the inpainting problem is to elicit a function u : Ω → [0, 1] such that u ≈û for x ∈ O c = Ω\O, and u assumes values within the inpainting region O which attains a "reasonable" replacement ofû.
While there are a multitude of methods for inpainting, variational frameworks are particularly popular, e.g., [1,3,12,15,17,20,25]. In many variational frameworks, the solution u to the inpainting problem is obtained through the minimization of some functional E[u] over an appropriate admissibility set U . Various models are distinguished by the form of the functional E[u] and the admissibility set U . In order to lend credibility to the model proposed in this work as well as acknowledge several inspirational works, we now review several well-known variational models.  Local Approaches: In local variational approaches, some regularity in the functional representation of the image is assumed. In these approaches, global features and pattern recognition are not utilized. These methods tend to perform well when structure needs to be diffused into the region; however, they fail to take into account symmetry, such as mirror symmetry in a face, and repetitive features, such as patterns in fabric, within an image. It is well known that these local approaches are typically more successful when the inpainting region is small or the region to be recovered is sufficiently regular, but fail to recover texture [8].
Local total variation: In [25] a PDE inpainting procedure, often referred to as the TV inpainting algorithm, was developed based on the popular total variation (TV) denoising algorithm of Rudin, Osher, and Fatemi (the ROF Model) [24]. In the total variation inpainting model, they introduce a collar domain E about the inpainting region O such that E ⊂ O c and ∂O is contained in the interior of O ∪ E. The functional proposed in [25] is where λ > 0 is a scaling constant andû is the observed data from the initial image. The functional E[u] is minimized over the admissibility set U = BV (O ∪ E), i.e., the set of functions of bounded variation on O ∪ E. The û − u 2 L 2 (E) term is sometimes referred to as a fidelity term and prevents the recovered image from diverging too significantly from the initial image in the desirable/intact region E. Under the minimization of (1), the ∇u L 1 (O∪E) term will reduce the total variation over the region O ∪ E and consequently diffuses structure into the inpainting region O from the region E. The local total variation inpainting model is computationally inexpensive, but suffers from various shortcomings such as the production of artifacts like staircasing. In an attempt to mitigate or eliminate these artifacs, several higher-order models were developed, e.g. [5,7,22,26].
Local first and second-order total variation: In [22] a higher-order generalization of the local total variation model (1) was proposed. As in the total variation model, a collar domain E about the inpainting region O is utilized. The proposed functional in [22] is where α and β are non-negative regularization parameters, and f and g are convex nonnegative functions with at most linear growth at infinity. The functional (2) is minimized over the space of bounded Hessian BH(Ω). If one takes β = 0 and f = | · |, then (2) reduces to (1). As was demonstrated in [21,22], introducing higherorder terms alleviates the staircasing effect produced by the local total variation model. The associated cost of these improvements is some blurring, which can be controlled to some extent by the parameter β, as well as increased computational cost. As mentioned previously, local variational approaches tend to be most successful when the inpainting region is thin or small. When the impainting region is larger or texture recovery is important, so-called nonlocal approaches often offer superior performance.
Nonlocal Approaches: In nonlocal variational approaches, rather than just propagating structure into the inpainting region through regularity restrictions, global features and pattern recognition are often exploited. In order to take advantage of repetitive features such as texture about a point, the neighborhood of a point, often called a patch, is utilized. To formalize the concept of patches, let P be the rectangle centered at (0, 0) with side lengths s 1 and s 2 , i.e., We define the patch of u about the point x as p u (x) := u (x + P) , where x + P = {x + y : y ∈ P} denotes the Minkowski summation. Nonlocal models view an image u as a manifold M u embedded in the space of all patches of u, {p[u](x) : x ∈ Ω}. Nonlocal methods frequently take advantage of the low dimensionality inherent in the patch manifold [20]. Discrete representations of patch manifolds are often interpreted as weighted graphs and the choice of a weighting function determines the flow of information from the known to the unknown regions of the image. Nonlocal total variation: A nonlocal variant of the local total variation inpainting model was introduced in [13]. In this method, given an initial imageû defined on the domain Ω and an inpainting region O ⊂ Ω, a nonlocal gradient is employed as a regularization term instead of the local derivatives in (1). In the the nonlocal total variation framework, both isotropic and anisotropic functionals are considered: respectively. The weighting function w(x, y) in (4) is given by where for a given n, A n (x) is the set of n nearest neighbors of x in a weighted patch distance metric d[û](x, ·) based on the initial imageû: with dP(h) exp − h 2 2 dh. In this formulation, the weighting function w(x, y) = 1 when the patches around x and y are more similar and w(x, y) = 0 when the patches around x and y are less similar. Consequently, under the minimization of the functional E[u] in (4a) or (4b), the regularization term (the first term in (4a) or (4b)) will cause u(y) and u(x) to be more similar when their corresponding patches are similar with respect to (5). The second term in (4a) or (4b) is the fidelity term which forces the recovered image u to be close to the initial imageû in the complement of the inpainting region, O c . One of the most serious critiques of this model is that the weighting function w(x, y) is not adaptive and so the inpainting algorithm requires one to a priori know the weighting function w before minimizing the functional. This is a significant drawback when the inpainting region covers a considerable portion of the neighborhood of a pixel.
Correspondence map: Early examples of adaptivity in the weighting function can be found in correspondence map inpainting models. In these models, a correspondence map Γ : O → Ω\O is determined for each pixel x in the inpainting region. Then the corresponding image value u(x) is assigned the image value of the pixel x is mapped to under the correspondence map, i.e., u(x) =û (Γ (x)). An early correspondence map inpainting model was proposed in [9] where they introduced the functional Unfortunately, (6) is highly non-convex and cannot be minimized easily [2]. In order to overcome this obstacle, in [27] a relaxed variant of (6) was produced by adding the unknown image u to the functional: whereÕ := O + P = {x ∈ Ω : (x + P) ∩ O = ∅} is the set of pixels whose corresponding patches intersect the inpainting domain O.
Adaptive weight graph-based regularization: A generalization of the nonlocal total variation model which employs adaptive weighting was introduced in [23]. This model tackled the issue of assigning weights between pixels when one or both of the corresponding patches intersects the inpainting region. In addition to the novelty of an adaptive weighting scheme, the model also regularizes on patches rather than on pixels; this consideration improves convergence properties and stability within their proposed algorithm. The functional proposed in [23] is and the adaptive weighting function w u (x, y) described by Since these weights are functions of the optimal solution u, the algorithm is adaptive to the image content. By introducing adaptive weights, the nonlocal functional (8) is nonconvex in u and is more expensive and challenging to minimize than the nonlocal total variation function (4). However, the resulting optimization problem can be solved by the alternating minimization technique described in Algorithm 1.
Higher-order adaptive graph-based regularization: The final model we review was proposed in [1], wherein a variational framework which employs higher-order graph regularization techniques was introduced by means of the functional

subject to
Õc w(x, y)dy = 1, whereÕ := O + P and d[u, ∇u](x, y) is a higher-order weighted patch distance metric given by with r, q ∈ {1, 2} and λ ∈ [0, 1]. Unlike several of the previous models, (9) does not employ a fidelity term. Rather, the model relies on the entropy term which was justified in [1] by appealing to the principle of maximum entropy [14]. In order to determine the form of the weighting function w(x, y), the function u is held fixed and (9) is minimized in w(x, y). The resulting Algorithm 2 Gradient based exemplar inpainting Solve the boundary-value problem weighting function is a probability distribution overÕ c given by Here σ is a parameter which controls the quantity of patches considered in the comparison. With the weighting function described by (11), the functional (9) is a generalization of the adaptive weight graph-based regularization functional (8). The parameter σ in (11) determines the selectivity of the weights. When σ → ∞, the weighting function w(x, y) tends to the uniform distribution overÕ c . Alternatively, when σ → 0, the weighting function w(x, y) tends to Dirac deltas and the functional in (9) is a direct generalization of (7). In order to minimize the functional (9) with weighting function (11), an iterative approach of alternating between the updating of u and w(x, y) may be utilized. This process is illustrated in Algorithm 2. The model in [1] has two main novelties. The first novelty is the justification of the exponential form of the adaptive weighting function (11) through the entropy term in (9). The second novelty is the functional in (9) involves gradient terms which produces two benefits. The first is smoother continuation of information across the boundary of the inpainting region. The second benefit is the introduction of gradient terms allows filtration of additive differences in brightness from the patch difference metric (10). This allows less emphasis to be placed on differences in color or intensity when comparing patches.

Our approach
One of the contributions of this work is the introduction of a model which permits simultaneous utilization of multiple features to guide the inpainting procedure. The proposed model is a generalization of many of the frameworks described in Section 2. We begin with the introduction of a generalized patch distance metric based on general convolution operators: where each g i is a kernel of a scalar-valued convolution operator, which we henceforth refer to as a filter, that determines the feature(s) of interest, and λ i (x) determines the degree of dominance of the filter g i at a pixel x. If the feature(s) described by g i are similar (dissimilar) between two patches at x and y, then the metric described by (12) is small (large). Note that the distance metric (12) is a direct generalization of (10) with r = q = 2. As opposed to the models discussed in Section 2, by employing the more general formulation in (12), the similarity comparison can depend on multiple targeted features. Similarly to (9), we extend the inpainting domain O so that only information from pixels outside the inpainting region is utilized to determine values of pixels in the inpainting region. To accomplish this, we first define the subset O * of Ω such that for every element y in the complement O c * = Ω\O * , the convolution (g i * u)(y) is determined entirely by pixels outside the inpainting region 2 : In addition, we extend O * to the subsetÕ * of Ω such that for every element y in the complementÕ c * = Ω\Õ * , the patch about y is a subset of O c * (cf.(3)): 2 Note that this places limitations on the support of g i if there is to be any region that is completely determined by pixels outside the inpainting region.   (14) is that for each y ∈Õ c * and h ∈ P, the quantity (g i * u)(y + h) is calculated entirely on O c , the complement of the inpainting region. Consequently, restricting y to the set O c * in (12) ensures that structure at x is only compared to information in the complement of the inpainting region O c . Now one can define the inpainting model by the analogy with (9) using the modified distance metric in (12). Instead, we extend this definition by introducing auxiliary graphs in the selected feature domains with the corresponding weights and distance metrics given by and Note that we permit differences in patch shapes between various features.
With the introduced modifications, the proposed functional takes the form The coefficients β j (x) above define partial contributions of the selected feature graphs at each x. Figure 3 gives an example of a possible selection of these coefficients in the case of two features.
In order to minimize the functional (16), we employ an iterative approach of alternating between the updating of u and w(x, y). This approach is inspired by Algorithms 1 and 2 which appear in [23] and [1], respectively. Before we present our algorithm, we first explore the weight and image update steps individually. We begin with the weight updating step.

Updating weights
When the image u is held fixed, updating the weights is relatively simple. In practice it is convenient to set σ j → 0 in (15), in which case the weights tend to delta distributions or more precisely where N N F j (x) is the nearest neighbor field ofÕ * , i.e.,

Updating image
In this section we derive the image update equation appearing in Algorithm 3. We begin with the expanded form of the functional (16): In addition, sinceẑ − h ∈Õ c * impliesẑ ∈ O c * by (14), we may reduce the limits of integration inẑ to O c * : Next we notice the integral is constant in the image update step 3 . To see this we simply note that by (13), we have forẑ, z ∈ O c * that g i * (u(ẑ) − u(z)) is informed entirely by the region O c and therefore unchanged in the image update step. Consequently, a minimizer of (18) is also a minimizer of the functional (19) and (18) only differ by a constant. Before we continue our derivation, we introduce the following auxiliary functions: Note that using the weight function in (17), we get since m j (z,ẑ) = 0 otherwise. Forẑ ∈ O c * , we know (g i * u)(ẑ) is entirely dependent on O c . Also recall the weighting functions w j are treated as constant in the image update step. Consequently, m j (z,ẑ), k j (z), and f j i (z) are constant in the image update step. Hence, by expanding the quadratic term and regrouping appropriately, the functional (19) can be simplified as   Hence the minimizer of (19) is also a minimizer of the functional Now that we have determined minimizers of (16) in the image update step are minimizers of (20), we will simply deal with (20) for the remainder of the derivation. In order to minimize (20), we consider its first variation. Since u is constant in O c , in the calculation of the first variation of (20) we consider a function v(z) which is identically zero in O c . We find where g i (t) = g i (−t) is the kernel of the adjoint convolution operator. We used the fact that v(z) = 0 for z ∈ O c for the third equality in (21) and for the fourth equality in (21) we used (13) and the fact that supp(g i ) = supp(g i ) since g i has symmetric support. Hence, the Euler-Lagrange equations take the form of the nonlocal boundary value problem with Dirichlet boundary The well-posedness of this boundary value problem (22) depends on the properties of the convolution operators in (22). Without loss of generality, we suppose g 1 (t) = δ(t). This term acts as a classical Tikhonov regularizer and the existence and uniqueness of the solution to (22) can be guaranteed. In fact, for simple cases it is even possible to obtain an analytic solution to (22). For example, when N g = 1, λ 1j (x) = λ j (x) and λ ij = 0 for i = 1, we find u on the inpainting domain is given by With the weights in (17), the above expression can be simplified to One can view the solution (23) as a result of applying to the image a cleverly designed nonlinear filter. In this regard, it can also be considered as a generalization of the patch nonlocal means filter proposed in [1].
The discretization of the system in (22) is obtained trivially by replacing all integrals with sums and all continuous convolutions with their discrete analogs. Algorithm 3 provides the details of the proposed inpainting technique.

Algorithm 3 Feature driven exemplar inpainting
1: function UpdateWeights(u k ) 2: for j ∈ #f eatures do 3: for x ∈Õ * , y ∈Õ c * do 4: Evaluate the patch distance d j [u, g](x, y) as Evaluate the auxiliary functions   are disjointly located in the parts of the image with the opposite intensity. We employ the following kernels and their adjoints One can recognize g 1 as the identity map while (g ∇x , g ∇y ) and g ∆ correspond to the finite difference stencils of the image gradient and image Laplacian respectively. For the given patch P, we consider patch weights as probability measures of the form such that P dP(h) = 1. We also take a single feature graph so that N β = 1 and β(x) := 1 in (16) and set all λ i to be constants. With this choice, we get k(z) = P dP(h) = 1, ∀z and the boundary value problem (22) simplifies to To better illustrate the impact of the choice of the convolutional filters g i on the result of the inpainting procedure, we start with the trivial step image in Figure 9a initialized with random noise. We choose a 15 × 15 patch with σ = 10 and consider three different cases. In the first case, we set λ 1 = 1 and λ i = 0, i = 1; this leads to the following image update step which simply assigns the value of each pixel x based on the "votes" of the nearest neighbors of the pixels in the patch around x. The result is presented in Figure 9b. One can see that the algorithm is capable of the exact recovery of the constant image intensity in the regions where all pixels in the patch around x have nearest neighbors in either left or right parts of the image. The smooth transition between constant regions happens in the band whose width coincides with the size of the patch.
For the second case we set λ ∇x = λ ∇y = 1 and λ i = 0 otherwise; this choice gives As a result, we get the following homogeneous boundary value problem The direct substitution shows which is nothing but the finite difference approximation of the Dirichlet problem for the Laplace equation. The produced result is shown in Figure 9c and is identical to the standard harmonic image extension [10]. Analogously, the standard local biharmonic inpainting corresponds to the choice of g ∆ as the convolutional kernel which gives i.e., the finite difference approximation of the biharmonic differential operator. Figure 9d presents the corresponding result. It is clear that the results of the harmonic and biharmonic inpainting schemes are completely specified by the known values of the image at the boundary of the inpainting domain and do not depend on the provided initialization as opposed to the nonlocal methods. The benefits of the nonlocal approach become apparent when considering textured images. One can see from Figure 9e that the local scheme fails to recover the original image structure while the same operator equation with the nonlocal forcing term i λ i (g i * f i )(x) produces the desirable result.
It is worth noting that the inpainting schemes based on the convolutions g 1 and g ∇ = (g ∇x , g ∇y ) can be viewed as the particular implementations of the patch nonlocal means and the patch nonlocal Poisson methods proposed earlier in [1]. The proposed framework is hence more general and extends capabilities of the algorithm in [1]. The presented case of the biharmonic inpainting based on the convolution g ∆ is the most obvious such extension. The nonlocal variants of the above operators can be also considered. For example, the nonlocal gradient and divergence operators are defined as follows [13] ∇ γ u(x, y) = u(y) − u(x) γ(x, y), where γ(x, y) is a symmetric kernel with a support on a patch K centered at x. The nonlocal Laplacian operator is then defined as The discrete versions of these operators can be easily written as convolutions. For example, the corresponding kernels of the nonlocal gradient over the 3 × 3 patch K have the form and the kernel of the discrete nonlocal Laplacian is defined respectively as The choice of nonlocal kernels instead of local ones might provide new insights into the design of exemplarbased algorithms. While the idea of embedding images into higher dimensional space of patches allows for the exploration of self-similarity of their local properties globally within the image, nonlocal operators can provide a self-contained similarity measure which makes such embeddings unnecessary. For example, a nonlocal gradient g γ measures variation of the weighted image intensity in a neighbourhood of each pixel similarly to the original patch distance metric (12). Indeed, by taking dP(h) = γ 2 (h)dh, h ∈ P, the discrete version of (12) corresponding to the nonlocal means method reads as while for h ∈ K we can write the distance metric for the nonlocal gradient as Obviously, when u(x) = u(y), these metrics are equivalent; also note that this condition can be forced by taking with a sufficiently large α.
When using nonlocal gradients, a patch P can be collapsed into a single pixel and the Euler-Lagrange equation (22) takes the simpler form with f ij (z) = β j (z) · (g i * u) N N F j (z) . We will refer to this algorithm as a nonlocal γ-Poisson method. Despite the similarity of utilized metrics, it has different properties than the nonlocal means method. For example, it is well known that solutions of the twodimensional nonlocal Laplace equation are in H s , i.e., the fractional Sobolev space of order s [11]. Larger values of s, which correspond to more localized kernels, lead to the smoother interpolation as can be seen from Figure 10. Smaller values of s put more weight on distant pixels instead. While resulting in less smooth  Example 2. To illustrate the performance of the algorithms in Example 1 in application to the real image, we consider a fragment of the famous painting by Georges Seurat depicted in Figure 5. The selected fragment is 500 × 500 pixels in size and contains both geometric structures and textured regions. Figure 12 shows the results of the inpainting procedure for the nonlocal means (g 1 ), nonlocal Poisson (g ∇ ) and nonlocal γ-Poisson (g γ ) methods. To make the comparison meaningful, we used 15 × 15 Gaussian patch weights for the nonlocal means and Poisson methods and chose equivalent Gaussian kernels γ(x, y) of the same size for the γ-Poisson method. To initialize the algorithms, we downscaled the original image by a factor of four and then upascaled it to the original size. This choice provides a rough hint on the large-scale geometric features of the original image and can be considered as an idealized case of the multi-level initialization strategy [16].
As expected, the nonlocal means algorithm is the best at interpolating image texture and less successful at interpolating non-trivial geometric structures. At the same time, the nonlocal Poisson method leads to the overly smoothed solution and completely fails at reconstructing edges-like structures. However, such behavior is common for highly textured images as the gradients are distributed nearly uniformly in the vicinity of each pixel and hence their "patch averaged" values do not contain useful information. Finally, the nonlocal γ-Poisson method results in the smooth transition of intensities as well but with much better resolution of geometry and colors. It should be noticed that the  solutions corresponding to less localized kernels are less smooth and hence more accurate as was also expected.
Example 3. The aim of this example is to demonstrate capabilities of the algorithm in reconstructing geometric structures. Figure 6 shows the setup of Example 3; one can see that the image is almost cartoon-like with only a few textured regions. Following terminology of the previous examples, convolutional kernels g ∇x , g ∇y representing gradient of the image seem to be a natural choice in this case. When λ ∇x = λ ∇y = 1, the image update step of the algorithm is thus given by the Dirichlet problem for the Poisson equation with a nonlocal forcing term. Figure 13a illustrates the obtained result along with the classical harmonic extension. It is clear that the nonlocal approach leads to better propagation of edges across small holes (e.g., missing edges of a table or the wall over the printer) but still performs far from perfect in larger regions (e.g., the windows) and regions with structures not present elsewhere in the image (e.g., the printer). In order to improve the result, we can supplement the algorithm with a hint in the form of the edge completion E(x) in Figure 13c. This permits the consideration of a nonlocal patch distance metric (12) with anisotropic coefficient where λ a is the "asymptotic" value of λ(x), τ is the corresponding relaxation time and DT (E(x)) is the distance transform of the binary edge map E(x). The Euler-Lagrange equation (22) in this case describes an anisotropic diffusion with λ(x) controlling the intensity of diffusion within the image. Figure 13d shows the results of the local and nonlocal inpaintings using this approach. Both methods are successful but it is noticeable that the nonlocal technique produces crisper edges and more natural colors. The distinction is much more apparent for textured images like the one in Figure 11. For the sake of comparison, we have also considered inpainting with the state-of-the-art generative adversarial network proposed in [18]. All results in Figures  13b-13d use the same edge completion in Figure 13c and show superiority of the proposed nonlocal method for the given image.
Example 4. Our final example demonstrates flexibility of the proposed algorithm in controlling its behavior. For this purpose, consider the image in Figure 7 and its inpainting in Figure 8 obtained with a multiscale initialization strategy using a 15 × 15 Gaussian patch with σ = 5. This result is by all means not new and will be used solely as a reference to compare against. As a first improvement attempt, we enforce the edge completion and calculate the anisotropic coefficient λ ∇ (x) in (26) with λ a = 0.1 and τ = 20. Figure 14a shows this procedure along with the local and nonlocal inpainting results illustrating relative success of the method. While the desired geometry is resolved much better in comparison to standard methods in Figure 8, interpolation of the textured regions (grass and water) is not quite acceptable.
To improve the result even further, we separate inpainting regions as shown in Figure 14b and set λ 1 = 1, λ ∇ = 0 in the light blue region. As one can see, this leads to a better resolution of textures as desired. Next, to improve the resolution of geometry in region 1, we completely separate the feature graphs of the red and blue regions and set σ = 10 for the patch weight in region 1. Figure 14c illustrates the final result for two different combinations of selected features. In our opinion, the proposed technique provides an appealing solution to the inpainting problem.

Conclusion
In this work we presented an image inpainting model which is free to depend on a variety of features. The model is capable of propagating structure within the inpainting region as well as exploiting self-similarity in intact portions of the image to recover texture. The obtained numerical results support our findings and illustrate superiority of the proposed technique in comparison to similar methods.
We see several opportunities for potential improvements of the presented model. For example, we derived the anisotropic coefficient in the patch distance metric (12) using manual edge completion. It is interesting to explore automated techniques for edge reconstruction.    Second, the metric (12) is quadratic. It is known that TV like formulations are more natural for images and lead to sharper transition regions. Finally, the inclusion of convolutions into the metric (12) results in a boundary value problem for the unknown parts of the image. The well-posedness of such problems should be also analyzed. We would also like to consider more general (potentially nonlinear)ar operators in addition to convolutions. We intend to study these questions in our future works.      12: Inpainting of the image in Example 2 with nonlocal means (g 1 ), nonlocal Poisson (g ∇ ) and nonlocal γ-Poisson (g γ ) methods using three different Gaussian weights (σ = 5, 10, ∞) for the patches P and kernels K.