Image Recovery via Truncated Weighted Schatten-p Norm Regularization

Abstract

Low-rank prior knowledge has indicated great superiority in the field of image processing. However, how to solve the NP-hard problem containing rank norm is crucial to the recovery results. In this paper, truncated weighted schatten-p norm, which is employed to approximate the rank function by taking advantages of both weighted nuclear norm and truncated schatten-p norm, has been proposed toward better exploiting low-rank property in image CS recovery. At last, we have developed an efficient iterative scheme based on alternating direction method of multipliers to accurately solve the nonconvex optimization model. Experimental results demonstrate that our proposed algorithm is exceeding the existing state-of-the-art methods, both visually and quantitatively.

1 Introduction

Compressive Sensing (CS) [1,2,3,4,5] draws recently much more attention in the field of image processing. Compared with the traditional scheme of sampling followed by compressing, CS carries out the above two steps at the same time. From fewer measurements than required by Nyquist theorem, CS can efficiently reconstruct images under the condition that they satisfy the sparsity.

Traditional CS algorithms often exploit the sparsity in some transform domains [6,7,8,9,10,11]. Lately, the intrinsic low-rank property exploited by self-similarity and nonlocal operation, has widely used in many research fields, such as face recognition [12,13,14], image inpainting [15] and compressive sensing [16, 17]. These methods based on low-rank property have shown competitive performances in each area.

The success of these low-rank regularization based CS methods depends on the solution of the low-rank regularization problem. Unfortunately, the low-rank regularization problem is NP-hard and there is no method to solve it directly. Many methods use different substitution functions to approximate the rank function [18,19,20]. [18, 19] selected convex nuclear norm and employed singular value thresholding [21] to efficiently resolve the rank regularization problem. Compared with the original rank definition has the fact that all nonzero singular values play the same important role, the nuclear norm based approaches minimized the summarization of all the singular values. [16] chose logdet function (the logarithm sum of all the singular values) and can obtain better results than nuclear norm. However, logdet function is fixed and essentially deviates from the rank function. In order to obtain a competitive solution of low-rank regularization problem, many methods adopt distinct schemes and treat each singular value differently [22,23,24,25]. Weighted nuclear norm [22] assigned larger weights to larger singular values and smaller weights to smaller ones. So smaller singular values are penalized more than larger ones. Since the largest r (the rank) singular values will not impact the rank, in our previous work, truncated schatten-p norm [24] abandoned them and only minimized the summation of surplus singular values to the power of p.

In this paper, truncated weighted schatten-p norm (TWSP), which is taking advantages of both weighted nuclear norm and truncated schatten-p norm, has been firstly proposed toward better exploiting low-rank property in image CS recovery. At last, we further propose an efficient iterative scheme based on alternating direction method of multipliers to accurately solve the nonconvex optimization model.

The reminder is organized as follows. Section 2 simply reviews the weighted nuclear norm based image CS model and truncated schatten-p norm based image CS model. In Sect. 3, our proposed TWSP and an efficient iterative scheme for the optimization model are given in details. In Sect. 4, the effectiveness of our method is proved by several experiments. Finally, we summarize our proposed model in Sect. 5.

2 Related Work

In this section, we will review low-rank regularization based image CS recovery model. Suppose an image is defined as $x \in {R^n}$ and its sampling matrix is $\varPhi \in {R^{m \times n}}(m \ll n)$, the purpose of CS is to reconstruct the image x from the measurement $y \in {R^m}$ ($y = \varPhi x$) than suggested by traditional Nyquist sampling theorem.

Usually, natural images have a large number of repetitive structures and these blocks with repetitive structures are located in the global scope of the images. So the rank of each block matrix grouped by corresponding nonlocal similar blocks is low. The intrinsic low-rank property exploited by self-similarity and nonlocal operation, has widely used in face recognition, compressive sensing and image denoising. These methods based on low-rank property have shown competitive performances in each area.

Suppose ${x_j} \in {R^d}$ is a block, we query for h most similar blocks from all image blocks. ${R_j}x = \left[ {{R_{{j_1}}}x,{R_{{j_2}}}x, \cdots {R_{{j_h}}}x} \right] \in {R^{d \times h}}$ (${R_{{j_k}}}$ is the corresponding extraction matrix) is the j-th block matrix formed by these similar blocks. Then the CS recovery problem is formulated as follows:

$$\begin{aligned} \left( {x,{L_j}} \right) = \mathop {\arg \min }\limits _{x,{L_j}} \left\| {y - \varPhi x} \right\| _F^2 + \lambda \sum \limits _j {rank\left( {{R_j}x} \right) } \; . \end{aligned}$$

(1)

where $\left\| {\; \cdot \;} \right\| _F^2$ is the square sum of all elements.

Weighted nuclear norm [22] assigned larger weights to larger singular values and smaller weights to smaller ones. So smaller singular values are penalized more than larger ones. So the weighted nuclear norm based image CS model is represented as follows:

$$\begin{aligned} x = \mathop {\arg \min }\limits _x \left\| {y - \varPhi x} \right\| _F^2 + \lambda \sum \limits _j {\sum \limits _{i = 1}^{\min (d,h)} {{w_i}{\delta _i}\left( {{R_j}x} \right) } } \; . \end{aligned}$$

(2)

where ${w_i} = \rho \sqrt{h} /\left( {{\delta _i}\left( {A_j^s} \right) \mathrm{{ + }}\varepsilon } \right)$, $\rho$ is a normal number and $\varepsilon \mathrm{{ = }}{10^{\mathrm{{ - }}16}}$.

Since the largest r (the rank) singular values will not impact the rank, truncated schatten-p norm [24] abandoned them and only minimized the summation of surplus singular values to the power of p. Then the truncated schatten-p norm based image CS model is defined as

$$\begin{aligned} \left( {x,{A_j},{B_j}} \right) = \mathop {\arg \min }\limits _{x,{A_j},{B_j}} \left\| {y - \varPhi x} \right\| _F^2 + \lambda \sum \limits _j {\sum \limits _{i = 1}^{\min (d,h)} {\delta _i^p\left( {{R_j}x} \right) } \cdot \left( {1 - {\delta _i}\left( {B_j^T{A_j}} \right) } \right) } \; . \end{aligned}$$

(3)

Assume $U\varDelta {V^T}$ is the singular value decomposition of ${L_j}$, where $\varDelta \in {R^{d \times h}}$, $U = ({u_1}, \ldots {u_d}) \in {R^{d \times d}}$ and $V = ({v_1}, \ldots {v_h}) \in {R^{h \times h}}$, then $A \in {R^{r \times d}}$ and $B \in {R^{r \times h}}$ are the corresponding transposition of former r columns from U and V respectively.

3 Truncated Weighted Schatten-p Norm for Image Compressive Sensing Recovery

In this paper, to obtain better results of low-rank regularization problem, truncated weighted schatten-p norm regularization, which is taking advantages of both weighted nuclear norm and truncated schatten-p norm, is presented toward better exploiting low-rank property. Specially, we only minimize the summation of few smallest singular values to the power of p multiplied by the certain weights.

From the above analysis, our method can be modeled as

$$\begin{aligned} \left( {x,{A_j},{B_j},{w_i}} \right) \!=\! \mathop {\arg \min }\limits _{x,{A_j},{B_j},{w_i}} \left\| {y - \varPhi x} \right\| _F^2 + \lambda \sum \limits _j {\sum \limits _{i = 1}^{\min (d,h)} {{w_i}\delta _i^p\left( {{R_j}x} \right) } \left( {1 \!-\! {\delta _i}\left( {B_j^T{A_j}} \right) } \right) } \; . \end{aligned}$$

(4)

Except for the compressive measurements, all the other information cannot be known. We introduce auxiliary variables and address the above problem by alternating direction method of multipliers, where the image x, the block group ${R_j}x$ and the corresponding auxiliary variable ${L_j}$ are computed in turn. Then Eq. (4) can be reformulated as

$$\begin{aligned} \begin{array}{l} \left( {x,{A_j},{B_j},{w_i},{L_j}} \right) = \mathop {\arg \min }\limits _{x,{A_j},{B_j},{w_i},{L_j}} \left\| {y - \varPhi x} \right\| _F^2 + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\lambda \sum \limits _j {\left( {\sum \limits _{i = 1}^{\min (d,h)} {{w_i}\delta _i^p\left( {{L_j}} \right) \left( {1 - {\delta _i}\left( {B_j^T{A_j}} \right) } \right) } + \beta \left\| {{R_j}x - {L_j}} \right\| _F^2} \right) } \; \end{array} \; . \end{aligned}$$

(5)

Equation (5) contains the following four subproblems.

$$\begin{aligned} \left( {A_j^{t + 1},B_j^{t + 1}} \right) = \mathop {argmax}\limits _{{A_j},{B_j}} \sum \limits _{i = 1}^{\min (d,h)} {w_i^t\delta _i^p\left( {{L_j}} \right) } {\delta _i}\left( {B_j^T{A_j}} \right) \; . \end{aligned}$$

(6)

$$\begin{aligned} w_i^{t + 1} = \mathop {\arg \min }\limits _{{w_i}} \sum \limits _{i = 1}^{\min (d,h)} {{w_i}\delta _i^p\left( {{L_j}} \right) } \left( {1 - {\delta _i}\left( {{{\left( {B_j^{t + 1}} \right) }^T}A_j^{t + 1}} \right) } \right) \; . \end{aligned}$$

(7)

$$\begin{aligned} L_j^{t + 1} = \mathop {\arg \min }\limits _{{L_j}} \sum \limits _{i = 1}^{\min (d,h)} {w_i^{t + 1}\delta _i^p\left( {{L_j}} \right) } \left( {1 - {\delta _i}\left( {{{\left( {B_j^{t + 1}} \right) }^T}A_j^{t + 1}} \right) } \right) + \beta \left\| {{R_j}{x^t} - {L_j}} \right\| _F^2 \; . \end{aligned}$$

(8)

$$\begin{aligned} {x^{t + 1}} = \mathop {\arg \min }\limits _x \left\| {y - \varPhi x} \right\| _F^2 + \lambda \beta \sum \limits _j {\left\{ {\left\| {{R_j}x - L_j^{t + 1}} \right\| _F^2} \right\} } \; . \end{aligned}$$

(9)

3.1 $\left\{ {A_j},{B_j} \right\}$ Subproblem

According to the definition of truncated schatten-p norm [24], when ${A^{t + 1}}$ and ${B^{t + 1}}$ are calculated based on singular value decomposition of $L_j^t$, Eq. (6) gets the maximal value. Given intermediate estimated value $L_j^t$, we first calculate the singular value decomposition of $L_j^t$ ($\left[ {U_j^t,\varDelta _j^t,V_j^t} \right] = svd(L_j^t)$), and then estimate ${A^{t + 1}}$ and ${B^{t + 1}}$ by the following formula.

$$\begin{aligned} {A^{t + 1}} = {\left( {u_{{j_1}}^t, \ldots u_{{j_r}}^t} \right) ^T},\;\;{B^{t + 1}} = {\left( {v_{{j_1}}^t, \ldots v_{{j_r}}^t} \right) ^T} \; . \end{aligned}$$

(10)

3.2 ${w_j}$ Subproblem

Since the larger singular values are corresponding to the energy of the major components, they are more important than the smaller ones. According to the definition of weighted nuclear norm [22], we set

$$\begin{aligned} w_i^{t + 1} = \rho \sqrt{h} \,/\left( {{\delta _i}\left( {L_j^t} \right) \mathrm{{ + }} \varepsilon } \right) \; . \end{aligned}$$

(11)

3.3 ${L_j}$ subproblem

Although ${L_j}$ subproblem is nonconvex, we can obtain a suboptimal solution through a local minimization method referred to [4, 16, 24]. $g(\delta ) = w_i^{t + 1}\delta _i^p\left( {{L_j}} \right)$ $\left( {1 - {\delta _i}\left( {{{\left( {B_j^{t + 1}} \right) }^T}A_j^{t + 1}} \right) } \right)$ can be approximated using first-order Taylor expansion.

$$\begin{aligned} g(\delta ) = g({\delta ^k}) + \left\langle {\nabla g\left( {{\delta ^k}} \right) ,\delta - {\delta ^k}} \right\rangle . \end{aligned}$$

(12)

Suppose ${\delta ^{t + 1,k}} = \delta \left( {L_j^{t + 1,k}} \right)$ is the k-th iteration solution. Therefore, neglecting the constant term, Eq. (12) can be solved with by iteratively computing

$$\begin{aligned} \begin{array}{l} L_j^{t + 1,k + 1} = \\ \mathop {\arg \min }\limits _{{L_j}} \sum \limits _{i = 1}^{\min (d,h)} {w_i^{t + 1}p{{\left( {\delta _i^k} \right) }^{p - 1}}} \left( {1 - {\delta _i}\left( {{{\left( {B_j^{t + 1}} \right) }^T}A_j^{t + 1}} \right) } \right) {\delta _i} + \beta \left\| {{R_j}{x^t} - {L_j}} \right\| _F^2 \end{array} \; . \end{aligned}$$

(13)

Equation (13) denotes the weighted nuclear norm and has an analytical solution [4, 16, 24].

3.4 x Subproblem

Equation (9) is a quadratic problem and has a closed-form solution.

$$\begin{aligned} {x^{s + 1}} = {\left( {{\varPhi ^T}\varPhi \mathrm{{ + }}\lambda \beta \sum \limits _j {R_j^T{R_j}} } \right) ^{ - 1}}\left( {{\varPhi ^T}y + \lambda \beta \sum \limits _j {R_j^TL_j^{t + 1}} } \right) \; . \end{aligned}$$

(14)

When an estimated image x is obtained, the variables ${w_j}$, ${A_j}$, ${B_j}$ and ${L_j}$ can be updated. Then ${L_j}$ is used to obtain a better estimated image. This process continues to iterate until convergence. The algorithm is summarized as bellows.

4 Experimental Results

In order to prove the effectiveness of our model, TWSP is compared with total variation based method (TV) [25], low-rank regularization based method (NLR) [16], weighted nuclear norm based method (WNN) [22] and truncated schatten-p norm based method (TSPN) [24]. Note that TV exploits the gradient sparsity; NLR, WNN and TSPN all employ nonconvex substitution function to exploit nonlocal low-rank property; TSPN shows the current state-of-the-art performance.

The parameters are set as follows: random sampling rate is $\frac{{100m}}{n}\%$; the size of block is $6 \times 6$ and the number of similar blocks is 45; we divide the image into overlapping blocks into reference blocks for every five pixels; the regularization parameter p is 0.6, r is 4, $\lambda$ and $\beta$ are tuned separately for each sampling rate. Eight test natural images are used which are shown in Fig. 1. The Peak Signal-to-Noise Ratio (PSNR) is employed to evaluate the different recovery results.

4.1 Experiments on Noiseless Measurements

The PSNR comparison when the sampling rates are 2.5%, 5%, 10%, 15% and 20% is provided in Table 1. From Table 1, we can see that (1) WNN, TSPN and TWSP outperform NLR for almost all the situations; (2) on average, WNN and TSPN get similar recovery results; (3) TWSP obtains the highest PSNRs in all the cases; (4) The average PSNR gains of TWSP over TV, NLR, WNN and TSPN are 3.66 dB, 1.57 dB, 0.39 dB and 0.36 dB respectively with 2.5% sampling rate. The visual results of three images are provided as Figs. 2, 3, and 4. We can see that TWSP can better exploit the nonlocal low-rank property and shows better performance than NLR, WNN and TSPN.

Table 1. The PSNR (dB) results on noiseless measurements

Fig. 1.

Eight test images. (a) Barbara; (b) House; (c) Lena; (d) Cameraman; (e) Foreman; (f) Monarch; (g) Leaves; (h) Vessels.

Fig. 2.

Recovered Barbara with 5% sampling rate. (a) Original image; (b) NLR recovery (29.79 dB); (c) WNN recovery (30.54 dB); (d) TSPN recovery (30.63 dB); (e) TWSP recovery (30.81 dB).

Fig. 3.

Recovered Monarch with 2.5% sampling rate. (a) Original image; (b) NLR recovery (23.76 dB); (c) WNN recovery (24.91 dB); (d) TSPN recovery (24.74 dB); (e) TWSP recovery (25.32 dB).

Fig. 4.

Recovered Leaves with 2.5% sampling rate. (a) Original image; (b) NLR recovery (18.24 dB); (c) WNN recovery (20.87 dB); (d) TSPN recovery (21.27 dB); (e) TWSP recovery (21.56 dB).

4.2 Experiments on Noisy Measurements

In this subsection, experiments with noisy measurements are carried out to verify the robustness of TWSP approach to Gaussian White noise. The sampling rate is 20%. The signal-to-noise ratio ($SNR = 20*\log \frac{{\bar{A}}}{{\bar{D}}}$), where ${\bar{A}}$ is the average value and ${\bar{D}}$ is the standard derivation of noise, varies from 15dB to 35 dB. The PSNR comparisons when SNR is 15 dB, 20 dB, 25 dB, 30 dB and 35 dB are provided in Table 2. TWSP achieves the highest PSNR results among all the methods. The average PSNR gains of TWSP over TV, NLR, WNN and TSPN can be as much as 5.07 dB, 2.80 dB, 1.80 dB and 1.82 dB respectively when SNR=15dB. Some visual results are shown in Figs. 5, 6 and 7, which verify the superiority of our proposed TWSP approach.

Table 2. The PSNR (dB) results of different methods on noisy measurements

Fig. 5.

Recovered Cameraman with SNR = 35 dB. (a) Original image; (b) NLR recovery (35.77 dB); (c) WNN recovery (37.04 dB); (d) TSPN recovery (36.99 dB); (e) TWSP recovery (38.11 dB).

Fig. 6.

Recovered Foreman with SNR = 30 dB. (a) Original image; (b) NLR recovery (35.47 dB); (c) WNN recovery (37.16 dB); (d) TSPN recovery (36.96 dB); (e) TWSP recovery (39.27 dB).

Fig. 7.

Recovered of Leaves with SNR = 35 dB. (a) Original image; (b) NLR recovery (35.80 dB); (c) WNN recovery (36.73 dB); (d) TSPN recovery (36.32 dB); (e) TWSP recovery (38.29 dB).

5 Conclusion

In this paper, we have presented a new approach toward image recovery via truncated weighted schatten-p norm which is taking advantages of both weighted nuclear norm and truncated schatten-p norm. Truncated weighted schatten-p norm can better exploit the nonlocal low-rank property than current CS methods based on low-rank regularization. In addition, we also propose an efficient iterative scheme based on alternating direction method of multipliers to accurately solve the nonconvex optimization model. Experimental results demonstrate that our proposed algorithm is exceeding the existing state-of-the-art methods, in terms of subjective and objective qualities.