A low complexity based spectrum partitioning--ESPRIT for noncontact vital radar.
Non-contact vital detection applications such as medical monitoring  and , sensor network applications  and rescue recently have attracted strong interest for microwave radar. In medical applications, research on the application of microwave Doppler radar has focused on detecting of diagnose sleep apnea and other respiratory disorders such as sudden infant death syndrome. In the case of military applications, these techniques can be used to find hidden enemies behind walls, or rapidly unveil the positions of victims on the battlefield. In search and rescue operations, these techniques can detect victims in disaster situations such as an earthquake, fire, etc. In order to obtain the Doppler spectrum of a vital signal, the fast Fourier transform (FFT) algorithm is widely used. However, the conventional FFT for noncontact vital radar suffers from decreased performance in terms of accuracy and resolution due to smearing problems caused by the limited data length. The harmonic components of the respiration signal conceal the heartbeat signal in the Doppler spectrum estimation of the FFT. Furthermore, the FFT requires a long processing window to analyse the time-varying received signals of the vital radar. In the case of urgent situations such as intensive care units, postoperative recovery of patients, severe trauma, etc., the FFT can not analyse the vital Doppler spectrum with high accuracy and resolution. For frequency estimations, parametric approaches can be employed. Well-known parametric methods are relaxation (RELAX) , multiple signal classification (MUSIC) , estimation of signal parameters via rotational invariance techniques (ESPRIT) , and the spectral partitioning (SP) based super resolution algorithm , Among them the SP based super resolution algorithm is the most recent algorithm. It provides the estimation of parameters directly and can operate in a low signal-to-noise ratio (SNR) environment. Nevertheless, in order to apply the SP based super resolution algorithm such as ESPRIT to vital radar systems, a number of practical issues related to increased computational load should be addressed. In this paper, we choose the super-resolution algorithm as ESPRIT because it is the most recent algorithm that provides the estimation of parameters directly and achieves good performance and is thus widely used. Compared with the conventional ESPRIT, the complexity of the SP-ESPRIT is increased dramatically by running multiple ESPRIT algorithms. Therefore, in this paper, we propose a scheme that is modified from the conventional SP-ESPRIT technique with the aim of reducing the computational load for vital signal detection.
II. SIGNAL MODEL
The mathematical form of the continuous wave (CW) transmitted signal for the vital measurement  is defined as follows
5(t) = cos[2[pi] ft + [sigma](t)], (1)
where f is the carrier frequency and [sigma](t) is the time-varying phase noise of the CW transmitted signal. Consider a target's nominal distance [d.sub.0] with the time-varying displacement x(t) by the body movement, for which the total distance between the radar and body d(t)= [d.sub.0] + x(t), and x(t) can be represented by
x(t) = [x.sub.h](t) + [x.sub.r](t) [approximately equal to] [a.sub.h] sin([[omega].sub.h]t) + [a.sub.r] sin([[omega].sub.r]f), (2)
where [x.sub.h](t) and [x.sub.r](t) denote the body movements of the heartbeat and the respiration signal in the human body, which can be expressed by sinusoids with amplitude a\t and a, and angular frequency [[omega].sub.h] and [[omega].sub.r], respectively.
In the received part, when the transmitted signal s(t) is reflected by the human body, we can obtain the received signal y(t) as
y(t) [approximately equal to] cos [2[pi] ft - 4[pi][d.sub.0]/[lambda] - 4[pi] x(t)/[lambda] + [sigma] (t - 2[d.sub.0]/C)] + [psi](t), (3)
where C denotes the propagation speed, [lambda] = C/f is the wavelength and [psi](t) is the additive wliite Gaussian noise (AWGN) signal. By down-converting y(t) , the baseband quadrature signals p(t) are represented including the respiration harmonics due to the nonlinear phase modulation and body movement as
p(t) = exp [j(4[pi] [x.sub.h](t)/[lambda] + 4[pi]/[lambda] [M.summation over (m=1)] [x.sub.r,m](t) + [theta])] + [psi](t), (4)
where [x.sub.r,m](t) represents the m-th harmonic component of respiration with amplitude [a.sub.r,m] and angular frequency [[omega].sub.r,m] for m = 1, 2, ..., M, e.g., the original respiration component with m = 1, and [theta] denotes the total accumulated phase residual. Through an analog-to-digital converter (ADC), e.g.. [f.sub.s] = 1/[T.sub.s], the phase value q[n] of the discrete time model p[n] for n = 0, 1, ..., N-1 can be described as follows
q[n] = atan (Im(p[n])/Re(p[n])) = = 4[pi[x.sub.h][n]/[lambda] + 4[pi]/[lambda] M.summation over (m=1)] [x.sub.r,m][n] + [theta] + [zeta][n], (5)
where Re(*) and Im(*) are the real value and imagery value, respectively; atan(*) denotes the arctangent operator and [zeta][n] is the arctangent result of the AWGN noise.
III. CONVENTIONAL ALGORITHM
The conventional SP based ESPRIT method is composed of a two-step approach consisting of the SP stage and general ESPRIT stage, as shown in Fig. 1. The conventional algorithm presents a super resolution algorithm that can operate in the low SNR environment. Each block is connected by the bus signal with N channels. Given the received signal, the algorithm's 1st step is to transform the signal into the frequency spectrum. We can define the Doppler FFT as a frequency transform
R[l] = [N-1.summation over (n=0)] r[n][e.sup.-j2[pi]ln/N], (6)
where l denotes an index of the discrete frequency for the Doppler spectrum and (*)[sup.T] is the transpose. After the frequency spectrum lias been achieved, it is partitioned to multiple sub-bands according to the number of Z. We can describe a spectral partition matrix [S.sub.Z] for the z-th sub-band z=0, 1, ..., Z-1, as
[S.sub.z] [??] diag ([s.sup.z.sub.0], [s.sub.z.sub.1], ..., [s.sup.z.sub.N-1]), (7)
where diag(*) means a matrix with the elements of vector on the main diagonal in which the off-diagonal elements are all zero and the diagonal element is given by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (8)
where, [I.sub.z] is a set of indexes defined as
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (9)
where A is the size of sub-bands, that is, A = N/L, and integer values and [i.sub.z, j] = ((z -1) A + j).
Each partitioning part performs Z times of the super resolution algorithm such as ESPRIT iteratively. After partitioning, each partitioning part obtains the low power of noise even though it does not degrade the accuracy performance. Finally, the conventional algorithm can achieve high resolution results in a low SNR environment. However, in terms of complexity, the conventional algorithm has Z times greater computation power than the general ESPRIT algorithm.
IV. PROPOSED ALGORITHM
The proposed method is a 'two--stage method' (Fig. 2), consisting of the received 'sample reduced spectrum partitioning stage' (stage 1) and 'ESPRIT stage' (stage 2). As described in the previous section Doppler FFT is performed and window partitioning is processed. Up to this point, there is no difference from the conventional algorithm. However, after spectrum partitioning, the proposed algorithm enables the frequency of z-th window signal to shift into the baseband region. The baseband signal of z-th window signal [R.sub.f,z] is described such as
[R.sub.f,z] = diag([S.sub.z]R)[F.sub.s,z], (10)
where the frequency shift vector of z-th sub-band [F.sub.S,Z] = [[F.sub.S,Z], [F.sub.S,Z][l], ..., [F.sub.S,Z][[N - 1]].sup.T] is such as
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (11)
where [f.sub.c,z] means the centre frequency of the z-th window signal. After frequency shift, the baseband signal is processed by down sampling with an integer factor D. The size of the Doppler spectrum is reduced from N samples to P samples (P << Y). I) = N/P and the characteristics of down sampling operation are linear and time invariant. Next, the frequency signal is transformed into a time signal through P point inverse FFT (IFFT). The time signal is fed into the ESPRIT block.
Using the IFFT signal d[k] with P samples, the autocorrelation matrix [R.sub.dd] of L by L is defined as
[R.sub.dd] = [P-L.summation over (m=0)] [dd.sup.H], (12)
where the sequence d = [d[m], ..., d[m + L - 1]].sup.T] and (*)[sup.H] is the Hermitian transpose. In order to reduce the correlation effect, the forward-backward technique is used, which is given as follows
[R.sub.fb] = 1/2([R.sub.dd] + J[R.sup.*] [sub.dd]J), (13)
where J is the L x L exchange matrix.
The eigenvalue decomposition (EVD) of forward-backward autocorrelation [R.sub.fb] has a form given by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (14)
where the signal eigenvector matrix S = [[S.sub.0], ..., [S.sub.M] has M + 1 eigenvectors that span the signal subspace of the correlation matrix, the noise eigenvector matrix N = [n.sub.0], ..., [h.sub.L-M-2]] represents L-M-1 eigenvectors spanning the noise subspace of the correlation matrix, and [[lambda].sub.n] denotes the n-th eigenvalues of [R.sub.fb]. Here, M + 1 means the total number of the respiration and heart frequency. The largest M + 1 eigenvalues of [[lambda].sub.0], ..., [[lambda].sub.M] correspond to the M + 1 eigenvectors of S. The other eigenvalues [[lambda].sub.M+1], ..., [[lambda].sub.L-1] correspond to the eigenvectors of N such that [[lambda].sub.M+1] = ... = [[lambda].sub.L-1] = [[sigma].sup.2]. Let us define the [S.sub.1] and [S.sub.2] matrices, removing the last row vector and the first row vector, respectively, such that [S.sub.1] = [[I.sub.L-1] [0.sub.1xL-1]] S, [S.sub.2] = [[0.sub.1xL-1] [I.sub.L-1]S, [I.sub.M] M X M Idenotes a M x M identity matrix, and [0.sub.MxN] is a M x N zero matrix. Sub-matrices [S.sub.1], [S.sub.2] are solved such that:
[S.sub.1] =[[I.sub.L-1][0.sub.1xL-1]] AT, (15)
[S.sub.2] = [[I.sub.L-1] [0.sub.1xL-1]A[PSI]T, (16)
where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and T denotes the non-singular transformation matrix of M + 1 by M + 1. The sub-matrices are achieved by a pseudo inverse as follows
C = [S.sub.1.sup.[dagger]] [S.sub.2], (17)
where C = [T.sup.-1] [PSI]T and [dagger] denotes the Moore-Penrose pseudo inverse. We can then obtain the heartbeat frequency fi with the last element of [PSI] and the eigenvalues of C as follows
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (18)
where [angle](*) denotes the phase angles for a complex signal.
V. SIMULATION AND EXPERIMENTAL RESULTS
We obtained a snapshot of the Doppler spectrum and we conducted a Monte-Carlo simulation averaged over 10,000 estimates to verily the performance of the proposed algorithm. According to the harmonic model of vital signs, the simulated respiration and heartbeat signals were set to 18 beats/min (0.3 Hz) and 63 beats/min (1.05 Hz), respectively, and M = 5 harmonics of the respiration were included with amplitudes satisfying the following: [a.sub.r1] : [a.sub.r2] : [a.sub.r3] : [a.sub.r4] : [a.sub.r5] : [a.sub.h] = 10 : 4 : 0.1 : 0.02 : 0.05 : 2. We used the FFT, the conventional ESPRIT, the conventional SP-ESPRIT and the proposed algorithm to detect the vital signs. In the case of spectrum partitioning, the number of samples (AI), after down sampling, is 25. A reflected signal sampled at 20 Hz was generated. To be consistent with practical laboratory experiments, additive Gaussian noise was imported with a SNR of 1 and 50 dB.
The Doppler spectrum for the FFT, conventional ESPRIT, conventional SP-ESPRIT and the proposed method was respectively derived and presented in Fig. 3 and Fig. 4. In Fig. 3, in the case of a low SNR, the heartbeat peak of the conventional ESPRIT and the FFT deviates from the real value, while the heartbeat peak of the proposed algorithm and conventional SP-ESPRIT method is accurately detected. The simulation results in Fig. 4 show that the detection performance of the proposed method and conventional SP-ESPRIT is quite similar to that of the FFT and the conventional ESPRIT with a SNR of 50 dB. Therefore, the proposed algorithm yields good performance in a low SNR situation, especially in the case of the heartbeat signal.
In Fig. 5, the root mean square error (RMSE) as a function of SNR, for each algorithm was calculated for C times in the case of heartbeat Doppler signals with a short duration. The RMSE is defined by [[square root of 1/C [summation].sup.C.sub.n=1] ([[??].sub.n,n] - [[omega].sub.h,n]).sup.2], where C is set to [10.sup.4] and [tau]0,n is the angular frequencies of the heartbeat estimation in the n-th Monte-Carlo trial, respectively.
Based on Fig. 5, with a low SNR, the proposed algorithm performs better than the other algorithms, and the ESPRIT shows the worst performance for the heartbeat signal. For a SNR of 6 dB, the RMSE of the proposed algorithm is about 11 times lower than that of the conventional ESPRIT algorithm.
To evaluate the performance of the proposed method in a real situation, we conducted various experiments using iMotion radar  at Texas Tech University. We used a 2.4 GHz CW RF module with a transmitted channel and a received channel. CW radar signal s(t) is reflected from the human body. After down-converting, the baseband quadrature signals p(t) can be analysed. We conducted experiments to evaluate the proposed method for a human body in a room. When the target was placed at R 0.2 m, the following Doppler spectrum of the heartbeat rate was obtained, as shown in Fig. 6, because the heartbeat is sensitive with a low SNR. As seen in Fig. 6, the proposed method can estimate the peak of the heartbeat frequency well compared with the reference  while the conventional ESPRIT and FFT methods could not estimate it accurately relative to the exact heartbeat frequency at one randomly chosen frame.
VI. COMPUTATIONAL COMPLEXITY
In order to assess the processing time of the proposed and conventional algorithm, we design and implement both methods. Conventional algorithms such as ESPRIT and spectrum partitioning ESPRIT are developed with matrix computation, which involves EVD and matrix inversions by MATLAB code. The total processing time of the implemented algorithms was verified by MATLAB with debugging and analysing. MATLAB can observe the output of algorithms through a CPUTIME. The FMCW chirp parameters used in the preceding section for Monte-Carlo simulations are applied to assess the computation complexity in the same manner. In Fig. 7, in the case of the conventional spectrum partitioning algorithm, Z times computation time is needed compared with the general ESPRIT. Therefore, the proposed algorithm has much less complexity to reduce number of samples of the received signal using frequency shift and down sampling.
We have proposed a low complexity based spectrum partitioning super resolution method for noncontact vital radar. It uses a combination of the sample reduced spectrum partitioning stage and the ESPRIT stage. The suggested approach is designed to maintain the performance of the Doppler resolution in a low SNR environment and to be applied to real time processing systems. From Monte-Carlo simulation results and experimental results with a SNR of 6dB, the RMSE of the proposed algorithm is about 11 times lower than that of the conventional ESPRIT algorithm. The proposed method is applicable to vital radar due to its high performance of parameter estimation.
The authors would like to thank Dr. Changzhi Li and Ms. Yiran Li of Texas Tech University [Lubbock, Texas, USA] for their support with our experimental data.
 C. Li, J. Ling, J. Li, J. Lin, "Accurate Doppler radar noncontact vital sign detection using the RELAX algorithm", IEEE Trans. Instrum. Meas., vol. 59, no. 3, pp. 687-695, 2010. [Online]. Available: http://dx.doi.org/10.1109/TIM.2009.2025986
 L. Sun, Y. Li, H. Hong, F. Xi, W. Cai, X. Zhu, "Super-resolution spectral estimation in short-time non-contact vital sign measurement", Rev. Sei. Instrum., vol. 86, pp. 0447081-04470819, 2015. [Online]. Available: http://dx.doi.org/10.1063/l.4916954
 M. Cerny, M. Penhaker, "Wireless body sensor network in health maintenance systems", Elektronika ir Elektrotechnika, vol. 115, no. 9, pp. 113-116, 2011. [Online]. Available: http://dx.doi.org/10.5755/ jOl.eee.115.9.762
 X. Li, K. Pahlavan, "Super-resolution TOA estimation with diversity for indoor geolocation", IEEE Trans, on Wireless Commun., vol. 3, pp. 224-234, 2004. [Online]. Available: http://dx.doi.org/10.1109/ TWC.2003.819035
 S. Kim, B. Kim, D. Oh, J. Lee, "An effective pre-processing technique for robust ESPRIT-Based single-tone frequency estimation against an I/Q mismatch", Elektronika ir Elektrotechnika, vol. 21, no. 6, pp. 3439, 2015. [Online]. Available: http://dx.doi.org/10.5755/ j01.eee.21.6.13757
 V. K. Nguyen, M. D. E. Turley, G. A. Fabrizio, "A new data extrapolation approach based on spectral partitioning", IEEE Signal Process. Lett., vol. 23, no. 4, pp. 454-458, 2016. [Online]. Available: http://dx.doi.org/10.1109/LSP.2016.2533602
 C. Li, J. Lin, "Random body movement cancellation in Doppler radar vital sign detection", IEEE Trans. Microw. Theory Techn., vol. 56, no. 12, pp. 3143-3152, 2008. [Online]. Available: http://dx.doi.org/10.1109/TMTT.2008.2007139
 Microwave Noncontact Motion Sensing and Analysis. [Online], Available: https://sites.google.com/site/clilabsite/
 E. Toth-Laufer, A. R. Varkonyi-Koczy, "Personal-statistics-based heart rate evaluation in anytime risk calculation model", IEEE Trans, on Instrum. and Meas., vol. 64, no. 8, pp. 2127-2135, 2015. [Online]. Available: http://dx.doi.org/10.1109/TIM.2014.2376111
Caption: Fig. 1. Block diagram of the conventional SP based ESPRIT algorithm.
Caption: Fig. 2. Block diagram of the proposed SP based algorithm.
Caption: Fig. 3. Doppler spectrum of various algorithms at SNR = 1 dB.
Caption: Fig. 4. Doppler spectrum of various algorithms at SNR = 50 dB.
Caption: Fig. 5. RMSEs of the respiration and heartbeat signals.
Caption: Fig. 6. One randomly chosen frame: the experimental results from iMotion radar in the case of the heartbeat signal.
Caption: Fig. 7. MATLAB CPU execution time for both the conventional ESPRIT and the proposed SP-ESPRIT.
|Printer friendly Cite/link Email Feedback|
|Author:||Kim, Sangdong; Lee, Kyunkyung|
|Publication:||Elektronika ir Elektrotechnika|
|Date:||Apr 1, 2017|
|Previous Article:||Design and modelling of an enclosed array of square spiral antennas for microwave tomography.|
|Next Article:||Recent advances in crest factor minimization of multisine.|