Image superresolution (SR) is a technique aiming at the estimation of a highresolution (HR) image from one or several lowresolution (LR) observation images, which is widely used in remote sensing, biometrics identification, medical imaging, video surveillance, etc. There are three categories of super resolution methods. Interpolation methods are simple but short of highfrequency component, while reconstructed methods degrade rapidly when the desired magnification factor is large.
Recently, the third category called learning based methods are developed, which become the most active research area. In this method, a HR image can be predicted by learning the cooccurrence relationship between a set of LR example patches and corresponding HR patches. Standard methods are example based method^{[1]}, neighbor embedding^{[2]}, etc. Motivated by compressive sensing theories^{[3]}, Ref.[4] proposed an algorithm which used sparse representation of the input LR image to reconstruct the corresponding HR image with two jointly trained dictionaries. The method used the inherent data message, mapped the data in some dictionaries, and reflected the data information by some sparse coefficients, which turned out to reconstruct the HR image greatly.
There are many classic sparse representation methods. Greedy methods, like orthogonal matching pursuit (OMP^{[5]}), attack the problem heuristically by fitting the sparse models using greedy stepwise least squares. But they are often computationally slow. The least angel regression (LARS^{[6]}) algorithm adds a new element to the active set of nonzero coefficients by taking a step along a direction having equal angles with the vectors in the active set at each iteration. But when the iteration number is large, the method is not efficient. Preconditioned conjugate gradients (PCG^{[7]}) uses the internal Newton's method to minimize the logarithmic barrier function and receives good results. But it is timeconsuming.
In this paper, the feature sign method for single image SR via sparse representation is proposed which can overcome above drawbacks. By determining the sign of the sparse coefficients, the nondifferentiable problem is changed to an unconstrained quadratic optimization problem (QP) which can be solved easily. It is competent to capture the sparse coefficient of data in an overcompleted dictionary efficiently and rapidly. Simulation results demonstrate that it obtains better reconstruction performance qualitatively and quantitatively over other classic SR methods.
1 Single Image SR Using Sparse RepresentationThe superresolution image reconstruction problem is known to be an illposed inverse problem. Various approaches have been proposed to regularize it, while they all share two parts of constraints priors:
$\mathit{\boldsymbol{U}}(x) = \left\ {y  \mathit{\boldsymbol{H}}x} \right\_2^2 + \lambda \mathit{\boldsymbol{E}}(x)$  (1) 
where
In this paper, the
$\min {\left\ {{\alpha _i}} \right\_1}{\rm{s}}{\rm{.t}}{\rm{.}}\left\{ \begin{array}{l} \mathit{\boldsymbol{F}}\left\ {{\mathit{\boldsymbol{Z}}_l}{\alpha _i}  {y_i}} \right\_2^2 \le {\varepsilon _1}\\ \mathit{\boldsymbol{F}}\left\ {{x_i}  {\mathit{\boldsymbol{Z}}_h}{\alpha _i}} \right\_2^2 \le {\varepsilon _2}\\ \left\ {\mathit{\boldsymbol{R}}{\mathit{\boldsymbol{Z}}_h}{\alpha _i}  \mathit{\boldsymbol{v}}} \right\ \le {\varepsilon _3} \end{array} \right.$  (2) 
where
The SR algorithm is a patchwise based sparse recovery with the joint learning dictionaries. The input LR image
In this work, the pair of overcomplete dictionary
$\begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{Z}}_h},{\mathit{\boldsymbol{Z}}_l},\{ {\alpha _i}\} _{i = 1}^N} \sum\limits_{i = 1}^N {(\left\ {{x_i}  {\mathit{\boldsymbol{Z}}_h}{\alpha _i}} \right\_2^2} + \left\ {{y_i}  {\mathit{\boldsymbol{Z}}_l}{\alpha _i}} \right\_2^2) + \lambda {\left\ {{\alpha _i}} \right\_1}\\ \;\;\;\;\;\;\;\;\;\;{\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;{\left\ {{\mathit{\boldsymbol{Z}}_x}(:,k)} \right\_2} \le 1,{\left\ {{\mathit{\boldsymbol{Z}}_y}(:,k)} \right\_2} \le 1 \end{array}$  (3) 
How to solve formula (2) fast and efficiently is the fundamental of sparse representation and quality determination of reconstructed HR image. It is a typical
To keep it simple, it can be rewritten in a vector form as:
${\min _\alpha }\sum\limits_{i = 1}^m {\left\ {{y_i}  \mathit{\boldsymbol{Z}}{\alpha _i}} \right\_2^2} + \lambda \sum\limits_{i = 1}^m {{{\left\ {{\alpha _i}} \right\}_1}} $  (4) 
Let
${\min _{{\alpha _i}}}p({\alpha _i}) = \left\ {{y_i}  \mathit{\boldsymbol{Z}}{\alpha _i}} \right\_2^2 + \lambda \sum\limits_{j = 1}^k {\left {{\alpha _i}^{(j)}} \right} $  (5) 
If the sign of
The sign can be settled by 4 steps:
1) Define
2) If
3) So the optimality conditions for achieving the optimal value of
$\left\{ \begin{array}{l} {\nabla _i}^{(j)}f({\alpha _i}) + \lambda {\rm{sign}}({\alpha _i}^{(j)}) = 0\;\;\;\;{\rm{if}}\;\left {{\alpha _i}^{(j)}} \right > 0\\ \left {{\nabla _i}^{(j)}f({\alpha _i})} \right \le \lambda \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{if}}\;{\alpha _i}^{(j)} = 0 \end{array} \right.$  (6) 
4) Consider how to select the optimal subgradient
The algorithmic procedure of learning coefficients using feature sign is described in the following 5 steps.
An active set
1) Initialize:
2) Activate: From zero coefficient of
3) Feature sign: Let
$\min p({\hat \alpha _i}) = {y_i}  \mathit{\boldsymbol{\hat Z}}{\hat \alpha _i}_2^2 + \lambda {\mathit{\boldsymbol{\hat \beta }}^{\rm{T}}}{\hat \alpha _i}$  (7) 
Let
${\hat \alpha _i}^{{\rm{new}}} = {({\mathit{\boldsymbol{\hat Z}}^{\rm{T}}}\mathit{\boldsymbol{\hat Z}})^{  1}}({\mathit{\boldsymbol{\hat Z}}^{\rm{T}}}{y_i}  \lambda \mathit{\boldsymbol{\hat \beta }})$  (8) 
Perform a discrete line search on the closed line segment from
4) Check the optimality conditions: Check the optimality conditions based on formula (6);
5) Output: The optimal coefficient matrix is
In the following section, simulation results are given to illustrate the performance of our scheme. The simulation and comparison are carried out by Matlab implementations. All experiments are executed on a 2.33 GHz Intel Core 2 Quad CPU Q8200 processor with 2 GB memory in Windows XP OS.
This paper samples 20 000 HR and LR patch pairs from the training images to learn the overcomplete dictionary randomly.
In this part, some experiments are conducted to compare the proposed method and other sparse representation methods. Contrast algorithms are classic interpolation method bicubic, and sparse representation methods OMP^{[5]}, LARS^{[6]}, PCG ^{[7]}.
Bicubic reconstructed images are quite fuzzy for lacking of high frequencies while OMP, LARS, and PCG images are short of image details. The edge blur and sawtooth effect are much more obvious in bicubic, OMP, LARS, and PCG, while feature sign pictures are more distinct and clearer. Specifically, as Fig.1 shows, the line of the hat in Lena picture is more fluent and distinct than others in the reconstructed picture. And from the white part of the orange magnified in Fig.2, the proposed method has the clearest picture. Comparing the water ripple in yacht picture, bicubic picture is quite fuzzy, LARS, OMP, PCG pictures have blocking artifact, and the feature sign picture is more discerning.
Table 1 compares the RMSEs of the reconstructed images generated by different methods with different input images. The results show that the proposed algorithm achieves the lowest RMSE against bicubic, LARS, OMP, and PCG. Illustrated by the case of Lena, the RMSE reductions of feature sign over bicubic, LARS, OMP, and PCG are 1.472 1, 0.494 6, 0.480 3, and 0.391 9 respectively.
The reconstruction time of the algorithms is shown in table 2. It can be concluded that the feature sign method yields the best performance with almost the least time. The time of proposed method is nearly one half of LARS and one percent of PCG.
As table 3 presents, the feature sign method can yield the biggest SSIM number, which indicates that the feature sign method can best restore the image. Furthermore, using the feature sign method can improve the efficiency of sparse representation in super resolution.
To test the efficiency of the proposed method more comprehensively, 100 SR experiments are performed by using different algorithms. The 100 test images are downloaded from the international open source image library. The average of RMSE and SSIM are computed in Table 4.
From table 4, the feature sign method yields the lowest RMSE with much less time, also the SSIM value is the biggest, It demonstrates the good quality of the proposed method used in image SR.
5 ConclusionThis paper proposes an efficient sparse representation method called feature sign for single image superresolution. This method guesses the sign of sparse coefficients, then changes the complicated
[1] 
FREEMAN W T, PASZTOR E C, CARMICHAEL O T. Learning lowlevel vision[C]//Proceedings of the Seventh IEEE International Conference on Computer Vision. Los Alamitos, CA, USA: IEEE Comput Soc. 1999.

[2] 
CHANG H, YEUNG D Y, XIONG Y. Superresolution through neighbor embedding[C]//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamitos, CA, USA: IEEE Comput Soc 2004: 275282.
http: //ieeexplore. ieee. org/stamp/stamp. jsp?arnumber=1315043 
[3] 
CANDES, EMMANUEL J. Compressive sampling[C]//25th International Congress of Mathematicians, ICM 2006. United States: Asociacion International Congress of Mathematicians, 2006: 14331452.

[4] 
YANG J, WRIGHT J, HUANG T S, et al. Image super resolution via sparse representation[J].
IEEE Transactions on Image Processing, 2010, 19(11): 2861–2873.
DOI:10.1109/TIP.2010.2050625 
[5] 
DAVIS G, MALLAT S, AVELLANEDA M. Adaptive greedy approximation[J].
Constructive Approximation, 1997, 13(1): 57–98.
DOI:10.1007/BF02678430 
[6] 
EFRON B, HASTIE T, JOHNSTONE I, et al. Least angle regression[J].
Annals of Statistics, 2004, 32(2): 407–499.
DOI:10.1214/009053604000000067 
[7] 
KOH K, KIM S J, BOYD S. An interiorpoint method for large scale?_{1}regularized logistic regression[J].
Journal of Machine learning research, 2007, 1(4): 1519–1555.

[8] 
DONOHO D L. For most large underdetermined systems of linear equations, the minimal?_{1}norm solution is also the sparsest solution[J].
Communication on Pure and Applied Mathematics, 2006, 59(7): 907–934.
DOI:10.1002/(ISSN)10970312 
[9] 
ZENG L, LI X F, XU J. An improved joint dictionary training method for single image super resolution[J].
COMPELThe International Journal for Computation and Mathematics in Electrical and Electronic Engineering, 2013, 32(2): 721–727.
DOI:10.1108/03321641311297142 
[10] 
AHARON M, ELAD M, BRUCKSTEIN A. KSVD: an algorithm for designing overcomplete dictionaries for sparse representation[J].
IEEE Transactions on Image Processing, 2006, 54(11): 4311–4322.
DOI:10.1109/TSP.2006.881199 
[11] 
WANG Z, BOVIK A C, SHEIKH H R, et al. Image quality assessment: From error visibility to structural similarity[J].
IEEE Transactions on Image Processing, 2004, 13(4): 600–612.
DOI:10.1109/TIP.2003.819861 