Sparsity Adaptive Matching Pursuit Algorithm for CompressedSensing with Fuzzy Pruning Threshold

GUO Qing-qing，ZHOU Fei-fei，LI Lei

(Faculty of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

Sparsity Adaptive Matching Pursuit Algorithm for CompressedSensing with Fuzzy Pruning Threshold

GUO Qing-qing，ZHOU Fei-fei，LI Lei

(Faculty of Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

Sparsity Adaptive Matching Pursuit (SAMP) is a mainstream image reconstruction algorithm in Compressed Sensing (CS).However,with the increase of iterative times,it has multiplied atoms candidate set that lead to wasting storage capacities and lengthening reconstruction time.A method called Fuzzy Pruning Threshold Sparsity Adaptive Matching Pursuit (FPTSAMP) is proposed.The Discrete Wavelet Transform (DWT) destroys the correlation among low-frequency approximation coefficients in CS sparsity processing,which results in bad reconstruction quality,so a High Frequency Sub-Band Wavelet Transform (HFSBWT) is adopted instead of DWT to realize the sparse representation of signal.Simulation results show that compared with the same reconstruction algorithms the HFSBWT has achieved a better Peak Signal To Noise Ratio (PSNR) of images and that compared with SAMP algorithm the FPTSAMP combined with HFSBWT has lifted the reconstruction performance of images significantly with its reconstruction time cutting in half.

compressed sensing;reconstruction algorithm;high frequency sub-band wavelet transform;fuzzy pruning threshold sparsity adaptive matching pursuit

1 Summarization

Compressed Sensing (CS)[1-3]theory had broken through the restriction of Nyquist sampling theorem on the sampling rate, and realized sampling and compressing data simultaneously. CS projects high-dimensional data to low-dimensional data, and recovers the signal by projection observation and reconstruction algorithm. It is described as follows:

y=Φx=ΦΨθ=Aθ

(1)

Wherex∈RNis theK-sparse signal which can be represented sparsely in a certain transform domainΨ, i.e.x=Ψθ,ydenotes the measurement values vector with reduced dimensionn,Φis a measurement matrix with sizen×N, andA=ΦΨis called an×Nsensing matrix.

The signal can be reconstructed from relatively few incomplete measurementsb=Axfor a carefully chosenA∈Rm×nby solving thel0-minimization problem.

(2)

(3)

Where‖·‖l1denotesl1-norm, ifΦandΨare incoherent and sensing matrixAsatisfies the Restricted Isometry Property (RIP), then theK-sparse signalxcan be well reconstructed. Thus, the non-convex problem is transformed into a convex one to solve.

l1-linear programming problem has been found several algorithms including BP[4], Gradient Projection for Sparse Reconstruction (GPSR)[5], and Iterative Thresholding (IT)[6]. For thel0-optimization problem, iterative greedy pursuit is a good idea that contains Orthogonal Matching Pursuit (OMP)[7], Compressive Sampling Matching Pursuit (CoSaMP)[8], Stagewise Orthogonal Matching Pursuit (StOMP)[9]and Sparsity Adaptive Matching Pursuit (SAMP)[10],etc.

The CS theory has three main steps:signal sparse representation, measurement matrix and reconstruction algorithm.

Signal sparse representation is premise of compressed sensing technique to ensureits effectiveness. In this paper, High-Frequency Sub-Band Wavelet Transform (HFSBWT) sparse representation has been provided instead of traditional image sparsity, wavelet basis or Discrete Wavelet Transform (DWT)[11]to enhance sparsity property and to promote reconstruction effect of images.

The most critical step for compressed sensing is reconstruction, which determines performance and operation time of reconstruction. To deal with wasting storage capacity and time-consuming operation with Sparsity Adaptive Matching Pursuit (SAMP) algorithm, Fuzzy Pruning Threshold Sparsity Adaptive Matching Pursuit (FPTSAMP) algorithm has been proposed, which adopts fuzzy threshold preliminary rule to avoid using a priori information of signals in primary election phase and then realizes adaptive recovery and achieves purpose of shrinking the atoms selection space and cutting down iteration time.

In this paper, a novel transform named HFSBWThas been adopted to improve performance of traditional transform and then FPTSAMP algorithm has been proposed to deal with wasting space and time-consuming on SAMP algorithm, which introduces the fuzzy preselected method, and pruning and stop threshold to eliminate redundant atom and reduce unnecessary iterations. The proposed algorithm has not only improved reconstruction precision but also accelerated convergence speed. In addition, some simulation experiments has been conducted to verify better performance of FPTSAMP algorithm over others.

2 Improved FPTSAMP Reconstruction Algorithm Based on HFSBWT Sparse Representation

2.1TheHFSBWTSparseRepresentation

The first step of CS Theory is to transform the original non-sparse signal to sparse signal. To make the image signal sparse, universally the method of sparse transformation DWT[3-4]is adopted. After having decomposed image with single-layer wavelet transform, four sub-band coefficient matrixes is acquired including average part, vertical detail, horizontal detail and diagonal detail, i.e.{cA,cV,cH,cD}, where average part should be deemed to frequency component of image, and the remaining three parts are considered as high frequency section. Low-frequency part can be regarded as an approach signal of the original image within the different scales, so the low-frequency component is non-sparse and difficult to be more sparse. Nevertheless, the remaining three high frequency parts are sparse relatively. If coefficients of the high-frequency and low-frequency sub-band simultaneously multiplied with measurement matrix to obtain the measured values the correlation among the low-frequency approximation coefficients would be destroyed, which could lead to a worse quality of the reconstructed signal.

So anovel kind of image sparse transform way is provided based on compressed sensing, called HDSBWT[12-13]. First, the product ofΦandcV,cH,cDis calculated respectively with high frequency sub-band measurementscv,ch,cd, while the low-frequency sub-band is remained incA, then setting a measuring numberM, and constructing i.i.d. Gaussian matrix as measurement matrixΦwith the size ofM×Q, whereQ≈N/2, furthermore in decoder side, reconstruction algorithm was used to recovery three high frequency coefficient matrixescV,cH,cDrespectively. Finally inverse wavelet transform together with sub-bandcAwas carried out to reconstruct image.

2.2ImprovedFPTSAMPReconstructionAlgorithm

SAMP[14]is a kind of typical algorithm to solve the optimization problem ofl0-norm with two advantages of adaptive sparsity and involving retrospective thoughts. However, there are mainly two drawbacks that appeared during pre-selection and pruning atom:

(1)Atpre-selection stage, whenkis larger, index of new added atom is seldom due to the weak-correlation between the residual valuerk-1 and the sensing matrix. Then the excessive collection of atom candidate index leads to choosing atom support set repeatedly, even causes large consuming of time, and impacts accuracy of least squares estimation method.

(2)At pruning atom stage, the iteration stepwould be doubled while there is a failure to meet the constraint, so that number of elements in candidate set would beStimes that of original set at each stage. While candidate set are superfluous, it is bound to affect the composition of support set.

Aimed at the drawback of SAMP algorithm, an improved algorithm named FPTSAMP has been proposed. Where fuzzy pre-selection stage is set and the original candidate atom method is replaced by adding pruning threshold.

Having been inspired by stagewise weak threshold conjugate gradient algorithm and subspace pursuit algorithm, FCTSAMP adopts fuzzy threshold instead of the original pre-selection program.

(4)

Where sort(·,'decend') is descending order elements, and idx(·) is extracting element index,αprandβprare two fuzzy threshold parameters available for the user to set, and function rand(1) can generate random numbers range from 0 to 1. Because of each iteration the weak-correlation ofAandrk-1 leads to uncertain number of new added subscript. Compared with the original preselected program the fuzzy threshold method promotes the correlation to manipulate more new subscript with common sense.

For the problem of repeated prune with SAMP in each of iteration, FPTSAMP sets stop and pruning thresholds at the first time. When residual energy norm is less than the stop thresholdp1*‖y‖2, which indicates that the current residual of iteration is small enough, no cutting operation is needed, or demonstration meets iteration termination conditions to avoid unnecessary cutting operation and to save calculations time. When residual energy norm is less than the pruning thresholdp2*‖y‖2, this situation suggests pruning operation of atomic candidate set need to be implemented. To crop the redundant atoms accurately one subscript in candidate set at a time has been discarded and then it is determined whether change the residual valueror not. If the residual valuerincreases, it indicates that no need to perform pruning operation, the step size of candidate set has been doubled, then access to the next iteration. Otherwise, if the residual value is smaller or unchanged, indicating that the subscript being pruned is certainly redundant, then iterating the pruning step until redundancy is eliminated.

As mentioned above, there are four input parameters,αpr,βpr,p1andp2. Based on huge simulation experiments and balance between operation time and reconstruction accuracy, if settingαpr=0.8,βpr=1, and selectingp1=6×10-4,p2=1×10-2, performance of signal reconstruction is better. In brief, the FPTSAMP execution process lists as follows:

(1)Input:sensing matrixA, observation vectory, fuzzy thresholdαpr,βpr, stopping thresholdp1, pruning thresholdp2, step factorS, tolerance errorδ.

(3)Fork=1,k=k+1 until meeting stopping criterion ‖rk‖2≥δ

(a)J=abs(AT*rk-1),Th=αpr+rand(1)*(βpr-αpr).

(b)H=abs(Th*J),H=sort(H,'decend').

(c)Sk={i|i=idx(H(t)),1≤t≤L},Ck=Fk-1∪Sk.

(d)If(‖rk-1‖2≤p1*‖y‖2), break; else go on.

3 Experimental Results and Analysis

In order to verify the advantage of reconstruction accuracy and time with FPTSAMP over those with SAMP,in experiments, HFSBWT transform, sampling 256×256 Lena and Boat images respectively at rateM/N=0.3, then image sparsity handled by HFSBWT transform, and measurement matrix is i.i.d. Gaussian matrix. Finally, reconstructed effect of Boat and Lena images have been completed by the FPTSAMP and SAMP respectively, shown by Fig.1.

Fig.1 Reconstruction effect comparison of images

Contrast analyses of Fig.1 shows that when sampling rate is 0.3, the reconstructed image achieved by SAMP reconstruction algorithm may have a significant fuzzy effect and there is a lot of interference when regardless of Lena or Boat image. However the reconstructed image achieved by FPTSAMP reconstruction algorithm, its texture pattern is visible clearly, only fuzzier than original image slightly. In order to illustrate the superior performance of FPTSAMP, more effective comparison with SAMP and comparison charts in Fig.2.

Fig.2 Comparing reconstructed performance of SAMP and FPTSAMP

As can be seen from Fig.2(a), when at the lower sampling rate, the reconstruction PSNR of two algorithms are relatively low, but with sampling rate increasing, the PSNR also improves significantly. And PSNR achieved by FPTSAMP is always higher than that achieved by SAMP. So the improved algorithm is much better than the original algorithm with advantageous reconstruction performance. Because of fuzzy pruning threshold taken into account in the improved algorithm, each iteration time could be shortened and convergence rate be sped up. Above all, Lena image for example, draw running time contrastive figure of two algorithms under various sampling rates shown in Fig.2(b).

With increase of the sampling rate Fig.2(b) shows that running time increases, but the increasing amplitude in FPTSAMP is always shorter than that in SAMP. Moreover, in terms of various sampling rates, the running time of FPTSAMP is significantly shorter than that of the SAMP so that time almost cut by half.

4 Conclusion

Based on the classical pursuit algorithm SAMP, FPTSAMP has been proposed, which introduces the fuzzy preselected method, pruning threshold and stop threshold to cut down redundant atom, to reduce unnecessary iterations, to improve reconstruction precision, and to accelerate convergence speed. In addition, the traditional DWT transform breaks the correlation among coefficients and leads to a poor reconstruction performance, the HFSBWT has been proposed. A large number of simulation experiments show that after having handled images with sparse transform HFSBWT and employed FPTSAMP for recovery images, the reconstruction performance has been improved significantly and its running time is cut by half.

[1] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[2] Candès E J,Wakin M B. An introduction to compressive sampling[J].IEEE Signal Processing Magazine,2008,25(2):21-30.

[3] Gao Z,Xiong C, Ding L,et al. Image representation using block compressive sensing for compression applications[J].Journal of Visual Communication and Image Representation,2013,24(7):885-894.

[4] Chen S S,Donoho D L,Saunders M A.Atomic decomposition by basis pursuit[J].SIAM Review,2001,43(1):129-159.

[5] 徐 健,常志國,趙小強,等.基于自適應梯度最速下降的分類字典訓練算法[J].計算機工程,2013,39(5):225-229.

[6] 張宗念,李金徽,黃仁泰.迭代硬閾值壓縮感知重構算法—IIHT[J].計算機應用,2011,31(8):2123-2125.

[7] Donoho D L,Tsaig Y,Drori I,et al.Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2012,58(2):1094-1121.

[8] Needell D,Tropp J A.CoSaMP:iterative signal recovery from incomplete and inaccurate samples[J].Communications of the ACM,2010,53(12):93-100.

[9] 周 燕,曾凡智,趙慧民,等.一種基于精細化稀疏自適應匹配追蹤算法的圖像檢索方法研究[J].電子學報,2014,42(12):2457-2466.

[10] 楊 成,馮 巍,馮 輝,等.一種壓縮采樣中的稀疏度自適應子空間追蹤算法[J].電子學報,2010,38(8):1914-1917.

[11] Zhang Y,Mei S,Chen Q,et al.A novel image/video coding method based on compressed sensing theory[C]//IEEE international conference on acoustics,speech and signal processing.[s.l.]:IEEE,2008:1361-1364.

[12] 甘 偉,許錄平,羅 楠,等.一種自適應壓縮感知重構算法[J].系統工程與電子技術,2011,33(9):1948-1953.

[13] 周飛飛,李 雷.小波高頻子帶變換裁剪閾值SAMP算法研究[J].計算機技術與發展,2014,24(5):83-86.

[14] 甘 偉,許錄平,張 華,等.一種貪婪自適應壓縮感知重構[J].西安電子科技大學學報:自然科學版,2012,39(3):50-57.

2016-06-15

：2016-09-22 < class="emphasis_bold">網絡出版時間

時間：2017-07-05

國家自然科學基金資助項目(61501251,61071167,61373137)；江蘇省普通高校研究生科研創新計劃資助項目(KYZZ15_0236)；南京郵電大學引進人才科研啟動基金資助項目(NY214191)

郭青青(1991-)，女，碩士，研究方向為信號圖像處理、數據可視化和數值計算；李 雷，教授，研究方向為模式識別和智能系統、計算機網絡、非線性分析、計算與應用數學、數學和模糊系統以及信號處理等。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1649.018.html

基于模糊裁剪閾值的SAMP壓縮感知算法

郭青青，周飛飛，李 雷

(南京郵電大學 理學院，江蘇 南京 210023)

稀疏度自適應匹配追蹤(SAMP)算法是壓縮感知(CS)中一種主流的圖像重構算法。隨著迭代次數的增加，SAMP算法的原子候選集將成倍增加，會導致系統空間的浪費和重構時間的增長。為此，提出了一種模糊裁剪閾值稀疏度自適應匹配追蹤(FPTSAMP)算法。由于離散小波變換(DWT)在CS稀疏處理過程中破壞了低頻逼近系數間的相關性，對信號的重構質量產生了一定的負面影響，因而采用小波高頻子帶變換(HFSBWT)來替代DWT，實現對信號的稀疏表示。仿真實驗結果表明，相比于同一重構算法，采用HFSBWT方法得到的峰值信噪比更好；與SAMP算法相比，與HFSBWT相結合的FPTSAMP算法的重構效果有了明顯提高，重構時間也減少了一半。

壓縮感知；重構算法；高頻子帶小波變換；模糊裁剪閾值SAMP算法

TP301.6

:A

:1673-629X(2017)09-0035-05

10.3969/j.issn.1673-629X.2017.09.008