{'fraction_non_alphanumeric': 0.04346246093466095, 'fraction_numerical': 0.017200862465779974, 'mean_word_length': 4.2496502607147395, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Non-Local Robust Quaternion Matrix Completion for Color Images and Videos Inpainting

The image nonlocal self-similarity (NSS) prior refers to the fact that a local patch often has many nonlocal similar patches to it across the image and has been widely applied in many recently proposed machining learning algorithms for image processing. However, there is no theoretical analysis on its working principle in the literature. In this paper, we discover a potential causality between NSS and low-rank property of color images, which is also available to grey images. A new patch group based NSS prior scheme is proposed to learn explicit NSS models of natural color images. The numerical low-rank property of patched matrices is also rigorously proved. The NSS-based QMC algorithm computes an optimal low-rank approximation to the high-rank color image, resulting in high PSNR and SSIM measures and particularly the better visual quality. A new tensor NSS-based QMC method is also presented to solve the color video inpainting problem based on quaternion tensor representation. The numerical experiments on color images and videos indicate the advantages of NSS-based QMC over the state-of-the-art methods.


Introduction
The robust quaternion matrix completion (QMC) method is recently proposed in [1] to reconstruct low-rank matrices from incomplete and corrupted entries. By encoding color images into purely imaginary quaternion matrices, this method has been successfully applied to solve the color image inpainting problem with superiority on preserving original color information. In theory, the QMC method can successfully recover the original color image which satisfies incoherent conditions and is of low rank when the missed and noised pixels obey uniform distribution and independence constrains [1]. However, we find that the QMC method performs wonderfully when the target color images are smooth, but often loses the sharp information such as color edges when the original color images contain plenty of textures. Mathematically, the low-rank property of their quaternion matrix representations is the inherent issue. This motivates us to develop a method to rearrange the pixels of observation such that the rearranged original color image is of low-rank. In this paper, a new nonlocal self-similarity (NSS) based QMC method is proposed to apply the NSS prior of color images to significantly improve the completing capability. Numerical experiments indicate that this new method can successfully recover natural color images which are essentially not of low-rank and is efficient to solve the large-scale color image and video inpainting problem.
In the literature, the latest denoising methods have attempted to take advantage of another regularity, the self-similar structures of most images. The nonlocal-means method [2,3] seems to be one of the most famous methods to this aim. It discovers the property that images are redundant and have self-similar structures and uses this property to find a series self-similar patches or similar pixels. The first version nonlocal-means uses similar patches to find similar pixels and calculates the weighted means of the similar pixel values. Until Buades et al. [2,3] introduced the idea to find patches that are similar to the currently processed one, this idea was called nonlocal-means. Since the search for similar pixels will be made in a larger neighborhood, but still locally, the name "non-local" is somewhat misleading [4], but people have been familiar with it. Algorithms proposing parsimonious but redundant representations of patches on patch dictionaries are proposed in [5][6][7][8]. The BM3D [9] is probably the most efficient patch-based current method which creates a 3D block with all patches similar to a reference patch, on which a threshold on the 3D transformed block is applied. Zhang et al. [10,11] replaced the discrete cosine transform (DCT) by an adaptive local linear transform, the principal component analysis (PCA), and achieves state-of-the-art performance in both quantitative PSNR measures and visual qualities.
NSS refers to the fact that there are many repeated local patterns across a natural image and those nonlocal similar patches to a given patch can help much the reconstruction of it. The NSS-based image denoising algorithms such as BM3D [9], LSSC [12], NCSR [13], and WNNM [10] have achieved state-of-the-art denoising results. However, it is still open to apply NSS into color image inpainting, which considers the gross missing and random noise at the same time. Meanwhile, QMC [1] exactly reconstructs a color image of sufficiently small rank. But, this is not true for a color image of high rank. Interestingly enough, QMC still computes an optimal low-rank approximation to the high-rank color image, although sometime the quality of reconstruction is not very satisfactory. This motivates us to apply the NSS prior to search similar patches of a single color image and gather them together to generate a commonly low-rank quaternion matrix to be reconstructed by QMC.
The main contribution of this paper is in three aspects: • The working principle of NSS-based approaches is rigorously explained by introducing numerical rank to quaternion matrices. The NSS prior based on quaternion representation is first applied to solve the color image inpainting problem. A new NSS-based robust quaternion matrix completion method (NSS-based QMC) is proposed and is theoretically and experimentally proved efficient to reconstruct color images from incomplete and corrupted entries.
• A novel tensor NSS-based QMC method (TNSS-based QMC) is developed to solve the color video inpainting problem. Color videos are represented by quaternion tensors. TNSS-based QMC is in fact a novel quaternion tensor completion method. It is feasible to recover color videos from incomplete and corrupted tubes (that is, frontal slices miss pixels at the same positions).
• The NSS-based and TNSS-based QMC methods are applied to inpaint natural color images and videos from incomplete and corrupted pixels and their performances are su-perior to the state-of-the-art methods on recovering the color and geometric properties such as color edges and textures. This paper is organized as follows. In Section 2, we briefly present necessary information about quaternion matrices and recall the QMC model and theory. In Section 3, we propose a new NSS-based QMC method, including in the numerical rank analysis, the nonlocal selfsimilarity, and a new NSS-based QMC algorithm. In Section 4, we develop a new TNSSbased QMC method to solve the large-scale color image and video inpainting problems. In Section 5, we apply the NSS-based and TNSS-based QMC methods to practical inpainting problems of color images and videos. Finally, the concluding remark and further work are given in Section 6.

Preliminaries
In this section, we firstly recall the basic information of quaternion matrices and the robust quaternion matrix completion method [1].

Quaternion matrices
Quaternion, introduced by Hamilton [14], has one real part and three imaginary parts given by a = a r + a i i + a j j + a k k where a r , a i , a j , a k ∈ R and i, j and k are three imaginary units satisfying Here a symbol of boldface indicates that it is a quaternion scalar, vector or matrix. When a r = 0, a is called a purely imaginary quaternion. For simplicity, we denote Q by a set of quaternions. The set of n 1 × n 2 quaternion matrices are defined by is called a purely imaginary quaternion matrix if its real part is zero (A r = 0). The maximum number of right linearly independent columns of a quaternion matrix A ∈ Q n1×n2 is called the rank of A, denoted by rank(A).
A quaternion matrix X is called of δ-rank r if it has r singular values bigger than δ.
For any τ > 0, we define a low-rank approximation of A as where σ 1 ≥ · · · ≥ σ k > τ and the rest singular values of A that are smaller or equal to τ are replaced with zeros. The inner product between two quaternion matrices A and B is defined by where Tr(A H B) denotes the trace of A H B. The matrix norms of A are defined by the ; the spectral norm A 2 := max{σ 1 , · · · , σ r } and the nuclear norm A * := r i=1 σ i , where σ 1 , · · · , σ r are all nonzero singular values of A.

The robust quaternion matrix completion method
The QMC method, recently proposed in [1], aims to recover an n 1 -by-n 2 quaternion matrix L 0 from its partly known entries with noise. Let P Ω be the orthogonal projection onto the linear space of matrices supported on Ω ⊆ [1 : A few available data of L 0 + S 0 in the subset Ω are written as X = P Ω (L 0 + S 0 ), where S 0 is a sparse matrix containing the noise information. For each observed quaternion matrix X ∈ Q n1×n2 , we consider the following robust quaternion matrix completion model as in [1] to recover the underlying quaternion matrix, From [1, Theorem 2], the solutionL of (3) with λ = 1 √ ρn (1) is exact, i.e.,L = L 0 , provided that the rank of L 0 is under a given bound and S 0 is sufficiently sparse. Here, ρ = |Ω|/n 1 n 2 denotes the ratio of sampling and n (1) = max{n 1 , n 2 }. Note that the optimal balance parameter λ is fixed, which sets us free from the hard work on parameter selection. The prior assumption on the rank of L 0 is one of motivations to write this paper.
The robust quaternion matrix completion can be applied into color image inpainting. Essentially, the observed color image with the spatial resolution of n 1 × n 2 pixels is represented by an n 1 ×n 2 quaternion matrix X in Q n1×n2 as follows: where R ij , G ij and B ij are the red, green and blue pixel values respectively at the location (i, j) in the image. From Theorem 2 in [1], the rank of the targeted color image (denoted by L 0 ) is smaller, the possibility of exactly recovering it is higher. However, the natural color images are not always of low rank. When the original L 0 is of high rank, the computedL by the soft threshold method suggested in [1] is not the exact solution anymore but an optimal low-rank approximation of L 0 . This undoubtedly reduce our expectation on reconstructions from observed color images with missing data. This foundation motivates us to enhance the QMC method with the patching or non-local mean technique.

Non-Local Robust Quaternion Matrix Completion
In this section, we present a new non-local QMC approach and a fast patch-based QMC algorithm based on the ADMM frameworks.

Model and Low-Rank Theory
Now we propose a NSS-based framework for robust color images completion under quaternion representation, called by NSS-based QMC.
Suppose an observed color image is expressed as a quaternion matrix X = Ri + Gj + Bk ∈ Q n1×n2 , where R, G and B ∈ R n1×n2 represent the red, green and blue components, respectively. By moving across the spatial domain with overlaps, we build a group of patches in which Y i,j is a patch centred at (i, j) of color image X and w × h is the fixed patch size, 0 < w ≤ n 1 and 0 < h ≤ n 2 . Using a unit metric (say, the Euclidean distance with a threshold), the nonlocal similar patches are found from G and gathered into different subgroups. The classic method to do so is firstly setting m key patches (covering the whole color image), and then finding a fixed number of patches most similar to it by block matching. Mathematically, the subgroup of similar patches to each given key patch Y i,j is where f is a distance function between two patches, e.g., f (Y s,t , Y i,j ) = Y s,t −Y i,j F , and δ > 0 is a manual threshold. It is practically convenient to gather a fixed number of similar patches in each subgroup. That is, we search a priorly decided number of similar patches, i.e., |G i,j | = d with d being a positive integer. Finally, one quaternion matrix X i,j ∈ Q (wh)×d is constructed from each subgroup of patches, G i,j , with ordering all elements lexicographically as a column vector, i.e, where Y i k ,j k denotes the k-th element of G i,j . Here, vec(Y i,j ) means to stack all columns of quaternion matrix Y i,j into a quaternion vector. The diagram of the construction is displayed in Fig.1. It is interesting to observe that the singular values of X i,j decay fast. Next, we apply the QMC algorithm (see Algorithm 1 in Section 3.2) on each X i,j defined by (6) to recover the subgroup G i,j . The aim is to compute a low-rank reconstruction L i,j by applying the QMC method on X i,j . In the converse way of generating X i,j , we get the low-rank approximations to patches from G i,j , denoted by By the averaging technique, a good approximation, denoted by L, to the original color image is reconstructed from m reconstructed subgroups G i,j 's. Now we show that each X i,j generated by (6) is of numerically low rank.
Proof. Let v i and v j be two different columns of unitary matrix V.
and that if r satisfies (8) Suppose the distance function for each patch group G i,j defined as in (5) is uniformly Lemma 3.1 can be used to analysis the numerical low-rank property of each key patching matrix X i,j . Note that X i,j can be seen as a sum of a low-rank matrix and a perturbation, where L i,j and S i,j are the patch matrices of original image L 0 and sparse noise matrix S 0 , respectively, and Ω i,j is the patched region of available data.
and the associated patching matrix X ij ∈ Q (wh)×d (with wh ≥ d) has the singular value decomposition, where where [w 1 , . . . , Then σ ri,j ≤ δ and thus the δ-rank of X i,j is less than r i,j .
Proof. By Lemma 3.1, we only need to show that the distance between any two columns of X i,j is less than or equal to 2δ holds for any two columns vec(Y s1,t1 ) and vec(Y s2,t2 ) of X i,j .

Practical QMC algorithm
Now we are at the position to solve the resulting QMC problem corresponding to each X i,j defined by (6): min For the convenience of presentation, we omit the subscripts of X i,j and Ω i,j in (12), and use X and Ω instead.
To solve (12), we present a practical QMC algorithm under the ADMM framework with theoretical convergence guarantee [16]. Firstly, we reformulate (12) as the following equivalent optimization problem by introducing two auxiliary variables P and Q, min L,S,P,Q The augmented Lagrangian function is given as follows by attaching multipliers Y and Z: where µ is the penalty parameter for linear constraints to be satisfied. Such joint minimization problem can be decomposed into two easier and smaller subproblems such that two groups of variables [L, Q] and [S, P] can be minimized in an alternating order, followed by the update of multipliers Y and Z. This strictly follows the ADMM framework in [16], and thus, the theoretical convergence is guaranteed. Moreover, L and Q are decoupled in the [L, Q] subproblem, and they can be solved separately. It is also true for S and P in the [S, P] subproblem. The detailed analysis is presented in the supplementary material.
We summarize above steps of solving (12) into Algorithm 1, in which a quaternion matrix The computational cost of Algorithm 1 at per iteration is O(n 1 n 2 + min(n 1 n 2 2 , n 2 1 n 2 )) for each observed quaternion matrix X ∈ Q n1×n2 .

NSS-based QMC Algorithm
Based on above analysis, we propose the NSS-based QMC algorithm, whose pseudo code is proposed in Algorithm 2.
In Algorithm 2, the overlapped patches are averaged with weights generated by the similarity to key patch; see (20) (By Lemma 3.1, the δ-rank of X i,j is less than r which is the index of the first singular value such that σ r (X i,j ) ≤ δ.) From Theorem 3.2, it is possible to get low δ-rank quaternion matrices, X i,j 's, in the NSS-based QMC by setting small δ. This is indicated in Fig.1. From Theorem 2 in [1], the lower the rank of the matrix is, the accurate the matrix is recovered by QMC. The idea of NSS-based QMC provides a method to construct low-rank matrices, on which the QMC is applied.
Remark 3.1. Finding the patches similar to a given patch by block matching, NSS-based QMC and BM3D group them into a quaternion matrix and a third order tensor, respectively. The differences are in two folds: (1) NSS-based QMC is for robust completion and BM3D is for denoising; (2) the redundancy of similar patches is characterized by the lowrankness of the quaternion matrix in NSS-based QMC and the redundancy of similar patches is characterized by the sparsity of the transformed third-order tensor in BM3D.
So we will not compare NSS-based QMC with BM3D [9] in our numerical experiments since it is not appropriate for solving color image inpainting problem. In fact, if BM3D without modification is applied into Example 5.1 then the obtained reconstructions will contain unknown pixels and some noise.

While not converge
3. Update L and Q: 4. Update S and P : Update Y and Z:
1. Input: The color image X = [X 0 X 1 X 2 X 3 ]; the set of the indexes of known pixels Ω; the patch size w × h with 0 < w ≤ n 1 and 0 < h ≤ n 2 ; the number of key patches m; a tolerance δ > 0; the dimension of the patching group d.

While not converge
3.
Generate the group of patches G as in (4). Choose m key patches Y i,j with (i, j) ∈ Ω.

4.
Search d similar patches to Y i,j and gather them into G i,j . Generate a quaternion matrix X i,j as in (6).

5.
Apply the QMC algorithm (Algorithm 1) to compute a low-rank approximation L i,j of X i,j . Reconstruct the subgroups of approximation patches G i,j .

6.
Compute the reconstruction L from m reconstructed subgroups G i,j .

Large-scale Color Image and Video Inpainting
The NSS-based QMC method can not be directly applied to handle the large-scale color video inpainting problem. In this section, a new tensor NSS-based QMC (TNSS-based QMC) method is presented for color video inpainting based on the quaternion tensor representation. At first, we present a new TNSS-based QMC algorithm for color video inpainting. Under the quaternion representation, a color video is represented by a third-order quaternion tensor, whose slices are quaternion matrices. When the scale of each slice of color video is huge, it is practical to set a window for searching similar patches. For a given size D > 0, the searching window corresponding to the key patch Y i,j with the centre (i, j) is defined by where · ∞ denotes the sup norm: is the centre index set of patches with the centre (s, t) near to (i, j). Let X ∈ Q n1×n2×n3 be a third-order quaternion tensor and let its k-th frontal slice be X(k) := X (:, :, k) ∈ Q n1×n2 , k = 1, · · · , n 3 . Once the key patch Y i,j (k) and the searching window N D (i, j) on the k-th slice X (:, :, k) is set, we use the same index (i, j) of the key patch and the size of searching window to other slices, and search the similar patches on all slices. More specifically, let the patches in the fixed searching window on the k-th slice be grouped in We search d patches that are similar to the key patch where (i s , j s ) ∈ N D (i, j) and 1 ≤ k s ≤ n 3 , s = 1, · · · , d. Then a quaternion matrix X D i,j (k) ∈ Q (wh)×d is generated by Then the rest steps are similar to the NSS-based QMC algorithm. The indication is shown in Fig.2 and the pseudo code is proposed in Algorithm 3. Here, the superscript ' ' has the similar meaning as in Algorithm 2. TNSS-based QMC is in fact a novel quaternion tensor completion method. The corresponding exact recovery theory can be similarly built to the QMC theory in [1]. This method is feasible to solve the color video inpainting problems with incomplete and corrupted pixels. Especially, it excels at dealing with one of the challenging problems, i.e., all frames of the color video miss pixels at the same positions. That is, TNSS-based QMC can efficiently reconstruct quaternion tensors from incomplete and corrupted tubes. Although difficult to prove theoretically, this capability of TNSS-based QMC obviously relies on two facts: the quaternion representation (each color pixel is represented by a purely quaternion) can fully preserve color information [1] and the NSS technique leads to low-rank prior (see Theorem 3.2). We will perform numerical verification in Example V.4.
The strategy of searching similar patches in Algorithm 3 can also be introduced into Algorithm 2 to tackle the large-scale color image inpainting problem. For a given key patch Y i,j and a searching window N D (i, j) defined in (15), we find d patches similar to the key patch from and denote them by Replacing X i,j in Step 4 of Algorithm 2 with X D i,j , we get the NSS-based QMC algorithm with searching window, which can handle the large-scale color image inpainting problem.
To enhance the visual comfort of the reconstructed color image, we usually select searching windows with a proper size (decided by experiments), and the patches are often reconstructed more than once. The similarity of two patches is estimated by weighted Euclidean distance as follow with a(ς, ϑ) > 0 being some fixed weights (see, e.g., [2,3]). This similarity suggests a weight to the reconstruction of patch Y s,t at the step of applying the searching window N D (i, j).
Remark 4.1. TNSS-based QMC is different to recently proposed methods: LRQA [17] and LRQTC [18]. LRQA [17] is proposed based on nonconvex functions and is applied to each frame of color video. In LRQTC [18], the global low-rank prior to quaternion tensor is encoded as the nuclear norm of unfolding quaternion matrices of large-scale. In TNSSbased QMC, the low-rank prior is of small-scale quaternion matrices generated by similar neighbourhood patches from G D i,j (k) and the local prior information in searching window are from all frames.
1. Input: The color video X ∈ Q n1×n2×n3 ; the set of the indexes of known pixels Ω on the k-th frontal slice; the patch size w × h with 0 < w ≤ n 1 and 0 < h ≤ n 2 ; the number of key patches m; a tolerance δ > 0; the dimension of the patching group d; the size of searching window D > 0.

While not converge
3.
Choose the key patch Y i,j (k) and set the searching window N D (i, j) on the k-th slice. Generate a group of patches G D (k) as in (16).

4.
Search d similar patches as in (17). Generate a quaternion matrix X D i,j (k) as in (18).

5.
Apply the QMC algorithm (Algorithm 1) to compute a low-rank approximation Reconstruct the subgroups of approximation patches G D i,j (k).

6.
Compute the reconstruction L from m reconstructed subgroups G D i,j (k).

end
Remark 4.2. TNSS-based QMC is also different to the tensor methods proposed in [19][20][21][22][23][24][25], which have been applied to the restoration of color images and videos. In the tensor methods, a color image is represented by a third-order tensor and a color video is represented by a fourth-order tensor, and their entries are real numbers which denote the values of red, green or blue channels. The operation process follows the real number operation rules and the relationship of the values of three color channels of the same color pixel is often ignored. They apply the low-rank prior of real algebraic structures. Differently, TNSS-based QMC processes the quaternion operation and always operates the values of the three color channels of the same color pixel as a whole by encoding them into a quaternion [1]. In numerical experiments, we will make a comparison with several tensor methods for which the corresponding codes can be found.

Numerical Examples
In this section, we apply the newly proposed NSS-based QMC and TNSS-based QMC approaches to solving the inpainting problems of color images and videos. We compare our approaches with the state-of-the-art methods in the literature. All these experiments were performed in MATLAB on a personal computer with 2.4 GHz Intel Core i7 processor and 8 GB 1600MHz DDR3 memory.
Example 5.1 (Color Image Inpainting). In this experiment, we apply the proposed NSSbased QMC approach to color image inpainting from incomplete and corrupted entries, and compare it with four well-known methods: • QMC-Quaternion matrix completion algorithm [1].
Numerical comparisons were implemented on eight standard color images and in four cases with different levels of missingness and noise. The detailed settings are as follows. A standard uniform noise is independently and randomly added into pixel locations of red, green and blue channels of color images. The sparsity of noise components is denoted by γ = /(n 1 n 2 ), where the size of image is n 1 -by-n 2 . Let Ω be the set of observed entries which are generated randomly and let ρ = |Ω|/(n 1 n 2 ) denote the percentage of observed entries. Four different situations are considered: (1−ρ, γ) = (10%, 0%), (50%, 0%), (50%, 10%), (0%, 10%). The stopping criteria of the alternating direction method of multipliers are that the norm   of the successive iterates is less than 1e-4 and the maximum number of iteration is 500. Note that many state-of-the-art real-matrix completion-based methods are not listed in the compared algorithms since QMC was shown in [1] to have better performance in color image inpainting.
All numerical results are listed in Table 1. The best PSNR and SSIM values are shown in bold, and the second-best ones are underlined. It is worth mentioning that TMac TT and LRQMC cannot handle the latter two cases with noise (γ > 0) according to [20] and [18], respectively. LRQA-L [17] cannot handle the third case with missing pixels and noise (1 − ρ > 0, γ > 0). In other words, these three methods are not designed for robust color image inpainting (i.e., inpainting color image from incomplete and corrupted pixels) 1 .
Also, TMac TT cannot be directly implemented on the color image 'Flower' of size 500× 362, since TMac TT is limited to the size of picture because of the ket augmentation (KA) technique, which was originally introduced in [27] using an appropriate block addressing.
From Table 1, we can see that NSS-based QMC performs better than the other methods in most of cases. LRQMC achieves the highest PSNR values in the first case with missing 10% pixels and without noise (TMac TT achieves the second highest PSNR values for seven color images). However, when the missing rate rises to 50%, NSS-based QMC achieves the highest PSNR values. For instance, when only 10% pixels are missing, the PSNR value of the reconstructed 'Pepper' image by LRQMC is 39.25, which is about 5 points higher than NSS-based QMC (34.72); but when 50% pixels are missing, the PSNR value of the reconstructed 'Pepper' image by NSS-based QMC is 33. 22, which is about 2 points higher than LRQMC (31.54). The superiority of NSS-based QMC is more obvious when turning to the SSIM values in Table 1. Not only that, NSS-based QMC can handle the case with both missing pixels and noise, and performs better than QMC and TC. Overall, the newly proposed algorithm outperforms the other compared algorithms.
For the visual comparison, the original, observed and recovered color images in the case of robust color image inpainting with (1 − ρ, γ) = (50%, 10%) are shown in Fig.3. (Note that since TMac TT cannot directly recover the image 'Flowers', the observation is located at row 3 and column 5.) It is easily to find a lot of noise left in the reconstructions of TMac TT, LRQA-L, and LRQMC from Fig.3(e-g). This numerically indicates that these three methods cannot handle robust color image inpainting, which is not their goal. From Fig.3(c,d,h), we can find that QMC, TC and NSS-based QMC successfully remove noise during inpainting, since they are designed for robust color image inpainting.
More importantly, it is observed from Table 1 that the PSNR and SSIM values of reconstructions by NSS-based QMC are much higher than those by QMC and TC. And from the visual comparison in Fig.3(c,d,h), the recovered color images by NSS-based QMC are of higher quality. The enlarged parts of these reconstructions are listed in Fig.4. The color and edge information is well preserved by NSS-based QMC. However, the sharp geometry shapes, likes the edges and angles, are not clearly recovered by QMC and TC. Moreover, the newly proposed NSS-based QMC overcomes the disadvantage of color mixture of TC. For instance, the pale yellow appears at the edges of red zones in Fig. 4(row 1 and column 4), which is recovered by TC ; but the different color zones are very clean and the color edges are very sharp in Fig. 4(row 1 and column 5), which is recovered by NSS-based QMC. More numerical and visual results can be seen in the supplementary material.
For the completeness of comparison, we also show the reconstructed color images of the third and fourth cases (50%, 0%) and (0%, 10%) in the 1st and 3rd rows of Fig.5 and Fig.6, and their enlarged parts are listed in the 2nd and 4th rows. These visual comparisons indicate that NSS-based QMC can preserve the color information and color edges well while Notice that TC and TMac TT represent color images by third-order tensors, while QMC, LRQA-L, LRQMC, and NSS-based QMC by quaternion matrices. LRQA-L and NSS-based QMC apply nonlocal self-similarity, but the former does not performs as expected. Our methods are not compared with BM3D [9], LSSC [12], NCSR [13], and WNNM [10] since they are efficient image denoising methods but not proper to solve color image inpainting problem. For instance, if BM3D without modification is applied to solve the color inpainting problem in Example 5.1, then the obtained reconstructions will contain unknown pixels and a few of noise, and their PSNR and SSIM values are lower than those in Table 1. In Fig.7, we list the reconstructed images from two different cases: (ρ, γ) = (50%, 0%) and Here we only compare NSS-based QMC with QMC since both of them are able to avoid the color mixture during the recovering process. From the numerical results in Fig.7, it is observed that NSS-based QMC performs better than QMC by producing images with higher PSNR and SSIM values. From the enlarges parts of size 170 × 170 in Fig. 8, one can see that the reconstructions by NSS-based QMC are smoother than those by QMC and in the case (ρ, γ) = (50%, 30%), there are still some noise left in the recovered image by QMC and the color edges are not sharp.

Example 5.3 (Color Video Inpainting).
In this experiment, we apply the TNSS-based QMC proposed in Section 4 to the inpainting problem of color videos. The testing video is downloaded from the 'videoSegmentationData' database 2 in [28] and contains 72 frames which are of size 288 × 352. We randomly take 20 frames of the color video 'M07 058' and store them in a third-order quaternion tensor. The observed color video is generated by randomly re- moving 80% pixels from the original color video. The size searching window D = 20 and the number of patches in each patching group d = 60. The stopping criteria of the alternating direction method of multipliers are that the norm of the successive iterates is less than 1e-4 and the maximum number of iteration is 100. For comparison, we also apply QMC to each frame and reconstruct all frames of color video one by one.
For indication, the first 4 frames of original, observed and reconstructed color videos are listed in Fig.9 and their enlarged parts of size 60 × 60 are also shown in Fig.9. The PSNR and SSIM values of color videos are given in Table 2. From these numerical results, we observe that TNSS-based QMC successfully reconstructs color video from 20% known pixels. It performs better than QMC by producing each frame with higher PSNR and SSIM values. Moreover, QMC fails to recover the edges of airplane, but TNSS-based QMC successfully reconstructs the color information and geometric shape of airplane. From the enlarged parts in Fig.9, one can observe that the aircraft nose reconstructed by TNSS-based QMC is smooth and has sharp edge, but the aircraft nose recovered by QMC is rough and has blur edge. The computational cost of CPU time by TNSS-based QMC is about 5.23% of that costed by QMC.    Example 5.4 (Comparison with tensor completion methods ). In this experiment, we compare TNSS-based QMC with QMC, TMac TT and three other tensor completion methods: • TNN-A method based on the tensor tubal rank [23].
• TTNN-A model for tensor robust principle component analysis based on tensor train rank [25].
We implement the comparison on a widely used color video 'DO01 013' from the 'videoSeg-mentationData' database [28], which contains 89 frames of size 288 × 352. According to the setting mentioned in [25], we need to resize the testing color video into 243 × 256 × 3 × 27 to implement TTNN and TMac TT. The frame mode is merged with the image row mode to form a third-order tensor, called by a video sequence tensor, of size 6561 × 256 × 3. Then the tensor is reshaped into a ninth-order tensor of size 6 × 6 × 6 × 6 × 6 × 6 × 6 × 6 × 3 using the KA technique [27]. The ninth-order video sequence tensor is directly used for the tensor completion algorithms (TTNN and TMac TT). For the validity of comparison, we set two cases: • Case 1: The observed color video is generated by randomly adding sparse noise to 10% pixels of the original color video.
• Case 2: The observed color video is generated by randomly removing 80% pixels from the original color video.  TNN and TTNN are tested in Case 1, since they can't handle the problem with missing pixels. TMac TT and LRQTC are tested in Case 2, because they can't handle the problem with sparse noise. QMC and TNSS-based QMC are tested in two cases. The size of searching window D = 20 and the number of patches in each patching group d = 60. The stopping criteria of the alternating direction method of multipliers are that the norm of the successive iterates is less than 1e-4 and the maximum number of iteration is 100. Moreover, two types of sparse noise and pixel missing are designed. One type is called 'TUBE' missing or noise, where all frames are missing or noisy at the same positions. Another type is called 'NON-TUBE' missing or noise, where all frames are missing or noisy at different locations but at the same percentage.
For Case 1, the PSNR and SSIM values are given in Table 3. The numerical results indicate that TNSS-based QMC is superior to other compared methods.  Fig.10. It can be observed that all compared methods remove sparse noise well, and the horse silhouette and mane recovered by TNSS-based QMC are more obvious than the other methods.
For Case 2, the PSNR and SSIM values are given Table 4. The numerical results also indicate that TNSS-based QMC is superior to other compared methods (LRQTC is the second best one). For instance, within 'NON-TUBE' missing (see Table 4), TNSS-based QMC has the average PSNR and SSIM values: (35.77, 0.9483), which are higher than QMC (30.47, 0.8493), TMac TT (32.00, 0.8596), and LRQTC (34.67, 0.9300). The first 4 frames of original, observed (with 'NON-TUBE' missing), reconstructed color videos and their enlarged parts are shown in Fig.11. We can also observe that all compared methods successfully recover the missed pixels, and visually, TNSS-based QMC reconstruct the horse silhouette and mane at a much higher level than the other methods. Interestingly, TMac TT, LRQTC and NSS-based QMC perform better in the situation of 'NON-TUBE' than in the situation of 'TUBE'. This numerically confirms our previous judgement that the inpainting problem with incomplete and corrupted tubes is one of the challenging problems. Fortunately, the proposed TNSS-based QMC is good at handling such color video inpainting problem with 'TUBE' missing. For instance, TNSS-based QMC improves the average SSIM value from the second highest value 0.9027 (LRQTC) to 0.9456 in the 'TUBE' type, while it increases the average SSIM value from the second highest value 0.9305 (LRQTC) to 0.9483 in the 'NON-TUBE' type.
Combined with Example 5.3, the above numerical results show that TNSS-based QMC is able to reconstruct color video from incomplete and/or corruptted pixels and its performance is superior to the state-of-the-art methods in terms of PSNR and SSIM values. More valuable is that the TNSS-based QMC can effectively recover the color information and geometry of objects in color videos, thus presenting visually comfortable reconstructions.

Conclusion
In this paper, a theoretical analysis is proposed for the working principle of NSS-based approaches. Based on this, a new NSS-based QMC method is presented and applied to solve the color image inpainting problem. The NSS prior is applied to search similar patches, gathered into a low-rank quaternion matrix, of a color image, and a good reconstruction is computed by a new QMC algorithm. A novel TNSS-based QMC method is also developed to inpaint color videos from incomplete and corrupted frontal tubes. Numerical experiments on (large-scale) color image and video inpainting indicate the superiority of the newly proposed methods, resulting in high PSNR and SSIM measures and particularly the best visual quality among competing methods. If all entries are real numbers, then the TNSS-based QMC method reduces to the TNSS-based matrix completion method, which can be applied to solve the grey video inpainting problem.
In our numerical experiments, the proposed TNSS-based QMC has superiority on color video inpainting to the state-of-the-art methods. This has been verified within the 'TUBE' and 'NON-TUBE' types of incompleteness and corruption. We find the 'TUBE' type of incompleteness more challenging. Fortunately, TNSS-based QMC can solve this problem well. However, there is still an open problem that how to inpaint a color video from a piece of incompleteness and corruption. This will be a topic worth studying in the future. New fast algorithms for the proposed methods also need to be further investigated. We refer to [29,30] as preliminary knowledge for future research.
A The supplementary material of Section 3.2 In this section we present the detailed steps of solving the joint minimization problem (14) in the main body.
The [L, Q] subproblem of (14) is where µ is the penalty parameter. Since L and Q are decoupled, the [L, Q] subproblem can be solved separately. The L subproblem is which has the exact solution as UΣ 1 The computational cost of updating L is O(min(n 1 n 2 2 , n 2 1 n 2 )). The Q subproblem min PΩ(P+Q)=X can be exactly solved as The computational cost of updating Q is O(n 1 n 2 ).
The [S, P] subproblem of (14) is where µ is the penalty parameter. Since S and P are decoupled, the [S, P] subproblem can solved separately. The S subproblem is can be exactly solved as In this section, we compare the efficiency of NSS-based QMC with various sizes of patch and searching window. Without changing the setting above experiments, two cases are tested: • Case 1: The size of patch is set as s 1 = 6 and the size of searching window is randomly chosen as about multiplications of s 1 , s 2 = 12, 18, 24, 30, 54.
• Case 2: The size of patch is set as s 1 = 16 and the size of searching window is randomly chosen as s 2 = 16, 18, 20, 32, 64.
The reconstructed color images are listed in Fig.12, and the variation trend of PSNR and SSIM values are shown in Figs.13-14. From these numerical results, we find that the smaller the patch size, the better the reconstruction. As the searching window increases, the PSNR and SSIM values firstly go up and then go down. A proper size of searching window depends on the data. C The supplementary material of Example 5.4 In this section, we show first 4 frames of original, observed and recovered video in Case 1 that 10% percent pixels are corrupted by sparse noise and in the 'NON-TUBE' type of corruption and their corresponding enlarged parts in Fig.15. Next, we show show first 4 frames of original, observed and recovered videos in Case 2 that 80% percent pixels are missing randomly and in the 'TUBE' type of incompleteness and their corresponding enlarged parts in Fig.16.

D More numerical and visual results
In this section, we present more numerical and visual results for Example 5.1 in the main body. Several comparisons were implemented on the additional seven standard color images under the situation: (1 − ρ, γ) = (50%, 10%). The stopping criteria are that the norm of the successive iterates is less than 1e-4 and the maximum number of iteration is 500. The numerical results are shown in Table 5. The best PSNR and SSIM values are shown in bold, and the second-best ones are underlined. The corresponding color images are shown in Fig.17.
From the numerical and visual comparisons, it is not difficult to find that TMac TT [20], LRQA-L [17] and LRQMC [18] fail to handle the robust color image inpainting problem (i.e., inpainting color image from incomplete and corrupted pixels), which is consistent with the models in the corresponding papers. What's more, there are three methods, QMC, TC and NSS-based QMC successfully recovering color images from incomplete and corrupted pixels. Especially, both from the PSNR, SSIM values and the recovered images in the situation (1 − ρ, γ) = (50%, 10%), the performance of NSS-based QMC is the most excellent among them. Take 'Sails' as an example, the PSNR and SSIM values of NSS-based QMC are (26.99, 0.8389), which are higher than those of QMC (23.97, 0.7070) and TC (24.12, 0.7072). For the reconstructed images, the edges recovered by NSS-based QMC are much cleaner than those recovered by two other methods.