Two-Dimensional Compressive SAR Imaging with Nonconvex Model Constraint

Two-Dimensional Compressive SAR Imaging with Nonconvex Model Constraint

AhmedM.Awadallah,Guanghui Zhao,Guangming Shi

School of Electronic Engineering Xidian University Xian,P.R. China

ZhaozhaoGao

Science and technology on Electronic Information Control Laboratory

Chengdu, P.R. China

AbstractCompressed sensing (CS) based SAR imaging approacheshave shown its superior capability in providing high quality SAR images and reducing the storage pressure. However, such performance will degraded when the number of measurements is not sufficient. To significantly reducing the sampling number, we adopt a nonconvex model to deeply exploit the two-dimensional (2D) sparsity in both range and azimuth dimensions, and a two-dimensional gradient projection (TDGP) scheme is employed for fast reconstruction, finally, a new compressive SAR imaging is proposed. The simulation results demonstrate the superior reconstruction performance of the proposed algorithm.

IndexTermsSAR Imaging; Compressed Sensing (CS); Nonconvex Model; Gradient Projection.

1. INTRODUCTION

   Synthetic aperture radar (SAR) is a radar imaging technology that is capable of producing high resolution images of the stationary surface targets. The main advantages of SAR are that it can reduce the effects of clouds and fog and allow them to be independent of external sources for imaging, having day and night and all-weather imaging capability. Traditional compressions of SAR data utilize the redundancy inherent in sampled data under the Nyquist theorem to achieve compressed representation and profitable transmission. This theory claims that one must sample at least two times faster than the signal bandwidth while capturing it without losing information. Thereby there are large amounts of onboard data that have to be stored and it inevitably results in complex computation and expensive hardware.

   Candès, Tao and Romberg [1] and Donoho [2] have proposedan approach, known as compressed sensing (CS), in which arandom linear projection is used to acquire efficient representations of compressible signals directly. The theory of CS states that it is possible to recover sparse images from a small number of random measurements, provided that the under-sampling results in noise like artifacts in the transform domain and an appropriate nonlinear recovery scheme is used [3]. Because of its compressed sampling ability, compressed sensing has found many applications in radar and remote sensing, and other fields.

   R.Baraniuk et al. proposed the radar imaging system based on CS for the first time [4]. The papers [5, 6] use CS

   in along-track interferometric SAR imaging and moving target velocity estimation. Some major open questions related with the application of CS to SAR and ISAR are listed in [7].

   In [8], Li introduces a novel two-dimensional (2-D) SAR imaging algorithm based on CS theory to reconstruct 2-D targets in the range and azimuth dimension, respectively. This algorithm provides the approach of receiving the echo data via 2-D random sparse sampling beyond the Nyquist theorem. This radar system randomly transmits fewer pulses in azimuth direction and samples fewer data than traditional systems at random intervals in range direction.

   In this paper, we focus on SAR imaging from under- sampled target return in both range and azimuth dimensions, and finally, propose a nonconvex model for robust image reconstruction.

   The reminder of this paper is organized as follows.Section II reviews the CS theory. Section III presents the SAR imaging with 2Ddownsampling. Section IV presents the proposed two-dimensional nonconvex gradient projection (TDNGP) algorithm. The experimental results are shown in section V. Finally, Conclusions are given in section VI.

2. REVIEW OF CS THEORY

   The CS theory points out that, any sparse or compressible signal vector has a sparse representation in the basis dictionary, i.e., = , low-dimensional measurements vector of the signal is calculated through an irrelevant observation matrix × ( ). Then the information of the signal can be obtained by resolving the following optimization problem.

   0 0

   min , s.t. = (1)

   where . 0represents 0norm and = .

   Since resolving program in Eq. 1 is an NP-hard problem, Donoho [2], Cands [9], Romberg [10], and Tao [1] proposed the following relax convex optimal model:

   1 1 , s.t. = (2)

   They also pointed out that Eq. 2 has the same solution with the Eq. 1 when the number of measurements satises the

   inequality constraint log (b is a constant, K represents the sparsity degree of the signal, N is the length of the signal). Many algorithms have been developed to solve this model, such as LASSO [11], BP [12], and GPSR

   [13] which is often being significantly faster (in terms of computation time) especially in large-scale settings.

   The research of Cands [9] and Chartrand [10] discovered that, when the constraint condition logcannot be satisfied, the minimization of (1) has different solutions from that of (0) norm, which means program (1) cannot fully exploit sparsity of the signal. So Cands introduced a sparsity promoting weighted 1 norm to better approximate (0) norm. Since 0 = lim0 , Chartrand proposed an iterative weighted least squares (FOCUSS/IRLS) to solve the minimization of 01norm, and the corresponding nonconvex model is as follows:

   min () , s.t. = (3)

   e

   Azim tm	X max uth Ri (tm )			i						Rang
   0	Rmin X min									Rmax

   M N

   Figure 2, 2D scene division map

   If the slow time ( ) sequence length is , fast time () sequence length is , then the echo signal is × dimensional matrix. The scene according to the azimuth and range dimensions respectively wasdivided equally into × small squares = ( )/,

   = ( )/, as shown in Fig. 2.

   where = = . However, for a large

   =1

   sized image, FOCUSS algorithm process (the process of calculating least-squares solution) requires huge calculations which will seriously influence the reconstructed speed and decrease the recovered image quality and consequently prevent this algorithm from widely used in the field of image.

   Consider each small square can only have one scattering point (with the same resolution), if there is a target then scattering coefficient is not zero, and vice versa. The scene grid is divided into small squares with a unified numbers of(1,2,3, , ), where = × .

   Assuming LFM signal is transmitted as

   S (t)

   exp( j 2 f t j t2 )

   (4)

   Inspired by the fast performance of the GPSR (convex CS) and the ability FOCUSS (nonconvex CS) to overcome the insufficient measurements by solving the 01 norm in which the nonconvex problem is converted into convex one, we propose a novel fast algorithm named Two-Dimensional Nonconvex Gradient Projection (TDNGP) based on mini-

   mization of 01 norm, which can succeed in the process

   t r c

   where is the transmission fast time, is the range window function, is the carrier frequency, is the modulation frequency.

   Assume = 0, then the echo baseband signal is

   n j 4 Ri t m 2Ri t m

   of large-scale image, and adopt it in SAR imaging.

   S r (t ,t m ) i exp

   r t c

   i 1

3. SAR IMAGING WITH 2D DOWNSAMPLING

   This section will describe the 2D downsampling scheme

   t

   2

   2R t

   exp j t i m

   (5)

   a m

   c

   for the strip-map SARimaging,the imaging geometry can be referred to Fig.1.According to SAR imaging process to construct a two-dimensional joint basis matrix, the coming echo will be transformed into a product form of the basis matrix and the scene scattering coefficient vector while two dimensional reconstruction.

   where is the radar time (slow time), and ( )are the i-thscattering coefficient and point target rangerespectively, is the signal wavelength, is the light speed, is the azimuth window function.

   The echo baseband signal is analyzed line by line, where the k-th line signal is:

   n j 4 Ri t k 2Ri t k

   Flight Path

   S r (t ,t k ) i exp

   r t c

   i 1

   2

   Radar Beam

   t exp j t 2Ri t k (6)

   a k c

   Ground Path

   a k

   with the a assumption that:

   Swath

   Range

   hi (t k ) r t

   2Ri t k t exp j

   4 Ri t k

   Azimuth

   c

   Figure 1, Strip-map SAR data acquisition mode

   2R t 2

   exp j t

   i k

   (7)

   c

   thenEq. 6 can be written as:

   T (8)

   As been shown in Fig. 1, in strip-map SAR mode the echo can be written as:

   S r (t ,t k )N 1 H (t k )N n n 1

   S t,t

   T

   (10)

   where = , , , , ,

   ,

   R m M N

   M M M N N N

   1

   2

   ×

   ×1

   = 1, 2, , . Similarly, the baseband echo signal can be expressed as:

   whereis the scene scattering coefficient. and are the basis matrices for azimuth and range dimensions

   T

   S

   r (t ,t m ) H (t m )(N M )n n1

   (9)

   respectively, so we can get the following imaging solution

   model:

   where

   = , , ,

   , namely the

   min u p , s.t Echo u

   0 p 1

   (11)

   1 2 × × p A R

   two-dimensional joint basis matrix.

   Analysis of the above formula, we find that the left side of the equation is the echo signal pulled into one column, which contains all the echo information and related information. Thus as the observed signal will contain richer

   where is a vectorized form for , and .are the azimuth and range dimension basis matrices respectively

   In gradient projection framework, the first step is to compute the gradient of

   information than a single line signal contains, so the

   d

   1 u

   p u u

   (12)

   reconstruction results will be improved. Moreover,

   k u p

   k 1 p

   k 1

   k 1

   traditional algorithm should first perform range migration correction as the coupling between the echo range and azimuth dimensions does not exist, so the two-dimensional separate reconstruction needs more processing. In this formula the echo signal will be written in vector multiplication form of a large matrix and the objectives

   where 1 = 1 2 + 2, and 2 < 0, the parameter is introduced into the weight to avoidthe appearance of singular matrix at each iteration.

   To make sure the solution converges stably, the step-size

   should satisfy

   scattering coefficients, without range migration correction, therefore no distinction between broadside and squint modes

   uk min u

   k

   k 1

   p

   • d

   k k p

   (13)

   which makes the algorithm more pervasive.

4. PROPOSED IMAGING ALGORITHM (TDNGP) Traditional SAR imaging algorithms are performed based

   on matched filtering and Nyquist theory. Our proposed algorithm doesnt use matched filtering and can reconstruct a high quality image from echo data beyond Nyquist theorem using CS theory and even without the sparsity constraint satisfied by using the nonconvex approach. Figure 3 shows

   simple diagrams for the traditional range Doppler (RD)

   Considering the nonconvex property of the 01 norm, the solution of cant be achieved precisely according to Eq.13. In the methodology of gradient projection (GP), many methods can be utilized to get proper estimation of , such as linear search. However, it has been testified that such option is time-consuming [14], especially for nonconvex model. In the proposed method, inspired by FOCUSS/IRLS, we make use of the methodology of the reweighted 2 norm, and the step-size should satisfy

   algorithm and the proposed two-dimensional nonconvex

   min E u

   T

   k 1

   k d k

   min u

   k 1

   k d k

   gradient projection (TDNGP) algorithm.

   k k

   u

   k 1

   u

   k 1

   k dk

   (14)

   Random sampling of echo data

   in range and azimuth dimensions

   (below Nyquist rate)

   Full Echo data sampling (according to Nyquist theorem )

   where = 1 , then making a differential with

   respect to deduces:

   E u d

   d T d d T u d

   (15)

   k 1 k k

   k k k

   k k 1 k

   Let Eq. 15 equals zero, the step-size is:

   Two- dimensional Non-convex CS

   reconstruction with Gradient Projection (TDNGP)

   Range compression (matched filtering)

   + range cellmigration correction

   Two-dimensional combined basis matrix

   k

   d k ,d k

   d k , uk 1

   d k

   (16)

   where . denotes the inner product process. To make sure the equality constraint = , the descending

   direction can be obtained via projecting the gradient

   Azimuth compression (matched filtering)

   into the null space of as:

   d d

   d

   (17)

   High quality

   k k A A k R R

   where( . ) denotes the generalized inverse procedure. Then the new estimation of in the (k+1)-th iteration can be updated as:

   SAR iamge

   SAR image

   uk uk 1 k d k

   (18)

   1. (b)

   Figure 3, (a) Traditional RD(b) The TDNGP

   The process ends when reaching the maximum number of iteration or threshold condition is satisfied.

   The TDNGP algorithm can be concluded as: (12.66%, 3.42%), the random sampling is in both range and

   0 A R 0

   1. Initialize u Echo k : 1

   2. Calculate gradient of 1 1

      azimuth dimensions. Comparing images quality, it can be seen that the GPSR is the lowest resolution imaging algorithm, TDNGP algorithm and CVX algorithm imaging quality are equivalent. Table II shows measured parameters

      d

      1 u

      p u u

      for the bottom target in the reconstructed images using

      k u p k 1 p

      k 1 k 1

      3.42% sampling rate. Comparing running time, TDNGP

      k 1

      uk 1 diag

      u i 2

      p 2 ;

      k 1

      requires only 4~5 times of the GPSR required time, and CVX costs 150~300 times of the TDNGP required time.

      ;

      Figure 6 shows the time comparison at different sampling

   3. Step calculation: k

      d k ,d k

      d k , uk 1

      d k

      rates. The previous experiments show that even with a significant reduction in the SAR echo, the proposed algorithm can make fast reconstruction for a high quality

   4. The null space projection

      images.

      d k d

      d ;

      -80

      k A A k R R

      -60

      update uk uk 1 k d k ;

      -40

      -20

   5. Setting a threshold value If

   uk uk 1

   0

   k : k 1 go to step (2), else stop.

5. EXPERIMENTAL DESIGN

   To verify the validity of the proposed image formation algorithm, the following raw data simulation and experiments have been done. The raw data for a scene with five point targets were simulated according strip-map SAR mode with the parameters listed in Table I. The resulting image using full-sampling data obtained under the traditional RD algorithm is shown in Fig. 4.

   Experiments comparison with the proposed TDNGP, GPSR, and the CVX [15] algorithms for SAR imagingwithdifferent random sampling rates in both range

   -80

   -60

   -40

   -20

   0

   20

   40

   60

   80

   20

   40

   60

   80

   3800 3900 4000 4100 4200

   Figure 4, SAR image using traditional RD

   -80

   -60

   -40

   -20

   0

   20

   40

   60

   80

   and azimuth dimensions are tested. We also compare the

   3800 3900 4000 4100 4200

   3800 3900 4000 4100 4200

   quality and CPU elapsed time for image reconstruction under these algorithms. In the GPSR and CVX algorithm, range

   (a) 12.66% (GPSR) (b) 3.42%

   and azimuth dimensions reconstruction processing are -80 -60 performed separately, while our proposed TDNGP algorithm -40			-80 -60
   performs the two dimensional reconstruction directly. Figure	-20		-20
   5 shows two imaging results for the GPSR, TDNGP, and	0		0
   CVXalgorithms at two different random sampling rates	20		20
   	40		40

   -40

   TABLE I. SIMULATION PARAMETERS

   60

   80

   Parameter	Value
   Transmit bandwidth	60 MHz
   Pulse duration	5 µs
   Carrier frequency	10 GHz
   Antenna length	4m
   Platform velocity	100 m/s
   Platform height	3000 m
   Point targets coordinates	(0,3900) (0,4000) (0,4100) (-50,4000) (50,4000)

   3800 3900 4000 4100 4200

   60

   80

   3800 3900 4000 4100 4200

   -100

   -50

   0

   50

   (c) 12.66% (TDNGP) (d) 3.42%

   -80

   -60

   -40

   -20

   0

   20

   40

   60

   100

   3800 3900 4000 4100 4200

   80

   3800

   3900 4000 4100 4200

   (e) 12.66% (CVX) (f) 3.42%

   Figure 5, Comparison results of imaging algorithms under different

   sampling rates

   	GPSR	TDNGP	CVX
   3dB(A) m	1.7319	0.8061	0.9338
   3dB(R) m	2.6479	1.1990	1.2490
   PSLR(A) dB	-14.9170	-18.3098	-19.0603
   PSLR(R) dB	-11.7282	-16.4402	-14.0146
   ISLR(A) dB	-10.3454	-14.1775	-14.7972
   ISLR(R) dB	-9.6142	-12.2230	-13.9128
   Time (s)	3.1	26.5	1215.1

   TABLE II. COMPARISON OF RESOLUTION ANALYSIS AT THE BOTTOM TARGET FOR RECONSTRUCTED IMAGES FROM 3.42% SAMPLING RATE

   4

   10

   CVX

   TDNGP

   GPSR

   CPU Elapsed Time (s)

   3

   10

   2

   10

   1

   10

   0

   10

   25 20 15 10 5

   Samling Ratio (%)

   Figure 6, Comparison results of the CPU elapsed time for different algorithms under different sampling rates

6. CONCLUSION

The proposed algorithm (TDNGP) is based on solving the nonconvex optimization problem with gradient projection and combining with the two-dimensional CS reconstruction. Since the proposed algorithm only involves some matrix-vector products, it is easy to implement fast implicit operation and make it possible to take use of the advantage of 0p1 semi-norm based model practically in large-scale applications such as SAR image reconstruction, which is a hard task for common procedure for 0p1semi- norm optimization such as FOCUSS/IRLS. The simulation of SAR image reconstruction shows the super-performance of the proposed algorithm in the quality improvement and

the significant reduction in the required time which has consequently a great advantage on the SAR imaging problem.

ACKNOWLEDGMENT

This work is supported in part by the Major State Basic Research Development Program of China (973 Program, No. 2013CB329402), in part by the National Science Foundation of China under Grants 61372071, 60902079, 61201289,

61033004, 61072104 and 61070138.

REFERENCES

1. E. Cand`es, J. Romberg, T. Tao,Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory., vol. 52, no. 2, pp. 489-590, Feb.2006.

2. D.L. Donoho,Compressed sensing, IEEE Trans. Inf. Theory., vol.52,no.4, pp. 1289-13.6, Apr,2006.

3. J. Romberg, Iaging via compressive sampling, IEEE signal Process. Mag., pp. 14-20, March 2008.

4. R.Baraniuk and Steeghs.P, Compressive radar imaging, in Proc IEEE Radar Conf., Waltham,MA,Apr.2007,pp.128-133.

5. Y.G. Lin, B.C. Zhang, et al, Along-track interferometric SAR imaging based on distributed compressed sensing. IET Electronics Letters, vol.46,no. 12,pp.858-860, Jun,2010.

6. A.S. Khwaja and J.W. Ma, Applications of Compressed Sensing for SAR Moving-Target Velocity Estimation and Image Compression, IEEE Trans. Instrumentation and Measurement, vol. 60,no. 8, 2848- 2860,Aug,2011.

7. J.H.G Ender, On compressive sensing applied to radar, Signal Proceesing, vol. 90, no. 5, pp.1402-1414, May,2010.

8. Jing Li; Shunsheng Zhang; Junfei Chang, "Two-dimensional random sparse sampling for high resolution SAR imaging based on compressed sensing," Radar Conference (RADAR), 2012 IEEE , vol., no., pp.0001,0005, 7-11 May 2012.

9. Cand`es E J. Compressive sampling. In: Proceedings of International Congress of Mathematics. 2006. 14331452

10. Cand`es E J, Romberg J. Quantitative robust uncertainty principles and optimally sparse decompositions. Found Comput Math, 2006, 6: 227254

11. Tibshirani R. Regression shrinkage and selection via the lasso. J Roy Stat Soc B, 1996, 58: 267288

12. Chen S, Donoho D, Saunders M. Atomic decomposition by basis pursuit. SIAM J Sci Comput, 1998, 20: 3361

13. Figueiredo M A T, Nowak R D, Wright S J. Gradient projection for sparse reconstruction: application to compresed sensing and other inverse problems. IEEE J Sel Top Signal Proc, 2007, 1: 586597

14. R.Chartrand, Exact reconstructions of sparse signals via nonconvex minimization, IEEE Signal Proc. Lett., vol.14, no.10, pp.707-710, 2007.

15. Michael Grant and Stephen Boyd. CVX: Matlab software for disciplined convex programming,version 2.0

beta.http://cvxr.com/cvx, September 2013.