# Inpainting in Discrete Sobolev Spaces: Structural Information for Uncertainty Reduction
## 2 Functional Formalization
A direction is considered _valid_ if the calculation of the associated finite difference \(\Delta_{\theta}^{(k)}I(p,q)\) does not involve the to-be-inpainted point of coordinates \((i,j)\). In the standard inpaint-by-patch process the value of \(I\) in \((i,j)\) is excluded from the calculation of the pointwise differences: in the same way we excluded it in the finite differences calculation. In Figure 3 an example of the non-valid directions for the calculation of the finite differences of order one is given: the directions highlighted by the black arrows, connecting the red squares with the yellow ones are not valid, being \(I(i,j)\) the unknown. The normalization coefficients are \(R_{k}=8k(\#\Theta_{k}-1)\) with \(\#\Theta_{k}=8k\), where the symbol \(\#\) denotes the cardinality of a set. The maximum order of finite differences \(l\) is chosen accordingly with the size of \(I\) and of \(T_{S}\). The finite differences in the direction \(\theta=0\), from order \(1\) to \(k\), are defined as  
\[\Delta_{0}^{(1)}I(p,q) = I(p,q+1)-I(p,q);\] \[\Delta_{0}^{(2)}I(p,q) = \Delta_{0}^{(1)}\Delta_{0}^{(1)}I(p,q)=I(p,q+2)+I(p,q)-2I(p,q+1);\] \[\widetilde{\Delta}_{0}^{(k)}I(p,q) = \underbrace{\Delta_{0}^{(1)}...\Delta_{0}^{(1)}}_{\text{k times}}I(p,q).\]  
We recall that, being in a discrete case, the finite differences have a local (and not pointwise like the derivatives) character, as evident from the definitions above. The logic paving the definition of \(E_{S_{T}}\) is the same of \(E_{C_{T}}\), except that the functional calculation involves, here, the finite differences for each available direction in the digital image set. For this reason, similarly to \(E_{C_{T}}\), we interpret the functional \(E_{S_{T}}\) as representative of a _structure-associated_ energy, carrying information connected with the structure of the image content. The reason we employ the word \"structure\" stands from the fact that derivatives are representative of the shape, i.e., the \"structure\" of a function. Knowing the tangent to a function in each of its points is equivalent to knowing its structure, the same way the knowledge of an ordinary first order differential equation is effective for the knowledge of the unknown function, given the initial conditions. The _content-related_ term considers the pointwise differences only, while the _structure-associated_ term takes into account of the local variation contribution. Combining \(E_{C_{T}}\) with \(E_{S_{T}}\) in a new functional \(E_{T}:=E_{C_{T}}+E_{S_{T}}\), we can control the contributions related to both the content and the structure in the inpainting process. This combination represents a novelty in the exemplar-based inpainting-by-patch literature. Figure 3: Example of not valid directions for \(k=1\). The red square is the missing point to-be-inpainted, having coordinates \((i,j)\); the grid represents \(\text{supp}\ \chi\) (being \(3\times 3\) in size for finite differences of order one); the arrows, connecting the yellow squares with the red ones, identify the non-valid directions: being centered in the yellow squares it is not possible to calculate the corresponding finite difference of order one because the value of the red square is unknown. It follows that, for each point, 7 directions are valid, and they are identified by the lines connecting the center of the white squares with the center of the red one. Indeed, in this example, \(\Theta_{1}=\{0^{\circ},45^{\circ},90^{\circ},135^{\circ},180^{\circ},225^{ \circ},270^{\circ},315^{\circ}\}\), \(\#\Theta_{1}=8\), \(R_{1}=56\). Being \(E_{C}\) and \(E_{S}\) dimensionally different, the introduction of normalization coefficients \(\beta_{k}\), is needed. The expression of \(E_{S}\) is, then  
\[E_{S}((i,j),(r,s),l):=\sum_{\Lambda}\sum_{k=1}^{l}\frac{\beta_{k}}{R_{k}}\sum_{ \theta\in\Theta_{k}}d(\Delta_{\theta}^{(k)}I(p,q),\Delta_{\theta}^{(k)}I(h,k)),\]  
with \(\beta_{k}\in\mathbb{R}\) (their values will be calculated in Section 3).