# Inpainting in Discrete Sobolev Spaces: Structural Information for Uncertainty Reduction
## 2 Functional Formalization  
Working with a W-bits coded image function \(I\), of size \(M\times N\) ( \(M\) rows, \(N\) columns), containing the area \(\Omega\) to be inpainted (see Figure 2), we consider a function \(\chi:[1,2L+1]^{2}\subset\mathbb{N}^{2}\to[0,2^{W}-1)\) (\(L\in\mathbb{N}\) determines the size of the square (Without loss of generality, the \(\operatorname{supp}\chi\) is assumed to be square. In the experimental part we will use also non-square-shaped neighborhoods.) \(\operatorname{supp}\chi\)), that, centered in the generic point \((i,j)\) of \(I\), is defined as  
\[\chi_{i,j}:=\chi(i+a,j+b)=I(i+a,j+b)\]  
with \(a=\{-L,-L+1,\ldots,L-1,L\}\), \(b=\{-L,-L+1,\ldots,L-1,L\}\), \(i\in[L+1,M-L]\) and \(j\in[L+1,N-L]\) (We assume the first element of a matrix to be at coordinates (1,1)). We will refer to \(\operatorname{supp}\chi\) in the following as the neighborhood of the point to be inpainted (see blue square in Figure 2 again). The choice as of a square-shaped support for \(\chi\), with an odd value for its dimensions, simplifies the mathematical notation without loss of generality (On the contrary, this aspect must be taken into account in the numerical implementation). We will see in Section 3 how the shape and size of \(\chi\) (i.e., value of \(L\)) is fundamental for the correct reconstruction of \(\Omega\). We outline the inpainting task in three main sub problems:  
1. Identifying the best _content-driven_ solutions;
2. Identifying the best _structure-driven_ solutions;
3. Inpainting using the best possible value, resulting from the combination of the best fits individuated in the two previous steps. In general, it is possible to define a pointwise distance function between two points of coordinates \((i,j)\) and \((h,m)\) in \(I\) as  
\[d(I(i,j),I(h,m)):=||I(i,j)-I(h,m)||\, \tag{1}\]  
where \(||\,.\,||\) is a generic norm. Using a similar approach as the one described in [15], the best _content-driven_ correspondence for \(\Omega\) is related to the minimization of the functional  
\[E_{C_{T}}(r,s):=\sum_{(i,j)\in\Omega}E_{C}((i,j),(r,s)),\]  
where, given a point of coordinates \((r,s)\in I\setminus\Omega\), \(E_{C}((i,j),(r,s))\) is defined as  
\[E_{C}((i,j),(r,s)):=\sum_{ \begin{subarray}{c}(p,q)\in\operatorname{supp}\chi _{i}\setminus(i,j)\\ (h,m)\in\operatorname{supp}\chi_{\kappa}\setminus(r,s)\end{subarray} }d(I(p,q),I(h,m)). \tag{2}\]  
The coordinates \((r,s)\) varies in a suitable subset \(T_{S}\subset I\setminus\Omega\), such that the above sum is well defined without the introduction of further boundary conditions (e.g., red zone in Figure 2). In Equation (1), the \(||\,.\,||_{2}\) norm, originally used in [15], has been replaced by a generic norm \(||\,.\,||\). We will explicit this norm in the following. To the light of the previous consideration, the functional \(E_{C_{T}}\) represents a sort of _content-related_ energy: it is the amount of error one commits comparing two patches having same support, equal to \(\operatorname{supp}\chi\). In a fashion similar to the one used to formalize \(E_{C_{T}}\), we introduce a new _structure-driven_ functional, defined as follows  
\[E_{S_{T}}((r,s),l):=\sum_{(i,j)\in\Omega}E_{S}((i,j),(r,s),l),\]  
where  
\[E_{S}((i,j),(r,s),l):=\sum_{\Lambda}\sum_{k=1}^{l}\frac{1}{R_{k}}\sum_{\theta \in\Theta_{k}}d(\Delta_{\theta}^{(k)}I(p,q),\Delta_{\theta}^{(k)}I(h,k)),\]  
Figure 2: On the left the image \(I\) containing the to-be-inpainted area \(\Omega\); in the center, the neighborhood \(\chi\) in blue, centered in the top-left point to be inpainted; on the right, the red line represents the set \(T_{S}\) of points for which \(E_{C_{T}}\) is well defined. In the above equation, \(k\) is the order of the finite differences \(\Delta_{\theta}^{(k)}I(p,q)\) and \(\theta\) is their orientation, given the set \(\Theta_{k}\) of all the available and _valid_ orientations in the considered discrete set.