# Inpainting in Discrete Sobolev Spaces: Structural Information for Uncertainty Reduction
## 4 Causality  
In signal theory, a system is defined to be _causal_ if and only if the values of its output depend only on the present and past values of the input [41]. In the inpainting case, we state that the minimization of \(E_{T}\) is meaningful if and only if \(\text{supp}\,\chi\) guarantees the causality condition, i.e., if the calculation of \(E_{T}\) is performed including only known points. If this does not happen, the values calculated, let us say in \((i,j+1)\) in Figure 6, modifies the previously calculated ones (\((i,j)\) in the same figure), whose number and position both depend on the size and shape of \(\text{supp}\,\chi\). The inpainting energy \(E_{T}\) changes with time (the points of \(\Omega\) are inpainted sequentially), such that the presence of unknown values for its calculation introduces loops in the system (feedback), making the minimization effectively not computable. Moreover, we remark that, in general  
\[\min_{(r,s)\in T_{S}}\sum_{(i,j)\in\Omega}E_{C}((i,j),(r,s))\
eq\sum_{(i,j) \in\Omega}\min_{(r,s)\in T_{S}}E_{C}((i,j),(r,s))\,.\]  
Figure 4: A square wave signal, with values in the range \([0,1]\), represents the normalized signal with the highest amount of variation, whose maximum value is equal to \(1\,(=2^{0})\) (first figure on the left). We assume the values \(0\) and \(1\) to be respectively the minimum and the full scale of the measurement instrument. Performing the calculation of the finite difference of first order (second figure from the left) the range of variation expands to \(2=2^{1}\) and so on, proceeding exponentially with the differentiation (last two figures on the right, relative to the second and third order finite differences, respectively). Figure 5: On the left, the trend of the number \(N_{E_{T}}\) of patches having the same minimum value for \(E_{T}\) when varying the size (side in pixels) of \(\text{supp}\,\chi\) on the right the trustability \(C\,(=1-U,\) where \(U\) is the uncertainty) in the choice of the available patches when varying \(\text{supp}\,\chi\). The blue line is relative to the use of \(E_{C_{T}}\) only, the red line gives reason for the introduction of \(E_{S_{T}}\) (first order differences term in red, both first and second order difference terms in yellow). In particular, the closer \(C\) is to one, the better the choice of the value for the reconstruction tends to be; on the contrary, the lower the number of candidate points is, the better the discrimination between different patches will be. In the right figure, \(C\) (blue line) increases with the size of \(\text{supp}\,\chi\) while tending to decrease when the number of available patches in the image becomes too small (right side of the graph on the right). To the best of our knowledge, the previous inequality has been completely ignored by the existing exemplar-based inpainting-by-patch methods, in which the minimization is operated tacitly turning it to an equality (see, e.g., [15]). Another novelty of our work is, in fact, in the inclusion of this aspect of crucial importance in the inpainting dynamic. The procedure described, e.g., in [13], is an example of an algorithm that does not take into account the causality and, to achieve convergence, sets random initial conditions in \(\Omega\). Even if a convergence is reached, this way of proceeding has two main drawbacks:  
* the inpainted result is not always the same, because it depends on the random initial conditions;
* if in \(T_{S}\) the missing area is given, such that we expect to find a perfect match for \(\Omega\) (i.e., \(E_{T}=0\;\forall\;(i,j)\in\Omega\)), the inpainting procedure does not generally reconstruct it as expected. The missing of the causality condition is a source of uncertainty and its respect is needed to reduce the inpainting error.