The single image super-resolution (SISR) problem represents a class of efficient models appealing in many computer vision applications. In this paper, we focus on designing a proximal symmetric alternating direction method of multipliers (SADMM) for the SISR problem. By taking full exploitation of the special structure, the method enjoys the advantage of being easily implementable by linearizing the quadratic term of subproblems in the SISR problem. With this linearization, the resulting subproblems easily achieve closed-form solutions. A global convergence result is established for the proposed method. Preliminary numerical results demonstrate that the proposed method is efficient and the computing time is saved by nearly 40% compared with several state-of-the-art methods.
Notes
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
BG proposed the main algorithm and drafted the manuscript. FS participated in the design of the method. YT participated in the design of the study and performed the experiment part. SX conceived of the study and helped to draft the manuscript. All authors read and approved the final manuscript.
1 Introduction
SISR is a technique that aims at restoring a high-resolution (HR) image from a single degraded low-resolution (LR) image. Since the HR image contains more details than the LR one, the image of HR is preferred in many practical cases, such as video surveillance, the hyperspectral technique, and remote sensing. Super-resolution (SR) is a typical ill-posed inverse problem since a multiplicity of solutions exist for any input LR pixel [1]. To tackle such a problem, most of the SR methods reduce the size of the solution space by incorporating strong prior information, which can be obtained by training data, using various regularization methods, and capturing specific image features [2]. Motivated by those ideas, the SISR schemes can be broadly divided into three categories: interpolation-based methods, learning-based methods, and reconstruction-based methods.
Interpolation-based methods such as the bicubic approach are simple and easy to implement but tend to blur the high frequency details and produce aliasing artifacts at salient edges [3]. The learning-based algorithms recover the missing high frequency details by learning the relations between LR and HR image patches from a given database [4]. However, they highly rely on the similarity between the training set and the test images and generally have high computational complexity. Reconstruction-based methods that are considered in this paper belong to the third category of SISR schemes [5‐7]. As SISR essentially is a highly ill-posed problem, the performance of such approaches mainly relies on the prior knowledge. Among all the priors, smoothness priors such as the total variation (TV) prior have been widely used in many image processing applications [8]. To reduce its computational complexity, a fast SR alternating direction method of multipliers (FSR-ADMM) based on the TV model is proposed in [9]. Considering the efficiency of a symmetric alternating direction method of multipliers (SADMM) [10], our paper aims at constructing a fast SR symmetric alternating direction method of multipliers (FSR-SADMM).
Advertisement
In the SISR problem, the observed LR image is modeled as a noisy version of the blurred and downsampled HR image estimated as follows:
$$ y=\Phi Hx+\nu, $$
(1.1)
where the vector \(y \in\mathbb{R}^{N_{l}}\) (\(N_{l}=m_{l}\times n_{l}\)) corresponds to the LR observed image and \(x \in\mathbb{R}^{N_{h}}\) (\(N_{h}= m_{h}\times n_{h}\)) denotes the HR image with \(N_{h}> N_{l}\). \(\nu\in\mathbb{R}^{N_{l}}\) represents a zero-mean additive white Gaussian noise (AWGN), \(\Phi \in\mathbb{R}^{N_{l}\times N_{h}}\) and \(H \in\mathbb {R}^{N_{h}\times N_{h}}\) stand for the downsampling and the blurring operations, respectively.
Concisely, the SISR TV model corresponds to solving the following optimization problem:
where \(\|y - \Phi Hx\|_{2}^{2}\) stands for the data fidelity term while \(\|x\|_{\mathrm{TV}}=\phi(Ax)= \sqrt{\|\nabla_{h}x\| _{2}^{2}+\|\nabla_{\nu}x\|_{2}^{2}}\) represents the regularization1 prior with \(A=[\nabla _{h},\nabla_{\nu}]^{\mathsf{T}}\in \mathbb{R}^{2N_{h}\times N_{h}}\), and α denotes the regularization parameter balancing the regularization term and the data fidelity term. The direct ADMM in [6] is given hereinafter which first rewrites the problem (1.2) as
$$\begin{aligned} &\min_{x,z,u} \frac{1}{2} \|y - \Phi {z} \|_{2}^{2} + \alpha \phi(u) \\ &\quad \text{s.t. } H x = z, \\ &\hphantom{\quad \text{s.t. }}A x = u, \end{aligned}$$
Recently, Zhao et al. [9] proposed a fast single image super-resolution by adopting a new efficient analytical solution for \(\ell_{2}\)-norm regularized problems, which can reduce the number of iterations in each loop from five steps to three steps by tackling the downsampling operator Φ and the blurring operator H simultaneously. By rewriting (1.2) as the following constrained optimization problem:
$$ \begin{aligned} &\min_{x,u} \frac{1}{2} \|y - \Phi Hx \|_{2}^{2} + \alpha \phi(u) \\ &\quad \text{s.t. } A x = u, \end{aligned} $$
(1.4)
they proposed the easier ADMM-type iterative scheme, i.e., FSR-ADMM:
As to such an expensive inversion process, the methods to alleviate the computational burden can be roughly categorized into two main categories, one is to ideally assume \(A^{\mathsf{T}}A=I\). Then such formula can be solved efficiently by a Thomas algorithm in \(32N_{h}^{2}\) flops [11]. The other option is to establish a block circulant matrix with circulant blocks (BCCB) A. Under such conditions, the Woodbury formula can be utilized to decrease the order of computation complexity from \(\mathcal{O} (8N_{h}^{3})\) to \(\mathcal{O}(2N_{h}\log2N_{h})\) [9]. Nevertheless, in realistic settings the problem is that one does not necessarily know in advance if the BCCB assumption is good for SISR because it may lead to the appearance of ringing artifacts emanating from the boundaries, which is a well-known mismatch and degradation consequence of such deconvolved images [12].
To alleviate the above dilemma and further apply FSR-ADMM into wider scenarios with proper matrix A, we propose a new method with two-fold solution. (1) Compute \((H^{\mathsf{T}}\Phi^{\mathsf{T}}\Phi H+\frac{\mu}{\tau }I_{N_{h}})^{-1}\) instead of computing \((H^{\mathsf{T}}\Phi^{\mathsf{T}}\Phi H+ {\mu} A^{\mathsf{T}}A)^{-1}\) so as to bypass the need of special condition of A. (2) Accelerate FSR-ADMM by introducing a new dual multiplier \(\lambda ^{k+\frac{1}{2}} \).
In light of the above analysis, this paper proposes the following iterative scheme based on semiproximal symmetric ADMM (FSR-SADMM):2
In a nutshell, the contributions of this article can be summarized as follows:
1.
We propose a customized semiproximal term especially suitable for SR imaging system which can avoid computing some boring matrix inversion such as \((H^{\mathsf{T}}\Phi^{\mathsf{T}}\Phi H+\mu A^{\mathsf{T}}A)^{-1}\) existing in (1.5a). Consequently, FSR-SADMM can be applied in wider scenarios without a strict condition of A.
2.
Based on the iterative scheme of strictly contractive semiproximal Peaceman-Rachford splitting method, our proposed FSR-SADMM can significantly reduce the total iteration count while only involving additional dual update (i.e., \(\lambda^{k+\frac {1}{2}}\)) which added negligible computational burden for each iteration. As a result, our proposed FSR-SADMM prefers to maintain a better convergence rate which can experimentally reduce the computing time by 40%.
3.
We prove that the FSR-SADMM is convergent under mild conditions.
Advertisement
The rest of this paper is organized as follows. In Section 2, we present some preliminaries which are useful for the subsequent analysis. In Section 3, we illustrate the FSR-SADMM to reconstruct the single image super-resolution. Section 4 provides convergence analysis of the proposed method. Section 5 presents extensive numerical results that evaluate the performance of the proposed reconstruction algorithm in comparison with some state-of-the-art algorithms. Finally, concluding remarks are provided in Section 6.
In this section, following He and Yuan’s approach [13], we reformulate the convex minimization model (1.4) as a variational form, which is useful for succedent algorithmic illustration and convergence analysis. Let us denote \(z_{1}=x\), \(z_{2}=u\), \(B_{1}=A\), \(B_{2}=-I_{2N_{h}}\), then (1.4) becomes
where \(\theta_{1}(z_{1})=\frac{1}{2\mu}\|y-\Phi H z_{1}\|_{2}^{2}\) and \(\theta _{2}(z_{2})=\alpha\phi(z_{2})\). The Lagrangian function and augmented Lagrangian function of (2.1) can be written as
respectively, where \(\lambda\in \mathbb{R}^{2N_{h}}\) is a Lagrangian multiplier. Then seeking a saddle point of \(L(z_{1},z_{2},\lambda)\) is to find \((z_{1}^{*},z_{2}^{*},\lambda^{*})\) such that
Note that the mapping \(F(w)\) defined in (2.8) is affine with a skew-symmetric matrix, it is monotone. We denote by \(\Omega^{*}\) the solution set of \(\operatorname{VI}(\Omega,F,\theta)\).
2.2 Some notations
We use \(\|\cdot\|\) to denote the 2-norm of a vector and let \(\|z\| _{G}^{2} = z^{\mathsf{T}} Gz\) for \(z \in \mathbb{R}^{N}\) and \(G \in \mathbb{R}^{N \times N}\). For a real symmetric matrix S, we denote \({S}\succeq0\) (\({S}\succ0\)) if S is positive semidefinite (positive definite). For convenient analysis, we define the following matrices:
Below we prove three assertions regarding the matrices just defined. These assertions make it possible to present our convergence analysis for the new algorithm compactly with alleviated notation.
Lemma 2.1
If\(R\succ0\), \(\mu\in(0,1)\), \(r\in(0,1)\), \(s\in(0,1]\), and\(B_{2}\)is full column rank, then the matricesH, M, andQdefined, respectively, in (2.9), (2.10), and (2.11) satisfy
Thus H and G are positive definite and positive semidefinite, respectively. Here, we would emphasize that we do not require the positive definiteness of G. Instead, positive semidefiniteness of G is enough for our algorithmic analysis. □
3 Algorithm
3.1 FSR-SADMM
In this section, we will present our new algorithm to solve (1.4). But we first present the iterative scheme by using the standard strictly contractive Peaceman-Rachford splitting method with two different relaxation factors:
where \(R=\frac{\mu}{\tau}I_{N_{h}}-\mu B_{1}^{\mathsf{T}} B_{1}\) is a customized semidefinite matrix.
3.2 Related methods
The methods proposed in [14] and [15] belong to the category of SADMM-type approaches with logarithmic-quadratic proximal regularization, which have larger step sizes compared with SADMM. The former is with the step sizes of \(r\in (0,1)\), \(s\in(0,1)\) while the latter \(s\in(0,2)\), \(r\in(0,2-s)\), which are different from \(r\in(0,1)\), \(s\in(0,1]\) considered in this paper. The parameters r and s in SADMM have also been studied intensively by He et al. [16] and Gu et al. [15]. However, both of them cannot fully utilize the special structure of SISR scenarios involved in this paper. And computing \((H^{\mathsf{T}}\Phi^{\mathsf{T}}\Phi H+\mu A^{\mathsf{T}} A)^{-1}\) cannot be avoided.
4 Global convergence
To make the analysis more elegant, we reformulate FSR-SADMM (3.2a)-(3.2d) into the form3
Now we analyze the convergence for our proposed FSR-SADMM (4.1a)-(4.1d). We prove its global convergence from the contraction perspective. In order to further alleviate the notation in our analysis, we define an auxiliary sequence \(\tilde{w}^{k}\) as
Now we start to prove some properties for the sequence \(\{\tilde{w}^{k}\} \) defined in (4.2). We are interested in estimating how accurate the point \(\tilde{w}^{k}\) is to a solution point \(w^{*}\) of \(\operatorname{VI}(\Omega,F,\theta)\). The main result is proved in Theorem 4.1. To prove this main result, we require two lemmas. The first key lemma provides a lower bound on specially constructed functional in terms of a quadratic term involving the matrix Q defined in (2.11).
Lemma 4.1
For given\(w^{k}\in\Omega\), let\(w^{k+1}\)be generated by FSR-SADMM (4.1a)-(4.1d) and\(\tilde{w}^{k}\)be defined in (4.2). Then we have\(\tilde{w}\in\Omega\)and
By using the notation of Q in (2.11), and w and F in (2.8), the compact form of the above inequality is exactly (4.4). □
In the next lemma, we further analyze the right-hand side of the inequality (4.4) and reformulate it as the sum of some quadratic terms. This new form is more convenient for our further analysis.
Lemma 4.2
For given\(w^{k}\in\Omega\), let\(w^{k+1}\)be generated by FSR-SADMM (4.1a)-(4.1d) and\(\tilde{w}^{k}\)be defined in (4.2). Then for any\(w\in\Omega\), we get
Substituting it in (4.15) and considering (4.13), we immediately obtain the assertion (4.12). The proof is complete. □
Now, we try to find a lower bound in terms of the discrepancy between \(\|w-w^{k+1}\|_{H}^{2}\) and \(\|w-w^{k}\| _{H}^{2}\) for any \(w\in\Omega\).
Theorem 4.1
For given\(w^{k}\in\Omega\), let\(w^{k+1}\)be generated by FSR-SADMM (4.1a)-(4.1d) and\(\tilde{w}^{k}\)be defined in (4.2). Then for any\(w\in\Omega\), we have
The assertion (4.16) holds immediately from (4.12) and (4.18). The proof is complete. □
The next lemma demonstrates the contraction property of the sequence \((w^{k})_{k=0}^{\infty}\) generated by FSR-SADMM (4.1a)-(4.1d).
Lemma 4.3
Let\((w^{k})_{k=0}^{\infty}\)be the sequence generated by the FSR-SADMM (4.1a)-(4.1d) and\(\{\tilde{w}^{k}\}\)be defined in (4.2). Then for any\(w^{*}\in\Omega^{*}\), we have
where the last inequality follows from the fact that \(w^{*}\in\Omega^{*}\) (see (2.6)). The proof is complete. □
Recall that for the case \(0< r<1\), \(0< s<1\), the matrix G is positive definite, while when \(0< r<1\), \(s=1\), G may not be positive definite. We need further investigate the term \(\|w^{k}-\tilde{w}^{k}\|^{2}_{G}\). For the case \(0< r<1\), \(s=1\), we have
Recall \(\tilde{w}^{k}\) defined by (4.2) and combining with (4.19), we have the following lemma, which is important for the proof of the convergence.
Lemma 4.4
Let\((w^{k})_{k=0}^{\infty}\)be the sequence generated by the FSR-SADMM (4.1a)-(4.1d) with\(r\in (0,1)\), \(s=1\), and\(\{\tilde{w}^{k}\}\)be defined in (4.2). Then we have
With the above lemmas, we are now ready to establish the global convergence of FSR-SADMM for solving \(\operatorname{VI}(\Omega,F,\theta)\).
Theorem 4.2
The sequence\((w^{k})_{k=0}^{\infty}\)generated by FSR-SADMM (4.1a)-(4.1d) converges to some\(w^{\infty}\)that is a solution of\(\operatorname{VI}(\Omega,F,\theta)\).
Proof
(I) For the case \(r\in(0,1)\), \(s\in(0,1)\). Summing (4.19) over \(k = 0, \ldots,\infty\) yields
Recall the sequence \(\{w^{k}\}\) is bounded (see Lemma 4.3), we see that the sequence \(\{\tilde{w}^{k}\}\) is also bounded, and it has at least one cluster point. Let \(w^{\infty}\) be a cluster of \(\{\tilde {w}^{k}\}\) and the subsequence \(\tilde{w}^{k_{j}}\) converge to \(w^{\infty }\). Combining (4.4) and (4.31), we get
which implies that \(w^{\infty}\in\Omega^{*}\). From \(\lim_{k\rightarrow\infty}\|w^{k}-\tilde{w}^{k}\|_{G}=0\), we can deduce \(\lim_{k\rightarrow\infty}\|w^{k}-{w}^{k}\|_{{H}}=0\). Recall \(\{\tilde{w}^{k_{j}}\}\rightarrow w^{\infty}\), thus for any given \(\epsilon>0\), there exists an integer l such that
Recall the bounded sequence \(\{w^{k}\}\) again, we see that the sequence \(\{\tilde{w}^{k}\}\) is also bounded, and it has at least one cluster point. The following proof for the assertion is similar and omitted. □
5 Numerical results
In this section, we study the performance of the FSR-SADMM for solving (1.2). Our codes were written in MATLAB R2014a. In addition, all of the experiments were performed on a laptop with an Intel Core 2 Duo CPU at 2.2 GHz and 2 GB memory.5
Experiments were conducted on three different text images: Peppers, Lena, and Baboon. Images are all with \(256\times256\times3\) RGB images. Color images were processed using the illuminate channel only, as in [9]. Precisely, the RGB images were transformed into YUV coordinates and the color channels (Cb, Cr) were upsampled using bicubic interpolation. The results were quantitatively evaluated by using the standard peak signal-to-noise ratio (PSNR) [17], defined as
where x and x̂ are the original and reconstructed images, L denotes the maximum intensity value in x. We compare direct ADMM, FSR-ADMM and FSR-SADMM under the stop criterion such as \(\frac{\|x^{k}-x^{k-1}\|}{\|x^{k-1}\|}<\{1e^{-6},1e^{-5},1e^{-4}\}\).
Figures 1-3 compare the PSNR outputs of our FSR-SADMM with direct ADMM and FSR-ADMM, while Figure 4 depicts the comparison of total computational time of the three methods. Direct ADMM splits the super-resolution imaging problem into three subproblems by using two dual multipliers while FSR-ADMM reduces the computational complexity of each iteration by efficiently reducing the order of computation complexity of their subproblems from \(\mathcal {O} (N_{h}^{3})\) to \(\mathcal{O}(N_{h}\log N_{h})\). Similarly, our FSR-SADMM has the computation complexity of \(\mathcal{O}(N_{h}\log N_{h})\) and shares much better convergence performance. In our experiments, we set \(\mu =0.005\) for all three methods. In all figures, we list the PSNR below the reconstructed image corresponding to compared methods. As the reconstructed images shown in Figures 1-3, there are not noticeable differences in the texture of the Peppers, the wrinkles on the eyes of Lena, and also hair on Boboon’s nose. FSR-SADMM can only get a little higher PSNR rather than Direct ADMM and FSR-ADMM for various tolerance. However, the results shown in Figure 4 indicate that, compared with FSR-ADMM, our FSR-SADMM saves roughly 45% computational time with high precision \(\mathrm{Tolerance}=10^{-6}\) and can still save roughly 20% computational time under low precision \(\mathrm{Tolerance}=10^{-4}\). On the whole average, 30% computational time can be reduced, which efficiently accelerates the super-resolution imaging process.
Figure 1
From left to right: super-resolutionPeppersby direct ADMM, FSR-ADMM, and FSR-SADMM.
Figure 2
From left to right: super-resolutionLenaby direct ADMM, FSR-ADMM, and FSR-SADMM.
Figure 3
From left to right: super-resolutionBaboonby direct ADMM, FSR-ADMM, and FSR-SADMM.
Figure 4
The original signal, noisy measurement, and reconstruction results by using different methods.
×
×
×
×
We also test the influence of relaxation parameter r for FSR-SADMM. We fix \(s=1\), \(\mu=0.005\) and choose different values of r in the interval \([0.3,1]\) (more specifically, we choose \(r=\{ 0.3,0.5,0.7,0.9,1\}\)). For comparison purposes, we also plot for FSR-ADMM with \(\mu=0.005\). As shown in Figure 5, we see that the relaxation parameter r works well for a wide range of values. In particular, when \(r\geq0.9\), the PSNR cannot be improved and even decrease in the first 20 iterations, while the effectiveness of the improvement of PSNR is not obvious especially when r is less than or equal to 0.3. As such, some offending values for the interval \([0.7,0.9]\) are preferred.
Figure 5
Evolutions of PSNR with respect to iterations forPeppersunder different parameter r.
×
From Table 1, our proposed FSR-SADMM outperforms ADMM and FSR-ADMM for all the tolerance. Especially, FSR-SADMM costs much less computing time and has a shorter iteration number for tolerance with higher precision such as 10−6.
Table 1
The performance of different SADMM-type algorithms in terms of PSNR and SSIM
Tolerance
Images
Peppers
Lena
Baboon
PSNR (dB)
Time (sec.)
Iter.
PSNR (dB)
Time (sec.)
Iter.
PSNR (dB)
Time (sec.)
Iter.
10−6
ADMM
30.6
205
1,420
30.9
246
1,725
22.5
274
1,941
FSR-ADMM
FSR-SADMM
10−5
ADMM
30.6
80.7
566
31
94.3
667
22.5
111
783
FSR-ADMM
FSR-SADMM
10−4
ADMM
30.6
21
150
31.2
19.8
136
22.6
46.8
333
FSR-ADMM
FSR-SADMM
The and for each algorithm are indicated by and , respectively, with respect to r = 0.6.
6 Conclusions
For solving the SISR problem (1.2), we proposed a new algorithm based on the strictly contractive semiproximal Peaceman-Rachford splitting method in this paper. The global convergence of our algorithm is established. Then the computational results indicate that our algorithm achieves better performance compared with start-of-the-art methods including direct ADMM and FSR-ADMM. More specifically with \(\mathrm{Tolerance}=10^{-6}\), our algorithm can save computing time about 80% and 45% compared with direct ADMM and FSR-ADMM, respectively.
Acknowledgements
This research was supported by Jiangsu Key Laboratory of Meteorological Observation and Information Processing Foundation (KDXS1503).
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
BG proposed the main algorithm and drafted the manuscript. FS participated in the design of the method. YT participated in the design of the study and performed the experiment part. SX conceived of the study and helped to draft the manuscript. All authors read and approved the final manuscript.
As our proposed method can be applied in the two different TV models in a similar way, we just consider the isotropical model and omit the anisotropical case.
Note that the proximal term \(\frac{\mu}{2}\|z_{1}-z_{1}^{k}\|^{2}_{R}\) plays an important role to linearize the term \(-(\lambda^{k})^{\mathsf{T}}B_{1}z_{1}+\frac{\mu }{2}\|B_{1}z_{1}-B_{2}z_{2}^{k} \|_{2}^{2}\) so as to avoid computing \((H^{\mathsf{T}}\Phi ^{\mathsf{T}}\Phi H+\mu B_{1}^{\mathsf{T}}B_{1})^{-1}\) to find an analytical solution of (1.7a). In fact, many manuscripts using approximate linearization process [18], they first denote \(h(x)=\frac {1}{2}\|B_{1}z_{1}-B_{2}z_{2}^{k}-\lambda^{k}/\mu\|_{2}^{2}\), given the Lipschitz constant τ, and use the Taylor approximation \(h(x)=\nabla h(z_{1}^{k})(z_{1}-z_{1}^{k})+\frac{1}{\tau}\|z_{1}-z_{1}^{k}\|^{2}_{2}\) to approximate the term \(\mu\|B_{1}z_{1}-z_{2}^{k}-\lambda^{k}/\mu \|_{2}^{2}\), which increases the difficulty of convergence analysis and needs a specific customized stop criterion [19].
Note that in this paper \(B_{2}^{\mathsf{T}}B_{2}=I_{2N_{h}}\), R is assumed to be semidefinite and the last term in (4.37) is deduced with the aid of (4.22).
and
for each algorithm are indicated by
and
, respectively, with respect to r = 0.6.