**Vol:** 2016 **Issue:** 1

**Published In: January 2016**

**Article No: **2 **Page:** 11-28 doi: 10.13052/jconasense2246-2120.2016.002

**Beamforming Algorithms for UWB Radar-based Stroke Detection: Trade-off Performance-Complexity**

Received 19 April 2016; Accepted 1 May 2016;

Publication 21 May 2016

E. Ricci, E. Cianca and T. Rossi

*Department of Electronic Engineering, University of Rome “Tor Vergata”, Rome, Italy*

*E-mail: elisa.ricci.ing@gmail.com*

The use of UWB (Ultra-Wide Band) radar microwave imaging in stroke detection opens the possibility to develop low cost, fast response and transportable diagnostic devices, which could play a key role in emergency scenarios. The feasibility of such a device is strictly related to the trade-off performance-complexity, which depends from the chosen beamforming algorithm, the number of antennas and the radar mode (monostatic/multistatic). This paper aims to provide a better understanding of this trade-off for several beam-forming algorithms and radar configurations (monostatic/multistatic) applied to stroke detection. Comparisons are performed assuming an antenna system with a low number of antennas (namely 8) with respect to more commonly considered settings for this application (from 16 to 48 antennas). The study is based on FDTD simulations and considered beamforming algorithms are: Delay & Sum (considered in most of the works on UWB radar stroke detection); MIST algorithms and adapted versions of the MIST and RAR algorithms originally proposed for breast cancer detection.

- Brain stroke detection
- beamforming algorithms
- microwave UWB radar

Microwave Imaging (MWI) is an emerging diagnostic branch based on the observation that microwaves penetrate biological tissues and are reflected by discontinuities in the dielectric properties of the crossed tissues. Different tissues, or the same tissue but in different functional condition (i.e. cancerous and healthy tissue) have different dielectric properties in the microwave band. Two types of active microwave imaging techniques exist: tomography imaging, that uses the scattered signals to reconstruct the profile of the dielectric properties of the tissues; UWB radar imaging, whose objective is to identify the presence and location of significant backscattered energy arising from the dielectric discontinuities between two different types of tissues. This paper is focused on UWB radar imaging.

Much works can be found on UWB radar imaging for breast cancer detection [1–5], MWI has been also recently applied to brain imaging [6–9]. For both applications, the main pro offered by MWI lies in a nonionizing, non-invasive screening technology that may help in reducing the number of false positives and false negatives [2]. However, in case of brain imaging, MWI offers the further advantage of allowing the design of a low cost, transportable and fast-response device that could efficiently complement the traditional high-resolution imaging systems, such as CT (Computed Tomography) and MRI (Magnetic Resonance Imaging), in emergency scenarios. As for the heart attack, stroke patients should be dispatched at the highest level of care available in the shortest time possible. In this context a transportable system, able to evaluate the presence of an acute brain lesion, can be placed in specialized ambulances, to perform a fast diagnosis and shorten the delay of treatment. In particular, the identification of a haemorrhagic nature of the event could help to differentiate the subgroup of “haemorrhagic” patients from “possible ischemic” patients to select the most adequate hospital destinations. Therefore, in case of brain imaging, besides the potential to reduce the false positives and false negatives, it is important to keep low size, cost and the response time of the diagnostic device, which are related to the computational complexity of the performed signal processing. The latter is based on two main steps: a backscattered signals artifacts removal phase and a beamforming algorithm.

As a matter of fact, most of the works in UWB radar for stroke detection are based on a monostatic system and the Delay & Sum (DAS) beamforming algorithm [8, 9], which is characterized by low computational complexity but also limited robustness to artifacts. To achieve good performance, a very high number of antennas must be used (e.g. 16 and 32 in [9]). To improve the performance and reduce the number of antennas, two different approaches are possible:

This paper aims to provide a better understanding of the trade-off performance-computational complexity of different beamforming algorithms applied to UWB radar stroke detection. We consider the following algorithms:

- Delay & Sum;
- Microwave Imaging Space-Time (MIST) [2, 3] algorithm, which was originally proposed for breast cancer detection;
- a modified version of the Robust andArtifacts Resistant (RAR) algorithm proposed in [12] for stroke detection.

In this paper, those algorithms are compared considering different performance metrics, taking also into account the computational complexity, both in a monostatic and multistatic mode.

This section presents the processing carried out on the received signals to obtain an image of backscattered microwave energy.

In the monostatic mode each antenna transmits a broadband pulse and receives the backscattered signals to be processed. In the multistatic mode each antenna transmits a broadband pulse and all the antennas, including the transmitter, receive the backscattered signals. However, not all signals carry useful information. For example, the channels related to antennas that are not in line of sight, since the head is interposed between them, do not contain relevant information. On the other hand, channels related to adjacent antennas have very high information content and must be used by the processing algorithms.

Let *x _{ji}* be the signal associated to the

In this paper, the considered artifact removal is the PLSR (Partial Least Square Regression) artifact removal algorithm proposed in [10]. In particular, the artifact on each channel is estimated as a linear combination of the artifact in all other channels, utilizing the maximization of correlation as constraint and relying on the assumption that the artifacts in all channels are similar, but not identical. Finally, the estimate artifact is subtracted to the corresponding signal and this procedure is repeated for each signal of each different channel.

Moreover, before passing the backscattered signals to the pre-processing algorithm, a first cleaning of the signal is performed by a simple low pass filter [10], which helps to remove artifact components that are outside the main bandwidth extension of the stroke contribution.

The goal of beamforming is spatial filtering, i.e. separation of signals that have similar temporal frequency content but originate from different spatial locations. The output of a beamformer is a weighted combination of the signals received by each antenna. The beamformer is based on the principle of signals coherent sum. The received signals are synthetically focused in a focal point of tissue through time shifts to approximately align them. The output is a map of backscattering energy in which each focal point is associated to the intensity of corresponding pixel in the energy map. If a strong scatterer exists at the focal point, i.e. the point represents a transition between tissues having different dielectric properties, signals are summed coherently and the energy will be relatively high. On the other hand, if the focal point is homogeneous tissue, signals are summed incoherently and the energy level is low. All the focal points positions of the tissue to be examined are updating the time-shift phase.

The DAS is the simplest beamforming algorithm, widely used in brain application in monostatic mode [8, 9]. After the time-shift step, the aligned signals are summed for each time sample *n* and focal point *r*_{0}, as in (1):

where *C* is the number of channels, *x _{i}* is the backscattered signals of the

Finally, the energy output of the focal point is computed as the sum of squared samples within a window *h*, as described in (2):

The DAS algorithm has some drawbacks and requires further improvements. The main problem is the coarse time alignment, due to the phenomenon of spreading, i.e. temporal enlargement of the transmitted pulse and consequent energy dispersion. Moreover, the DAS provides limited capability to discriminate against clutter. On the other hand, the DAS has very low computational complexity; this is a desirable characteristic in the design of a low-cost and fast-response device.

The MIST algorithm was proposed for breast cancer application based on monostatic radar in [2] and then optimized for multistatic approach in[3]. In [13], MIST algorithm has been modified and optimized for stroke detection.

After the time-shift step, the time aligned signals are passed through a bank of FIR (Finite Impulse Response) filters, in order to provide amplitude equalization and a finer alignment compared to the previous phase. A detailed description of the MIST algorithm used in our application can be found in [13].

The output *z* is calculated for each time sample *n* and focal point *r*_{0 }as:

where *C* is the number of channels, *x _{i}* is the backscattered signals of the

The MIST has the not negligible disadvantage of a high computational complexity, due to the introduction of the FIR filters.

The RAR (Robust and Artifact Resistant) was proposed in [5] for breast cancer detection based on monostatic radar. A modification (Modified RAR) was proposed in [12] for head stroke detection both for monostatic and multistatic radar. The algorithm is a modified version of the DAS in which a weighting factor is introduced for each focal point, in order to compensate the drawbacks of the DAS without significantly increasing of the computational complexity.

The first two steps are the signals time alignment and the signals summation, as in (1). Then, an adaptive weight factor is introduced, by multiplying Pearson’s correlation coefficient of neighbouring pairwise transmitting-receiving antennas and selecting the *M* higher values. Let *i* be the number of useful channel, the weight factor is calculated as follows:

where *M* is the number of relevant correlation coefficients and *c _{i}* is the correlation coefficient associated to the

The correlation coefficients are particularly useful as a measure of signals similarity. Based on the assumption that the signals are delayed version of the transmitted pulse, a high correlation is expected at the same scatterer location.

In the modified RAR proposed in [12], and considered here, the number of correlation coefficients used for the weighting factor is an arbitrary value *M* chosen on the basis on MWI system features (number of antennas and distance between them), the pre-processing algorithm used (the less effective is the pre-processing algorithm, the higher is the number *M* of coefficients required to reduce the residual artifacts) and the trade-off between performance and complexity (increasing *M*, the performance but also the complexity increases).Alow number of the selected correlation coefficients would involve a worst discrimination between stroke and other scatterers, increasing the false positives. Whereas, a high number of the selected correlation coefficients would lead to information loss. The *M* value used in this paper is *C* for monostatic mode and *C/3* for multistatic mode, where *C* is the number of useful channels.

Finally the energy of the *r*_{0 }focal point is calculated as follows:

where *n = 1,… α* is the samples number, *wf* is the weight factor and *z* is the output calculated as in (1). If a scatterer is in a focal point *r*_{0}, most of the correlation coefficients have high value and *wf(r*_{0}*)* will be high. Conversely, if a focal point represents a residual artifact, most of the correlation coefficients have low value. Thus, *wf(r*_{0}*)* maintains a low weight factor associated with the corresponding focal point, even in the presence of an abnormal high correlation coefficient, which could lead to a high intensity energy value.

The algorithm robustness is based on building an adaptive weighting factor for each specific focal point.

The diagnostic device is composed by an 8 UWB antenna array system located around the head to be analyzed, arranged in an anatomical helmet-like structure. The number of antennas has been selected to limit the costs of the diagnostic device. The number of useful channel is *C = 24*. Each antenna transmits an UWB pulse (Ricker pulse) into the tissues and collects the backscattered signals, i.e. signals scattered from tissue discontinuities. Two radar approaches are considered: monostatic and multistatic.

The transmitted pulse has a bandwidth that extends from 1 to 4 GHz, as a consequence of a good trade-off between radar spatial resolution and waves attenuation inside the human brain [14].

Backscattered signals have been generated using Finite-Difference Time-Domain (FDTD) software. The latter are then pre-processed to remove useless information (artifacts). Then, the “cleaned” signals are processed by a beamforming algorithm, in order to build a map of backscattering energy of the head under examination. The antenna array assembly, the type of signal transmitted by the antennas and the 3D head model are the input data of the FDTD software.

The head has been modelled as a 3D multi-layered structure (skin, bone, brain matter). The 3D model consists in a blended ellipsoid, simulating the real head size [4]. In Cartesian coordinate system, the planar section of the model has semi axis along *x* of 80 mm and along *y* of 90 mm. The depth along *z* is 100 mm. The head consists of a roughly 2 mm thick skin layer,a6mm thick bone layer and brain matter. Since biological tissues are dispersive medium, it is necessary to take the dispersive behaviour into account. The electric properties have been evaluated according Cole-Cole model. In particular the calculated parameters are fitted to a second-order polynomial. The dispersive proprieties of the head tissues have been included in the FDTD model, setting different dispersive electrical properties for skin, bone, brain matter and bleedings. Table 1 reports the main parameters of the different head tissues considered in the model for the computation of the backscattered signals, at center frequency of 2.5 GHz [15].

Furthermore, we have also assumed the presence of a coupling medium, a mixture of different substance with dielectric constant similar to skin, between the antennas system and the head. This liquid increases electromagnetic energy transmission inside the skull and reduces the reflection contribution.Also the coupling medium has been included in the FDTD model.

Figure 1 shows the planar section of the system model described, with a planar section of the head as an ellipse and the antenna system as asterisks.

Noisy backscattered signals have been generated by adding white Gaussian noise with a SNR of 10 dB. A spherical bleeding (haemorrhage) with a diameter of 20 mm, around 4 cc of blood, placed in different positions of the head has been considered. Usually, the haemorrhages closer to the scalp are more difficult to localize as very close to the main source of artifacts.

Let us denote with *I* the obtained energy map, *S* the set of points that form a 2-D window around the detected target in the head, and *H* the set of all points within the head area, the following metrics have been used to compare different beamforming algorithms.

The absolute distance Δ between the actual location of stroke *χ* and the location of the stroke predicted by the estimated maximum energy value in the backscattering energy map *I* is a measure of the effectiveness of the proposed system in locating the stroke.

Tissue | Dielectric Constant | Loss Tangent | Conductivity (S/m) |
---|---|---|---|

Skin | 37.952 | 0.28184 | 1.4876 |

Bone | 11.352 | 0.25597 | 0.40411 |

Brain matter | 36.107 | 0.24699 | 0.24699 |

Blood | 58.181 | 0.31981 | 2.5878 |

where

$$\begin{array}{rr}\hfill {r}_{0}^{*}=\underset{p\in H}{\mathrm{arg}\text{\hspace{0.17em}}\mathrm{max}\left[I\left({r}_{0}\right)\right]}& \hfill \left(7\right)\end{array}$$The stroke is localized with more precision, when this distance is lower.

The metric *Q* is used to evaluate if the stroke energy is high enough to classify it as a detectable stroke, against not completely removed artifacts. *Q* compares the average energy value in the stroke region with the average energy value in the rest of head tissues, given by:

A high value of this metric implies that stroke intensity is stronger than intensity of the background region, and results in a low residual level of artifacts.

Furthermore, an important aspect to take into account is the algorithms computational complexity, evaluated as magnitude order in terms of number of basic mathematic operations (sums and products), as function of the algorithms free parameters. Low computational complexity is a key design driver for this application, as it has an impact both on the response time of the device and on the cost.

Figures 2–3 show the backscattering energy map, in planar section, for two positions of the stroke, obtained with the PLSR-based pre-processing algorithm and the DAS, the MIST and the Modified RAR beamforming algorithms. The external ellipse is the planar section of the head, while the internal black circumference is the bleeding location. The energy output is represented as colored pixel in normalized energy scale. Figures on the left refer to the monostatic mode and figures on the right to the multistatic mode.

Table 2 and Table 3 summarize the performance metrics previously described for the different beamforming algorithms in a monostatic and multistatic mode, respectively.

As previously mentioned, the computational complexity of the system is dominated by the complexity of the beamforming algorithm. Therefore, the beamformer computational complexity is an essential requirement for a fast-response imaging device. Table 4 indicates the computational complexity of the DAS, MIST and Modified RAR algorithms, in monostatic and multi-static mode, for each pixel of the energy map, evaluated in terms of number of basic mathematical operations, in magnitude order, as function of the algorithms free parameters (channels number, sample number, FIR filters length).

From Figures 2 and 3 and related tables, it is evident that with a monostatic mode and a moderate number of antennas (8 rather than 16–32 as considered in[9]), the DAS algorithm is not able to locate the stroke. Same can be observed for the modified RAR algorithm. Only the MIST algorithm provides good performance, as the distance Δ in Table 2 shows. However also in case of MIST, a not negligible number of false alarms are introduced, as shown in Figures 2 (b) and 3 (b). In general, it can be concluded that with a moderate number of antennas, the monostatic approach is not suitable.Also in multistatic mode the DAS algorithm offers poor performance, especially in terms of false positives. Much better performance are achieved by the MIST and the Modified RAR. For example, the distance Δ in Table 3 for stroke location 1 is 91.24 for the DAS, significantly higher than the one of the MIST (4.999) and the Modified RAR (7.070).

Δ (mm) | Q (dB) | |
---|---|---|

Stroke Location 1 | ||

DAS | 116 | –3.800 |

MIST | 4.999 | 6.671 |

Modified RAR | 60.827 | 6.924 |

Stroke Location 2 | ||
---|---|---|

DAS | 45.000 | –3.410 |

MIST | 5.000 | 7.239 |

Modified RAR | 49.244 | 15.060 |

From Figures 2, 3 and Table 3 and as expected, it is evident that the MIST algorithm shows better performance than the other processing algorithms, with better accuracy of stroke localization and reduced amount of clutter, as the distance Δ and the *Q* metrics show. However, the MIST is characterized by a very high computational complexity, even in monostatic mode, which drastically increases the response time of the imaging tool. As shown in Table 4, in multistatic mode the MIST algorithm complexity is 5 magnitude orders greater than the DAS complexity and 4 magnitude orders than the Modified RAR. Specifically, the run time of the algorithms has been measured on a laptop with Intel Core i3 M330 2.13 GHz CPU. Several runs have been performed of all algorithms and the average run time has been calculated. The MIST algorithm run time is of some hours of processing (about 14000 s), while the DAS and the Modified RAR algorithms need only few minutes (about 205 s for the DAS and about 250 s for the Modified RAR). Therefore, the MIST algorithm is not a suitable solution for this application. The best trade-off performance-complexity is provided by the Modified RAR, whose performance are comparable (slightly worse) to the ones obtained by the MIST but it has much lower computational complexity, even if higher than the one of the DAS algorithm.

Δ (mm) | Q (dB) | |
---|---|---|

Stroke Location 1 | ||

DAS | 91.240 | 1.479 |

MIST | 4.999 | 15.008 |

Modified RAR | 7.070 | 13.079 |

Stroke Location 2 | ||
---|---|---|

DAS | 68.007 | 4.920 |

MIST | 5.000 | 15.601 |

Modified RAR | 10.000 | 7.669 |

DAS | MIST | Modified RAR | |
---|---|---|---|

Complexity (monostatic) | 10^{4} |
10^{8} |
10^{5} |

Complexity (multistatic) | 10^{4} |
10^{9} |
10^{5} |

This paper addresses the challenging task of designing an UWB microwave imaging tool that is transportable, able to detect the presence of stroke within a short response time and that has a lower cost with respect to traditional imaging tools used for stroke detection (such as CT and MRI).

Different beamforming algorithms (DAS, MIST and Modified RAR) have been compared in terms of different performance metrics and also computational complexity, both in monostatic and multistatic mode. Moreover, in the considered comparison, the number of antennas has been kept lower than in other literature works as it also contribute to the size/weight and cost of the device. Performance evaluation has considered the presence of noise.

First of all, when the number of antennas is low, the monostatic approach is not able to guarantee good performance, regardless the beamforming algorithm. A multistatic approach provides much better performance at expense of an increased computational complexity. This increase in computational complexity makes the MIST algorithm not feasible for this application. The best trade-off performance-complexity is provided by the modified RAR algorithm in a multistatic mode, which achieves performance that are comparable, or just slightly worse, with the ones of the MIST. This is an important result toward the implementation of a low cost and fast-response device, which is the main driver for the use of a MWI approach in stroke detection.

[1] Li, X., Hagness, S. (2001). Confocal microwave imaging algorithm for breast cancer detection. *IEEE Microw. Compon. Lett.* 11, 130–132.

[2] Bond, E., Li, X., Hagness, S., Van Veen, B. (2003). Microwave imaging via space-time beamforming for early detection of breast cancer. *IEEE Trans. Antennas Propag.* 51, 1690–1750.

[3] O’Halloran, M., Jones, E., Glavin, M. (2010). Quasi-multistatic MIST beamforming for the early detection of breast cancer. *IEEE Trans. Biomed. Eng.* 57, 830–840.

[4] Zhang, H., Flynn, B., Erdogan, A., Arslan, T. (2012). “Microwave imaging for brain tumor detection using an UWB Vivaldi antenna array,” in *Antenna Propagation Conference LAPC,* Loughborough.

[5] Yin, T., Ali, F., Reyes-Aldasoro, C. (2015). A robust and artifact resistant algorithm of ultrawideband imaging system for breast cancer detection. *IEEE Trans. Biomed. Eng.* 62, 1514–1525.

[6] Fhager, A., Persson, M. (2012). “Stroke detection and diagnosis with a microwave helmet,” in *Proceeding of the 6th European Conference Antennas Propagation, EuCAP*, 1796–1798,

[7] Persson, M., Fhager, A., Trefnà, H., Yinan, Y., McKelvey, T., Pegenius, G. et al. (2014). Microwave-based stroke diagnosis making global prehospital thrombolytic treatment possible. *IEEE Trans. Biomed. Eng.* 61, 2806–2817.

[8] Ireland, D., Bialkowski, M. (2011). Microwave head imaging for stroke detection. *Progr. Electromagn. Res.* 21, 163–175.

[9] Mohammed, B. J., Abbosh, A., Mustafa, S., Ireland, D. (2014). Microwave system for head imaging. *IEEE Trans. Instrum. Meas.* 63, 117–123.

[10] Ricci, E., Di Domenico, S., Cianca, E., Rossi, T. (2015). “Artifact removal algorithms for stroke detection using a multistatic MIST beamforming algorithm,” in *Proceeding of the 37th Annual International Conference EMBC*, 1930–1933.

[11] Mustafa, S., Mohammed, B., Abbosh, A. (2013). Novel preprocessing techniques for accurate microwave imaging of human brain. *IEEE Antennas Wireless Propag. Lett.* 12, 460–463.

[12] Ricci, E., Colucciello, A., di Domenico, S., Cianca, E., Rossi, T. (2015). “Modified RAR and PLSR-based artifact removal for stroke detection in UWB radar imaging,” in *Proceeding of the 5th International Conference Wireless Vitae*, San Jose, CA.

[13] Ricci, E., Maggio, F., Rossi, T., Cianca, E., Ruggieri, M. (2015). “UWB radar imaging based on space-time beamforming for stroke detection,” in *Proceeding of the 6th European Conference IFMBE*, Dubrovnik, HR, 946–949.

[14] Scapaticci, R., Di Donato, L., Crocco, L. (2012). A feasibility study on microwave imaging for brain stroke monitoring. *Prog. Electromagn. Res.* 40, 305–324.

[15] *Dielectric Properties of Body Tissues in the Frequency Range 10 Hz– 100 GHz* Available at: http://niremf.ifac.cnr.it/tissprop/

**E. Ricci** received her M.Sc. degree in Medical Engineering in 2012 at University of Rome Tor Vergata, where she is PhD student in the Department of Electronic Engineering. Her research is focused on medical imaging, biomedical signal processing, microwave imaging and UWB radar for biomedical application.

**E. Cianca** is assistant professor at the Department of Electronic Engineering of the University of Rome Tor Vergata. Her research activity is focused on DSP and beamforming for radar and wireless communications.

**T. Rossi** isAssistant Professor at University of Rome Tor Vergata. His research activity is focused on space systems, DSP and beamforming for radar and TLC applications.

*Journal of Communication, Navigation, Sensing and Services, Vol. 2,* 1–18.

doi: 10.13052/jconasense2246-2120.2016.001

© 2016 *River Publishers. All rights reserved.*

2.2.2 Microwave imaging space-time algorithm

2.2.3 Robust and artifact resistant