# Image Completion with Hybrid Interpolation in Tensor Representation
## 3 Proposed Algorithm
\begin{array}{cc}\mathbf{F}(\tilde{\mathbf{\omega}}, \mathbf{\omega})&\mathbf{P}(\tilde{\mathbf{\omega}},:)\\ \mathbf{P}(\mathbf{\omega},:)^{T}&\mathbf{0}\end{array} \right]\left[ \begin{array}{c}\mathbf{w }(\mathbf{\omega})\\ \mathbf{c}\end{array} \right], \tag{20}\]  
where \(\mathbf{F}(\tilde{\mathbf{\omega}},\mathbf{\omega})\in\mathbb{R}^{|\Omega|\times|\Omega|}\) is obtained from \(\mathbf{F}\) by removing the rows and selecting the columns that are indexed by \(\Omega\), and the vector \(\bar{\mathbf{y}}=\mathbf{y}(\tilde{\mathbf{\omega}})\) contains the estimates for the missing entries in \(\mathcal{M}\). Hence, the completed image is expressed by  
\[\mathcal{Y}=[y_{i_{1},\ldots,i_{N}}],\quad\text{where}\quad y_{i_{1},\ldots,i_{N }}=\left\{ \begin{array}{cc}m_{i_{1},\ldots,i_{N}}&\text{if}&\omega_{i_{1}, \ldots,i_{N}}=1,\\ \tilde{y}_{i_{1},\ldots,i_{N}}&\text{otherwise}\end{array} \right. \tag{21}\]  
The system matrix in (19) has the order of \(|\Omega|+\prod_{n=1}^{N}R_{n}\). Applying Gaussian elimination to (19), the computational complexity amounts to \(\mathcal{O}\left(\left(|\Omega|+\prod_{n=1}^{N}R_{n}\right)^{3}\right)\), and it is relatively large if the number of missing entries in \(\mathcal{M}\) is small. It is therefore necessary to reduce the computational complexity for the LS problem associated with (19). To tackle this issue, let input tensor \(\hat{\mathcal{Y}}=\left[\hat{\mathcal{Y}}^{(s_{1},\ldots,s_{N})}\right]\in \mathbb{R}^{\mathbb{I}_{1}\times\ldots\times I_{N}}\) be partitioned into small overlapping subtensors \(\{\hat{\mathcal{Y}}^{(s_{1},\ldots,s_{N})}\}\), where \(\forall n:s_{n}=1,\ldots,S_{n}\) and \(S_{n}\) is the number of partitions of \(\hat{\mathcal{Y}}\) along its \(n\)-th mode. The total number of subtensors is equal to \(S_{Y}=\prod_{n=1}^{N}S_{n}\). Each subtensor can be expressed by \(\hat{\mathcal{Y}}^{(s_{1},\ldots,s_{N})}=\left[y_{\Gamma(s_{1}),\ldots,\Gamma(s_ {N})}\right]\in\mathbb{R}^{\mathbb{I}_{1}\times\ldots\times\mathbb{L}_{N}}\), where \(\forall n:L_{n}=\lceil\frac{I_{n}}{S_{n}}\rceil\leq I_{n}\). The set \(\Gamma(s_{n})\) contains the indices of the entries in \(\hat{\mathcal{Y}}\) which belong to \(\hat{\mathcal{Y}}^{(s_{1},\ldots,s_{N})}\) along its \(n\)-th mode, and it can be expressed by  
\[\forall n:\Gamma(s_{n})=\left\{ \begin{array}{ll}\{\gamma(s_{n})+1,\ldots, \gamma(s_{n})+L_{n}\}\in\mathcal{N}^{L_{n}}&\text{for}\quad s_{n}<S_{n}\\ \{\gamma(S_{n}),\ldots,I_{n}\}&\text{for}\quad s_{n}=S_{n}\end{array} \right. \tag{22}\]where \(\gamma(s_{n})=\lfloor(s_{n}-1)(L_{n}-\eta_{n})\rfloor\). The parameter \(\eta_{n}=\lfloor\frac{\theta_{n}L_{n}}{100}\rfloor\) determines the number of overlapping pixels along the \(n\)-th mode, and \(\theta_{n}\in[0,\ \ 99]\) expresses the percentage of the overlap along the \(n\)-th mode. The proposed methodology for image completion should be applied separately to each subtensor. The missing pixels are completed using a very limited volume of the input tensor but mostly restricted to their nearest neighborhood. It is thus a strategy that resembles PDE-based image inpainting, but it is much more flexible for highly dissipated known pixels and allows us to reduce the computational cost dramatically. Moreover, the factor matrices \(\{\mathbf{F}^{(n)}\}\) and \(\{\mathbf{P}^{(n)}\}\) in (16) are expressed by radial functions, and hence can be precomputed before using the subtensor partitioning procedure. In RBF-based interpolation methods, the samples or pixels that are close to the boundary of the region of interest are usually not well approximated. However, due to overlapping, boundary perturbation effects in our approach are considerably relaxed. The pseudo-code of the proposed image completion algorithm is presented in Algorithm 1.