CHEMICAL ENGINEERING TRANSACTIONS VOL. 51, 2016 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Guest Editors: Tichun Wang, Hongyang Zhang, Lei Tian Copyright © 2016, AIDIC Servizi S.r.l., ISBN 978-88-95608-43-3; ISSN 2283-9216 A New Video Super-resolution Reconstruction Algorithm Based on Compressive Sensing Ling Tang*, Hong Song, Mingju Chen, Yumei Chen College of Automation and Electronic Information, Sichuan University Of Science & Engineering, Zigong, 643000, Sichuan fashion-kitty@163.com Compressive Sensing(CS) theory can reconstruct the original images from the less measurements with using the priors of the image sparse representation. The CS theory is applied into the video super-resolution(SR) reconstruction, and a new algorithm based on wavelet transform is proposed in this paper. Firstly, wavelet transform is used to decompose the low resolution image so as to get the low frequency and high frequency sub bands, then the sub bands are reconstructed respectively by using CS method based on the orthogonal matching pursuit(OMP). Finally, the reconstruction image can be get by the wavelet inverse transform. The experimental results show that proposed algorithm can obtain better reconstruction image visual effect and has higher precision. Under different iterations and magnification level the quality of the reconstruction image is also better. 1. Introduction Compressive sensing (CS) theory proposed by Candes and Donoho et al. (2006) breaks through the traditional sampling theory of Shannon. The signals can be sampled with the rate far below the Nyquist sampling theory and compressed at the same time. Based on the assumption of the image sparse representation, the original signal can be reconstructed accurately at the receiver by solving the optimization problem. Compressed sensing theory is widely used after being proposed, and many practical applications are related to the acquisition of video images (Li et al., 2012), therefore, it has great practical value to study the effective video image reconstruction based on CS. At present, CS video image reconstruction algorithms are divided into two parts, which are video signal CS measurement and video signal reconstruction. The operation of the measurement is low, thus in the process of reconstruction, the iterative solution is needed to solve the optimization problem with high complexity. In order to obtain better reconstruction quality, many algorithms have been proposed, such as greedy algorithm (Sen et al., 2009), convex optimization algorithm and so on. Greedy algorithm can obtain high computation rate, such as Matching pursuit (MP) (Mallat et al., 1993) and Matching pursuit orthogonal (OMP) (Pati et al., 1993) algorithm are the most widely used. Compared with the MP algorithm, the OMP algorithm is based on the priors of the sparse degree of the signals, in each iteration the selected atoms are first processed by Schmidt orthogonal, and the least square method is introduced, so the calculation is more accurate. Therefore, we use the OMP algorithm for reconstruction, and taking into account that the wavelet transform can obtain the local characteristics of the signal in the time-frequency domain, a video super resolution reconstruction method based on compressed sensing and wavelet transform is proposed. Firstly, the low resolution image is decomposed into 4 sub bands by wavelet transform, then CS algorithm is used to reconstruct the image of each sub band. Finally, the high resolution image is reconstructed by wavelet inverse transform. The experimental results confirm the validity and practicability of the algorithm. 2. Super-resolution reconstruction model The image super resolution observation model generally can be expressed as: y DBMx N  (1) DOI: 10.3303/CET1651071 Please cite this article as: Tang L., Song H., Chen M.J., Chen Y.M., 2016, A new video super-resolution reconstruction algorithm based on compressive sensing, Chemical Engineering Transactions, 51, 421-426 DOI:10.3303/CET1651071 421 Where M is the motion operator, B is the fuzzy matrix, D is the down sampling operator, and N is the random additive noise. The degradation process is shown in Figure 1. From the formula (1), it can be seen that the process of SR reconstruction is an ill posed inverse problem. The solution of the reconstruction method is dependent on the different prior knowledge, which influences and limits the reconstruction results. In this paper, the sparse representation model based on compressed sensing theory is used to solve the above problems, and we can get the only sparse solution to the formula (1) under the specific conditions. Original HR image x Motion Mk + LR image yk Fuzzy PSF Bk Optical blur Sensor blur Inter frame motion blur Sampling Dk Noise nk SR reconstruction Figure 1: Observation model 3. Compressive sensing theory Compressed sensing is a new framework different from the traditional signal compression sampling. The sampling and compression are carried out simultaneously. For sparse expressed or compressed original signal, through the sparse transform the original signal can be accurately reconstructed with a little sampling values that meet certain conditions. So as to save a lot of sampling resources, operation resources and storage resources, the process is shown in Figure 2. Input signal Sparse transformation Observation projection Signal reconstruction Figure 2: Diagram of compressed sensing theory Assume one discrete one-dimensional real signal Nx R , do the sparse transformation x x , where  is the transformation matrix, x is the equivalent representation of x in sparse domain. Then the linear projection is used to the signal with the observation matrix  uncorrelated to  (Bo et al., 2013), y x ψx Ax     (2) We get the observed value My R ( M N ), where A= is a compressed sensing operator. x can be seen as the HR image on the SR reconstruction, y can be considered as the input LR images. However, the formula (1) is less certain, and there are many solutions. The CS theory can be used to obtain the unique solution with using the priors of the image sparse representation which of the signal x in the transform domain . But the premise is that  and  is not related, which meets the Restricted Isometry Property(RIP) (Donoho, 2006). Compressive sensing reconstruction is to get the sparsest representation of the signal when satisfying the observed values, it can be solved by the 0 optimization problem: 0 min || || . x x s t y Ax (3) Where 0 || ||x expresses the number of nonzero elements in the variation coefficient x . Due to the unstable solution of 0 norm, but the same solution with 1 norm under certain conditions. So in this paper, we use 1 norm to solve the above optimization problem, that is 1 min || || . x x s t y Ax (4) It is transformed into a convex optimization problem, thus the linear programming can be used to solve. 422 4. Super resolution reconstruction based on the wavelet transform Wavelet transform(WT) can decompose the original signal into high frequency and low frequency signal. The low frequency contains the main features of the signal, the high frequency component contains the characteristics details. Multiple low frequency signal can be obtained by re decomposition of the low frequency, so as to get the characteristics of the original signal. In the process of image super resolution reconstruction, the traditional methods to recover the lost high frequency information of the image such as interpolation method will bring the fuzzy edges. Wavelet transform is a technique for time-frequency analysis, which is widely used in image analysis. On the image SR reconstruction based on wavelet transform the acquisition of high and low frequency sub bands is very important, in practical applications the high frequency sub bands are directional, the visual effect of the reconstructed image with using interpolation method to reconstruct the high frequency sub band for wavelet inverse transform is poor, and the quality is also low. In view of the fact that CS technology can be realized in smaller distortion on the recovery of the original signal, so in this paper we use CS technology to reconstruct the sub band. Assuming a low resolution image of the size MN, the process of the SR reconstruction algorithm based on the WT is expressed as follows (Zuo et al., 2015): 1) Decompose the LR image into 4 sub bands using the WT, respectively are the low frequency sub band LL and three high-frequency sub bands HH, LH, and HL, corresponding the horizontal, vertical and diagonal directions, as shown in Figure 3; 2) Decompose the LL with the WT again, we can get 4 sub band images on the next level; 3) Reconstructed the low frequency sub band image by using the CS technology to the low frequency sub band; 4) Reconstructed the high frequency sub bands images by using the CS to three high frequency sub bands; 5) Using wavelet inverse transform to reconstruct the low frequency sub band and high frequency sub, so as to obtain the reconstructed image. Figure 3: Pyramidal Structure 5. Compressed sensing applied to the SR reconstruction Appling the CS theory in super resolution reconstruction needs to ensure that there is no correlation between the observation matrix and sparse matrix. So we need a low pass filter(LPF) for pretreatment before down sampling the HR image, which ensures the un-correlation between the sparse matrix and observation matrix after the HR image sampling. Consider the high resolution image is x, obtain the fuzzy representation by Gauss low-pass filter: xk=x, where =FHGF, down sampling to xh, then = H h x x F GFxy     (5) where F is the Fourier transform matrix. This filter effectively reduces the correlation between the sparse matrix and observation matrix, The CS theory can be applied to super resolution reconstruction. The process can also be regarded as solving the optimization problem with no constraint: 1 min || || . H x x s t y F GF x   (6) OMP algorithm is a nonlinear adaptive algorithm developed on the basis of MP algorithm, the difference between them is that in each iteration, the selected atoms are processed by the Schmidt orthogonal. The convergence rate of the algorithm is faster and it has higher accuracy. When the iteration number is sparse, 423 the iterative process is stopped. Consider the input signal is Nx R , sparse degree is K, the observation matrix is M NR  , the observed vector is My R , the steps of the algorithm are as follows: 1. Initialize the reconstructed signal ˆ 0x  , the residual error is 0 r y , the index set is 0   , and the iteration number t =1; 2. Find the maximum absolute value in the inner product of the residual error and observation matrix, and record the corresponding elements as t  ; 3. Update the index set 1 { } t t t       , reconstruct the atomic set 1 [ , ] t t t       in the observation matrix; 4. Using the least square method to calculate the reconstructed signal 2 1 2 ˆ ˆarg min || || i t t x y x    , and update the residual error 1 ˆ t t t r y x     ; 5. If meet the iteration condition, output x̂ , which is the reconstructed image, otherwise return to step 2. 6. Experiments and analysis Consider two groups of video image "calendar", "cap" as the original HR images, select one frame in each groups of the images for the space fuzzy of the Gauss point spread function with the size of 7×7 and the variance of 0.5, and 2 times space sampling, then add the random noise with SNR of 30dB, to be the LR images observed. The interpolation method, compressive sensing method and the algorithm proposed are compared in the experiments for the comprehensive analysis on the performance of reconstruction from two indexes of subjective effect and objective evaluation. Experiment 1 Comparison of the subjective effect The reconstruction effects of the various methods are shown in Figure 4. It can be seen that the interpolation method is the worst with loss of the image edge details and the fuzzy image. Compared with the interpolation method, the image effect of CS reconstruction is better, but the edge of the image is still relatively vague, and the local excessive is not very natural. The proposed algorithm is combined with the wavelet transform based on CS technology, The image edge detail information is restored by reconstructing the high frequency sub bands from wavelet transform decomposition, and the image reconstruction accuracy is also improved. The visual effect is very close to the original image, which confirms the superiority of the new algorithm. (a) Original HR (b) bilinear interpolation (c) compressive sensing (d) The proposed method (a) Original HR (b) bilinear interpolation (c) Compressive sensing (d) The proposed method Figure 4: The results of the image reconstruction 424 Experiment 2 The objective evaluation results We take the peak signal-to-noise ratio PSNR as the objective evaluation of the performance. 2 2 0 1 [ ] 255 10 lg ( ( , ) ( , )) MN n PSNR M N I x y I x y       where, M and N respectively is the size of the image pixels. Through the reconstruction effect in different magnification, the algorithm proposed performs well with the highest PSNR, thus the bilinear interpolation is the worst, as shown in Table 1. But with the increase of the magnification the observations is less, the reconstruction error will increase, the corresponding PSNR will decrease. And from the simulation result shown in Figure 5, with the increase of the iterations the PSNR of two kinds of algorithms for image reconstruction tends to be stable, but compared with the CS method, the new algorithm possesses higher result, which shows the better quality of the reconstructed image. Table 1: Comparison of PSNR in the different magnification Algorithms Magnification 2 3 4 5 6 7 Bilinear interpolation 27.56 26.05 23.93 21.22 18.31 17.57 Compressive sensing 28.89 27.74 24.07 21.56 19.45 18.08 The proposed 30.81 29.22 27.14 26.56 25.09 23.74 0 5 10 15 20 25 30 16 18 20 22 24 26 28 30 Iterations P S N R /d B compressive sensing the proposed algorithm Figure 5: PSNR changes with the different iterations 7. Conclusions In this paper the theory of compressed sensing is applied into the video super-resolution reconstruction, in order to improve the reconstruction accuracy, the method combined with wavelet transform and compressed sensing is proposed. The LR image is decomposed into low frequency and high frequency subbands using wavelet transform firstly, then the CS algorithm based on OMP for the reconstruction of two bands. Finally get the final reconstructed image by wavelet inverse transform, which can effectively recover the high frequency information of the image. The experimental results show that the method combined with the wavelet multiresolution decomposition and the ability of CS to recovery the signal in smaller distortion ratio, can obtain the ideal visual effect, and has better reconstruction quality from the subjective and objective evaluation index. Therefore it has a broad application prospect. 425 Acknowledgments This work was supported by programs of Sichuan Provincial Department of Education (13ZB0138), programs of Artificial Intelligence Key Laboratory of Sichuan Province (2013RYY02) and programs of Sichuan University Of Science & Engineering Teaching Reform (JG-1415). Reference Becker S., Bobin J., Candes E., 2009, NESTA: A fast and accurate first-order method for sparse recovery, SIAM Journal on Imaging Science, 4(1), 1-39, DOI: 10.1137/090756855 Candes E., 2006, Compressive sampling, Proceedings of the International Congress of Mathematics, Madrid: European Mathematical Society Publishing House, 1433-1452, DOI: 10.4171/022-3/69 Donoho D., 2006, Compressed sensing, IEEE Trans on Information Theory, 52(4), 1289-1306, DOI: 10.1109/TIT.2006.871582 Fan B., Yang X.M., Hu X.S., 2003, Super-resolution image reconstruction algorithms based on compressive sensing, Journal of Computer Applications, 33(2), 480-483 Goldstein T., Osher S., 2009, The split Bregman method for L1 regularized problems, SIAM Journal on Image Science, 2(2), 323-343, DOI: 10.1137/080725891 Li X.X., Wei Z.H., 2012, Compressed Sensing Video Images Recursive Reconstruction Algorithm Based on Local Autoregressive Model, ACTA ELECTRONICA SINICA, 40(9), 1795-1800 Mallat S., Zhang Z., 1993, Matching pursuits with time frequency dictionaries, IEEE Transactions on Signal Process, 41(12), 3397-3415, DOI: 10.1109/78.258082 Mun S., Fowler J.E., 2011, Residual reconstruction for block-based compressed sensing of video, Proceedings of the Data Compression Conference (DCC), Snowbird, USA: IEEE Press, 183-192, DOI: 10.1109/DCC.2011.25 Pati Y.C., Rezaiifar R., Krishnaprasad E.S., 1993, Orthogonal matching pursuit: recursive function approximation with application to wavelet decomposition, Proceedings of 1993 Conference Record of The Twenty-Seventh Asilomar Conference on Signals, Systems and Computers. Pacific Grove, 1-3 Nov, 40-44, DOI: 10.1109/ACSSC.1993.342465 Sen P., Darabi S., 2009, Compressive image super-resolution, Proceedings of 2009 Conference Record of the Forty-Third Asilomar Conference on Signals, Systems and Computers, Piscataway: IEEE, 1235-1242, DOI: 10.1109/ACSSC.2009.5469968 Tramel E., Fowler J.E., 2011, Video compressed sensing with multihypothesis, Proceedings of the Data Compression Conference(DCC), Snowbird, USA: IEEE Press, 193-202, DOI: 10.1109/DCC.2011.26 Tu J.H., 2014, A novel building boundary extraction method for high-resolution aerial image. Review of computer engineer studies, 1(2), 19-21, DOI: Zhao W.J., 2014, Image Super-Resolution Reconstruction Algorithm Based on Compressive Sensing, Jin Lin University, 6 Zuo Y.L., Ma Z.Q., Zuo X.Y., 2015, Super-resolution Reconstruction Method Based on Wavelet Domain and Compressive Sensing, Video Engineering, 39(9), 23-27 426 http://dx.doi.org/10.1137/090756855 http://dx.doi.org/10.1109/TIT.2006.871582 http://dx.doi.org/10.1137/080725891 http://dx.doi.org/10.1109/78.258082 http://dx.doi.org/10.1109/DCC.2011.25 http://dx.doi.org/10.1109/ACSSC.1993.342465 http://dx.doi.org/10.1109/ACSSC.2009.5469968 http://dx.doi.org/10.1109/DCC.2011.26