# A Low-Complexity Radar Detector Outperforming OS-CFAR for Indoor Drone
Obstacle Avoidance

Ali Safa, , Tim Verbelen, Lars Keuninckx, Ilja Ocket,
, Matthias Hartmann, André Bourdoux, ,
Francky Catthoor, , Georges G.E. Gielen Ali Safa, Ilja Ocket, Francky Catthoor
and Georges G.E Gielen are with imec and the Department of Electrical
Engineering, KU Leuven, 3001 Leuven, Belgium (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Georges.Gielen@kuleuven.be).Tim
Verbelen is with imec and the Department of Electrical Engineering, U Gent,
9000 Gent, Belgium (e-mail: Tim.Verbelen@imec.be).Lars Keuninckx, Matthias
Hartmann and André Bourdoux are with imec, 3001 Leuven, Belgium (e-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>Andre.Bourdoux@imec.be).

###### Abstract

As radar sensors are being miniaturized, there is a growing interest for using
them in indoor sensing applications such as indoor drone obstacle avoidance.
In those novel scenarios, radars must perform well in dense scenes with a
large number of neighboring scatterers. Central to radar performance is the
detection algorithm used to separate targets from the background noise and
clutter. Traditionally, most radar systems use conventional CFAR detectors but
their performance degrades in indoor scenarios with many reflectors. Inspired
by the advances in non-linear target detection, we propose a novel high-
performance, yet low-complexity target detector and we experimentally validate
our algorithm on a dataset acquired using a radar mounted on a drone. We
experimentally show that our proposed algorithm drastically outperforms OS-
CFAR (standard detector used in automotive systems) for our specific task of
indoor drone navigation with more than 19% higher probability of detection for
a given probability of false alarm. We also benchmark our proposed detector
against a number of recently proposed multi-target CFAR detectors and show an
improvement of 16% in probability of detection compared to CHA-CFAR, with even
larger improvements compared to both OR-CFAR and TS-LNCFAR in our particular
indoor scenario. To the best of our knowledge, this work improves the state of
the art for high-performance yet low-complexity radar detection in critical
indoor sensing applications.

###### Index Terms:

CFAR, indoor drone obstacle avoidance, indoor radar sensing, radar target
detection, drone navigation

## Supplementary Material

An evaluation code and videos showcasing hardware metrics and our system
implementation will be available at:
https://github.com/ali20480/RadarDetector

##  I Introduction

The use of radar sensors for indoor applications has been enabled recently
thanks to the enormous progress in radar miniaturization [1, 2] and energy
efficiency [3], making use of the Frequency Modulated Continuous Wave (FMCW)
design principle [4]. Among those indoor sensing applications, the navigation
of small Unmanned Aerial Vehicles (UAVs) or drones is extensively being
investigated for applications ranging from automated logistics [5] and indoor
maintenance inspection [6] to people search and rescue in partially damaged
infrastructures [7] all requiring robust obstacle avoidance. Currently, most
autonomous drone systems solely use camera-based sensing to perform obstacle
avoidance, path planning [8] and Simultaneous Localization and Mapping (SLAM)
[9]. As standard cameras have sensory limitations such as sensitivity to
lighting conditions, occlusion by dirt and no intrinsic ranging [10], many
teams are investigating the use of complementary sensors such as Light
Detection and Ranging (LIDARs) [11], Dynamic Vision Sensors (DVS) [12] and
radars [13]. The latter is the focus of this work. Radars are well-suited as a
complementary sensing modality because, unlike cameras, they intrinsically
provide range information, are very robust towards environmental effects and
are independent of lighting conditions [16]. Usually, radar sensors are
tightly coupled to pre-processing units that provide range, velocity and angle
of arrival spectra (so-called range-Doppler-angle profiles), which must be
filtered afterwards by detection algorithms in order to separate target peaks
from the background noise and clutter [17].

Traditional detectors used within the radar community are the so-called
Constant False Alarm Rate (CFAR) class of algorithms, from low-complexity Cell
Averaging (CA) CFAR to more computationally complex Ordered Statistics (OS)
CFAR [17]. As CA-based methods require a minimal separation distance between
targets, OS-CFAR has been proposed as a better approach to the CA-CFAR based
methods for multi-target scenarios where reflecting objects are closer to each
other [18]. OS-CFAR has thus widely been adopted in critical areas such as
outdoor automotive applications as its probability of detection $P_{D}$ for a
given probability of false alarm $P_{FA}$ is larger compared to CA-based
methods [19]. On the other hand, indoor scenes are usually composed of a much
larger number of reflecting objects placed closer to each other compared to
the outdoor case. During our experiments, we have observed that OS-CFAR fails
to detect all potential targets systematically when processing radar signals
during an indoor drone flight (a discussion is provided in section V-D), while
achieving a $P_{D}$ close to $1$ is essential for a safe obstacle avoidance.
Thus, reliable radar target detection remains a challenge as missed detections
can jeopardize the obstacle avoidance mechanisms and may crash the drone.
Therefore, there is a need for a better, yet low-complexity detection
algorithm featuring a higher $P_{D}$ for a certain $P_{FA}$ compared to the
conventional CFARs, not only including OS-CFAR but also more recent, state-of-
the-art CFAR variants such as OR-CFAR [40], TS-LNCFAR [41] and CHA-CFAR [42].

Finally, it is important to clarify that our aim is to achieve a safe obstacle
avoidance rather than odometry. When performing odometry (i.e., indoor
positioning), it is well known that detecting and tracking all potential
targets (even the weak ones) may worsen the positioning results (only good,
repeatable features must be tracked). On the other hand, when performing
obstacle avoidance like in our case, detecting all potential obstacles
($P_{D}$ close to $1$) is key for a safe drone flight (false alarms can be
further removed by fusion with other sensing modalities).

This paper is organized as follows. Section II briefly reviews the related
state-of-the-art works. Section III describes the background theory. Section
IV presents our proposed methods. Section V describes our experimental
validation. Finally, section VI concludes this article.

##  II Related Works

To the best of our knowledge, radar sensing for drones has mainly been
investigated for outdoor navigation above wasteland containing a sparse number
of ground objects (while our work addresses the indoor setting). Most recent
among those works, the authors in [13] demonstrated outdoor drone navigation
using an Inertial Measurement Unit (IMU, magnetometer, gyroscope and
accelerometer), a camera and a 24-GHz FMCW radar, and reported a lower RMS
navigation error against the ground-truth GPS compared to older radar-based
drone solutions [20, 21]. In addition, the authors in [13] clearly
demonstrated that conventional CFAR filters can suffer from a large number of
missed detections and therefore proposed an alternative detection mechanism by
first filtering the radar maps with a Gaussian kernel and then keeping the
five largest peaks as detection. While such detection algorithm is well suited
for navigation above wasteland containing an a priori known number of targets,
it is much less the case for the dense indoor setting where the (potentially
large) number of scatterers is unknown.

Regarding the use of radar in indoor drone navigation, the authors in [14]
proposed an indoor FMCW SAR imaging system mounted on a drone and tested in an
indoor setting with four corner reflectors and one large obstacle placed in
the middle of the scene. Although promising, a challenge faced with such
system is the lack of sufficient space in constrained indoor environments in
order to form a large aperture. In addition, as only a few strong reflectors
were present in the scene, it remains unclear how the system would behave in
realistic indoor scenarios in terms of effective detection and false alarms as
no explicit detection is performed (only imaging is provided). Another work
aiming at indoor SAR imaging using FMCW radars was proposed in [15], still
without a discussion on radar target detection.

As conventional CFAR filters can severely suffer from missed detection, a
large number of alternative methods have been proposed. The authors in [22]
proposed a detector which combines multiple conventional CFAR variants and
chooses the best one depending on the clutter homogeneity. The authors in [23]
proposed to estimate the detection threshold of conventional CFARs using
polynomial regression on the maps to be filtered, which, compared to the
conventional CA-CFAR, provided a better threshold estimate as higher
statistical moments are used during the estimation.

Recently, a number of CFAR detectors based on the truncated statistics
principle have been proposed for multi-target detection in outdoor
environments (e.g., ship detection from SAR images), using a careful modelling
of the clutter statistics [40, 41, 42]. In addition to OS-CFAR, the
applicability of those aforementioned methods to indoor scenarios is also
investigated in this work. Using modern machine learning techniques, a CFAR
detector using Support Vector Machines (SVMs) was proposed in [24] and a
neural network-based CFAR was proposed in [25]. Although highly efficient in
scenarios well captured by the training data, those methods based on
supervised training are not guaranteed to perform well across radically
different scenes.

Closely related to our work, the authors in [26] proposed the kernel RX (KRX)
detector as an enhancement of the classical Reed-Xiaoli (RX) detector used in
hyperspectral imagery [27]. They showed that KRX significantly outperforms RX
(in terms of the reachable $P_{D}$ for a certain $P_{FA}$) without being
significantly more computationally complex. Still, the KRX detector can be too
computationally expensive, as it requires a large number of matrix inversions
[26]. Therefore, we have derived our detector based on the same principles
used within KRX while proposing several modifications to simplify the
computational cost of the algorithm, such that implementation is possible in
extreme edge devices, in contrast to the KRX detector.

##  III Background Theory

First, the FMCW radar theory and pre-processing are briefly introduced. Then,
the conventional CFAR detectors are briefly discussed. Finally, the principles
behind the KRX detector are presented. These are needed to explain our method
in the next section.

###  III-A FMCW Radar

In Single Input Multiple Outputs (SIMO) mode, a radar uses one TX antenna and
$m=1,...,N_{RX}$ RX antennas, usually spaced by an inter-antenna distance
$d_{a}=\frac{\lambda}{2}$ where $\lambda$ is the radar carrier wavelength
[28]. In each sensing frame, the radar sends a sequence of $q=1,...,N_{c}$
chirps defined by:

$p_{q}(t)=\exp{j(2\pi f_{c}t+\pi\alpha t^{2})}$ (1)

where $f_{c}$ is the radar carrier frequency (77-GHz in this work) and
$\alpha$ is the chirp slope [29]. By reflection on surrounding objects, a mix
of delayed and attenuated versions of $p_{q}(t)$ is received at each RX
antennas. Those received signals are demodulated by the IQ receiver such that
for each chirp $q$ and each antenna $m$, an Intermediate Frequency (IF) signal
is obtained as follows:

$r_{qm}(t)=\sum_{i=1}^{N_{t}}\xi_{i}e^{j(-2\pi\alpha T_{d_{i}}t-2\pi
f_{c}T_{d_{i}}+\pi\alpha T_{d_{i}}^{2}+m\phi_{i})}$ (2)

where $N_{t}$ is the number of target reflectors in the scene, $\xi_{i}$ is
the attenuation of the target reflector $i$, $\phi_{i}$ is the phase shift of
target $i$ induced by its angle of arrival, and $T_{d_{i}}$ is the round-trip
time from the radar antenna to the target $i$, which is proportional to the
distance $d_{i}$ between the radar and the target as
$T_{d_{i}}=\frac{2d_{i}}{c}$ (where $c$ is the speed of light) [17]. The phase
shift $\phi_{i}$ for target $i$ is given by $\phi_{i}=\pi\sin{\theta_{i}}$
[28] where $\theta_{i}$ is the angle of arrival of the signal reflected by
target $i$. The IF signals $r_{qm}(t)$ (2) are then sampled by an ADC with a
sampling period $T_{f}$ to obtain the discrete-time signals $r_{qm}[n]$ for
each chirp $q$ and each antenna $m$. It is then possible to retrieve the
range, Doppler radial velocity and angle of arrival of each target $i$ by
computing the Discrete Fourier Transform (DFT) of $r_{qm}[n]$ along $n$, $q$
and $m$, respectively (a 3D DFT for each radar frame) [30]. The magnitude of
the resulting data cube exhibits $N_{t}$ peaks at the bin locations
corresponding to the range, velocity and angle of arrival of each target $i$
in the scene.

Noise, clutter (ground echo) and multipath will also result in additional
undesired peaks that must be filtered using a detection algorithm such as
conventional CFAR algorithms [17]. To reduce the number of DFT and detection
operations (and thus, to increase the maximal frame rate achievable by the
sensing system), the 3D DFT is not done at once; rather, a 1D DFT is first
performed along $n$ to obtain the so called range profile (RP) with its
magnitude containing peaks at target locations. The magnitude of the RP is
then filtered by a detector such as a CFAR, obtaining a subset of populated
range bins. It is then possible to perform the DFTs along $q$ and $m$ for each
populated range bin only, to reduce the computational costs. It must be noted
that this solution is well-suited when the relative velocity between the radar
and the obstacles is relatively low so that the target remains within the same
range bin at different time epochs, which is the case in indoor navigation,
where the drone speed is relatively low due to the size of the drone and the
weight of the payloads (for a drone flying at $10$kph with a typical coherent
processing interval of $12$ms as used in our radar setup, the maximum range
migration of obstacles will be about $2.8$m/s$\times 0.012=3.36$cm which falls
below the range resolution of $7.1$cm used in our radar setup).

Another, more expensive approach is to first perform the 2D DFT along $n$ and
$q$ to obtain the so-called range-Doppler profile (RDP). The RDP is then
filtered along each range and Doppler bin to find the subset of populated
bins. As this second method introduces an additional decorrelation,
conventional CFAR detectors will perform better at the expense of a severe
increase in computation (i.e., the detection in this second approach must be
performed along each range and Doppler bin with typical dimensions of e.g.
$256\times 128$ bins versus only one detection pass for the first approach)
[31].

As high frame rates are desired for our indoor drone application to increase
the dynamic responsiveness of the drone, we therefore adopt the first approach
even though this method trades off lower signal processing gain for higher
speed. In addition, this will allow us to assess the performance of our
algorithms on more challenging data in section V as a second decorrelation
introducing the additional Doppler processing gain is not introduced.

###  III-B Conventional CFAR detectors

CFAR filters are used to detect targets in unknown background noise [17]. The
most traditional CFAR is the CA-CFAR, which computes a local detection
threshold for the cell under test (CUT) proportional to the average of the
local training cells in a sliding analysis window (see Fig. 1 where $S$ is the
CUT and the $Z_{l}[x]$ and $Z_{r}[x]$ are the left and right training cells,
respectively).

Figure 1: A typical range profile being filtered by a CFAR detector. The CUT
is the cell $S$ in the middle, the training cells form a vector $Z[x]$ and the
remaining bins are the guard cells.

For locally open environments, where scatterers are well isolated, CA-CFAR
performs well, but its performance can strongly degrade in non-homogeneous
environments where multiple targets and clutter edges are present [24]. The
greatest of (GO) CA-CFAR (which chooses the greatest average between the left
training cells $Z_{l}[x]$ and the right training cells $Z_{r}[x]$) performs
better compared to CA-CFAR in environments with several clutter edges but
suffers from a loss in $P_{D}$ when mulitple targets are present locally. On
the other hand, smallest of (SO) CA-CFAR (which chooses the smallest average
between the left training cells $Z_{l}[x]$ and the right training cells
$Z_{r}[x]$) performs better in the multi-target scenario but is very sensitive
to clutter edges, resulting in a significant increase in $P_{FA}$ [17].

It has been reported that the OS-CFAR performs significantly better than CA-
based CFARs for the multi-target case (its $P_{D}$ is larger than CA-CFAR for
a certain $P_{FA}$) and therefore has widely been adopted in (outdoor)
automotive applications [18, 19, 32]. OS-CFAR first sorts all the training
cells in increasing order and selects the $k^{th}$ element as the noise
estimate $\hat{\beta}^{2}$. Then, the local detection threshold is derived as
$T=\alpha\hat{\beta}^{2}$ where $\alpha$ sets the $P_{FA}$ and $k$ is a
parameter to be chosen.

Clearly, as this method requires a sorting operation per CUT, it is
significantly more computationally expensive than CA-based methods [32]. OS-
CFAR has a typical complexity of $O(LN_{tc}^{2})$ when using Bubble sorting
and $O(LN_{tc}\ln{(N_{tc})})$ when using Quick sorting where $N_{tc}$ is the
number of training cells (noted as $Z[x]$ in Fig. 1) and $L$ is the total
number of range bins [18]. On the other hand, CA-based methods have a
complexity of $O(L)$ as multiply-accumulate operations can be done in one
clock cycle on CPUs with vectored instructions, unlike sorting. The goal of
our proposed detector is to improve the performance beyond OS-CFAR, while
reducing the computational complexity. In section V, we will benchmark our
proposed detector against OS-CFAR as it is the standard detector adopted in
most multi-target applications [17].

###  III-C State-of-the-art CFAR principles for multi-target scenarios

Even though still widely used in practice, the conventional CFAR detectors
discussed in section III-B have shortcomings in a number of situations where
their clutter statistics estimation performance becomes poor (multi-target
environments, non-homogeneous clutter and so on) [39]. Thanks to the enormous
progress made by the remote sensing community, a number of novel radar
detectors specially tailored for the multi-target scenario have been proposed,
achieving state-of-the-art result in anomaly detection from satellite SAR
images [40, 41, 42, 43]. Among those, we consider three candidate detectors in
this work, in addition to OS-CFAR.

####  III-C1 Outlier-robust CFAR (OR-CFAR)

OR-CFAR [40] has been proposed as a well-suited detector for Gaussian clutter
scenarios subject to an important number of outliers that could jeopardize the
noise estimation performance of conventional CFAR methods. OR-CFAR achieves a
robust noise estimation performance by using a truncated statistics (TS)
mechanism where outliers in the training cells $Z[x]$ are removed if:

$Z[x]-\mu>\gamma\sigma$ (3)

where $\gamma$ is the truncation depth, $\mu$ is the mean of the training
cells and $\sigma$ their standard deviation. Then, the maximum-likelihood (ML)
estimate of the clutter mean $\hat{\mu}$ and standard deviation $\hat{\sigma}$
from the remaining training cells $\tilde{Z}[x]$ after truncation by (7) are
given by [40]:

$\hat{\sigma}=\sqrt{\frac{1}{\chi}\\{\frac{1}{n}\sum_{i=1}^{n}\tilde{Z}[i]^{2}-(\frac{1}{n}\sum_{i=1}^{n}\tilde{Z}[i])^{2}\\}}$
(4)

$\hat{\mu}=\frac{1}{n}\sum_{i=1}^{n}\tilde{Z}[i]+\alpha\hat{\sigma}$ (5)

$\alpha=\frac{e^{-\frac{\gamma^{2}}{2}}}{\sqrt{2\pi}\phi(\gamma)},\hskip
10.0pt\beta=1-\gamma\alpha,\hskip 10.0pt\chi=\frac{1}{\beta-\alpha^{2}}$ (6)

where $\phi(.)$ is the CDF of the standard normal distribution and $n$ the
number of training cells after truncation. A CUT of amplitude $S$ is reported
as a detection if $S>\hat{\mu}+t\hat{\sigma}$ where $t$ is a parameter setting
the desired $P_{FA}$.

####  III-C2 Truncated statistics log-normal CFAR (TS-LNCFAR)

TS-LNCFAR [41] has been proposed as a well-suited detector for log-normal
clutter scenarios subject to an important number of outliers. Similarly to OR-
CFAR, TS-LNCFAR uses a TS approach for outlier rejection, followed by a ML
estimation of the clutter mean and standard deviation. Outliers in the
training cells are removed if:

$\ln Z[x]-\mu>\gamma\sigma$ (7)

with $\gamma$ the truncation depth and $\mu$, $\sigma$ the mean and standard
deviation of the log training cells $\ln Z[x]$. The ML estimate of the clutter
mean $\hat{\mu}_{ln}$ and standard deviation $\hat{\sigma}_{ln}$ are then
given by a set of equation similar to those in OR-CFAR [41]. A CUT of
amplitude $S$ is reported as a detection if $\ln
S>\hat{\mu}_{ln}+t\hat{\sigma}_{ln}$ where $t$ is a parameter setting the
desired $P_{FA}$.

####  III-C3 Censored harmonic averaging CFAR (CHA-CFAR)

CHA-CFAR [42] has been proposed as a well-suited detector for exponential
clutter scenarios affected by a large number of outliers. In contrast to
methods that seek to hardly remove outliers by truncation (such as in OR-CFAR
and TS-LNCFAR), CHA-CFAR softly removes the effect of outliers using the
harmonic mean and the OS principle to estimate the noise level $\hat{\omega}$:

$\hat{\omega}=(z_{m+1}^{-1}+z_{m+2}^{-1}+...+z_{N}^{-1})^{-1}$ (8)

where $\\{z_{1},...z_{N}\\}$ is a set obtained by sorting the elements of
$Z[x]$ in increasing order and $m$ is the number of discarded samples (with
the smallest amplitude) [42]. A CUT of amplitude $S$ is reported as a
detection if $S>t\hat{\omega}$ where $t$ is a parameter setting the desired
$P_{FA}$.

As those state-of-the-art, multi-target techniques have mostly been
demonstrated for earth and ocean observation, it is interesting to study their
applicability in indoor environments. Therefore, in addition to OS-CFAR
(standard detector for automotive applications), we will also benchmark our
proposed detector against OR-CFAR, TS-LNCFAR and CHA-CFAR in section V.

###  III-D KRX detection principle

The novel detector that we propose in this work (in section IV) is based on
the principles behind kernel RX (KRX) detection [26]. The KRX detector has
initially been proposed for hyperspectral images, where each pixel $\bar{x}$
is a vector with each vector entry corresponding to a certain spectral band
(as opposed to the RP that we aim to filter in this work, obtained after
applying range processing on (2), where each pixel $\bar{x}$ of the RP reduces
to a scalar). In order to introduce KRX, the original RX detector, on which
KRX is built, must be introduced first. The RX detector can be seen as a
generalization of the CA-CFAR method to the multivariate Gaussian case (pixels
are not scalars but rather vectors) [27]:

$RX(\bar{x})=(\bar{x}-\hat{\bar{\mu}})^{T}\hat{C}^{-1}(\bar{x}-\hat{\bar{\mu}})$
(9)

where a pixel $\bar{x}$ is detected when $RX(\bar{x})>T$, where $T$ is a
threshold setting the $P_{FA}$. $\hat{\bar{\mu}}$ and $\hat{C}$ respectively
denote the mean vector and the covariance matrix of the multivariate Gaussian
noise estimated from the training cells in the sliding window (similar to Fig.
1). When the background statistics cannot be modelled by a single Gaussian
distribution (as in our multi-target scenario), the RX detector performance
degrades significantly [33]. KRX was proposed in [26] as a nonlinear version
of RX, which expresses the original RX model of (9) in a high-dimensional
feature space $\mathcal{F}$ of dimension $D$ through a nonlinear
transformation $\Phi(\bar{x})$ as:

$KRX(\bar{x})=(\Phi(\bar{x})-\hat{\bar{\mu}}_{\Phi})^{T}\hat{C}^{-1}_{\Phi}(\Phi(\bar{x})-\hat{\bar{\mu}}_{\Phi})$
(10)

where $\hat{\bar{\mu}}_{\Phi}$ and $\hat{C}_{\Phi}$ denote the estimated mean
and covariance in $\mathcal{F}$. The covariance matrix in the feature space
$\mathcal{F}$ is defined as
$\hat{C}_{\Phi}=(\Phi(X_{tc})-\hat{\bar{\mu}}_{\Phi})^{T}(\Phi(X_{tc})-\hat{\bar{\mu}}_{\Phi})$
where $X_{tc}$ defines a matrix containing the training pixel vectors along
each column and $\Phi(X_{tc})$ denotes the application of $\Phi$ to each of
the individual vectors in $X_{tc}$. Eq. (10) is derived by considering that,
once projected to $\mathcal{F}$, the model is well-approximated by a Gaussian
distribution, even though the process is non-Gaussian in the original space
[33]. As $\mathcal{F}$ could possibly be of infinite dimensions, (10) is
simplified using the kernel trick [34], which replaces the inner products
found by expanding the terms in (10) by a kernel function
$k(\bar{x}_{i},\bar{x}_{j})=\langle\Phi(\bar{x}_{i}),\Phi(\bar{x}_{j})\rangle$.

A common choice for $k(\bar{x}_{i},\bar{x}_{j})$ is the Radial Basis Function
(RBF)
$k(\bar{x}_{i},\bar{x}_{j})=\exp(-\gamma||\bar{x}_{i}-\bar{x}_{j}||_{2}^{2})$
for which the Gaussian assumption in $\mathcal{F}$ holds [26]. Thus, KRX
nonlinearly projects the input data in a space $\mathcal{F}$ which is such
that a simple threshold decision region in $\mathcal{F}$ corresponds to a much
more complex decision region in the original space. This enables the algorithm
to perform significantly better in environments with complex background
statistics such as highly cluttered and multi-target indoor scenes [26]. Also,
other hyperspectral detectors have been extended using the non-linear
projection principle described above and it was demonstrated that the
nonlinear versions always outperformed the original ones in terms of reaching
a high $P_{D}$ for a given $P_{FA}$ [35].

Although promising for our near-sensor detection application, the approach
given above still presents three challenges for implementation on resource-
constrained computing platforms:

  1. 1.

Even when the kernel trick is used, (10) requires a large matrix inversion per
CUT ($N_{tc}\times N_{tc}$) [26], making is unsuited for fast near-sensor
detection.

  2. 2.

The RBF kernel is an exponential model requiring a high bit precision as its
scale changes rapidly [36]. Can we find a nonlinear transformation $\Phi$
well-suited for heavy quantization, even down to 1-bit precision?

  3. 3.

If such $\Phi$ that is well-suited for 1-bit quantization exists, the Gaussian
assumption in the feature space will not hold anymore. How can we then correct
for this initial assumption?

These challenges will be addressed by our proposed detector (see next
section).

##  IV Proposed Detector

In this section, we derive our novel detector starting from (10). We first
remark that (10) is the square of the Mahalanobis distance between
$\Phi(\bar{x})$ and $\hat{\bar{\mu}}_{\Phi}$, which is a measure of distance
between $\Phi(\bar{x})$ and the background statistics in $\mathcal{F}$ [33].
When this distance is larger than a threshold $T_{0}$, $\bar{x}$ is reported
as a detection. We can consider the dual problem [37]: when the correlation
between $\Phi(\bar{x})$ and the background statistics in $\mathcal{F}$ is
smaller than a threshold $T_{1}$, $\bar{x}$ is reported as a detection. The
original detection problem:

$(\Phi(\bar{x})-\hat{\bar{\mu}}_{\Phi})^{T}\hat{C}^{-1}_{\Phi}(\Phi(\bar{x})-\hat{\bar{\mu}}_{\Phi})>T_{0}$
(11)

then becomes:

$(\Phi(\bar{x})-\hat{\bar{\mu}}_{\Phi})^{T}\hat{C}_{\Phi}(\Phi(\bar{x})-\hat{\bar{\mu}}_{\Phi})<T_{1}$
(12)

where the computationally expensive matrix inversion does not appear anymore.
Eq. (11) and (12) are dual in the sense that searching for a $\Phi(\bar{x})$
with a distance larger than a certain threshold from a distribution
parametrized through $\hat{\bar{\mu}}$ and $\hat{C}_{\Phi}$ (11) is
conceptually the same as searching for a $\Phi(\bar{x})$ with a correlation
smaller than a certain threshold from the same distribution (12). It is
important to note that, although solving the same problem, (11) and (12) are
not identical per se as they are solutions to different optimization problems
(see [37] for a review). In order to simplify (12) even more, we choose a
transformation $\Phi$ such that $\hat{\bar{\mu}}_{\Phi}\xrightarrow{}\bar{0}$
with $\hat{\bar{\mu}}_{\Phi}$ defined as:

$\hat{\bar{\mu}}_{\Phi}=\frac{1}{N_{tc}}\sum_{i=1}^{N_{tc}}\Phi(\bar{x}_{i})$
(13)

where $N_{tc}$ is the number of training cells in the window from which the
noise estimation is performed. We therefore choose a $\Phi$ which induces
sparse projections $\Phi(\bar{x})$ in $\mathcal{F}$, with only a few (possibly
one) non-zero entries, such that $\hat{\bar{\mu}}_{\Phi}$ can be dropped in
(12). Under this sparse projection, (12) becomes:

$\Phi(\bar{x})^{T}\Phi(X_{tc})\Phi(X_{tc})^{T}\Phi(\bar{x})<T_{1}$ (14)

where $X_{tc}$ is a $D\times N_{tc}$ matrix with $D$ the dimension of
$\mathcal{F}$, containing the projection of the training cells in
$\mathcal{F}$. We can further rewrite (14) as:

$\Phi(\bar{x})^{T}\bar{N}_{\Phi}<T_{1}$ (15)

where $\bar{N}_{\Phi}$ can be seen as a summary of the background noise
statistics integrated through $\Phi(\bar{x})$ against which the correlation is
measured. As remarked in section III-D, (15) holds under Gaussian assumption
in the feature space. As we are aiming for a sparse $\Phi$, well-suited for
1-bit quantization, the Gaussian assumption does not hold and we need to
modify how the background noise statistics are summarized in $\mathcal{F}$
through a modification of $\bar{N}_{\Phi}$.

To this end, we use the simple heuristic used by SOCA-CFAR, which states that
the larger the norm of a pixel in the initial space, the less likely it is
noise, such that its effect should be attenuated when summarizing the
background noise statistics [17]. Using this heuristic, we replace
$\bar{N}_{\Phi}$ by a centroid across the training cells where each weight is
inversely proportional to the $L_{2}$-norm of its corresponding training
pixel:

$\bar{N}_{\Phi}^{m}=\frac{1}{\Gamma}\sum_{j=1}^{N_{tc}}\frac{1}{||X_{tc}[j]||_{2}}\Phi(X_{tc}[j])$
(16)

where $X_{tc}$ is assumed to be normalized to a maximum pixel $L_{2}$ norm of
$1$, with

$\Gamma=\sum_{j=1}^{N_{tc}}\frac{1}{||X_{tc}[j]||_{2}}$ (17)

being the amplitude normalization factor to effectively compute a centroid.
The test (15) then becomes:

$\Phi(\bar{x})^{T}\bar{N}_{\Phi}^{m}<T_{1}$ (18)

Further simplifications can be made to reduce the amount of multiply and
divide operations in (16), (17) and (18). First, we can truncate the Taylor
expansion of $x^{-1}$ around $1$ to the first-order term as
$\frac{1}{x}\approx 2-x$ where we can substitute $x=2||X_{tc}[j]||_{2}$ (with
$x\in[0,2]$ as we considered $||X_{tc}[j]||_{2}\in[0,1]$) to obtain:

$\frac{1}{||X_{tc}[j]||_{2}}\approx 2(1-||X_{tc}[j]||_{2})$ (19)

Therefore, instead of computing $\frac{1}{||X_{tc}[j]||_{2}}$, we will compute
$(1-||X_{tc}[j]||_{2})$ where the constant $2$ is dropped after normalization
by $\Gamma$. Secondly, we can remove the expensive multiply-accumulate
operations in (18) by solving the dual problem: a small ($<T_{1}$) correlation
between $\Phi(\bar{x})$ and $\bar{N}_{\Phi}^{m}$ corresponds to a large
distance between $\Phi(\bar{x})$ and $\bar{N}_{\Phi}^{m}$:

$||\Phi(\bar{x})-\bar{N}_{\Phi}^{m}||_{p}>T_{2}$ (20)

We choose $p=\infty$ instead of $p=2$ for two reasons. First, in order to
replace the explicit norm computation involving multiply-accumulate operations
by a sequence of simple comparison operations in parallel. Secondly, to
attenuate the data-dependent bias introduced in the relation between the
correlation in (18) and the $L_{2}$ norm
$||\vec{a}-\vec{b}||_{2}^{2}=\sum_{i}a_{i}^{2}+\sum_{i}b_{i}^{2}-2\sum_{i}\vec{a}_{i}\vec{b}_{i}$
where the term $\sum_{i}x_{i}y_{i}$ is the correlation and the term
$\sum_{i}x_{i}^{2}+\sum_{i}y_{i}^{2}$ is a data-dependent bias. The
$L_{\infty}$-norm attenuates this bias as
$||\vec{a}-\vec{b}||_{\infty}\leq||\vec{a}-\vec{b}||_{2}$ always holds [38].
At this point we have our final detector (20). In the sliding window, the CUT
$\bar{x}$ will be reported as a detection if (20) holds with $p=\infty$.

Finally, we need to find a non-linear and sparse transformation $\Phi$. As our
goal is to filter a radar RP in this work, the pixels $\bar{x}$ that were
generically considered as vectors become scalars that we note as $\xi=\bar{x}$
in the remainder of the derivation. We found that a well-suited $\Phi$ is the
one-hot encoding of $\xi$ as follows:

$\Phi(\xi)_{i}=\begin{cases}1,&\mbox{if
}i=D-\left\lfloor{\frac{D}{\xi}}\right\rfloor\\\ 0,&\mbox{else}\end{cases}$
(21)

where $D$ is the dimension of the destination space $\mathcal{F}$. Such
transformation is well-suited as it is binary (1-bit precision), sparse (as at
most one element is non-zero, $\hat{\bar{\mu}}_{\Phi}$ can be ignored in (12))
and promotes linear independence between the pixel projections in
$\mathcal{F}$ (which better complies with the constraint of non-singular
covariance matrix $\hat{C}_{\Phi}$ in the original problem of KRX (11)).

In summary, our detection algorithm performs the following steps:

  1. 1.

$\Phi$ (21) is applied to the CUT and the training cells in the sliding
window.

  2. 2.

$\bar{N}_{\Phi}^{m}$ is computed following (16), (17) with the simplification
of (19).

  3. 3.

Each entry $i$ of the CUT projection $\Phi(\xi)[i]$ is compared to
$T_{2}+\bar{N}_{\Phi}^{m}[i]$ and the CUT is reported as a detection as soon
as an entry $i$ gives $\Phi(\xi)[i]>T_{2}+\bar{N}_{\Phi}^{m}[i]$ (by virtue of
the infinite-norm in (20)).

Similar to the original KRX detector, finding a closed-form relation between
the threshold $T_{2}$ and the $P_{FA}$ is intractable, and the threshold must
rather be selected empirically by 1) acquiring a labelled dataset 2) measuring
the experimental $P_{FA}$ and $P_{D}$ values by sweeping the threshold and 3)
selecting a threshold returning the desired $P_{FA}$ and $P_{D}$ [33].

The complexity of our proposed algorithm is $O(LD)$ compared to
$O(LN_{tc}^{2})$ and $O(LN_{tc}\ln{(N_{tc})})$ for OS-based methods (such as
OS-CFAR and CHA-CFAR) and $O(L)$ for CA-based methods (such as OR-CFAR and TS-
LNCFAR) [32], where $D$ is rather small as equation (21) projects scalars to
vectors (we found $D\leq 15$ to be well-suited during our experiments, see
section V).

Because of the simple heuristic rule used in (16), we expect the performance
of the algorithm to degrade for degenerated situations where an overwhelmingly
large number of neighbouring targets are present, as most bins in the sliding
window will then miss-represent the noise statistics (those situations are
unlikely to happen through as realistic indoor scenes always have some empty
space between obstacles). Nevertheless, we found this rule to be both
necessary and efficient during our experiments in a regular indoor scenario:
removing it was causing a severe performance degradation while incorporating
it provided excellent detection results (see the ablation studies in section
V-F).

##  V Experimental Performance Assessment

In this section, we will experimentally assess the performance of our novel
detector against OS-CFAR by generating the Receiver Operating Curves (ROC:
$P_{D}$ versus of $P_{FA}$) of both solutions on labelled radar data acquired
using a drone flying in a dense indoor scene.

###  V-A Experimental Setup

Fig. 2 shows the NXP HoverGames drone that we used to acquire the radar data.
This drone setup is well-suited for indoor tasks such as automated logistics,
as it has sufficient power to carry payloads in the kilogram range. In
addition, the off-the-shelve 79 GHz radar sensor is well-suited for precise
obstacle ranging due to its centimetre-scale range resolution. The radar
parameters are given in table I, where $L$ is the number of ADC samples per
chirp, $T_{f}$ is the ADC sampling period, $N_{c}$ is the number of chirps in
one frame, $T_{c}$ is the chirp period, $\alpha$ is the chirp slope and
$d_{max}$ is the maximal distance that can be sensed.

$L$ | $T_{f}$ | $N_{c}$ | $T_{c}$ | $\alpha$ | $d_{max}$
---|---|---|---|---|---
256 | 160 ns | 128 | 80 $\mu$s | 50 MHz/$\mu$s |  $18.3$ m
TABLE I: Radar parameters

Figure 2: Our NXP HoverGames drone with a 79 GHz Texas Instruments radar and
an on-board camera.

Figure 3: An illustrative example RP obtained when the drone was moving
towards the shelves.

Figure 4: Effect of applying our detector to the RP of Fig. 3. The detection
is performed as in (20) by thresholding
$||\Phi(\bar{x})-\bar{N}_{\Phi}^{m}||_{\infty}$ (purple plot) against $T_{2}$.
The detections are shown in red. The $D$ parameter was set to $15$ in this
example.

We navigated the drone in an indoor environment composed of benches, chairs,
shelves and so on, and we obtained a dataset of nearly $400$ radar frames. Out
of that dataset, we selected a subset of $100$ frames corresponding to the
cases where the drone was flying towards a dense part of the environment,
either towards the three shelves in Fig. 2 or towards benches and chairs.
Those cases represent the challenging, dense scenarios where missed detection
can be detrimental to the drone. We finally obtained a dataset of 100 RPs and
we visually labelled as a detection each significant peak in each of the 100
RPs. Fig. 3 shows an illustrative example of a RP acquired when the drone was
flying towards the shelves. The red stars denote the labelled indexes against
which the detection algorithms will be compared. Fig. 4 shows the effect of
applying our detector to the RP of Fig. 3, as per (20),
$||\Phi(\bar{x})-\bar{N}_{\Phi}^{m}||_{\infty}$ is compared against a
threshold level $T_{2}=0.95$ to obtain the subset of detected range bins. Fig.
4 shows the processing gain that our detector provides by mapping not only the
strong RP peaks, but also the minute but significant peaks of the RP to high
values of $||\Phi(\bar{x})-\bar{N}_{\Phi}^{m}||_{\infty}$ (purple plot), while
keeping this value lower for noise bins.

###  V-B ROC-based Results

The standard method used to compare detectors is the generation of the ROC
curves giving the probability of detection $P_{D}$ versus the probability of
false alarm $P_{FA}$. $P_{D}$ is defined as the number of ground-truth
detection labels found by the detector under test over the total number of
ground-truth detection labels. Similarly, $P_{FA}$ is defined as the number of
detections returned by the detector under test and not associated to any
ground-truth detection label, over the total number of range-bin $L$. The
higher the $P_{D}$ for a given $P_{FA}$, the better. We compute $P_{D}$ and
$P_{FA}$ for both our method and OS-CFAR by applying them to each of the 100
RPs and by comparing their output to the labels. We consider that a detection
is a false alarm when it lies at a distance larger than $5$ range bins ($35$
cm) from any label and vice versa for a correct detection. We therefore obtain
the number of detected labels $N_{Di}$ and the number of false alarms
$N_{FAi}$ for each RP $i=1,...,100$. $P_{D}$ is then obtained as
$\frac{1}{100}\sum_{i}(N_{Di}/l_{i})$ where $l_{i}$ is the number of labelled
indexes for RP $i$ while $P_{FA}$ is obtained as
$\frac{1}{100}\sum_{i}(N_{FAi}/L)$ where $L=256$ is the number of range bins
in the RPs. The tuples $(P_{D},P_{FA})$ are computed for different threshold
values $T_{2}$ for our detector (see section IV), different $\alpha$ and $k$
parameters for OS-CFAR (see section III-B) and different numbers of training
and guard cells ($N_{tc}$, $N_{g}$) for both methods. Each threshold value
leads to a different tuple $(P_{D},P_{FA})$ and the set of tuples is plotted
as the ROC curve. For our proposed detector, we set the dimensionality $D$ of
the transformation $\Phi(\xi)$ to 15 as it gave us the best results. Fig. 5
shows the ROC curves for our proposed detector. Fig. 6 to 8 jointly show the
ROC curves for our proposed detector and for OS-CFAR, for different values of
order parameter $k$ and for the same combinations of $N_{tc}$ and $N_{g}$ as
in Fig. 5. It is visually clear that our method significantly outperforms OS-
CFAR without the requirement for computationally expensive sorting operations
per CUT. Our proposed algorithm always achieves a significantly larger $P_{D}$
for a given $P_{FA}$, for the different combinations of $k$, $N_{tc}$ and
$N_{g}$, with a measured average gain of more than $\mathbf{19\%}$ between
ROCs of the same $N_{tc}$ and $N_{g}$ on the achievable $P_{D}$ for a given
$P_{FA}$, for $P_{FA}$ values smaller than 1% (typical values used in
practice).

Figure 5: ROC curves for our proposed detector, for different combinations of
$N_{tc}$ and $N_{g}$. $D=15$.

Figure 6: k = 0.5 for OS-CFAR. Average gain of 40% on $P_{D}$ compared to OS-
CFAR for $P_{FA}<1\%$.

Figure 7: k = 0.7 for OS-CFAR. Average gain of 19% on $P_{D}$ compared to OS-
CFAR for $P_{FA}<1\%$.

Figure 8: k = 0.9 for OS-CFAR. Average gain of 21% on $P_{D}$ compared to OS-
CFAR for $P_{FA}<1\%$.

Figure 9: OR-CFAR with $\mathbf{\gamma=1.3}$. Average gain of 20% on $P_{D}$
compared to CHA-CFAR for $P_{FA}<1\%$.

Figure 10: TS-LNCFAR with $\mathbf{\gamma=1.8}$. Average gain of 35% on
$P_{D}$ compared to CHA-CFAR for $P_{FA}<1\%$.

Figure 11: CHA-CFAR with $\mathbf{m=0.65\times N_{tc}}$. Average gain of 16%
on $P_{D}$ compared to CHA-CFAR for $P_{FA}<1\%$.

In addition, we compare our proposed detector to OR-CFAR, TS-LNCFAR and CHA-
CFAR (Fig. 9, 10 and 11) by tuning the truncation parameter $\gamma$ of OR-
CFAR and TS-LNCFAR, and the order parameter $m$ of CHA-CFAR such that each
competing detector reaches its best performance on the indoor drone dataset
used for the assessment. A trend similar to the OS-CFAR case is observed where
our proposed detector systematically leads to a higher $P_{D}$ for a given
$P_{FA}$ for our particular indoor scenario (OR-CFAR, TS-LNCFAR and CHA-CFAR
are rather tailored for remote earth observation with higher-resolution SAR
images). This shows the effectiveness of our new detection algorithm when used
in indoor, industrial settings.

###  V-C Result confirmation with ground-truth data

As our goal is to detect as many targets as possible for a safe obstacle
avoidance, the assessment presented in section V-B has been conducted with
manually labelled RP data, where each significant peak is marked as a
potential obstacle. The potential downside of this visual labelling
methodology is that noise and clutter could also lead to peaks in the RP,
which, once labelled, would jeopardise the ROC assessment. On the other hand,
the scenes acquired by our drone and radar are rich of obstacles. This
motivates the fact that the overwhelming majority of labelled peaks would
correspond to actual targets. Still, it is important to confirm this fact
using a well-controlled, yet realistic radar dataset with ground-truth
measurements. Therefore, we acquired a second RP dataset in an empty room by
keeping our drone and radar setup static, with two people walking in front of
it. During the radar acquisition, a Marvermind indoor GPS device was used to
acquire the ground-truth location of the two walking people. This scenario was
chosen as it is more realistic than using usual corner reflector beacons
(e.g., the scenario simulates a drone waiting for instructions with people
walking in its neighbourhood). Yet, the chosen scenario enables precise
ground-truth measurements using the indoor GPS. Fig. 12 depicts the
acquisition scenario.

Figure 12: Ground-truth and radar acquisition. The two walking people hold
their indoor GPS beacon on their head during the radar acquisition.

Similar to section V-B, a ROC-based comparison of our method against OS-CFAR
has been conducted. The results are shown in Fig. 13. The OS-CFAR parameter
$k$ is set to $0.7$ as this value corresponds to the smallest gain between our
proposed method and OS-CFAR in the previous assessment of section V-B, Fig. 7.
The parameter $D$ of our proposed algorithm is set to $4$ in order to reach a
desired $P_{fa}$ range of $<1\%$ (the impact of the $D$ parameter will be
further detailed in section V-E). Compared to the results of section V-B, Fig.
13 shows a similar trend where our proposed detector provides again a
significant gain ($44\%$) on $P_{D}$ compared to OS-CFAR for the different
combinations of $N_{tc}$ and $N_{g}$ (same as in Fig. 5).

Figure 13: k = 0.7 for OS-CFAR. Average gain of 19 % on $P_{D}$ compared to
OS-CFAR for $P_{FA}$ values smaller than 1%.

Figure 14: $\mathbf{m=0.4\times N_{tc}}$ for CHA-CFAR. CHA-CFAR achieves a
better performance compared to OS-CFAR (Fig. 13) but is still outperformed by
our proposed method by an average gain of $14\%$.

In addition, Fig. 14 shows the performance of CHA-CFAR against our proposed
detector (OR-CFAR and TS-LNCFAR do not reach a $P_{D}>10\%$ on the tested
$P_{FA}$ range and are therefore not shown). The order parameter $m$ of CHA-
CFAR is chosen such that the detector performs at its best. Even though CHA-
CFAR outperforms OS-CFAR, our proposed method still outperforms CHA-CFAR with
an average gain of $32\%$ between the corresponding curves. Again, this
validates the effectiveness of our novel method for indoor radar sensing.

###  V-D Discussion

At this point, we have experimentally shown that our proposed detector
outperforms OS-CFAR, OR-CFAR, TS-LSCFAR and CHA-CFAR in our specific indoor
sensing scenario. The reason for this is twofold. First, conventional CFAR
methods and their state-of-the-art derivatives (see sections III-B and III-C)
perform detection by ML estimation of the clutter statistics given a prior
clutter distribution model [40, 41]. Therefore, the performance of those
conventional techniques degrade when the clutter distribution severely
deviates from their prior hypothesis. In outdoor scenarios such as remote
earth sensing, clutter distribution is often analytically well modelled by
distributions such as Gaussian, log-normal and so on [39] as the wave
propagation paths are simpler. In contrast, indoor scenarios lead to severe
multi-path effects as a large number of reflectors are present. In addition,
floor reflectively is not always uniform which can lead to an increased number
of clutter edges. Finally, compared to satellite SAR radars (as used in [40,
41, 42, 43]), our radar setup provides a much more modest resolution which may
lead to residual correlations between the bins in the RP, violating the
assumption of inter-bin statistical independence [17]. Fig. 15 and 16 show the
goodness-of-fit of an RP data distribution against the log-normal and the
exponential models, which gave the smallest Kolmogorov-Smirnov (KS) distances
out of a set of typical hypothesis distributions (log-normal, Gaussian,
Exponential, Gamma and Weibull) [17]. For both hypothesis PDFs, the KS
distance is above one order of magnitude larger than what is considered to be
acceptable in ML-based CFAR estimation [40, 42].

Figure 15: Log-normal fitting. The KS distance is $0.048$.

Figure 16: Exponential fitting. The KS distance is $0.056$.

The second reason behind the superiority of our method is the following.
Conventional CFAR methods based on the OS principle (OS-CFAR and CHA-CFAR in
this work) reject the outliers within the training cells by sorting the cells
and choosing either the $n^{th}$ entry as the clutter statistics (as done in
OS-CFAR) or either a combination of all entries above $n$ (as done in CHA-
CFAR). For OS-CFAR, this means that a maximum of $N_{tc}-n$ outliers can be
rejected, making it difficult to find a suitable $n$ in the dense, indoor case
(the number of outliers per training window is non-homogenous). CHA-CFAR
performs slightly better than OS-CFAR in the indoor case (see Fig. 13 vs. Fig
14) as it estimates the clutter statistics through a combination of the
training cell entries above $n$. This harmonic averaging combination is such
that entries with large values have a smaller contribution than entries with
small values. Consequently, the order $n$ can be chosen smaller than in the
OS-CFAR case, which allows an adaptive rejection of an increased number of
outliers in each training window (in contrast to the hard rejection of OS-
CFAR).

On the other hand, modern hyperspectral detection techniques such as SVDD or
KRX [33] (from which our proposed method is derived) do not estimate the
clutter statistics explicitly and therefore, must not rely on a prior PDF
model for ML estimation. Rather, those techniques solve a binary
classification problem by expressing the local data (training cells and CUT)
in a high-dimensional feature space $\mathcal{F}$ where the separability
between samples is enhanced [33]. Simple decision contours in $\mathcal{F}$
will then correspond to much more complex decision boundaries in the original
space, enabling high-performance detection in unknown and complex clutter
statistics [33]. As experimentally shown in this paper, such a detection
principle is especially attractive for indoor radar sensing where the
goodness-of-fit of usual PDF models is not as good as in the outdoor case due
to the complexity of the sensed environment. Finally, it must be noted that
such high-dimensional, non-linear methods come at the cost that finding
analytical expressions for e.g., setting the detection threshold $T_{2}$ to
meet a target $P_{FA}$ is mathematically intractable. This is not only the
case for our proposed detector (which uses (21) as a discontinuous non-
linearity function), but is also the case for the original KRX formulation
(which uses a smooth RBF kernel [26]).

###  V-E Effect of the $D$ parameter

In order to evaluate the effect of the $D$ parameter (dimensionality of the
transformation $\Phi(\xi)$ in (21)), we fix $N_{tc}=20$, $N_{g}=10$ and we
evaluate the ROC curves of the proposed detector using the same dataset used
in section V-B for a range of $D$ values. The results are shown in Fig. 17.

Figure 17: ROC curves for different $D$ values. The diamond-shaped points
denote the $(P_{D},P_{FA})$ achieved in the limit of $T_{2}\rightarrow 1$.

As Fig. 17 shows, the $D$ parameter affects the minimum reachable $P_{FA}$.
This can be explained as follows. Each element of the vector
$\bar{N}_{\Phi}^{m}$ in (16) can take a maximum value of $1$ because of the
normalization by $\Gamma$ during the centroid computation and following the
definition of $\Phi(\xi)$ in (21) where each element of the vector $\Phi(\xi)$
is either $0$ or $1$. Indeed, if all elements of $\Phi(X_{tc}[j]),\forall j$
are equal to $1$ (which is the limit case of the $\Phi(\xi)$ encoding), the
evaluation of (16) will result in a vector $\bar{N}_{\Phi}^{m}$ with all of
its components equal to $1$ because of the normalization by $\Gamma$. From
(20), we can therefore write:

$||\Phi(\bar{x})-\bar{N}_{\Phi}^{m}||_{\infty}\leq 1$ (22)

as the entries of $\Phi(\bar{x})$ are either $0$ or $1$ by the definition of
$\Phi(\xi)$ in (21). Therefore, only values of $T_{2}$ in (20) below $1$ will
affect the $P_{D}$ and $P_{FA}$ of the proposed detector. The $P_{FA}$
achieved in the limit of $T_{2}\rightarrow 1$ for a certain $D$ value will
thus be the minimal reachable $P_{FA}$ for that $D$. Then, the smaller $D$ is,
the less quantization slots are available during the binary coding induced by
$\Phi(\xi)$ in (21). As a consequence, the likelihood that the training cells
in the vector $X_{tc}$ have a $1$ in the same quantization slot ($i$ in (21))
will grow, leading to larger elements in $\bar{N}_{\Phi}^{m}$, which will
lower the evaluation of $||\Phi(\bar{x})-\bar{N}_{\Phi}^{m}||_{\infty}$,
lowering both the $P_{D}$ and the $P_{FA}$. This can clearly be observed in
Fig. 17, where the smaller the value of $D$, the smaller the minimum reachable
$P_{FA}$ is. Naturally, a similar discussion holds concerning the maximum
reachable $P_{D}$ in the limit of $T_{2}\rightarrow 0$, where, the smaller the
$D$, the smaller the maximum reachable $P_{D}$ will be.

###  V-F Ablation Studies

It is now important to verify the impact of the choices made for our detector
in section IV on the performance of the algorithm. We have introduced a
heuristic rule (16) that replaced the usual computation of (14) by a centroid
since we did not expect the projection of the RPs in the feature space
$\mathcal{F}$ to be Gaussian, as opposed to the assumption of (14). Fig. 18
compares our heuristic rule against (14) and against OS-CFAR with $k=0.7$ (as
it was the closest to our method in terms of performance). As expected, using
(14) results in a significant loss of performance compared to (16). This
experimentally validates the need for our heuristic rule (16).

Figure 18: ROC curves for different methods (k = 0.7 for OS-CFAR). Our method
uses (16).

Finally, we have decided to use the $L_{\infty}$ norm in (20) instead of the
$L_{2}$ norm and we gave motivations for this choice is section IV. Fig. 19
compares the use of the $L_{\infty}$ norm against the $L_{2}$ norm.

Figure 19: ROC curves for different methods (k = 0.7 for OS-CFAR). Our method
uses the $L_{\infty}$ norm.

It is interesting to see that OS-CFAR performs better for low $P_{FA}$ values
compared to using the $L_{2}$ norm in (20). Finally, it is visually clear that
our method (using the $L_{\infty}$ norm) leads to a significantly better
performance compared to the $L_{2}$ norm for $P_{FA}<0.015$.

###  V-G System implementation and hardware metrics

We have implemented our proposed detector in an ARM Cortex R4F processor
running at 40 MHz and integrated in the 79 GHz radar chip used during the data
acquisitions. Our detector returns a list of populated range bins which are
then passed to a conventional beamformer algorithm [37] to compute the angle
of arrival of each detection. As OS-CFAR involves an expensive search
operation for each cell under test, it is already clear that our method is
less computationally expensive. It is, however, more meaningful to compare our
method against the standard detection API provided by the chip vendor, which
uses a hardware-accelerated CA-CFAR applied on the full RD map (2D detection
performed along each range and Doppler bin) followed by additional clutter
filtering. Compared to our detector written in plain C, their detector is not
running in the CPU but in a dedicated hardware accelerator specially tailored
for their 2D CA-CFAR implementing vectored computation. This hardware
acceleration is needed to meet the inter radar frame timing as, unlike our
single-pass detection, they perform detection along each range and Doppler bin
($256\times 128$ detection passes vs. 1 in our case). Then, as CA-CFAR is
subject to a high amount of clutter false alarms, their API performs a final
clutter filtering step and the detection list is returned to a conventional
beamformer algorithm (identical to the one used with our proposed detector) to
compute the angle of arrival of each detection.

We have compare our method against theirs in term of average inter-frame
processing time margin, meaning the time slack available between the execution
of each complete radar frame processing (reception of raw ADC data - range-
Doppler processing - detection - angle of arrival estimation). Table II shows
the measured average inter-frame processing time margin.

Method | Time Slack [ms]
---|---
Standard | 26.7
Ours | 45.7
TABLE II: Measured average inter-frame processing time margin. The radar frame
rate is set to 10 FPS.

Figure 20: Radar-camera snapshot of our drone flying through industrial
aisles. The right and left shelves can easily be identified.

Table II clearly shows that our method executes nearly two times faster,
providing a significant increase in the time slack available between the
execution of each frame processing step, even though our method does not rely
on any dedicated hardware acceleration. In addition, a video in our
supplementary material showcases the reduction in measured CPU load reported
by the graphical interface provided by the radar vendor. This additional time
slack enables our system to run at frame rates $\sim$35 FPS before the dead-
lock of the MCU (due to the fact that radar chirps are incoming at speeds
larger than what the MCU can process), while the standard method can run at
maximum 17 FPS before the dead-lock of the MCU. This larger frame rate allows
our radar system to detect obstacles faster, enabling safer drone flights.
Furthermore, this additional time slack can be used to execute more complex
angle of arrival algorithms after the detection step to enhance the poor angle
resolution of the conventional beamformer [37]. Finally, Fig. 20 shows a
radar-camera snapshot of our drone flying through industrial shelves with our
proposed detector running on-line in the MCU of the radar chip at $30$FPS,
with a conventional beamformer [37] estimating the angle of arrival of the
detections. The aisles can clearly be observed thanks to the high $P_{D}$ over
$P_{FA}$ ratio that our detector provides, which qualitatively shows the
effectiveness of our detector. A video showing the full flight can be found in
the supplementary material.

##  VI Conclusion

This paper has focused on reliable radar target detection in dense indoor
environments for drone applications requiring obstacle avoidance for safe
navigation. We have proposed a novel radar target detection algorithm with low
computational cost suitable for near-sensor implementation in edge devices. It
is shown that the proposed detector outperforms OS-CFAR with more than 19%
higher $P_{D}$ and outperforms CHA-CFAR with more than 16% higher $P_{D}$ for
the same $P_{FA}$ in our indoor drone navigation scenario where missed
detection can be detrimental, while being less computationally complex than
both OS-CFAR and CHA-CFAR (as no sorting operations are needed). To the best
of our knowledge, this work improves the state of the art for high-performance
yet low-complexity radar detection in very dense indoor sensing applications.

## Acknowledgment

This work is partially supported by the Flanders AI research program. We would
like to thank Dr. Aliakbar Gorji for acquiring the dataset used in section
V-C.

## References

  * [1] S. Park et al., ”A 62mW 60GHz FMCW Radar in 28nm CMOS,” 2020 IEEE Radio Frequency Integrated Circuits Symposium (RFIC), Los Angeles, CA, USA, 2020, pp. 31-34, doi: 10.1109/RFIC49505.2020.9218357.
  * [2] A. Visweswaran et al., ”9.4 A 145GHz FMCW-Radar Transceiver in 28nm CMOS,” 2019 IEEE International Solid- State Circuits Conference - (ISSCC), San Francisco, CA, USA, 2019, pp. 168-170, doi: 10.1109/ISSCC.2019.8662357.
  * [3] Y. Liu et al., ”9.3 A680 $\mu$W Burst-Chirp UWB Radar Transceiver for Vital Signs and Occupancy Sensing up to 15m Distance,” 2019 IEEE International Solid- State Circuits Conference - (ISSCC), San Francisco, CA, USA, 2019, pp. 166-168, doi: 10.1109/ISSCC.2019.8662536.
  * [4] G. Wang, J. Muñoz-Ferreras, C. Gu, C. Li and R. Gómez-García, ”Application of Linear-Frequency-Modulated Continuous-Wave (LFMCW) Radars for Tracking of Vital Signs,” in IEEE Transactions on Microwave Theory and Techniques, vol. 62, no. 6, pp. 1387-1399, June 2014, doi: 10.1109/TMTT.2014.2320464.
  * [5] J. Tiemann and C. Wietfeld, ”Scalable and precise multi-UAV indoor navigation using TDOA-based UWB localization,” 2017 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Sapporo, 2017, pp. 1-7, doi: 10.1109/IPIN.2017.8115937.
  * [6] T. Zahariadis, A. Voulkidis, P. Karkazis and P. Trakadas, ”Preventive maintenance of critical infrastructures using 5G networks & drones,” 2017 14th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS), Lecce, 2017, pp. 1-4, doi: 10.1109/AVSS.2017.8078465.
  * [7] Y. Naidoo, R. Stopforth and G. Bright, ”Development of an UAV for search & rescue applications,” IEEE Africon ’11, Livingstone, 2011, pp. 1-6, doi: 10.1109/AFRCON.2011.6072032.
  * [8] A. Suleiman, Z. Zhang, L. Carlone, S. Karaman and V. Sze, ”Navion: A 2-mW Fully Integrated Real-Time Visual-Inertial Odometry Accelerator for Autonomous Navigation of Nano Drones,” in IEEE Journal of Solid-State Circuits, vol. 54, no. 4, pp. 1106-1119, April 2019, doi: 10.1109/JSSC.2018.2886342.
  * [9] C. Cadena et al., ”Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age,” in IEEE Transactions on Robotics, vol. 32, no. 6, pp. 1309-1332, Dec. 2016, doi: 10.1109/TRO.2016.2624754.
  * [10] Noureldin, A., Karamat, T., Georgy, J. (2013),”Fundamentals of Inertial Navigation, Satellite-based Positioning and their Integration,” 10.1007/978-3-642-30466-8-10.
  * [11] N. Jeong, H. Hwang and E. T. Matson, ”Evaluation of low-cost LiDAR sensor for application in indoor UAV navigation,” 2018 IEEE Sensors Applications Symposium (SAS), Seoul, 2018, pp. 1-5, doi: 10.1109/SAS.2018.8336719.
  * [12] G. Gallego et al., ”Event-based Vision: A Survey,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, doi: 10.1109/TPAMI.2020.3008413.
  * [13] Mostafa, M., Zahran, S., Moussa, A., El-Sheimy, N., Sesay, A. (2018), ”Radar and Visual Odometry Integrated System Aided Navigation for UAVS in GNSS Denied Environment,” Sensors 18, no. 9: 2776.
  * [14] J. Yan et al., ”Full-Coverage Indoor SAR Imaging with a Vehicle-based FMCW Radar System,” 2018 IEEE/MTT-S International Microwave Symposium - IMS, 2018, pp. 135-137, doi: 10.1109/MWSYM.2018.8439145.
  * [15] J. Zhou, R. Zhu, L. Li and Q. Fu, ”Comparision between the RMA and BPA for Indoor SAR Imaging Applications,” 2019 6th Asia-Pacific Conference on Synthetic Aperture Radar (APSAR), 2019, pp. 1-4, doi: 10.1109/APSAR46974.2019.9048559.
  * [16] V. M. Lubecke, O. Boric-Lubecke, A. Host-Madsen and A. E. Fathy, ”Through-the-Wall Radar Life Detection and Monitoring,” 2007 IEEE/MTT-S International Microwave Symposium, Honolulu, HI, 2007, pp. 769-772, doi: 10.1109/MWSYM.2007.380053.
  * [17] Mark A. Richards (2005), ”Fundamentals of Radar Signal Processing,” McGraw-Hill Professional.
  * [18] E. Hyun and J. Lee, ”A New OS-CFAR Detector Design,” 2011 First ACIS/JNU International Conference on Computers, Networks, Systems and Industrial Engineering, Jeju Island, 2011, pp. 133-136, doi: 10.1109/CNSI.2011
  * [19] H. Rohling and R. Mende, ”OS CFAR performance in a 77 GHz radar sensor for car application,” Proceedings of International Radar Conference, Beijing, China, 1996, pp. 109-114, doi: 10.1109/ICR.1996.573784.
  * [20] Antonio, F. S., Renga, A., Fasano, G., Moccia, A. (2018), ”Experimental analysis of radar odometry by commercial ultralight radar sensor for miniaturized UAS,” Journal of Intelligent & Robotic Systems, 90(3-4), 485-503.
  * [21] Scannapieco, A., Renga, A., Fasano, G., Moccia, A., (2017). ”Ultralight Radar For Small And Micro-UAV Navigation,” ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. XLII-2/W6. 333-338. 10.5194/isprs-archives-XLII-2-W6-333-2017.
  * [22] E. Wang, J. Wang and A. M. Ponsford, ”An adaptive hierarchal CFAR for optimal target detection in mixed clutter environments,” 2011 IEEE RadarCon (RADAR), Kansas City, MO, 2011, pp. 543-547, doi: 10.1109/RADAR.2011.5960596.
  * [23] A. L. Dzvonkovskaya and H. Rohling, ”Target Detection with Adaptive Power Regression Thresholding for HF Radar,” 2006 CIE International Conference on Radar, Shanghai, 2006, pp. 1-4, doi: 10.1109/ICR.2006.343550.
  * [24] L. Wang, D. Wang and C. Hao, ”Intelligent CFAR Detector Based on Support Vector Machine,” in IEEE Access, vol. 5, pp. 26965-26972, 2017, doi: 10.1109/ACCESS.2017.2774262.
  * [25] B. P. A. Rohman, D. Kurniawan and M. T. Miftahushudur, ”Switching CA/OS CFAR using neural network for radar target detection in non-homogeneous environment,” 2015 International Electronics Symposium (IES), Surabaya, 2015, pp. 280-283, doi: 10.1109/ELECSYM.2015.7380855.
  * [26] Heesung Kwon and N. M. Nasrabadi, ”Kernel RX-algorithm: a nonlinear anomaly detector for hyperspectral imagery,” in IEEE Transactions on Geoscience and Remote Sensing, vol. 43, no. 2, pp. 388-397, Feb. 2005, doi: 10.1109/TGRS.2004.841487.
  * [27] I. S. Reed and X. Yu, ”Adaptive multiple-band CFAR detection of an optical pattern with unknown spectral distribution,” in IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 38, no. 10, pp. 1760-1770, Oct. 1990, doi: 10.1109/29.60107.
  * [28] S. Ghosh and D. Sen, ”An Inclusive Survey on Array Antenna Design for Millimeter-Wave Communications,” in IEEE Access, vol. 7, pp. 83137-83161, 2019, doi: 10.1109/ACCESS.2019.2924805.
  * [29] Lin, J., Li, Y., Hsu, W., Lee, T., (2016), ”Design of an FMCW radar baseband signal processing system for automotive application,” SpringerPlus. 5. 10.1186/s40064-015-1583-5.
  * [30] Y. Sun, T. Fei, X. Li, A. Warnecke, E. Warsitz and N. Pohl, ”Real-Time Radar-Based Gesture Detection and Recognition Built in an Edge-Computing Platform,” in IEEE Sensors Journal, vol. 20, no. 18, pp. 10706-10716, 15 Sept.15, 2020, doi: 10.1109/JSEN.2020.2994292.
  * [31] Kim, Bong-seok; Jin, Youngseok; Kim, Sangdong; Lee, Jonghun. 2019. ”A Low-Complexity FMCW Surveillance Radar Algorithm Using Two Random Beat Signals” Sensors 19, no. 3: 608.
  * [32] Li, S., Bi, X., Huang, L., Tan, B. (2017). ”2-D CFAR Procedure of Multiple Target Detection for Automotive Radar,” SAE International Journal of Passenger Cars - Electronic and Electrical Systems. 11. 10.4271/2017-01-1972.
  * [33] N. M. Nasrabadi, ”Hyperspectral Target Detection : An Overview of Current and Future Challenges,” in IEEE Signal Processing Magazine, vol. 31, no. 1, pp. 34-44, Jan. 2014, doi: 10.1109/MSP.2013.2278992.
  * [34] Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin. (2012) ”Learning From Data,” AMLBook.
  * [35] Kwon, H., Nasrabadi, N.M. (2007). ”A Comparative Analysis of Kernel Subspace Target Detectors for Hyperspectral Imagery,” EURASIP Journal on Advances in Signal Processing. 2007. 10.1155/2007/29250.
  * [36] J. Partzsch et al., ”A fixed point exponential function accelerator for a neuromorphic many-core system,” 2017 IEEE International Symposium on Circuits and Systems (ISCAS), Baltimore, MD, 2017, pp. 1-4, doi: 10.1109/ISCAS.2017.8050528.
  * [37] H. Krim and M. Viberg, ”Two decades of array signal processing research: the parametric approach,” in IEEE Signal Processing Magazine, vol. 13, no. 4, pp. 67-94, July 1996, doi: 10.1109/79.526899.
  * [38] Strang, Gilbert. (2016) ”Introduction to linear algebra”.
  * [39] X. Wang, G. Li, X. -P. Zhang and Y. He, ”A Fast CFAR Algorithm Based on Density-Censoring Operation for Ship Detection in SAR Images,” in IEEE Signal Processing Letters, vol. 28, pp. 1085-1089, 2021.
  * [40] J. Ai, Q. Luo, X. Yang, Z. Yin, and H. Xu, ”Outliers-robust CFAR detector of gaussian clutter based on the truncated-maximum-likelihood estimator in SAR imagery,” IEEE Trans. Intell. Transp. Syst., vol. 21, no. 5, pp. 2039-2049, May 2020.
  * [41] J. Ai, X. Yang, J. Song, Z. Dong, L. Jia, and F. Zhou, ”An adaptively truncated clutter-statistics-based two-parameter CFAR detector in SAR imagery,” IEEE J. Ocean. Eng., vol. 43, no. 1, pp. 267-279, Jan. 2018.
  * [42] R. G. Zefreh, M. R. Taban, M. M. Naghsh and S. Gazor, ”Robust CFAR Detector Based on Censored Harmonic Averaging in Heterogeneous Clutter,” in IEEE Transactions on Aerospace and Electronic Systems, vol. 57, no. 3, pp. 1956-1963, June 2021.
  * [43] D. Tao, S. N. Anfinsen, and C. Brekke, ”Robust CFAR detector based on truncated statistics in multiple-target situations,” IEEE Trans. Geosci. Remote Sens., vol. 54, no. 1, pp. 117-134, Jan. 2016.

|  Ali Safa (Student Member, IEEE) received the MSc degree (summa cum laude)
in Electrical Engineering from the Université Libre de Bruxelles, Belgium. He
joined IMEC and the Katholieke Universiteit Leuven (KU Leuven), Belgium in
2020 where he is currently working toward the PhD degree on AI-driven
processing for extreme edge applications.
---|---
|  Tim Verbelen received his M.Sc. and Ph.D. degrees in Computer Science
Engineering at Ghent University in 2009 and 2013 respectively. Since then, he
is working as a senior researcher for Ghent University and imec. His main
research interests include perception and control for autonomous systems using
deep learning techniques and high-dimensional sensors such as camera, lidar
and radar. In particular, he is active in the domain of representation
learning and reinforcement learning, inspired by cognitive neuroscience
theories such as active inference.
---|---
|  Lars Keuninckx received a Master of Engineering in telecommunications from
Hogeschool Gent in 1996 after which he worked in industry for several years,
designing electronics for automotive, industrial and medical applications. He
received a Bachelor in Physics in 2009 and a PhD in Engineering in 2016, both
from the Vrije Universiteit Brussel. His interests include the applications of
complex dynamics and reservoir computing. He joined imec in 2019 where he is
involved in the design of neuromorphic systems.
---|---
|  Ilja Ocket (Member, IEEE) received the MSc and the PhD degrees in
Electrical Engineering from KU Leuven, Leuven, Belgium, in 1998 and 2009,
respectively. He currently serves as program manager for neuromorphic sensor
fusion at the IoT department of imec, Leuven, Belgium. His research interests
include all aspects of heterogeneous integration of highly miniaturized
millimeter wave systems, spanning design, technology and metrology. He is also
involved in research on using broadband impedance sensing and
dielectrophoretic actuation for lab-on-chip applications.
---|---
|  Mathias Hartmann graduated from the Faculty of Electrical Engineering and
Information Technology of the University of Technology Dresden. After
obtaining a master’s degree in the field of Information and System Technology,
he joined imec vzw (Leuven, Belgium) in 2008 working as a Research Engineer in
the Architecture and Compiler team and afterwards as the technical lead for
the PHADAR automotive radar program. Currently, he is engaged in the
Neuromorphic Radar program.
---|---
|  André Bourdoux (Senior Member, IEEE) received the M.Sc. degree in
electrical engineering from the Université Catholique de Louvain-la-Neuve,
Belgium, in 1982. In 1998, he joined IMEC, where he is currently a Principal
Member of Technical Staff with the Internet-of-Things Research Group. He is a
system-level and signal processing expert for both the mm-wave wireless
communications and radar teams. He has more than 15 years of research
experience in radar systems and 15 years of research experience in broadband
wireless communications. He holds several patents in these fields. He has
authored or coauthored over 160 publications in books and peer-reviewed
journals and conferences. His research interests include advanced signal
processing, and machine learning for wireless physical layer and high-
resolution 3D/4D radars.
---|---
|  Francky Catthoor (Fellow, IEEE) received a Ph.D. in electrical engineering
from KU Leuven, Belgium in 1987. Between 1987 and 2000, he has headed several
research domains in the area of synthesis techniques and architectural
methodologies. Since 2000 he is strongly involved in other activities at IMEC
including co-exploration of application, computer architecture and deep
submicron technology aspects, biomedical systems and IoT sensor nodes, and
photo-voltaic modules combined with renewable energy systems, all at IMEC
Leuven, Belgium. Currently, he is an IMEC senior fellow. He is also part-time
full professor at the Electrical Engineering department of the KU Leuven
(ESAT). He has been associate editor for several IEEE and ACM journals and was
elected IEEE fellow in 2005.
---|---
|  Georges G.E Gielen (Fellow, IEEE) received the MSc and PhD degrees in
Electrical Engineering from the Katholieke Universiteit Leuven (KU Leuven),
Belgium, in 1986 and 1990, respectively. He currently is Full Professor in the
MICAS research division at the Department of Electrical Engineering (ESAT) at
KU Leuven. Since 2020 he is Chair of the Department of Electrical Engineering.
His research interests are in the design of analog and mixed-signal integrated
circuits, and especially in analog and mixed-signal CAD tools and design
automation. He is a frequently invited speaker/lecturer and
coordinator/partner of several (industrial) research projects in this area,
including several European projects. He has (co-)authored 10 books and more
than 600 papers in edited books, international journals and conference
proceedings. He is a 1997 Laureate of the Belgian Royal Academy of Sciences,
Literature and Arts in the discipline of Engineering. He is Fellow of the IEEE
since 2002, and received the IEEE CAS Mac Van Valkenburg award in 2015 and the
IEEE CAS Charles Desoer award in 2020. He is an elected member of the Academia
Europaea.
---|---