# Inpainting in Discrete Sobolev Spaces: Structural Information for Uncertainty Reduction
## 3 Neighborhood  
For simplicity of notation, in what follows we do not explicitly indicate the dependency of the energy from \((i,j)\) and \((r,s)\). The new functional \(E_{T}=E_{C_{T}}+E_{S_{T}}\) hides a probabilistic interpretation. To prove this statement, we initially focus on \(E_{C_{T}}\). For each point \((i,j)\in\Omega\), \(E_{C}\) represents the sum of the differences, in modulus, in a domain of size \(\operatorname*{supp}\chi_{i,j}\), between \(\Omega\) and the subset \(T_{S}\in I\setminus\Omega\): the closer this sum is to zero, the higher the probability is to find a correct match. The value of \(E_{C}\) is the sum of the \(d((h,m),(p,q))\) contributions, as expressed in Equation (2). We can normalize each \(d((h,m),(p,q))\) in \(\operatorname*{supp}\chi_{i,j}\) as follows  
\[d_{CNorm}((h,m),(p,q)):=\frac{d((h,m),(p,q))}{(2^{W}-1)}\in[0,1]\]  
such that we can define  
\[E_{P_{C}}((h,m),(p,q)):= \begin{cases}d_{CNorm}((h,m),(p,q))\,\ if\ d\
eq 0\,\\ \varepsilon,\ otherwise\end{cases} \]  
where \(\varepsilon\) is arbitrarily small and \(E_{P_{C}}((h,m),(p,q))\) is the probability to have a match in \(\operatorname*{supp}\chi_{i,j}\). Introducing a scanning order of \(\operatorname*{supp}\chi_{i,j}\), e.g (without loss of generality) the raster scanning, we can write  
\[E_{M_{C}}(i,j):=\prod_{ \begin{subarray}{c}(p,q)\in\operatorname*{supp}\chi_{ i,j}(i,j)\\ (h,m)\in\operatorname*{supp}\chi_{i,j}(r,s)\end{subarray} }\left[1-E_{P_{C}}((h, m),(p,q))\right]. \tag{3}\]  
If \(E_{M_{C}}(i,j)\) is close to one (ideally one for each term of the product) the reconstruction is exact, i.e., without errors of any kind. On the other hand, if \(E_{M_{C}}(i,j)\) is close to zero, the probability to have a correct match is very low. From Equation (3) two conditions follow:  
* a hypothesis of statistical independence is hidden in the formulation;dropping a _at equal to one_ term in the product (3) is equivalent to drop part of the information related to the structure of \(I\). From the previous considerations it follows that the shape and the size of \(\operatorname{supp}\chi_{i,j}\) both determine the quality of the reconstructions. In particular, the second point states that it is not enough to take into account only the two orthogonal principal directions for the reconstruction (as it is usually desiderable in practice), because neglecting a point in \(\operatorname{supp}\chi\) is equivalent to assume to know its value with probability equal to one, i.e., that its value does not condition the outcome (size and shape of the neighborhood change the value of the _confidence_ term introduced in [35]). When the two above conditions, stating an \"ideal\" case, are not respected, the inpainting process does not generally perform correctly, the quality of the results depending on how far from the ideal case the real case is. We stress that \(\operatorname{supp}\chi\) is discriminating for content as it is for structure, but its shape (not necessarily square) and size are not sufficient for a correct reconstruction. In fact, if \(\operatorname{supp}\chi\) is made bigger and \(E_{M_{C}}(i,j)\) stays close to one, we have a high probability of having made the correct choice. The other way around, if \(E_{M_{C}}(i,j)\) decreases when \(\operatorname{supp}\chi\) grows, we have individuated a local similarity that is going to be lost increasing the \"field of view\" (i.e., the \(\operatorname{supp}\chi\)). From the previous consideration comes that the correct choice of \(\operatorname{supp}\chi\) depends on the image content. For what concerns \(E_{S}\), in a similar manner used for \(E_{C}\), it is possible to write  
\[d_{SNorm}(\Delta_{\theta}^{(k)}I(p,q),\Delta_{\theta}^{(k)}I(h,m)):=\frac{d( \Delta_{\theta}^{(k)}I(p,q),\Delta_{\theta}^{(k)}I(h,m))}{2^{k}(2^{W}-1)}\]  
and  
\[E_{P_{S}}((h,m),(p,q)):= \begin{cases}d_{SNorm}(\Delta_{\theta}^{(k)}I(p,q), \Delta_{\theta}^{(k)}I(h,m))\,\text{ if }d\
eq 0,\\ \epsilon,\text{ otherwise}\end{cases}