Image recovery task can be treated as a matrix completion problem, and it is proved to be really effective (Buades, Coll, and Morel 2005;Ji et al. 2010;Liu et al. 2009;Wang, Nie, and Huang 2014). In this task, pixels in an image are missing because of noise or occlusion, and we need to make use of observed information to reconstruct the original image without deviating too much from it. Rank minimization regularization is proposed to solve matrix completion problems, and has already achieved great success in other fields (Bennett and Lanning 2007). However, it leads to a non-convex and NP-hard problem. To solve this problem, trace norm is introduced to approximate rank minimization, and since then many algorithms have been invented to solve matrix completion problems using trace norm regularization (Shamir and Shalev-Shwartz 2014;Cai, Candès, and Shen 2010). However, trace norm is not the best approximation for rank minimization regularization. If a non-zero singular value of a matrix varies, the trace norm value will change simultaneously, but the rank of the matrix keeps constant. So, there is a big gap between trace norm and rank minimization, and a better model to approximate rank minimization regularization is desired for learning a low-rank structure.
In a recent work (Liu et al. 2009), Liu applied low-rank model to solve image recovery problem. He assumed that video is in low-rank structure, however, videos are not homogeneous, and they may contain sequences of images from different episodes. If we simply project all the video into a low-rank subspace, it is very likely to lose important information in the original video. More recently, Wang et al. introduced a spatiotemporal consistency low-rank tensor completion method (Wang, Nie, and Huang 2014). They proposed to utilize the content continuity within videos by imposing a new 2 -norm smoothness regularization. However, this 2 -norm smoothness regularization tends to force two consecutive frames to be similar, and it can not capture spatiotemporal variation properly.
In this paper, we propose a novel video recovery model Sectional Trace Norm with Variation and Consistency Constraints (STN-VCC). Our contributions are summarized as following: firstly, we utilize capped 1 -norm smoothness function to capture the spatiotemporal variation and consistency between consecutive frames in video clips; secondly, we introduce a new sectional trace norm to capture the lowrank structure, which is a better approximation of rank minimization than the traditional trace norm. Thirdly, instead of using Alternating Direction Method of Multipliers (ADMM) which was used by previous video recovery models, we use proximal gradient descent method to optimize and prove that our method is guaranteed to converge. all video sequences share the same content, spatiotemporal variation is also very frequent in video clips. 1 -norm is a common alternative to 2 -norm, and it is known for its robustness to outliers. It is intuitive to utilize 1 -norm regularization to capture both spatiotemporal consistency and variation. However, one video clip is usually made up of many different episodes, and it is natural that two consecutive frames are from different scenes and backgrounds. In this case, most of the pixels in two consecutive frames are different, and even 1 -norm regularization fails. In this paper, we propose to use capped 1 -norm regularization e∈E min(|e|, ε) to capture the spatiotemporal consistency and variation in video clips. Capped 1 -norm function is able to ignore the errors larger than ε, penalize the errors smaller than ε, and it is also used to handle outliers (Zhang 2009; Gong et al. 2013;Huo, Nie, and Huang 2016;Gao et al. 2015;Jiang, Nie, and Huang 2015). In this paper, it properly solves the problem of spatiotemporal consistency and variation in video clips.
We perform an experiment to illustrate the advantage of capped 1 -norm over 2 -norm and 1 -norm. The objective function of this task is min
where (|e|, ε) for three models. In this experiment, we set λ = 0.5 and ε = 100. We use stochastic gradient method to optimize and learning rate is 0.1. In Figure 1, as we know that 2 -norm regularization penalizes all the differences, after the optimization, all differences tend to be zero, and this is not what we want if there are spatiotemporal variations in video clips. The result of 1norm and capped 1 -norm are much better than 2 -norm. It is also clear that capped 1 -norm outperforms 1 -norm. In large difference ranges, |Dif f erence| ≥ 100 in the experiment, capped 1 -norm does not penalize these differences for they represent different objects or episodes.
Recently, the low-rank model and its approximation have been successfully applied to recover the images and videos with missing pixel. Most of these works used trace norm to recover the low-rank structure of the image matrix. For a low-rank matrix X ∈ R n×m , rank(X) = r, so its ksmallest singular values should be zero, where k = dr and d = min (n, m). Note that trace norm ||X|| * denotes the sum of singular values. If the non-zero singular values of matrix X change, ||X|| * will change as well, but the rank of X keeps constant. Thus, there is a big gap between trace norm ||X|| * and rank(X).
In this paper, we propose a new sectional trace norm to uncover the low-rank structure of a matrix, ||X|| str = k i=1 σ 2 i (X). In the sectional trace norm regularization, we minimize the sum of k-smallest singular value squares of X and ignore the other larger singular values. When the nonzero singular values increase largely, they are excluded by our sectional trace norm such that the norm value keeps constant.
Alternatively, in (Hu et al. 2013), truncated trace norm was proposed to minimize the sum of k-smallest singular values, and it can also avoid the effect of large singular values, and is better than the traditional trace norm. However, minimizing the sum of k-smallest singular values is a 1 minimization problem, which leads to sparse solution, namely some k-smallest singular values will be zero, but some of them may get large values. Our sectional trace norm can solve this issue. When we minimize the sectional trace norm, the sum of square of k-smallest singular values is minimized so that all of them will be shrunk near to zero.
We perform a low-rank matrix approximation experiment to illustrate the advantage of sectional trace norm over truncated trace norm. The objective function of this task is:
where D ∈ R 288×352 is an image matrix, and reg(X)
σ 2 i (X) for two models. We compute a low-rank matrix X and rank(X) = 12, so k = 276 and λ = 1000.
In Figure 2a, although there is a big gap between 12th and 13th singular values, some singular values after 12th are still large, and this is not what we expect. However, in Figure 2b, it is obvious that the singular values after 12th singular value are nearly zero. Thus our sectional trace norm is a better approximation of rank function than existing models, and is more suitable to be used for low-rank matrix completion tasks.
To sum up, our new video recovery model which uses sectional trace norm with consistency and variation constraints can be represented as:
where X , D ∈ R n×m×s , and there are s frames in a video, and each frame is a matrix of n × m. X pq,l denotes the predicted value in frame l at position (p, q), D denotes the original video tensor, Ω l denotes the observed pixel in frame i. ε is the threshold value and γ is the error upper bound.
In previous papers, they use ADMM to optimize the objective function. ADMM makes it easy to handle constraints in the objective function, however it is hard to prove convergence. In this paper, we use proximal gradient method to optimize our model, and in the next section, we will prove the convergence of our method. Define X l = U ΣV T , where Σ is diagonal singular matrix in ascending order. Let F l = U 1:k , where U 1:k means k smallest singular vectors:
First, we find out that we only need calculate F l F T l , instead of computing matrix F l , in the optimization process. We introduce an efficient way to compute F l T l as a whole term. Suppose singular value decomposition of X l X T l = U ΣU T , where U is the eigenvector matrix and Σ is the diagonal matrix in ascending order. Denote
where
We suppose that X l X T l is a low-rank matrix, so nk is a small value. Truncated SVD method can be applied in this procedure, and it is much more efficient to compute F l F T l in this way. Each F l is updated independently according to function (5) for each X l .
To handle capped 1 -norm term in our objective function (3), we define tensor S as:
Then, as per function ( 5) and ( 6), our objective function is transformed to:
Each X l is also solved independently and alternatively, and for any 1 < l < s, this subproblem is,
We use proximal gradient method to solve the subproblem above. Its gradient with respective to X l is
where α is the step size.
According to the constraint |X pq,l -D pq,l | ≤ γ. We need to project updated X l to this constraint domain. The optimal solution to this projection can be obtained by
X pq,l < D pq,lγ (11) As for l = 1 or l = s, we just need to ignore one of the two loss functions in (8), and follow the proximal gradient method steps to update X l .
Our optimization method is summarized in Algorithm. 1.
Algorithm 1 Algorithm to solve problem (3).
2. Update Xl via (9), (10).
3. Project to X l via (11) end for end while
Using the algorithm above, we can solve our original nonsmooth and non-convex objective function (3). In this section, we prove the convergence of our optimization algorithm, and that a local solution can be obtained in the end. Theorem 1 Through Algorithm. 1, the objective function (3) will converge, or the values of objective function (3) are non-increasing monotonically.
In order to prove Theorem 1, at first, we need the following Lemmas. Lemma 2 According to (Theobald 1975), any two hermitian matrices A, B ∈ R n×n satisfy the inequality (σ i (A), σ i (B) are singular values sorted in the same order)
Via Lemma 2, we know
Above all, we have,
Then, min{|ê|, ε}dê 2 ≤ min{|e|, ε}de 2 (18)
Proof: As we all know Lemma 5 Function value of ( 8) is non-increasing through proximal gradient descent method.
Proof: Firstly, function in ( 8) is convex, and its gradient Δ is Lipschitz continuous. Secondly, projection in ( 8) is convex and closed. According to (Beck and Teboulle 2010), if step size is small enough, proximal gradient descent method is able to improve the objective function value at each step. Now, we are able to prove Theorem 1 by applying these Lemmas above.
Proof: From Lemma 3 and definition of F l , the inequality holds:
Applying Lemma 4 to each element X pq,l and Xpq,l , we have:
According to Lemma 5, after we minimize the function (7) by using proximal gradient descent, it is guaranteed:
When we combine inequalities ( 23), ( 24) and ( 25), we can finally obtain:
So far, it is clear that the value of our proposed objective function will not increase by using our optimization algorithm, so we prove the Theorem 1 that our optimization algorithm is non-increasing monotonically. We also know that the objective function ( 3) is larger than zero at least, so it is lower bounded. We can conclude that our optimization algorithm converges, and a local solution is to be obtained in the end.
In this section, we evaluate our proposed video recovery model and compare it with other five related methods: Tucker algorithm (Tucker) (Eldén 2007), low-rank tensor completion (LRTC) (Liu et al. 2009), low-rank tensor completion with considering consistency ( 2 Tensor) (Wang, Nie, and Huang 2014), low-rank tensor completion with considering consistency and variation (capTensor), sectional trace norm with considering consistency (kmsv-2 ), and our sectional trace norm with considering both consistency and variation.
In the experiments, error bound γ = 0.05 |X |/(n × m × s). Relative square error (RSE) in (Wang, Nie, and Huang 2014) is used as performance metric criterion for comparison. R, G and B layer of each colorful video are represented as a 3D tensor and put into the model respectively and combined as final outputs.
• UCF11 Dataset: It contains 11 action categories: basketball shooting, biking, diving, golf swinging and so on. This dataset is very challenging due to large variations in camera motion, object appearance, pose and so on (Liu, Luo, and Shah 2009) .
• YUV Video Sequences Dataset: It includes video sequences of commonly used video test sequences in the 4:2:0 YUV format, e.g. Elephant Dream video, Highway, News and Stephan 1 .
• Hollywood Human Actions Dataset: It contains video clips, i.e. short sequences from 32 movies: American Beauty, As Good As It Gets, Being John Malkovich, Big Fish and so on (Laptev et al. 2008).
In this section, we evaluate the influence of parameters ksmallest singular value and ε outliers bound on recovery performance. According to the optimization analysis, instead of selecting parameter k, we take r = n-k, the rank of matrix, as the input. In the experiment, the value of ε is generated 1 http://trace.eas.asu.edu/yuv/index.html automatically by setting the number of outliers N ε . We perform experiment on the Sales video clip data. In this experiment, we tune the parameters through grid search strategy, r = {5, 10, 15, 20, 25, 30} and N ε = {1, 10, 10 2 , 10 3 , 10 4 }, and plot the results in Figure 3. As we can see in Figure 3a, the choice of rank value r is nontrivial. In this experiment, if r < 10 or r > 10, RSE value rises. So, in order to derive the best performance, it is of great importance to select an optimal rank value. Figure 3b indicates that when the value of outliers number ranges from 1 to 10000, the performance of our method remains stable. So, in the optimization, we do not need to spend to much time on this parameter. As for parameter λ, in the experiment, we search an optimal value from {10 -2 , 10 -1 , 1, 10, 10 2 } Video Recovery on Synthetic Video Clips In video recovery tasks, we randomly remove 60% pixels or a small patch from each frame, and perform six compared algorithms to recover these video clips. In the experiment, r = {5, 10, 15, 20, 25, 30} and N ε = 100. Experiment results are reported in Table 1 from D1 to D6.
It is clear that these methods with capped 1 -norm always show better performance than methods with 2 -norm. Thus the methods considering video consistency and variation simultaneously always outperform those methods which just consider video consistency. We can also find out that sectional trace norm is better at recovering low-rank structure of image than traditional trace norm. Figure 4 shows the convergence graph of our method on all the synthetic video clips. We ignore the first 5 iterations because the value of ε is learned adaptively during this time. It is obvious that the objective function value tends to converge after 25 iterations.
In this section, we implement the experiments on original movie clips from Hollywood Human Actions Dataset. In the experiment, we randomly mask 50% pixels or occlude a small patch from each frame, and perform six compared methods on these video clips. Parameters are set the same as in last section. Final performance are listed in the Table 2 from D7 to D12. Figure 5 shows the convergence graph of our method on all these six movie clips.
In Figure 6, we can see that the recovered images of our method are much better than others. In recovered images of other methods, the brink of occluded patch is obvious, color and pattern of the recovered patch is different from the original image.
In this paper, we proposed a novel video recovery model, and prove the convergence of our optimization algorithm. Capped 1 -norm smoothness function is utilized as regularization to impose the video spatiotemporal consistency and variation. A new sectional trace norm is introduced to approximate rank minimization which is tighter than traditional trace norm. We evaluate our new video recovery method on several practical videos and experiment results show that our proposed method consistently outperforms other models on video recovery tasks.
Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence