#  TransformLoc: Transforming MAVs into Mobile Localization Infrastructures in
Heterogeneous Swarms

Haoyang Wang1, Jingao Xu2, Chenyu Zhao1, Zihong Lu3, Yuhan Cheng1, Xuecheng
Chen1, Xiao-Ping Zhang1, Yunhao Liu2, Xinlei Chen1,4,5† † Corresponding author
1 Shenzhen International Graduate School, Tsinghua University, China;  2
School of Software, Tsinghua University, China; 3 Harbin Institute of
Technology, China;  4 Pengcheng Laboratory, Shenzhen, China; 5 RISC-V
International Open Source Laboratory, Shenzhen, China  Email:
{wanghaoyang0428, xujingao13, zhaocyhi, luzong2001, yhhncc,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A heterogeneous micro aerial vehicles (MAV) swarm consists of resource-
intensive but expensive advanced MAVs (AMAVs) and resource-limited but cost-
effective basic MAVs (BMAVs), offering opportunities in diverse fields.
Accurate and real-time localization is crucial for MAV swarms, but current
practices lack a low-cost, high-precision, and real-time solution, especially
for lightweight BMAVs. We find an opportunity to accomplish the task by
transforming AMAVs into mobile localization infrastructures for BMAVs.
However, turning this insight into a practical system is non-trivial due to
challenges in location estimation with BMAVs’ unknown and diverse localization
errors and resource allocation of AMAVs given coupled influential factors.
This study proposes TransformLoc, a new framework that transforms AMAVs into
mobile localization infrastructures, specifically designed for low-cost and
resource-constrained BMAVs. We first design an error-aware joint location
estimation model to perform intermittent joint location estimation for BMAVs
and then design a proximity-driven adaptive grouping-scheduling strategy to
allocate resources of AMAVs dynamically. TransformLoc achieves a
collaborative, adaptive, and cost-effective localization system suitable for
large-scale heterogeneous MAV swarms. We implement TransformLoc on industrial
drones and validate its performance. Results show that TransformLoc
outperforms baselines including SOTA up to 68% in localization performance,
motivating up to 60% navigation success rate improvement.

##  I Introduction

Heterogeneous micro aerial vehicles (MAV) swarms offer transformative
potential in conducting 4D (deep, dull, dangerous, dirty) tasks, especially
quick response scenarios, such as search and rescue [1], gas leak source
detection [2], wildfire suppression[3], leveraging their inherent advantages
of working scalability [4], flexibility [5], adaptability [6], etc. There are
forecasts that the market size for MAV swarm-supported applications will reach
$ 279 billion by 2032 [7].

A heterogeneous MAV swarm typically consists of: $(i)$ a handful of advanced
MAVs (AMAVs) equipped with intensive capabilities (eg. sensing, computing,
etc.) yet expensive [8]; and $(ii)$ a larger group of resource-limited and
cost-effective basic MAVs (BMAVs) [9], as shown in Fig. 1 111Results in Fig.1
and Fig.2a are measured with MH_02 of EuRoC dataset[10] and CCM-SLAM [11].
AMAV is equipped with Intel(R) i7-8750H and 32G RAM, and BMAV is equipped with
Cortex-A53 and 1G RAM.. The former primarily handles data management,
communication, and complicated computation tasks, while the latter is
dispersed into (hazard) target areas for data collection and environmental
exploration [12]. The AMAV-BMAV collaboration paradigm achieves an optimal
balance between overall cap-abilities and cost, facilitating its widespread
adoption [13].

Figure 1: Introduction of heterogeneous MAV swarm. The AMAVs are resource-
intensive and have a lower localization error and latency, while BMAVs are
resource-limited, resulting in a high error and latency.

However, the diverse onboard resources also lead to unbalanced localization
performance between AMAVs and BMAVs, which is the fundamental capability for
flight control [14], obstacle avoidance [15], etc. Precisely, localization
errors of the BMAV accumulate fast due to its noisy sensing data and low
computational capability, preventing it from achieving accurate and real-time
localization as the AMAV.

Unfortunately, current methods are not able to offer feasible solutions for
BMAV localization in quick response scenarios, which can be divided into 2
categories:
$\bullet$ Extra infrastructure based solutions. These solutions utilize
external devices to provide reference signals (e.g., GPS [16, 17], RTK, radio
[18, 14], or acoustic [19]) for localization. They require 1) pre-deploying
(densely) expensive localization infrastructure in the operation site and 2)
line-of-sight connection between localization infrastructure and MAVs.
However, in quick response scenarios like urban disaster relief, either
requirement is hard to satisfy, which leads to localization failures [20, 21].

$\bullet$ Intra on-board sensor based solutions. These solutions leverage
onboard sensors like cameras, IMU, LiDAR, and Radar, along with simultaneous
localization and mapping (SLAM) techniques, to achieve high-precision location
estimation[22, 23]. These methods require intensive on-board sensing and
computing capabilities, which only work for AMAVs. In contrast, BMAVs’ limited
on-board resources result in significant accumulated errors or computation
delays as illustrated in Fig.2a [15].

Therefore, this paper aims to improve BMAVs’ localization accuracy and
efficiency given limited onboard sensing and computing capabilities without
relying on any pre-deployed localization infrastructures. Our key insight is
to transform a handful of AMAVs as mobile localization infrastructures and
offload their sensing and computing capabilities to support location
estimation improvement of a larger group of BMAVs. Specifically, AMAVs provide
external observations (with their visual sensors) for BMAVs to correct
cumulative location estimation errors [24, 25].

However, turning this insight into a practical system is non-trivial, since
two technical challenges have to be solved:

$\bullet$ Unknown & Diverse localization errors of BMAVs (C1). On the one
hand, accumulated location estimation errors may be diverse among BMAVs due to
various reasons, such as various sensing noises, different operational
conditions, etc. On the other hand, due to its limited field of view (FoV),
each AMAV can only serve several BMAVs as localization infrastructure.
Therefore, AMAVs should provide external observations for BMAVs with
significant errors for estimation correction. However, online deriving BMAVs’
localization errors is challenging due to the lack of static location
references. As a result, localization errors of BMAVs may keep accumulating
without timely external observations from AMAVs. Meanwhile, we need to
consider how to correct BMAVs’ location with AMAV’s observations.

$\bullet$ Resource allocation given coupled influential factors (C2).
Assigning sensing and computing resources of a handful of AMAVs to a larger
group of BMAVs as localization infrastructure involves optimization in high
dimensional decision space. First, even if C1 is solved, the presence of
multiple AMAVs results in an exponential search space growth. Second, since
both AMAVs and BMAVs are in constant motion, the observed BMAVs by each AMAV
keep changing, necessitating dynamic adjustment of resource allocation
strategies. Third, the localization effectiveness is affected by the accuracy
of AMAVs’ observations given various distances and bearing angles between
AMAVs and BMAVs (as shown in Fig. 2b), further complicating the resource
allocation search space. These factors influence resource allocation decisions
in a coupled way, making it too complicated to run on MAVs.

To conquer these challenges, this paper presents TransformLoc, a novel
collaborative and adaptive location estimation framework for heterogeneous MAV
swarms. TransformLoc dynamically transforms AMAVs with intensive onboard
capabilities into mobile localization infrastructures to support location
estimation improvement for resource-constrained BMAVs. To achieve accurate and
real-time localization for the entire swarm, TransformLoc only requires
deploying intensive and expensive sensing and computing capabilities on a
small number of AMAVs, without relying on external localization
infrastructures. Consequently, this framework facilitates the widespread
deployment of swarm technology.

To address C1, we design an error-aware joint location estimation model. This
model designs an uncertainty-aided inference method to enable AMAVs to provide
observations for BMAVs with larger errors at first. Subsequently, it
integrates inaccurate estimation from BMAVs with discontinuous external
observations from AMAVs to perform intermittent joint location estimation for
BMAVs.

To address C2, a proximity-driven adaptive grouping-scheduling strategy is
proposed. Initially, MAVs are dynamically grouped according to the principle
of proximity, transforming the many-to-many resource allocation problem into
multiple one-to-many resource allocation problems. Then, several steps
lookahead about BMAVs are conducted to schedule each AMAV in a non-myopic
manner, which also finds optimal distance and angle.

(a) Accuracy & latency on BMAV (b) Accuracy of AMAV observation

Figure 2: Motivating example. (a) BMAVs have limited on-board resources,
resulting in a trade-off between accuracy and latency; (b) The accuracy of
observation is affected by distances and angles between MAVs.

We evaluate the performance of TransformLoc and compare it with baselines
including the state-of-the-art (SOTA) method through extensive experiments
with both real-time testbed and physical feature-based simulations. Results
show that TransformLoc is able to maintain BMAVs’ average localization error
under $1m$ with limited on-board resources in real-time, outperforming
baselines up to $68\%$, which motivates up to $60\%$ navigation success rate
improvement.

In summary, the main contributions are as follows:

  * •

We propose TransformLoc, a new framework that dynamically transforms AMAVs
into mobile localization infrastructures, enhancing localization accuracy and
real-time performance for lightweight BMAVs.

  * •

We design an error-aware joint location estimation model to boost the location
estimation accuracy of BMAVs with discontinuous observation from AMAVs.

  * •

We design a proximity-driven adaptive grouping-scheduling strategy to decouple
the resource allocation issue given coupled influential factors.

  * •

We validate our solution through in-field experiments on a real heterogeneous
MAV swarm and large-scale physical feature-based simulations.

The remainder of the paper is organized as follows: Section II provides an
overview of TransformLoc, with detailed descriptions of the error-aware joint
location estimation model in Section III and the proximity-driven adaptive
grouping-scheduling strategy in Section IV. Section V showcases the
implementation and evaluation. Sections VI and VII discuss the related work
and influencing factors of the framework, respectively. Section VIII concludes
TransformLoc. Appendix sections include detailed formula derivations of
essential variables.

##  II Overview

Figure 3: Illustration of TransformLoc framework. BMAVs estimate locations
with noisy measurements. With the assistance of the uncertainty-aided
inference method, AMAV generates discontinuous observations for BMAVs to
perform intermittent joint location estimation. Subsequently, TransformLoc
allocates resources of AMAVs by adaptive grouping and scheduling, which
adaptively groups MAVs at first, and then schedules AMAVs in a non-myopic
manner.

###  II-A TransformLoc: Framework goal

From the top perspective, we design and implement TransformLoc to transform
AMAVs into mobile localization infrastructures for BMAVs. This adaptation is
specifically crafted to cater to the economic and resource constraints of
BMAVs, effectively addressing the inherent challenges presented by these
limitations. The goal of framework design is to answer the questions:

$\bullet$ How to optimize the location estimation of BMAVs with unknown and
diverse localization errors? TransformLoc should infer the localization error
of BMAV and utilize observations generated by AMAV to assist BMAVs,
effectively reducing the localization error of BMAV.

$\bullet$ How to allocate sensing resources of AMAVs given coupled influential
factors to assist BMAVs? TransformLoc should decouple the resource allocation
problem and navigate the AMAVs in a non-myopic way, ensuring that the overall
localization error of BMAVs remains low.

###  II-B Framework overview

The architecture of TransformLoc is illustrated in Fig. 3. As seen,
TransformLoc consists of two main components:

$\bullet$ Error-aware joint location estimation model. Firstly, the BMAVs
utilize the state model and motion commands to conduct the prediction of
location at first, then transmit the yielded prior distribution of location to
AMAVs (D0 in Fig.3). Secondly, the uncertainty-aided inference method (Sec.
III-A) identifies when assistance is required for BMAVs (D1 in Fig.3).
Finally, utilizing observations generated by visual fiducial system, AMAV
intermittently corrects the location estimation of BMAVs (Sec. III-B), then
transmits the result posterior distribution of BMAVs’ location and motion
commands to BMAVs for following motions (D2 in Fig.3).

$\bullet$ Proximity-driven adaptive grouping-scheduling strategy. The number
of AMAVs is limited, and the proximity-driven adaptive grouping-scheduling
strategy is responsible to allocates resources of AMAVs to BMAVs. Firstly,
this strategy groups MAVs adaptively utilizing a graph-based adaptive grouping
method according to the relationship of AMAVs and BMAVs in the spatial
dimension (Sec. IV-A). Secondly, utilizing grouping result (D3 in Fig.3),
TransformLoc schedules each AMAV to allocate the sensing resource in a non-
myopic manner by constructing a search tree for each AMAV. Finally,
TransformLoc generates motion commands for AMAVs to allocate sensing resources
for BMAVs.

##  III Error-aware joint location estimation model

The BMAVs have unknown and diverse localization errors, complicating their
location estimation with AMAV’s assistance. In this part, we design an error-
aware joint location estimation model based on Kalman filter and focus on
localization error inference and joint location estimation of BMAVs. The main
process is as follows:

$\bullet$ In order to enable AMAVs to provide observations for BMAVs with
higher errors, we incorporate a measure of uncertainty to reflect the quality
of BMAVs’ location estimation in Sec III-A.

$\bullet$ Meanwhile, we estimate the location of BMAVs with two coupled
operations in Sec III-B: Prediction from state model utilizes noisy motion
measurements and the state model of BMAVs; Correction from observation
incorporates linearized observations generated by AMAVs.

The state model of BMAV and AMAV, observation model of AMAV are described in
Appendix A.

Figure 4: The error-aware joint location estimation model. (a) AMAV determines
the BMAV with a higher error under the assistance of the uncertainty-aided
inference method, and (b) generates observations for correction.

###  III-A Uncertainty-aided inference method

The goal of TransformLoc is to efficiently allocate the sensing resources of
AMAVs, thereby generating observations for BMAVs to mitigate localization
errors. The localization error of BMAV $B_{i}$ at time $t$ can be
mathematically expressed as

$\psi(i,t):=E\left[{||y_{i,t}-\widehat{y}_{i,t}||}^{2}\right],$ (1)

where $y_{i,t}$ is actual location of $B_{i}$ and $\widehat{y}_{i,t}$ is
location estimation of $B_{i}$. By integrating the Kalman filter-based model
for BMAVs’ location estimation, we employ a metric of estimation uncertainty
to gauge the accuracy of BMAVs’ location estimations. This approach eliminates
the necessity of having the actual locations of BMAVs to calculate the
localization error. In order to measure the BMAV’s estimation uncertainty, we
choose the trace of the covariance matrix of BMAV’s location estimation[26],
which can be mathematically expressed as

$\psi(i,t)=tr\left(\Sigma_{i,t}\right),$ (2)

where $\Sigma_{i,t}$ is trace of the covariance matrix of $B_{i}$’s location
estimation at time $t$. This indicator measures the uncertainty of
estimations, a lower value indicates greater certainty. For BMAVs exhibiting
varying degrees of localization errors (Fig. 4a), the AMAV generates
observations tailored to assist BMAVs with more substantial errors (Fig. 4b).

###  III-B Joint estimation of BMAVs’ location

The joint location estimation framework of BMAVs includes two operations: ①
prediction from the state model and noisy velocity measurement of BMAVs, which
calculates the prior distribution of BMAVs’ location; ② correction from the
observation of AMAVs, which calculates the posterior distribution of BMAVs’
location. The detail of joint estimation of BMAV’s location is illustrated in
Algorithm 1.

Prediction of BMAVs from state model. This process is outlined in lines 1-3 of
Algorithm 1. It leverages the motion model of BMAVs, incorporating the noisy
motion measurement $\dot{v}_{i,t-1}$ and the location estimation
$\boldsymbol{\hat{y}_{i,t-1}}$ of BMAV $B_{i}$ at time $t-1$ to compute the
prior distribution and covariance matrix of $B_{i}$’s location estimation,
denoted as $\boldsymbol{{y_{i,t}}^{-}}$ and ${\Sigma_{i,t}}^{-}$.

Correction of BMAVs from observations. This process is delineated in lines
4-11 of Algorithm 1. When BMAV $B_{i}$ is within the Field of View (FoV) of
AMAV $A_{j}$ at time $t$, this process employs the observation $z_{i,j,t}$ and
the prior distribution of $B_{i}$’s location estimation to compute the
posterior distribution and covariance matrix at time $t$, denoted as
$\boldsymbol{{y_{i,t}}^{+}}$ and ${\Sigma_{i,t}}^{+}$. The variable $\eta$ in
line 8 represents a normalization constant. If $A_{j}$ generates an
observation for $B_{i}$, the location estimation
$\boldsymbol{\widehat{y}_{i,t}}$ and covariance matrix of estimation
$\Sigma_{i,t}$ for $B_{i}$ at time $t$ are drawn from the posterior
distribution $\boldsymbol{{y_{i,t}}^{+}}$ and ${\Sigma_{i,t}}^{+}$; otherwise,
they are drawn from the prior distribution $\boldsymbol{{y_{i,t}}^{-}}$ and
${\Sigma_{i,t}}^{-}$.

Algorithm 1 $A_{j}$ assists $B_{i}$ for localization using the noisy motion
measurement and the observation.

0: Location estimation of $B_{i}$ at time $t-1$,
$\boldsymbol{\widehat{y}_{i,t-1}}$; covariance matrix of estimation at time
$t-1$, $\Sigma_{i,t-1}$; noisy motion measurement, $\dot{v}_{i,t-1}$; location
of $A_{j}$, $\boldsymbol{x_{j,t-1}}$; motion command of $A_{j}$, $u_{j,t-1}$.

0: Location estimation of $B_{i}$ at time $t$,
$\boldsymbol{\widehat{y}_{i,t}}$; covariance matrix of estimation at time $t$,
$\Sigma_{i,t}$.% Prediction of BMAV from state model

1: Update prior distribution of $B_{i}$’s location at time
$t$,$\boldsymbol{y_{i,t}}^{-}=\int
p\left(\boldsymbol{y_{i,t}}\mid\boldsymbol{y_{i,t-1}},\dot{v}_{i,t-1}\right)\boldsymbol{\hat{y}_{i,t-1}}d\boldsymbol{y_{i,t-1}}$;

2: Update covariance of estimation ${\Sigma_{i,t-1}}^{-}$ from
$\boldsymbol{y_{i,t}}^{-}$;

3: Update $\boldsymbol{\widehat{y}_{i,t}}$ and $\Sigma_{i,t}$, from
$\boldsymbol{y_{i,t}}^{-}$ and ${\Sigma_{i,t}}^{-}$;% Correction of BMAV from
observations

4: Update the FoV of $A_{j}$, $F_{j,t}$ according to Eq.(5);

5: if $B_{i}$ in the FoV of $A_{j}$ then

6: Update observation $\boldsymbol{z_{i,j,t}}$ according to Eq.(6);

7: Linearize the observation according to Eq.(7);

8: Update posterior distribution of $B_{i}$’ location at $t$,
$\boldsymbol{y_{i,t}}^{+}=\eta
p\left(\boldsymbol{z_{i,j,t}}\mid\boldsymbol{y_{i,t}}\right)\boldsymbol{y_{i,t}}^{-}$;

9: Update covariance of estimation ${\Sigma_{i,t}}^{+}$ from
$\boldsymbol{y_{i,t}}^{+}$;

10: Update $\boldsymbol{\widehat{y}_{i,t}}$ and $\Sigma_{i,t}$ from
$\boldsymbol{y_{i,t}}^{+}$ and ${\Sigma_{i,t}}^{+}$;

11: end if

##  IV Proximity-driven adaptive grouping-scheduling strategy

The resource allocation of AMAVs is influenced by coupled factors, involving
optimization in a high-dimensional decision space. In this part, we design a
proximity-driven adaptive grouping-scheduling strategy to allocate resources
of AMAVs to assist BMAVs in localization. The main process is as follows:

$\bullet$ This strategy first dynamically groups the AMAVs and BMAVs according
to the proximity in spatial domain based on the Voronoi diagram. This step
transforms the many-to-many resource allocation problem into multiple one-to-
many resource allocation problems.

$\bullet$ Following that, to strategically plan each AMAV in a non-myopic
manner and determine the optimal observational distance and angle, this
strategy constructs a search tree for each AMAV, incorporating several steps
of lookahead regarding BMAVs.

The mathematical formulation of the resource allocation problem is described
in Appendix B.

###  IV-A Graph-based adaptive grouping

The BMAVs are located in various locations with varying localization errors.
When generating observations for BMAVs, a single AMAV is limited by its
location and waste sensing resources by moving between different BMAVs. In
this section, we dynamically group BMAVs so that each AMAV can focus its
sensing resources on one group. Grouping BMAVs and assigning them to different
AMAVs pose a combinatorial optimization challenge that becomes inherently
difficult to solve with a substantial number of BMAVs and AMAVs, owing to its
NP-hard nature. To tackle this challenge, TransformLoc employs two key
operations:

$\bullet$ TransformLoc initially divides the entire area into non-overlapping
regions according to the locations of AMAVs.

$\bullet$ Subsequently, each AMAV allocates sensing resources for BMAVs within
the nearest region for a duration of $\delta$, which is the control command
interval for BMAVs.

As a result, all of BMAVs are categorized into non-overlapping groups, with
distinct groups being assigned to different AMAVs. The details are provided
below.

Figure 5: The proximity-driven adaptive grouping-scheduling strategy. This
strategy groups MAVs based on the Voronoi diagram to decouple the resource
allocation problem. Then, it constructs search trees for each AMAV by
involving several steps lookahead about BMAVs, resulting in $\delta$-step
paths for AMAVs. AMAV is scheduled in a non-myopic way to assist BMAVs with
significant errors in an optimal distance and angle. $x_{j,0}$ is state of
$A_{j}$, $\Sigma_{j,0}$ is covariance of assigned BMAVs’ estimation maintained
by $A_{j}$, and $\hat{y}_{0}$ is BMAVs’ estimation location.

Graph-based region partitioning. The partitioning approach is based on the
Voronoi diagram [27]. Under this scheme, each AMAV is associated with a region
encompassing points whose distance to the given AMAV is less than or equal to
their distance to any other AMAV. Fig.5a presents a depiction of this
partitioning method with five AMAVs and several BMAVs. The result is
represented by region boundaries denoted as L1 \- L8, which are separated by
perpendicular bisectors of neighboring AMAVs. Any BMAV located within the
region of $A_{1}$ is closer to it than to any other AMAV (i.e., d1 <d2 in
Fig.5a).

Grouping and assignment of MAVs. BMAVs within the designated region of an AMAV
are organized into groups, and the AMAV allocates its sensing resources
exclusively to assist in their localization for a duration of $\delta$. The
group renews after an interval of $\delta$. Importantly, the boundaries of an
AMAV’s region are solely determined by the locations of its neighboring AMAVs
and can be computed by identifying the perpendicular bisectors between
adjacent AMAVs. If no BMAVs are present within an AMAV’s region, it allocates
sensing resources to all BMAVs over the duration of $\delta$.

###  IV-B Search tree-based non-myopic scheduling

In this section, we present a methodology for integrating a search tree-based
scheduling strategy into the non-myopic resource allocation of AMAVs. The
primary procedure unfolds as follows:

$\bullet$ BMAVs receive commands at discrete time intervals of $\delta$,
enabling the acquisition of BMAVs’ motion commands within each $\delta$
interval for AMAVs.

$\bullet$ These motion commands are subsequently employed to plan trajectories
for AMAVs, incorporating a $\delta$-step lookahead in coordination with the
movements of BMAVs.

Search tree construction. We construct search trees for each AMAV. As Fig. 5b
shows, we construct a search tree $\mathcal{T}_{j}$ for $A_{j}$ as an example.
$\mathcal{T}_{j}$ includes a set of candidate trajectories $A_{j}$ can take,
starting from an initial location and covariance pair
$(\boldsymbol{x_{j,0}},\Sigma_{j,0})$, where $\boldsymbol{x_{j,0}}$ is the
starting location of $A_{j}$, and $\Sigma_{j,0}$ is the initial covariance of
the location estimations of the BMAVs assigned to $A_{j}$. The nodes of the
search tree at level $t\leq\delta$ correspond to reachable locations for
$A_{j}$ and are denoted as $(\boldsymbol{x_{j,t}},\Sigma_{j,t})$. The AMAV
measures the distance and angle for observable BMAVs at each location to
determine an optimal distance and angle to generate observations for BMAVs
with significant error. We discretized the control space of the AMAV, $A_{j}$
has a finite set of control options $\mathcal{U}$, with an edge for each
option $\boldsymbol{u_{j,t}}$ starting at node
$(\boldsymbol{x_{j,t}},\Sigma_{j,t})$ and leading to node
$(\boldsymbol{x_{j,t+1}},\Sigma_{j,t+1})$ by evaluating state model of AMAV
and Algorithm 1. Then estimation location of corresponding BMAVs
$\boldsymbol{\hat{y}_{t}}$ is computed by evaluating motion model of BMAV,
observation model of AMAV, and Algorithm 1.

Motion commands for AMAV. Upon finishing the construction of the search tree
for an AMAV $A_{j}$, we choose the node at level $\delta$ with the minimum
value of $tr(\Sigma_{j,\delta})$. Subsequently, through backtracking on this
node, we plan the trajectory of $A_{j}$ navigate it for a duration of
$\delta$.

###  IV-C Scheduling of BMAV

TransformLoc utilizes location estimation to navigate BMAVs to their
destinations. To achieve this, we design a lightweight planning algorithm
based on an artificial potential field, ensuring BMAVs can avoid collision.
The key points are as follows:

$\bullet$ TransformLoc maintains BMAVs’ location estimation and generates
motion commands with an interval of $\delta$ based on the distance to their
destination.

$\bullet$ BMAVs move within a field of forces, the destination attracting them
through a force proportional to the distance. The Wall and other BMAVs
generate repulsive forces which repel the BMAV. This approach enables BMAVs to
dynamically adjust motion when nearing the destination, decreasing velocity
and increasing navigation success.

##  V Evaluation

###  V-A Implementation and Methodology

Figure 6: Experiment area and heterogeneous MAV swarm implementation. The
AMAVs utilize a tracking camera to localize themselves and visual sensors to
generate observation. BMAVs mount AprilTag markers for recognition and
localization. The ground truth is obtained from the motion capture system. The
experiment area has a size of $8m\times 8m$.

Testbed Implementation. As Fig. 6 illustrated, we implemented the TransformLoc
based on DJI Robomaster TTs (BMAVs) and industry drones (AMAVs) built on
Pixhawk which is one of the most widely used autopilot systems, to validate it
in the real world. The AMAV is equipped with an Intel(R) T265 tracking camera
for localization and an RGB camera with a FoV of 120 degrees for observation
generation. Each BMAV is equipped with an IMU and downward-facing optical flow
sensor. Meanwhile, each BMAV mounts a $3cm\times 3cm$ AprilTag for recognition
and observation generation [24] (Fig. 6b). The AMAV adopts ArduPilot
frameworks for motion control (Fig. 6c). A motion capture system provides
millimeter-level ground truth at 240 FPS in the experiment area of $8m\times
8m$ (Fig. 6a and Fig. 6d). TransformLoc runs on a server featuring 128GB of
memory and an Intel(R) Xeon(R) Gold 6242R CPU. We test the robustness of
TransformLoc on a physical-feature-based simulator in an experiment area
similar to Fig 6a.

(a) The CDF of ATE

(b) Success rate within 200s

(c) Success rate with 0.2m accuracy

Figure 7: Overall performance in in-field experiments with two AMAVs and six
BMAVs. Our TransformLoc outperforms the baselines, demonstrating superior
performance in both localization error and navigation success rate.

(a) The CDF of ATE

(b) Success rate within 200s

(c) Success rate with 0.2m accuracy

Figure 8: Overall performance in physical feature-based simulation with five
AMAVs and twenty BMAVs. Even with the increased numbers of AMAVs and BMAVs,
TransFormLoc continued to outperform the baseline in terms of localization
accuracy and navigation success rate.

(a) Impact of the quantity of AMAVs

(b) Impact of the quantity of bMAVs

(c) Correlation of ATE and indicator

Figure 9: System Robustness Evaluation with five AMAVs and twenty BMAVs. The
experimental results indicate that TransformLoc is capable of adapting to
changes in the quantities of AMAVs and BMAVs. Moreover, our indicator can
infer the localization errors of BMAVs.

Experiment setting. The BMAVs have a maximum velocity of 0.5$m/s$ and a
command interval $\delta$ of 5 steps. The AMAVs have an observation angle
$\theta$ of 120 degrees and maximum observation distance $r_{m}$ of 1m. The
control commands of AMAVs use motion primitives
$\\{(u,\omega)\\}|u\in\\{0,1,3\\}m/s,\omega\in\\{0,\pm 1,\pm 3\\}rad/s$. We
evaluated the performance by conducting in-field experiments with two AMAVs
and six BMAVs, and simulations with five AMAVs and twenty BMAVs. The BMAVs
move toward the edge of the room for environmental sensing. The simulations
are conducted for $420$ seconds, consistent with the typical battery life of
the DJI Robomaster TT utilized in in-field experiments. The standard deviation
of noise models for BMAVs’ motion, AMAVs’ range and bearing measurements are
determined based on in-field experiments and set to 20%, 10%, and 5% of the
measured values, respectively.

Comparative Methods. We tested TransformLoc (TL) against three baseline
methods that do not require a localization infrastructure. ① Dead-Reckoning
(DR) estimates the location of BMAVs with only measurements from motion
sensors [28]; ② Station (ST) utilizes AMAVs with fixed locations to generate
observations for BMAVs [29]; ③ H-SwarmLoc (SL) [30] is a SOTA method that
navigates one AMAV based on reinforcement learning to assist BMAVs in
localization. To ensure a fair comparison, we standardize SL to group MAVs in
a consistent manner and direct AMAV to generate observation for BMAVs within
the same group during navigation [30].

Evaluation Metrics. TransformLoc aims to improve the localization accuracy and
navigation success rate of BMAVs. We use two metrics: ① Localization error: we
compares the localization error of different BMAVs at each timestep, which is
known as absolute trajectory error (ATE); ② Success rate: this is measured by
counting the ratio of BMAVs that reach destinations under constraints.

###  V-B Overall Performance

In-field experiments. Fig. 7 specifically focuses on in-field experimental
results. Regarding localization error, a 420-second random walk is conducted
for BMAVs, and the cumulative distribution function (CDF) of the ATE is
plotted. TransformLoc achieves an ATE below $1.5m$, while the SL remains below
$2.4m$, the ST below $2.8m$, and the DR below $3m$ (Fig. 7a). Regarding
navigation performance, the success rate of BMAVs over a 200-second duration
increases for all methods as the destination accuracy decreases (Fig. 7b).
TransformLoc surpasses all baselines, achieving a remarkable 63% success rate
with a stringent destination accuracy constraint of 0.05m. Furthermore, under
looser destination accuracy limits (0.2m-0.3m), TransformLoc attains a 100%
navigation success rate, outperforming the baselines. Additionally, as the
time limitation increases, the success rate of BMAVs with a destination
accuracy constraint of 0.2m improves for all methods, as they have more time
to reach the target (Fig. 7c). TransformLoc exhibits superior performance
compared to the baselines, achieving a navigation success rate 22.3% higher
than SL, 25.6% higher than ST, and 55.6% higher than DR within strict time
constraints (60-180 seconds). The above results illustrate enhancements in
performance achieved by TransformLoc as it efficiently allocates AMAVs’
resources to bolster the localization and navigation capabilities of BMAVs.

Physical feature-based simulation. Fig. 8 illustrates the performance of
TransformLoc in the physical-feature-based simulation. In terms of
localization error, TransformLoc achieves an impressive ATE below $0.7m$,
while SL, ST, and DR maintain ATE below $1.5m$, $2m$, and $2.5m$ respectively
(Fig. 8a). Regarding navigation success rate, TransformLoc consistently
outperforms SL, ST, and DR by significant margins of 25%, 26.67%, and 33.3% on
average, respectively, with varying destination accuracy over a 200-second
duration (Fig. 8b). Furthermore, under a destination accuracy of 0.2m,
TransformLoc surpasses SL, ST, and DR by an average of 22.8%, 25.6%, and 42.5%
respectively, with varying time limitations (Fig. 8c). These results highlight
the remarkable performance improvements achieved by TransformLoc.

###  V-C System Robustness Evaluation

Impact of Number of AMAVs. Fig. 9a compares ATE of BMAVs against varying
numbers of AMAVs with different methods. The TransformLoc exhibits lower
errors than DR, which means the introduction of AMAVs reduced ATE. With the
number of AMAVs increasing from 1 to 5, ATE of TransformLoc decreases below
$0.8m$, significantly lower than ST which only helped BMAVs when passing over
fixed AMAVs. Overall, the results indicate that increasing the number of AMAVs
significantly reduces ATE of BMAVs.

Impact of Number of BMAVs. Fig. 9b shows how different methods perform when
localizing varying numbers of BMAVs. As the number of BMAVs increases from 12
to 28, the ATE of all methods increases due to fewer percentage of BMAVs
passing through AMAVs. However, TransformLoc consistently achieves an ATE of
less than $1.2m$, which is more than 57% less than any other baselines. These
experimental results show that TransformLoc is able to allocate sensing
resources of AMAVs to provide observations for different numbers of BMAVs,
resulting in a low error.

Effectiveness of indicator. Fig. 9c shows the effectiveness of our indicator.
The indicator ($tr(\Sigma_{j,t})$) grows with ATE of BMAV, indicating that
this indicator reflects the extent of localization error.

##  VI Related Work

Multi-agent for environmental sensing. Advancements in AI have fueled
extensive research into multi-agent systems, harnessing their parallel
operational pipelines and coordinated complementarity to improve sensing
coverage and reduce time requirements for sensing tasks [5]. Agents in these
systems can integrate various sensors, such as cameras [31], Radar [22], Lidar
[32], IMU [20], acoustic sensors [19], and gas sensors [33]. This versatility
enables the execution of diverse sensing tasks, including urban monitoring
[34, 35], hazardous gas sourcing [36], and post-disaster data communication
[37]. The data collected by these agents is shared through communication
channels, providing insights into the agents’ tasks and individual states,
including motion policies [38, 39].

Localization and navigation of MAV swarm. In the realm of sensing tasks,
precise localization and navigation play a pivotal role in facilitating
effective collaboration among MAV swarms, particularly given the inherent
constraints in computing, communication, and sensing capabilities of
individual MAVs [40]. Simultaneous Localization and Mapping (SLAM) stands out
as the most widely employed method [41]. This method entails outfitting MAVs
with a suite of sensors, including RGB cameras, LiDAR, and depth cameras, to
gather information about the environment and their own states. Subsequently,
navigation algorithms are deployed to guide MAVs to their intended
destinations [15, 42]. While collaborative SLAM utilizing multiple MAVs has
been investigated in prior studies [31], the prohibitive cost of sensors
imposes limitations on the scalability of MAV swarms [11]. In response to this
challenge, approaches centered on external infrastructure have been proposed.
For instance, radio frequency-based localization offers high accuracy at a
relatively low cost of sensors [14]. However, these approaches rely on the
presence of additional installed localization infrastructure, presenting
challenges in environments where localization infrastructure may have been
destroyed or where such installations are impractical, especially in hazardous
conditions [43].

To address these constraints, we propose a collaborative and adaptive
localization framework, named TransformLoc , for a heterogeneous MAV swarm.
Within this framework, a group of AMAVs serves as mobile localization
infrastructure, collaboratively sharing sensing and computing capabilities
with a larger number of BMAVs. This cooperative approach enables precise
localization for a MAV swarm at a more economical cost.

##  VII Discussion

We delve into several influential factors of TransformLoc.

$\bullet$ Communication Load: The BMAV transmits location estimates (mean and
covariance) to AMAVs, and AMAV transmits motion commands to BMAVs. When
catering to twenty BMAVs, an AMAV both receives and transmits less than 10KB
of data every $\delta$ seconds. During grouping, an AMAV gathers location
information from others and transmits grouping results to others. with twenty
AMAVs, the data volume stays below 10KB. In summary, the communication load is
deemed manageable.

$\bullet$ Localization accuracy of AMAV: The system improves the localization
accuracy of BMAVs when the localization error of AMAVs is less than 10cm.
Achieving this level of accuracy is easily feasible by outfitting an AMAV with
a Lidar or depth camera and employing SLAM methods, such as VINS (Visual-
Inertial Navigation System).

##  VIII Conclusion

In this paper, we propose the design of TransformLoc, a new framework that
transforms AMAVs into mobile localization infrastructures. The innovation of
TransformLoc lies in two aspects: 1) we derive an error-aware joint location
estimation model to integrate inaccurate estimation from BMAVs with
observations from AMAVs to perform joint location estimation of BMAVs,
assisted by an uncertainty-aided inference method; and 2) we design a
proximity-driven adaptive grouping-scheduling strategy to dynamically allocate
AMAVs’ sensing resources to assist BMAVs. The evaluation through in-field
experiments and large-scale physical feature-based simulations demonstrate the
superior performance of the TransformLoc.

##  IX ACKNOWLEDGMENTS

This paper was supported by the National Key R&D program of China No.
2022YFC3300703, the Natural Science Foundation of China under Grant No.
62371269. Guangdong Innovative and Entrepreneurial Research Team Program No.
2021ZT09L197, Shenzhen 2022 Stabilization Support Program No.
WDZC20220811103500001, and Tsinghua Shenzhen International Graduate School
Cross-disciplinary Research and Innovation Fund Research Plan No. JC20220011.
We acknowledge the support from the Tsinghua Shenzhen International Graduate
School-Shenzhen Pengrui Endowed Professorship Scheme of Shenzhen Pengrui
Foundation.

##  Appendix A Key definitions

###  A-A Environmental Description

Let $\Omega$ be a bounded space in $\mathbb{R}^{3}$ with length, width, and
height $L$, $W$, and $H$, respectively, where the heterogeneous MAV swarm
operates. This swarm comprises a fixed number of BMAVs and AMAVs that operate
independently. For simplicity, we assume that both types of MAVs operate at
the same altitude in this paper.

###  A-B State model of AMAV

The heterogeneous MAV swarm contains $M$ ($M\textgreater 1$) AMAVs. The state
of each AMAV $A_{j}$ at time $t$ consists of the location and the motion
command. The location is denoted as
$\boldsymbol{x_{j,t}}=(x_{j,t}^{1},x_{j,t}^{2},\phi_{j,t})$, where
$\phi_{j,t}$ is the orient angle. The distance between two locations is
$d_{\chi}$. For motion command, $\boldsymbol{u_{j,t}}=(u_{j,t},\omega_{j,t})$,
where $u_{j,t}$ and $\omega_{j,t}$ are the translational and rotational
velocities, respectively. The AMAVs estimate their location accurately with
advanced sensing capabilities and follow the motion model
$\boldsymbol{x_{j,t}}=f(\boldsymbol{x_{j,t-1}},\boldsymbol{u_{j,t-1}})$, which
can be represented as follows:

$\left(\begin{array}[]{c}x_{j,t}^{1}\\\ x_{j,t}^{2}\\\
\phi_{j,t}\end{array}\right)=\left(\begin{array}[]{c}x_{j,t-1}^{1}\\\
x_{j,t-1}^{2}\\\
\phi_{j,t-1}\end{array}\right)+\left(\begin{array}[]{c}u_{j,t-1}\cos\left(\phi_{j,t-1}\right)\\\
u_{j,t-1}\sin\left(\phi_{j,t-1}\right)\\\ \omega_{j,t-1}\end{array}\right).$
(3)

###  A-C State model of BMAV

The heterogeneous MAV swarm includes $N$ ($N\textgreater 1$) BMAVs. The state
of each BMAV $B_{i}$ at time $t$ consists of the location and the motion
command. The location of $B_{i}$ is
$\boldsymbol{y_{i,t}}=(y_{i,t}^{1},y_{i,t}^{2})$, and its motion command is
$\boldsymbol{v_{i,t}}=(v_{i,t}^{1},v_{i,t}^{2})$. $B_{i}$ follows double
integrator dynamics with Gaussian noise represented as follows:

$\begin{gathered}\left(\begin{array}[]{l}y_{i,t+\delta}^{1}\\\
y_{i,t+\delta}^{2}\end{array}\right)=\left(\begin{array}[]{l}y_{i,t}^{1}\\\
y_{i,t}^{2}\end{array}\right)+\delta\left(\begin{array}[]{l}v_{i,t}^{1}+n_{i,t}^{1}\\\
v_{i,t}^{2}+n_{i,t}^{2}\end{array}\right),\\\ \text{$n_{i,t}^{1}$ is drawn
from $p(n^{1})$,}\\\ \text{$n_{i,t}^{2}$ is drawn from
$p(n^{2})$,}\end{gathered}$ (4)

where $n_{i,t}^{1}$ and $n_{i,t}^{2}$ are drawn from motion noise models
$p(n^{1})$ and $p(n^{2})$ respectively, $\delta$ ($\delta>1$) denotes the time
interval between two commands. $p(n^{1})$ and $p(n^{2})$ empirically obtained
from the testbed are specified as normal distributions with mean $\mu=0$ and
variance $\sigma$, expressed as a percentage of $v_{i,t}^{1}$ and
$v_{i,t}^{2}$, same as outlined in [44]. The location estimation of $B_{i}$ is
denoted as $\boldsymbol{\widehat{y}_{i,t}}$, and the covariance matrix is
denoted as $\Sigma_{i,t}$. The noisy motion measurement from $B_{i}$’s IMU is
denoted as $\boldsymbol{\dot{v}_{i,t}}$.

###  A-D Observation model of AMAV

The observation angle of the visual sensor is denoted by $\phi$, and the FoV
of $A_{j}$ at time $t$ is defined as follows,

$\displaystyle F_{j,t}=\\{(x,y)\mid$ (5) $\displaystyle\quad\quad
0<\sqrt{\left(y-x_{j,t}^{2}\right)^{2}+\left(x-x_{j,t}^{1}\right)^{2}}<r_{m}\quad\bigcap$
$\displaystyle\quad-\frac{\phi}{2}<\arctan\left(\left(y-x_{j,t}^{2}\right)\left(x-x_{j,t}^{1}\right)\right)-\phi<\frac{\phi}{2}\\},$

where $r_{m}$ is the maximum distance that the sensor can observe, which is
limited by the observation technique.

When $B_{i}$ in the FoV of $A_{j}$ at time $t$, $A_{j}$ generates noisy
observation $z_{i,j,t}$ for $B_{i}$, which consists of range $r_{i,j,t}$ and
bearing $\alpha_{i,j,t}$ for $B_{i}$, both $r_{i,j,t}$ and $\alpha_{i,j,t}$
are relative to $A_{i}$,

$\begin{gathered}\begin{aligned}
z_{i,j,t}&=h(\boldsymbol{x_{j,t}},\boldsymbol{y_{i,t}})+\boldsymbol{n_{i,j,t}},\\\
h(\boldsymbol{x_{j,t}},\boldsymbol{y_{i,t}})&:=\left[\begin{array}[]{c}r_{i,j,t}\\\
\alpha_{i,j,t}\end{array}\right]\\\
&:=\left[\begin{array}[]{c}\sqrt{\left(y_{i,t}^{1}-x_{j,t}^{1}\right)^{2}+\left(y_{i,t}^{2}-x_{j,t}^{2}\right)^{2}}\\\
\arctan\left(\left(y_{i,t}^{2}-x_{j,t}^{2}\right)\left(y_{i,t}^{1}-x_{j,t}^{1}\right)\right)-\phi\end{array}\right]\\\
\boldsymbol{n_{i,j,t}}&:=[n_{i,j,t}^{r},n_{i,j,t}^{\alpha}]^{T}\end{aligned},\\\
\text{$n_{i,j,t}^{r}$ is drawn from $p(n^{r})$},\\\ \text{$n_{i,j,t}^{\alpha}$
is drawn from $p(n^{\alpha})$}.\end{gathered}$ (6)

The noise models for range and bearing measurements are denoted as $p(n^{r})$
and $p(n^{\alpha})$, respectively, and are empirically obtained from our
testbed. $p(n^{r})$ and $p(n^{\alpha})$ are specified as a normal distribution
with mean $\mu=0$ and variance $\sigma$, expressed as a percentage of
$r_{i,j,t}$ and $\alpha_{i,j,t}$.

###  A-E Linearization of Observation model

We compute the Jacobian matrix of $h(\boldsymbol{x},\boldsymbol{y})$ based on
Taylor expansion by taking the gradient with respect to the location
estimation of $\boldsymbol{y}$ to linearize the observation model,

$\displaystyle\nabla_{\boldsymbol{y}}h(\boldsymbol{x},\boldsymbol{y})$ (7)
$\displaystyle=\frac{1}{r(\boldsymbol{x},\boldsymbol{y})}\left[\begin{array}[]{cc}\left(y^{1}-x^{1}\right)&\left(y^{2}-x^{2}\right)\\\
-\sin\left(\phi+\alpha(\boldsymbol{x},\boldsymbol{y})\right)&\cos\left(\phi+\alpha(\boldsymbol{x},\boldsymbol{y})\right)\end{array}\right].$

To simplify notation, we let
$\boldsymbol{y_{t}}:={[\boldsymbol{y_{1,t}^{T}},\dots,\boldsymbol{y_{N,t}^{T}}]}^{T}$,
$\boldsymbol{x_{t}}:={[\boldsymbol{x_{1,t}^{T}},\dots,\boldsymbol{x_{M,t}^{T}}]}^{T}$,
$\boldsymbol{u_{t}}:={[\boldsymbol{u_{1,t}^{T}},\dots,\boldsymbol{u_{M,t}^{T}}]}^{T}$,
$\boldsymbol{\widehat{y}_{t}}:={[\boldsymbol{\widehat{y}_{1,t}^{T}},\dots,\boldsymbol{\widehat{y}_{N,t}^{T}}]}^{T}$,
${\Sigma_{t}}:={diag(\Sigma_{1,t}^{T},\dots,\Sigma_{N,t}^{T})}^{T}$.

##  Appendix B Problem Formulation

We aim to optimize the trace of the covariance of BMAVs’ location estimation
$\Sigma_{t}$ to limit the localization error within a finite time horizon $T$,
considering the motion commands of each AMAV within $T$. The mathematically
formulated sensing resource allocation problem is given by,

$\min_{\boldsymbol{u_{0}},\ldots,\boldsymbol{u_{T-1}}}\xi(T)=\sum_{t=1}^{T}\left(tr\left(\Sigma_{t}\right)\right),$
(8)

s.t.

$\displaystyle\boldsymbol{x_{t+1}}=f(\boldsymbol{x_{t}},\boldsymbol{u_{t}}),t\in\\{0,\dots,T-1\\}$
(9) $\displaystyle 0\leq x_{j,t}^{1},y_{i,t}^{1}\leq L,$ (10)
$\displaystyle\quad
j\in\\{0,\dots,N\\},i\in\\{0,\dots,M\\},t\in\\{0,\dots,T-1\\}$ $\displaystyle
0\leq x_{j,t}^{2},y_{i,t}^{2}\leq W,$ (11) $\displaystyle\quad
j\in\\{0,\dots,N\\},i\in\\{0,\dots,M\\},t\in\\{0,\dots,T-1\\}$
$\displaystyle\Sigma_{t+1}=\rho_{t+1}^{e}\left(\rho_{t}^{p}\left(\Sigma_{t}\right),\boldsymbol{x}_{t+1}\right),t\in\\{0,\dots,T-1\\}.$
(12)

$\rho_{t}^{e}$ and $\rho_{t+1}^{p}$ are correction and prediction steps, which
are described in Section III-B.

## References

  * [1] M. T. Rashid, D. Y. Zhang, and D. Wang, “Socialdrone: An integrated social media and drone sensing system for reliable disaster response,” in _Proceedings of the IEEE INFOCOM_ , 2020, pp. 218–227.
  * [2] K. McGuire, C. De Wagter, K. Tuyls, H. Kappen, and G. C. de Croon, “Minimal navigation solution for a swarm of tiny flying robots to explore an unknown environment,” _Science Robotics_ , vol. 4, no. 35, p. eaaw9710, 2019.
  * [3] A. Khochare, Y. Simmhan, F. B. Sorbelli, and S. K. Das, “Heuristic algorithms for co-scheduling of edge analytics and routes for uav fleet missions,” in _Processings of the IEEE INFOCOM_ , 2021, pp. 1–10.
  * [4] L. Bertizzolo, S. D’oro, L. Ferranti, L. Bonati, E. Demirors, Z. Guan, T. Melodia, and S. Pudlewski, “Swarmcontrol: An automated distributed control framework for self-optimizing drone networks,” in _Proceedings of the IEEE INFOCOM_ , 2020, pp. 1768–1777.
  * [5] Y. Wang, Z. Su, Q. Xu, R. Li, and T. H. Luan, “Lifesaving with rescuechain: Energy-efficient and partition-tolerant blockchain based secure information sharing for uav-aided disaster rescue,” in _Processings of the IEEE INFOCOM_ , 2021, pp. 1–10.
  * [6] J. Li, H. Kang, G. Sun, S. Liang, Y. Liu, and Y. Zhang, “Physical layer secure communications based on collaborative beamforming for uav networks: A multi-objective optimization approach,” in _Processings of the IEEE INFOCOM_ , 2021, pp. 1–10.
  * [7] “Global drones market outlook (2022-2032),” https://www.factmr.com/report/62/drone-market.
  * [8] C. Ruiz, X. Chen, L. Zhang, and P. Zhang, “Collaborative localization and navigation in heterogeneous uav swarms: Demo abstract,” in _Proceedings of the 14th ACM Sensys_ , 2016, pp. 324–325.
  * [9] X. Chen, A. Purohit, S. Pan, C. Ruiz, J. Han, Z. Sun, F. Mokaya, P. Tague, and P. Zhang, “Design experiences in minimalistic flying sensor node platform through sensorfly,” _ACM TOSN_ , vol. 13, no. 4, pp. 1–37, 2017.
  * [10] M. Burri, J. Nikolic, P. Gohl, T. Schneider, J. Rehder, S. Omari, M. W. Achtelik, and R. Siegwart, “The euroc micro aerial vehicle datasets,” _The International Journal of Robotics Research_ , vol. 35, no. 10, pp. 1157–1163, 2016.
  * [11] P. Schmuck and M. Chli, “Ccm-slam: Robust and efficient centralized collaborative monocular simultaneous localization and mapping for robotic teams,” _Journal of Field Robotics_ , vol. 36, no. 4, 2019.
  * [12] T. Li, S. Leng, Z. Wang, K. Zhang, and L. Zhou, “Intelligent resource allocation schemes for uav-swarm-based cooperative sensing,” _IEEE Internet of Things Journal_ , vol. 9, no. 21, pp. 21 570–21 582, 2022.
  * [13] A. Trotta, F. D. Andreagiovanni, M. Di Felice, E. Natalizio, and K. R. Chowdhury, “When uavs ride a bus: Towards energy-efficient city-scale video surveillance,” in _Processings of the IEEE INFOCOM_ , 2018, pp. 1043–1051.
  * [14] G. Chi, Z. Yang, J. Xu, C. Wu, J. Zhang, J. Liang, and Y. Liu, “Wi-drone: Wi-fi-based 6-dof tracking for indoor drone flight control,” in _Proceedings of the ACM MobiSys_ , 2022.
  * [15] J. Xu, H. Cao, D. Li, K. Huang, C. Qian, L. Shangguan, and Z. Yang, “Edge assisted mobile semantic visual slam,” in _Proceedings of the IEEE INFOCOM_ , April 27-30 2020.
  * [16] J. Sharp, C. Wu, and Q. Zeng, “Authentication for drone delivery through a novel way of using face biometrics,” in _Proceedings of the 28th ACM MobiCom_ , 2022, pp. 609–622.
  * [17] S. Xu, X. Chen, X. Pi, C. Joe-Wong, P. Zhang, and H. Y. Noh, “ilocus: Incentivizing vehicle mobility to optimize sensing distribution in crowd sensing,” _IEEE Transactions on Mobile Computing_ , vol. 19, no. 8, pp. 1831–1847, 2019.
  * [18] D. Li, J. Xu, Z. Yang, Y. Lu, Q. Zhang, and X. Zhang, “Train once, locate anytime for anyone: Adversarial learning based wireless localization,” in _Proceedings of the IEEE INFOCOM_ , May 10-13 2021.
  * [19] W. Wang, L. Mottola, Y. He, J. Li, Y. Sun, S. Li, H. Jing, and Y. Wang, “Micnest: Long-range instant acoustic localization of drones in precise landing,” in _Proceedings of the 20th ACM SenSys_ , 2022.
  * [20] X. Chen, A. Purohit, C. R. Dominguez, S. Carpin, and P. Zhang, “Drunkwalk: Collaborative and adaptive planning for navigation of micro-aerial sensor swarms,” in _Proceedings of the 13th ACM Sensys_ , 2015, pp. 295–308.
  * [21] Y. Sun, W. Wang, L. Mottola, R. Wang, and Y. He, “Aim: Acoustic inertial measurement for indoor drone localization and tracking,” in _Proceedings of the 20th ACM Sensys_ , 2022, pp. 476–488.
  * [22] C. X. Lu, M. R. U. Saputra, P. Zhao, Y. Almalioglu, P. P. De Gusmao, C. Chen, K. Sun, N. Trigoni, and A. Markham, “milliego: single-chip mmwave radar aided egomotion estimation via deep sensor fusion,” in _Proceedings of the 18th Sensys_ , 2020, pp. 109–122.
  * [23] E. Dong, J. Xu, C. Wu, Y. Liu, and Z. Yang, “Pair-navi: Peer-to-peer indoor navigation with mobile visual slam,” in _Proceedings of the IEEE INFOCOM_ , April 29-May 2 2019.
  * [24] J. Wang and E. Olson, “Apriltag 2: Efficient and robust fiducial detection,” in _Processings of the IEEE IROS_ , 2016, pp. 4193–4198.
  * [25] J. Xu, G. Chi, Z. Yang, D. Li, Q. Zhang, Q. Ma, and X. Miao, “Followupar: Enabling follow-up effects in mobile ar applications,” in _Proceedings of the ACM MobiSys_ , June 24-July 2 2021.
  * [26] D. Ucinski, _Optimal measurement methods for distributed parameter system identification_. CRC press, 2004.
  * [27] X. Zhang, A. Zhang, J. Sun, X. Zhu, Y. E. Guo, F. Qian, and Z. M. Mao, “Emp: Edge-assisted multi-vehicle perception,” in _Proceedings of the 27th ACM Mobicom_ , 2021, pp. 545–558.
  * [28] J. Borenstein, H. Everett, and L. Feng, _Navigating mobile robots: Systems and techniques_. AK Peters, Ltd., 1996.
  * [29] J. Xu, F. Zhong, and Y. Wang, “Learning multi-agent coordination for enhancing target coverage in directional sensor networks,” _Processings of the NeurIPS_ , vol. 33, pp. 10 053–10 064, 2020.
  * [30] H. Wang, X. Chen, Y. Cheng, C. Wu, F. Dang, and X. Chen, “H-swarmloc: Efficient scheduling for localization of heterogeneous mav swarm with deep reinforcement learning,” in _Proceedings of the 20th ACM Sensys_ , 2022, pp. 1148–1154.
  * [31] J. Xu, H. Cao, Z. Yang, L. Shangguan, J. Zhang, X. He, and Y. Liu, “Swarmmap: Scaling up real-time collaborative visual slam at the edge,” in _Proceedings of the USENIX NSDI_ , 2022, pp. 977–993.
  * [32] D. Li, J. Xu, Z. Yang, Q. Zhang, Q. Ma, L. Zhang, and P. Chen, “Motion inspires notion: self-supervised visual-lidar fusion for environment depth estimation,” in _Proceedings of the 20th MobiSys_ , 2022, pp. 114–127.
  * [33] J. Luo, Y. Hu, C. Yu, C. Hong, X.-P. Zhang, and X. Chen, “Field reconstruction-based non-rendezvous calibration for low cost mobile sensors,” in _Proceedings of the ACM Ubicomp_ , 2023, pp. 688–693.
  * [34] J. Guo, H. Wang, W. Liu, G. Huang, J. Gui, and S. Zhang, “A lightweight verifiable trust based data collection approach for sensor–cloud systems,” _Journal of Systems Architecture_ , vol. 119, p. 102219, 2021.
  * [35] X. Chen, H. Wang, Z. Li, W. Ding, F. Dang, C. Wu, and X. Chen, “Deliversense: Efficient delivery drone scheduling for crowdsensing with deep reinforcement learning,” in _Proceedings of the ACM Ubicomp_ , 2022, pp. 403–408.
  * [36] Y. Liu, X. Liu, F. Man, C. Wu, and X. Chen, “Fine-grained air pollution data enables smart living and efficient management,” in _Proceedings of the 20th ACM Sensys_ , 2022, pp. 768–769.
  * [37] J. Ren, Y. Xu, Z. Li, C. Hong, X.-P. Zhang, and X. Chen, “Scheduling uav swarm with attention-based graph reinforcement learning for ground-to-air heterogeneous data communication,” in _Proceedings of the ACM Ubicomp_ , 2023, pp. 670–675.
  * [38] X. Chen, S. Xu, X. Liu, X. Xu, H. Y. Noh, L. Zhang, and P. Zhang, “Adaptive hybrid model-enabled sensing system (hmss) for mobile fine-grained air pollution estimation,” _IEEE Transactions on Mobile Computing_ , vol. 21, no. 6, pp. 1927–1944, 2020.
  * [39] L. Zhou, S. Leng, Q. Liu, and Q. Wang, “Intelligent uav swarm cooperation for multiple targets tracking,” _IEEE Internet of Things Journal_ , vol. 9, no. 1, pp. 743–754, 2021.
  * [40] Z. Li, F. Man, X. Chen, B. Zhao, C. Wu, and X. Chen, “Tract: Towards large-scale crowdsensing with high-efficiency swarm path planning,” in _Proceedings of the ACM Ubicomp_ , 2022, pp. 409–414.
  * [41] R. Mur-Artal, J. M. M. Montiel, and J. D. Tardos, “Orb-slam: a versatile and accurate monocular slam system,” _IEEE transactions on robotics_ , vol. 31, no. 5, pp. 1147–1163, 2015.
  * [42] X. Zhou, X. Wen, Z. Wang, Y. Gao, H. Li, Q. Wang, T. Yang, H. Lu, Y. Cao, C. Xu _et al._ , “Swarm of micro flying robots in the wild,” _Science Robotics_ , vol. 7, no. 66, p. eabm5954, 2022.
  * [43] S. Kumar, S. Gil, D. Katabi, and D. Rus, “Accurate indoor localization with zero start-up cost,” in _Proceedings of the ACM MobiCom_ , 2014, pp. 483–494.
  * [44] X. Chen, C. Ruiz, S. Zeng, L. Gao, A. Purohit, S. Carpin, and P. Zhang, “H-drunkwalk: Collaborative and adaptive navigation for heterogeneous mav swarm,” _ACM Transactions on Sensor Networks_ , vol. 16, no. 2, pp. 1–27, 2020.


# Enhance Sketch Recognition’s Explainability via Semantic Component-Level
Parsing

Guangming Zhu1,2,3, Siyuan Wang1, Tianci Wu1, Liang
Zhang1,2,3,111Corresponding Author

###### Abstract

Free-hand sketches are appealing for humans as a universal tool to depict the
visual world. Humans can recognize varied sketches of a category easily by
identifying the concurrence and layout of the intrinsic semantic components of
the category, since humans draw free-hand sketches based a common consensus
that which types of semantic components constitute each sketch category. For
example, an airplane should at least have a fuselage and wings. Based on this
analysis, a semantic component-level memory module is constructed and embedded
in the proposed structured sketch recognition network in this paper. The
memory keys representing semantic components of each sketch category can be
self-learned and enhance the recognition network’s explainability. Our
proposed networks can deal with different situations of sketch recognition,
i.e., with or without semantic components labels of strokes. Experiments on
the SPG and SketchIME datasets demonstrate the memory module’s flexibility and
the recognition network’s explainability. The code and data are available at
https://github.com/GuangmingZhu/SketchESC.

## Introduction

Free-hand sketch is a universal tool to depict the visual world, and it is not
bound by age, race, language, geography, or national boundaries. Sketch images
are highly sparse, abstract and lack of background. Sketch can be regarded as
an expression of the human brain’s internal representation of the visual world
(Xu et al. 2022). Humans can recognize sketches and identify the intrinsic
semantic components easily, even sketches of the same category drawn by
different persons may be very different in appearance.

Sketch can be represented as an image in the static pixel space, as a time
series in the dynamic stroke coordinate space, or as a graph in the geometric
graph space. This results in various Convolutional Neural Network (CNN),
Recurrent Neural Network (RNN), and Graph Neural Network (GNN) based methods
for sketch recognition (Zhang et al. 2019; Xu et al. 2022). These methods
usually take image- or Scalable Vector Graphics (SVG)- format data as input,
and predict the category label for a given sketch sample. However, there is
lacking of work on interpreting the reason of giving such predictions.

Explainable artificial intelligence (XAI) has become a hot research topic to
explain models’ decision (Ramaswamy et al. 2020; Shitole et al. 2021; Garau et
al. 2022). Visualizing the activation maps of deep neural networks is widely
used in computer vision. However, sketch images composed of stroke lines
without textures, are different from natural images. This means that the
existing XAI methods cannot be applied directly in the sketch research field.
A first look at explainability for human sketches was achieved by SketchXAI
using the counterfactual explanation (Qu et al. 2023). The stroke location
inversion module in SketchXAI offers an explainability angle to sketch in
terms of asking a network how well it can recover stroke locations of an
unseen sketch. Liu et al. developed an image classifier explanation model
using the counterfactual maps, in which the counterfactual map generator
module is used to identify the critical structures for the specific category
(Liu et al. 2023).

Counterfactual explanation (CE), as a post-hoc explainability method, aims to
identify what are the minimal input changes for a model to make a different
visual decision (Van Looveren and Klaise 2021). SketchXAI (Qu et al. 2023)
used CE to relocate reshuffled strokes to construct a sketch given a category,
while Liu et al. designed a counterfactual map generator to discover the
stroke-level principal components for a specific category (Liu et al. 2023).
The above two methods try to explain the question of “why the sketch is
classified as X” by providing positive and negative semantic explanation
evidences. However, we believe that the concurrence and layout of the
intrinsic semantic components of a category can be a crucial evidence to
explain the question from another perspective. For example, taking into
consideration the common knowledge that an airplane should at least have a
fuselage and wings, if a sketch is composed of strokes which can be
semantically grouped into a fuselage and wings, it probably is an airplane. As
to the analysis above, we propose to enhance sketch recognition’s
explainability via semantic component-level parsing.

Specifically, a Semantic Component-level Memory (SCM) module is constructed,
whose memory keys represent the semantic components of different sketch
categories. The SCM module is embedded in a Structured Sketch Recognition
(SSR) network, and evolves the stroke features based on the similarity with
the learnable features of memory keys. The fused stroke-level or component-
level features are fed into a Transformer to achieve a high recognition
performance under the supervision on segmentation (if available) or
compositionality (i.e., which types of semantic components constitute each
sketch category). For the dataset with the category labels and the semantic
component labels of strokes, the supervision on the component-level parsing in
the SCM module and on the semantic segmentation results of the Transformer can
be used to achieve a precise and explainable recognition performance. For the
dataset only with category labels, the supervision on the compositionality can
be used in the proposed SSR network to enhance the recognition network’s
explainability. This flexibility makes the proposed SCM module and SSR network
applicable on sketch recognition and segmentation tasks and achieve better and
explainable performance.

The main contribution of this study can be summarized as follows.

  * •

A semantic component-level memory module is constructed, which can learn and
store memory keys representing semantic components, and do explainable parsing
from strokes to components.

  * •

A structured sketch recognition network is proposed, which has hierarchical
and explainable abilities, from stroke-level embedding, component-level
parsing to sketch-level recognition.

  * •

The proposed network is explainable and flexibility to deal with the sketch
recognition situations with or without semantic component labels of strokes,
and can achieve remarkable performance on the public datasets.

## Related Work

### Sketch Recognition

Sketches are generally represented as pixel-level rasterized images or ordered
sequences of point coordinates. Typically, CNNs (Yu et al. 2017; Prabhu et al.
2018), RNNs (Sarvadevabhatla and Kundu 2016; Ha and Eck 2017), or CNN-RNN
architectures (Xu et al. 2018; Li et al. 2020) were constructed for sketch
recognition. Recently, the trend from Euclidean (CNN, RNN based) to
topological analysis (GNN based) has emerged in sketch recognition. A sketch
can also be represented as the sparsely connected graphs in the topological
space. Therefore, GNN based models were proposed to model sketch’s local and
global topological stroke structures (Xu, Joshi, and Bresson 2021). There is
no consensus on which representation style is better than the other, as each
has its own merits based on the application scenarios. Rasterized images
ignore the sketching orders and are better for offline recognition. Sequence-
based representation can be used to continuously predict the labels using
accumulated sketch strokes online, and can be used in more interactive real-
time applications. Graph-based representation is flexible to encode local and
global geometric sketch structures, and can be used for sketch grouping or
segmentation. However, no matter which representation style is used, visual
explanation is rarely studied for sketch recognition.

### Visual Explanation

Various activation map visualization techniques, such as the Grad-CAM series
methods(Selvaraju et al. 2017; Chattopadhay et al. 2018; Omeiza et al. 2019),
have been widely researched to interpret the classifier’s decision-making
rationale. These methods highlight the essential regions, but the
explainability on sketch recognition is better to explore strokes’ effects on
recognition, therefore they are not suitable for sketch researches. Contrasted
to these pixel-level methods, patch-level methods tried to use representative
patches to explain the classifier’s prediction (Chen et al. 2019; Zhang et al.
2018; Ge et al. 2021). However, considering the surrounding or overlapping
between strokes of a sketch in the spatial layout, patches can not always
represent individual semantic components. Besides, explanation via
visualization is hard to understand for non-expert users.

Counterfactual explanation methods (Van Looveren and Klaise 2021; Miller 2019)
supplied alternative approaches to identify what are the minimal input changes
for a model to make a different visual decision. SketchXAI(Qu et al. 2023)
used CE to relocate reshuffled strokes to construct a sketch given a category,
while Liu et al. designed a counterfactual map generator to discover the
stroke-level principal components for a specific category (Liu et al. 2023).
These methods contribute the first exploration on sketch recognition’s
explainability in the stroke-level.

Humans draw free-hand sketches based a common consensus that which types of
semantic components constitute each sketch category. Strokes of a sketch can
be considered as abstract representation of the object’s shape, component, or
attributes. Therefore, since humans perceive the visual world by parsing
objects’ shape, components and attributes hierarchically and structurally, why
cannot sketch recognition networks enhance their explainability by identifying
the semantic components that strokes constitute. Alanize et al. constructed a
Primitive-Matching Network (PMN) to learn interpretable abstracts of a sketch
through simple primitives (Alaniz et al. 2022). Zhu et al. proposed a
simultaneous sketch recognition and segmentation (SketchRecSeg) network which
parses the semantic components at the same time when recognizing a sketch (Zhu
et al. 2023). However, PMN (Alaniz et al. 2022) only fulfills the matching
between strokes and primitives. SketchRecSeg (Zhu et al. 2023) uses a two-
stream architecture, but its segmentation stream cannot enhance its
recognition stream’s explainability. In this paper, we construct a semantic
component-level memory module and embed it in a structured recognition network
to enhance sketch recognition’s explainability.

## Methodology

We aim to construct a Structured Sketch Recognition (SSR) network which does
Stroke-Level Embedding on each stroke, implements Component-Level Parsing, and
fulfills explainable Sketch-Level Recognition, as shown in Fig. 1. For the
data with category labels and the semantic component labels of each stroke
(i.e., the scenario ① in Fig. 1), sketches can be recognized and semantically
segmented simultaneously. For the data only with category labels and the prior
knowledge about the intrinsic semantic components of each category (i.e., the
scenario ② in Fig. 1), sketches can be recognized with the auxiliary
constraint that which types of semantic components constitute each sketch
category. Both two scenarios result in sketch recognition results with the
auxiliary information about which types of semantic components constitute each
sketch sample. This enhances the sketch recognition network’s explainability.

Figure 1: Overview of the proposed Structured Sketch Recognition network. The
① indicates the scenario that the Semantic Component-Level Memory module feeds
the fused stroke-level features into Transformer for sketch recognition and
segmentation. The ② indicates the scenario that the fused component-level
features are fed into Transformer for sketch recognition and the probability
prediction on the existence of each type of semantic component.

### Stroke-Level Embedding

Formally, each sketch can be represented as an ordered sequence of strokes,
denoted as $\\{s_{1},s_{2},\cdots,s_{i},\cdots,s_{N}\\}$. Stroke $s_{i}$
consists of $k$ points, $\\{s_{i,1},s_{i,2},\cdots,s_{i,k-1},s_{i,k}\\}$, and
each point contains a two-dimensional coordinate value and a two-dimensional
binary pen state (Ha and Eck 2018). Three descriptors are learned to identify
three inherent properties of each sketch, i.e., shape $sh_{i}$, stroke order
$o_{i}$ and location $l_{i}$, as in SketchXAI (Qu et al. 2023). The location
of stroke $s_{i}$ is defined as the coordinate of the first point $s_{i,1}$.
Specifically, a bidirectional Long Short-Term Memory (LSTM) is used for the
shape embedding to extract shape information $sh_{i}$ of each stroke, a
learnable embedding is used for the order embedding $o_{i}$, and one linear
layer is used for the location embedding $l_{i}$. These three kinds of
embeddings are summed as the stroke embeddings.

### Component-Level Parsing

When a sketch is represented as a sparsely connected graph, the graph nodes
generally denote the stroke points, as in SketchGNN (Yang et al. 2021) and
MultiGraph Transformer (Xu, Joshi, and Bresson 2021). In this study, stroke
points have been aggregated in the stroke-level embedding stage, therefore a
stroke-level graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ can be constructed.
$\mathcal{V}$ denotes the graph node set, in which each node represents a
stroke. $\mathcal{E}$ denotes edges that connect adjacent strokes in sketching
order.

#### Dynamic Graph Convolution

The above stroke-level embedding does not involve inter-stroke feature fusion.
However, the semantic meaning of a stroke does not only depend on its shape
and location, but also depends on the context of strokes. Inter-stroke fusion
is necessary to learn which strokes constitute a semantic component. A two-
layer dynamic graph convolution (Yang et al. 2021) unit is used in our
network. The same graph convolution operation as in EdgeConv (Wang et al.
2019) is adopted. In order to enlarge the receptive field, $\mathcal{E}$ is
updated layer-by-layer using the Dilated k-NN (Li et al. 2019). The motivation
of updating $\mathcal{E}$ is to explore the feature fusion between strokes
which belong to the same semantic component but are not adjacent in sketching
order. The dilation ratios in the two layers are 1 and 2, respectively. A
residual connection exists in each graph convolution layer to sum the input
and output features.

#### Semantic Component-Level Memory

Memory augmented neural networks utilize external memory to explicitly access
the experiences (Khasahmadi et al. 2019). A Semantic Component-level Memory
(SCM) module can store the feature representation of semantic components, so
that a similarity metric can be implemented to associate strokes with the
semantic components to which they belong. In such case, strokes belonging to
the same semantic component can be fused further to get the component-level
features. Explainable similarity metrics ensure the explainability of the
semantic component-level parsing, and the category classifier can do
explainable inference, i.e., “The sketch is recognized as X because it is
composed of the semantic components which constitute X”.

Specifically, the SCM module consists of a multi-head array of memory keys.
Each semantic component is represented by a multi-head key in SCM. Given the
stroke feature $q_{i}$ outputted by the dynamic graph convolution module, we
use Eq. (1) as a kernel to measure the normalized similarity between the
stroke feature $q_{i}$ and the key $k_{j}$ of SCM as222The head index of
multi-head keys is omitted for simplicity :

$C_{i,j}=\frac{(\varepsilon+\|q_{i}-k_{j}\|^{2}/\tau)^{-\frac{\tau+1}{2}}}{\sum_{j^{\prime}}{(\varepsilon+\|q_{i}-k_{j^{\prime}}\|^{2}/\tau)^{-\frac{\tau+1}{2}}}},$
(1)

where $C_{i,j}$ is the normalized score between the stroke feature $q_{i}$ and
the memory key $k_{j}$ (representing the $j$-th type of semantic component),
$\tau$ is the degree of freedom, and $\varepsilon$ is a bias value which is
much smaller than the average of $\|q_{i}-k_{j}\|^{2}/\tau$. Memory keys are
learnable parameters and learned automatically during the network training
process.

A Max-pooling operation is implemented to select the most similar head from
the multi-head key of each semantic component for each stroke. For simplicity,
we use $C_{i,j}$ to represent the similarity between the stroke $q_{i}$ and
its most similar head key $k_{j}$ of the $j$-th type of semantic component in
the following description, and use $\mathbf{K}\in\mathcal{R}^{K\times d}$ to
represent the set of the most similar head key of each semantic component for
one stroke, where $K$ is the component type count. A Softmax operation is
further implemented along the $j$-dimension of $\\{C_{i,j}\\}$ to obtain the
normalized assignment matrix $\mathbf{C}\in\mathcal{R}^{N\times K}$, where $N$
is the stroke count.

Feature Fusion. Two feature fusion strategies are designed. One is the stroke-
level feature fusion, i.e., enhancing the stroke features by memory keys,
denoted as

$\mathbf{F}_{s}\in\mathcal{R}^{N\times
d}=(1-max_{j}(\mathbf{C}))\circ\mathbf{Q}+max_{j}(\mathbf{C})\circ\mathbf{C}*\mathbf{K}.$
(2)

The enhanced features $\mathbf{F}_{s}$ are further fed into Transformer for
sketch recognition and segmentation. The other is the component-level feature
fusion, i.e., generating component features by fusing stroke features and
memory keys,

$\mathbf{F}_{c}\in\mathcal{R}^{K\times
d}=(1-max_{j}(\mathbf{C}))\circ\mathbf{C}^{\top}*\mathbf{Q}+max_{j}(\mathbf{C})\circ\mathbf{K}.$
(3)

The component features $\mathbf{F}_{c}$ can be fed into Transformer for sketch
recognition along with the prediction on the existence of each type of
semantic component. In Eqs. (2) and (3), $\mathbf{Q}\in\mathcal{R}^{N\times
d}$ is the stroke features outputted by the dynamic graph convolution module,
$\circ$ is the broadcasting multiply operation, and $*$ is the matrix
multiplication operation. The balance ratio $max_{j}(\mathbf{C})$ means that
if a stroke can be assigned to a semantic component with a high confidence,
the key feature of the semantic component is more representative and better
used for sketch recognition.

Supervision on SCM. The keys in MemGNN are learned without extra supervision
(Khasahmadi et al. 2019). We believe that it is better to ensure keys’
distinguishability, since keys represent different types of semantic
components. Therefore, a linear classifier and a Cross-Entropy (CE) loss are
implemented in the SCM module as

$\mathcal{L}1=CE(f_{w1}(k_{j}),j).$ (4)

Besides, if the semantic component label of each stroke is available, a
supervision on the assignment matrix $\mathbf{C}$ can be implemented by a
balanced Binary Cross-Entropy (bBCE) loss as

$\displaystyle\mathcal{L}2$ $\displaystyle=bBCE(\mathbf{C},\mathbf{C}^{gt})$
(5)
$\displaystyle=\gamma_{n}\sum{C^{gt}_{i,j}C_{i,j}}+\gamma_{p}\sum{(1-C^{gt}_{i,j})(1-C_{i,j})},$

where the $(i,j)$-th value $C^{gt}_{i,j}$ in
$\mathbf{C}^{gt}\in\mathcal{R}^{N\times K}$ is 1 when the $i$-th stroke
belongs to the $j$-th type of semantic component, otherwise the value is 0.
The $\gamma_{n}$ and $\gamma_{p}$ denote the ratio of 0 and 1 in
$\mathbf{C}^{gt}$, respectively. The balance ratio $\gamma_{n}$ and
$\gamma_{p}$ prevent the $\mathbf{C}$ from being learned as all-zero, since
only one of $K$ elements in each row of $\mathbf{C}^{gt}$ is 1.

### Sketch-Level Recognition

The Transformer architecture in ViT (Dosovitskiy et al. 2020) is used for
sketch-level recognition. When taking the fused stroke-level features
$\mathbf{F}_{s}$ as input, the Transformer outputs the category label and the
semantic component label of each stroke. The classification ($\mathcal{L}4$)
and stroke-level semantic segmentation ($\mathcal{L}5$) losses can be denoted
as

$\mathcal{L}3=\underbrace{CE(f_{w2}(\mathbf{F}_{s}),y_{c})}_{\mathcal{L}4}+\lambda_{s}\underbrace{CE(f_{w3}(\mathbf{F}_{s}),\mathbf{y}_{s})}_{\mathcal{L}5},$
(6)

where $y_{c}$ is the ground-truth category label and $\mathbf{y}_{s}$ is the
ground-truth semantic component label of strokes.

When taking the fused component-level features $\mathbf{F}_{c}$ as input, the
Transformer outputs the category label and the prediction probability on the
existence of each semantic component in the sketch sample. The classification
($\mathcal{L}4$) and compositionality prediction ($\mathcal{L}6$) losses can
be denoted as

$\mathcal{L}3=\underbrace{CE(f_{w2}(\mathbf{F}_{s}),y_{c})}_{\mathcal{L}4}+\lambda_{c}\underbrace{bBCE(f_{w4}(\mathbf{F}_{c}),\mathbf{y}_{e})}_{\mathcal{L}6},$
(7)

where $\mathbf{y}_{e}$ indicates the existence or not of each type of semantic
component. $\mathbf{y}_{e}^{j}=1$ when the sketch sample should contain the
$j$-th type of semantic component, otherwise $\mathbf{y}_{e}^{j}=0$. The
component-level features $\mathbf{F}_{c}$ has fixed $K$ feature vectors, no
matter how many strokes are contained in the sketch sample. Therefore,
$\mathbf{y}_{e}$ is sparse, and a balanced binary cross-entropy loss is used
(denoted as $\mathcal{L}6$).

### Losses

The overall loss can be calculated as

$\mathcal{L}=\lambda_{1}\mathcal{L}1+\lambda_{2}\mathcal{L}2+\mathcal{L}3.$
(8)

$\mathcal{L}1$ ensures the distinguishability of the memory keys in SCM, and
it does not need the semantic component labels of keys or strokes.

$\mathcal{L}2$ works only when the dataset has the semantic component labels
of strokes. If not, the memory keys are learned without the direct supervision
on the assignment matrix $\mathbf{C}$.

$\mathcal{L}3$ in Eq. (6) works for sketch recognition and segmentation. If
the semantic component labels of strokes are unavailable but the prior
information about which types of semantic components constitute each sketch
category is known, $\mathcal{L}3$ in Eq. (7) can help the Transformer achieve
a better and explainable recognition performance.

## Experiments

### Datasets

The SPG dataset (Li et al. 2018) and SketchIME dataset (Zhu et al. 2023) are
used to verify the advantages of the proposed network. SPG was originally
constructed for sketch perceptual grouping, and the same 20 categories as in
SketchGNN (Yang et al. 2021) are used for evaluation. An average of 600
samples per category are used for training, while 100 samples for testing.
Total 87 types of semantic components are defined according to the original
labels in SPG to support our researches. SketchIME is a systematic dataset
comprising 374 specialized sketch categories. Total 139 types of semantic
components are defined. This study selects 56K samples which have category
labels and semantic component labels of strokes from the released 209K
samples. An average of 100 samples per sketch category are used for training,
while 50 samples for testing.

### Evaluation Metrics

The Top-1 accuracy (Acc@1) is used as the evaluation metric for sketch
recognition. SketchSegNet (Wu et al. 2018) and SketchGNN (Yang et al. 2021)
used point-based accuracy and component-based accuracy for sketch
segmentation. Since the proposed SSR network does predictions on strokes for
semantic segmentation directly, only the component-based accuracy (C-Metric)
which indicates the percentage of the correctly predicted strokes is used as
the evaluation metric for segmentation.

Available Labels | SCMFeat | w/ $\mathcal{L}2$ | w/ $\mathcal{L}5$ | w/ $\mathcal{L}6$ | Acc@1 | C-Metric
---|---|---|---|---|---|---
C-Labels Only |  $\mathbf{F}_{s}$ as Eq. (2) |  |  |  | 88.48 | -
$\mathbf{F}_{s}=\mathbf{C}*\mathbf{K}$ |  |  |  | 91.41 | -
$\mathbf{F}_{s}=\mathbf{Q}$ |  |  |  | 91.01 | -
C-Labels and Prior Info |  $\mathbf{F}_{c}$ as Eq. (3) |  |  |  | 92.02 | -
$\mathbf{F}_{c}=\mathbf{C}^{\top}*\mathbf{Q}$ |  |  |  | 90.71 | -
$\mathbf{F}_{c}$ as Eq. (3) |  |  | ✓ | 94.04 | -
$\mathbf{F}_{c}=\mathbf{C}^{\top}*\mathbf{Q}$ |  |  | ✓ | 94.55 | -
C-Labels and SC-Labels |  $\mathbf{F}_{s}$ as Eq. (2) | ✓ | ✓ |  | 95.81 | 90.12
$\mathbf{F}_{s}=\mathbf{C}*\mathbf{K}$ | ✓ | ✓ |  | 96.62 | 89.69
$\mathbf{F}_{s}=\mathbf{Q}$ | ✓ | ✓ |  | 96.67 | 89.42

Table 1: The sketch recognition and segmentation performance on the SPG
dataset under different configurations. “SCMFeat” denotes which kinds of
features are fed into Transformer by the SCM module. “C-Labels” means the
category labels, and “SC-Labels” denotes the semantic component labels of
strokes. “Prior Info” represents the prior information about which types of
semantic components constitute each sketch category. The losses $\mathcal{L}1$
and $\mathcal{L}4$ are always used, but $\mathcal{L}2$, $\mathcal{L}5$ and
$\mathcal{L}6$ may not be used when different labels are available.

### Network Details

In the stroke-level embedding module, a bidirectional LSTM layer takes a
sequence of 4-dimensional stroke points as input and outputs a 768-dimensional
shape embedding, a linear layer transforms a two-dimensional coordinate into a
768-dimensional location embedding, and the 768-dimensional order embedding is
learned by PyTorch’s nn.Embedding function. In the dynamic graph convolution
module, the number of neurons in each convolution layer is all 768. The same
Transformer as ViT-Base (Dosovitskiy et al. 2020) is used for sketch-level
recognition.

### Training Details

The learning rate is initialized to $3\times 10^{-4}$ with a batch size of
128. The Adam optimizer is used. Total 200 epochs are implemented for each
training. The $\tau$ in Eq. (1) is set to 1. The $\lambda_{1}$ and
$\lambda_{2}$ in Eq. (8) are set to 1 and 20, respectively. The $\lambda_{s}$
in Eq. (6) and the $\lambda_{c}$ in Eq. (7) are set to 10 empirically. The SSR
network is trained from scratch, except the Transformer module initialized
with the pretrained ViT-Base model from HuggingFace
333https://huggingface.co/. Our network is implemented by Pytorch and trained
on a single NVIDIA GTX 3090.

### Ablation Study

As aforementioned, the proposed SCM module and SSR network can deal with
different cases with or without semantic component labels of strokes. As
illustrated in Table 1, three cases which use different features and losses
are evaluated.

Firstly, when the category labels and semantic component labels of strokes are
available, the supervision on the assignment matrix $\mathbf{C}$ (i.e., “w/
$\mathcal{L}2$”) and on the prediction of the semantic component labels of
each stroke (i.e., “w/ $\mathcal{L}5$”) can be used. The multi-rows of the
case “C-Labels and SC-Labels” in Table 1 illustrate the evaluation results. No
matter which kinds features outputted by the SCM module are fed into
Transformer for recognition and segmentation, excellent performances are
achieved compared with the cases without semantic component labels of strokes.
“$\mathbf{F}_{s}=\mathbf{Q}$” means that the stroke features learned by the
dynamic graph convolution module are fed into Transformer, while
“$\mathbf{F}_{c}=\mathbf{C}*\mathbf{K}$” means that the transformed memory
keys are fed into Transformer. Both the two cases have achieve comparable
performance. This means the learned memory keys can represent the semantic
components effectively, although the memory keys are not calculated from the
stroke features directly. “$\mathbf{F}_{s}=\mathbf{Q}$” does not mean the SCM
module is excluded from the learning process, $\mathbf{Q}$ is still partially
updated according to the gradient propagation from the supervision on the
assignment matrix $\mathbf{C}$.

Secondly, when the semantic component labels of strokes are unavailable but
the prior information about which types of semantic components constitute each
sketch category is known, the prior information still can be used to enhance
recognition’s performance. The multi-rows of the case “C-Labels and Prior
Info” in Table 1 illustrate the evaluation results. In such case, the
supervision on the existence of each type of semantic component given a sketch
can be used (i.e., “w/ $\mathcal{L}6$”). The stroke features cannot be fed
into Transformer directly, since Transformer cannot be supervised on the
semantic component prediction for strokes. Therefore, the component-level
features transformed from the stroke features based on the assignment matrix
$\mathbf{C}$ are fed into Transformer. The four rows show that using the
supervision can improve recognition performance significantly (92.02% vs.
94.04% and 90.71% vs. 94.55%). It also makes the recognition explainable,
since Transformer can tell which types of semantic components are contained in
each sketch sample, although it does not know to which type of semantic
component each stroke belong.

Thirdly, when neither the semantic component labels of strokes nor the prior
information are available, the proposed network can still be used as a typical
recognition network, as illustrated in the case of “C-Labels Only” in Table 1.
Both the fused stroke-level features $\mathbf{F}_{s}$ (i.e., see the three
rows of the case of “C-Labels Only”) and the fused component-level features
$\mathbf{F}_{s}$ (i.e., see the top two rows of the case of “C-Labels and
Prior Info”) can be fed into Transformer which only does the prediction of
category labels. It is unsurprising that the performances are not so good,
since the memory keys are hard to learn without any extra supervision.

In conclusion, it is expected that more supervision can result in better
performance, and the proposed method gives a flexible and explainable
architecture to deal with sketch recognition with different auxiliary
information.

### Comparison with State-of-The-Art

Table 2 gives the comparison results with the state-of-the-art methods on the
SPG dataset. The proposed SSR network outperforms all the methods except
SketchRecSeg (Zhu et al. 2023). This is because SketchRecSeg is a two-stream
network which takes both image- and SVG-format data as input, but the proposed
SSR network only uses the SVG-format data. Besides, SketchSegNet (Wu et al.
2018), SketchGNN (Yang et al. 2021) and SketchRecSeg (Zhu et al. 2023) all
construct stroke point-level graphs and predict point-level segmentation
labels. The proposed SSR network uses a hierarchical and structural
architecture, stroke-level graphs are constructed and stroke-level predictions
are performed. Furthermore, the proposed SSR network can fulfill simultaneous
recognition and segmentation with the one-stream architecture, while
SketchRecSeg (Zhu et al. 2023) employs a two-stream architecture for
recognition and segmentation, respectively. These factors demonstrate the
superiority of the proposed SSR network.

Table 3 gives the comparison results on the selected SketchIME dataset which
has 374 categories and 139 types of semantic components. The proposed SSR
network still obtains the superior performance. This exactly demonstrates the
applicability on large-scale datasets.

Networks | Acc@1 | C-Metric
---|---|---
ViT (Dosovitskiy et al. 2020) | 76.21 | -
BiGRU (Chung et al. 2014) | 79.10 | -
ResNet18 (Xu et al. 2022) | 80.66 | -
MGT (Xu, Joshi, and Bresson 2021) | 91.05 | -
SketchSegNet (Wu et al. 2018) | - | 45.46
SketchGNN (Yang et al. 2021) | - | 87.86
SketchRecSeg (Zhu et al. 2023) | 97.47 | 91.65
SSR($\mathbf{F}_{s}$ as Eq. (2)) | 95.81 | 90.12
SSR($\mathbf{F}_{s}=\mathbf{C}*\mathbf{K}$) | 96.62 | 89.69
SSR($\mathbf{F}_{s}=\mathbf{Q}$) | 96.67 | 89.42

Table 2: Comparison with state-of-the-art methods on the SPG dataset. The
proposed SSR network using all the losses in Eq. (6) and Eq. (8).

Networks | Acc@1 | C-Metric
---|---|---
ViT (Dosovitskiy et al. 2020) | 22.02 | -
ResNet18 (Xu et al. 2022) | 89.01 | -
MGT (Xu, Joshi, and Bresson 2021) | 70.31 | -
SketchSegNet (Wu et al. 2018) | - | 61.78
SketchGNN (Yang et al. 2021) | - | 94.01
SSR($\mathbf{F}_{s}$ as Eq. (2)) | 89.88 | 94.59
SSR($\mathbf{F}_{s}=\mathbf{C}*\mathbf{K}$) | 87.92 | 94.43
SSR($\mathbf{F}_{s}=\mathbf{Q}$) | 91.48 | 94.91

Table 3: Comparison with state-of-the-art methods on the SketchIME dataset.
The proposed SSR network using all the losses in Eq. (6) and Eq. (8).

### Visualization

Figure 2 gives the visualization of semantic component features using t-SNE
(Van der Maaten and Hinton 2008) and some sketch samples. It can be concluded
from the feature visualization in Fig. 2(a) that, the classification
supervision on the memory keys of SCM ensures the distinguishability of the
keys, and the SCM module further enhances the distinguishability of the
strokes in the feature space. The memory mechanism can store the features of
semantic components using multi-head arrays, and outperforms the mechanisms
using classifiers to recognize the strokes’ label directly or using
Conditional Random Field (CRF) based methods (Yuan and Ji 2020) to learn
strokes’ clustering relationship. Figure 2(b) gives some sketch examples which
have indistinguishable semantic components in the stroke feature space but are
recognizable when considering the concurrence and layout of the semantic
components. The proposed SSR network uses the SCM module to evolve stroke
features in an explainable way, and uses Transformer to recognize the category
label and the semantic component labels of strokes (or probabilities on the
existence of each type of semantic component). This ensures the explainability
of sketch recognition via semantic component-level parsing.

Figure 3 displays the recognition and segmentation results of some wrongly
recognized sketch samples. It can be seen from Fig. 3 that these sketches are
wrongly recognized because their strokes are wrongly resolved. Eqs. (2) and
(3) show that the features fed into Transformer by the SCM module are
calculated based on the stroke features outputted by the dynamic graph
convolution module in an explainable way. Therefore, Transformer’s prediction
can be mapped into original strokes. This exactly demonstrates the
explainability of our sketch recognition network.

Figure 2: Visualization of semantic component features using t-SNE and some
sketch samples. Fig. 2(a) shows the feature visualization of the 87 types of
semantic components in SPG. Fig. 2(b) shows some sketch examples whose parts
of semantic components are indistinguishable in the feature space, but our SSR
network can do recognition and segmentation correctly. Figure 3: Examples of
wrongly-recognized sketches. The numbers around the strokes are the
groundtruth or predicted type indexes of semantic components.

## Discussion

Activation map visualization techniques are not suitable for sketch
recognition’s explainability in the stroke-level. Counterfactual explanation
based methods supply an alternative way, but SketchXAI (Qu et al. 2023) only
uses CE to explore the deserved layout of strokes of a sketch, and Liu et al.
use CE to discover the stroke-level principal components for a specific
category (Liu et al. 2023). They just partially answer the question of “why
the sketch is classified as X”. This study answers the question from a
perspective of semantic component-level parsing. Humans generally describe an
object using sentences about its components and attributes. If a consensus can
be reached that a sketch is represented structurally by some types of semantic
components and their layout, we can easily find the superiority of our
proposed network because the stroke-level embedding module can encode the
layout of strokes, and the SCM and Transformer modules have abilities to
resolve the semantic components. The proposed SSR network gains sketch
recognition’s explainability in a more understandable and explainable way.

## Conclusion

Deep learning based sketch recognition networks have achieved remarkable
performance that even beats humans. However, humans can explain “why the
sketch is classified as X” easily, while sketch recognition networks are
lacking of interpretable reasons of giving such predictions. This study tries
to explore sketch recognition’s explainability via semantic component-level
parsing. A semantic component-level memory module is constructed, which can
learn and store features of semantic components in multi-head arrays, and
parse the strokes in the component-level. A structured sketch recognition
network is proposed and equipped with the memory module. The network gives the
explanation “The sketch is recognized as X because it is composed of the
semantic components which constitute X”.

## Acknowledgments

This work is partially supported by the National Natural Science Foundation of
China under Grant No.62073252. and No.62072358.

## References

  * Alaniz et al. (2022) Alaniz, S.; Mancini, M.; Dutta, A.; Marcos, D.; and Akata, Z. 2022.  Abstracting sketches through simple primitives.  In _ECCV_ , 396–412.
  * Chattopadhay et al. (2018) Chattopadhay, A.; Sarkar, A.; Howlader, P.; and Balasubramanian, V. N. 2018.  Grad-CAM++: Generalized Gradient-Based Visual Explanations for Deep Convolutional Networks.  In _WACV_ , 839–847.
  * Chen et al. (2019) Chen, C.; Li, O.; Tao, D.; Barnett, A.; Rudin, C.; and Su, J. K. 2019.  This looks like that: deep learning for interpretable image recognition.  volume 32.
  * Chung et al. (2014) Chung, J.; Gulcehre, C.; Cho, K.; and Bengio, Y. 2014.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  _arXiv preprint arXiv:1412.3555_.
  * Dosovitskiy et al. (2020) Dosovitskiy, A.; Beyer, L.; Kolesnikov, A.; Weissenborn, D.; Zhai, X.; Unterthiner, T.; Dehghani, M.; Minderer, M.; Heigold, G.; Gelly, S.; et al. 2020\.  An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale.  In _ICLR_.
  * Garau et al. (2022) Garau, N.; Bisagno, N.; Sambugaro, Z.; and Conci, N. 2022.  Interpretable part-whole hierarchies and conceptual-semantic relationships in neural networks.  In _CVPR_ , 13689–13698.
  * Ge et al. (2021) Ge, Y.; Xiao, Y.; Xu, Z.; Zheng, M.; Karanam, S.; Chen, T.; Itti, L.; and Wu, Z. 2021.  A peek into the reasoning of neural networks: Interpreting with structural visual concepts.  In _CVPR_ , 2195–2204.
  * Ha and Eck (2017) Ha, D.; and Eck, D. 2017.  A neural representation of sketch drawings.  _arXiv preprint arXiv:1704.03477_.
  * Ha and Eck (2018) Ha, D.; and Eck, D. 2018.  A Neural Representation of Sketch Drawings.  In _ICLR_.
  * Khasahmadi et al. (2019) Khasahmadi, A. H.; Hassani, K.; Moradi, P.; Lee, L.; and Morris, Q. 2019.  Memory-Based Graph Networks.  In _ICLR_.
  * Li et al. (2019) Li, G.; Muller, M.; Thabet, A.; and Ghanem, B. 2019.  Deepgcns: Can gcns go as deep as cnns?  In _ICCV_ , 9267–9276.
  * Li et al. (2018) Li, K.; Pang, K.; Song, J.; Song, Y.-Z.; Xiang, T.; Hospedales, T. M.; and Zhang, H. 2018.  Universal sketch perceptual grouping.  In _ECCV_ , 582–597.
  * Li et al. (2020) Li, L.; Zou, C.; Zheng, Y.; Su, Q.; Fu, H.; and Tai, C.-L. 2020.  Sketch-R2CNN: an RNN-rasterization-CNN architecture for vector sketch recognition.  _IEEE TVCG_ , 27(9): 3745–3754.
  * Liu et al. (2023) Liu, S.; Li, J.; Zhang, H.; Xu, L.; and Cao, X. 2023.  Prediction with Visual Evidence: Sketch Classification Explanation via Stroke-Level Attributions.  _IEEE TIP_.
  * Miller (2019) Miller, T. 2019.  Explanation in artificial intelligence: Insights from the social sciences.  _Artificial intelligence_ , 267: 1–38.
  * Omeiza et al. (2019) Omeiza, D.; Speakman, S.; Cintas, C.; and Weldermariam, K. 2019.  Smooth Grad-CAM++: An Enhanced Inference Level Visualization Technique for Deep Convolutional Neural Network Models.  _arXiv preprint arXiv:1908.01224_.
  * Prabhu et al. (2018) Prabhu, A.; Batchu, V.; Munagala, S. A.; Gajawada, R.; and Namboodiri, A. 2018.  Distribution-aware binarization of neural networks for sketch recognition.  In _WACV_ , 830–838.
  * Qu et al. (2023) Qu, Z.; Gryaditskaya, Y.; Li, K.; Pang, K.; Xiang, T.; and Song, Y.-Z. 2023.  SketchXAI: A First Look at Explainability for Human Sketches.  In _CVPR_ , 23327–23337.
  * Ramaswamy et al. (2020) Ramaswamy, H. G.; et al. 2020.  Ablation-cam: Visual explanations for deep convolutional network via gradient-free localization.  In _WACV_ , 983–991.
  * Sarvadevabhatla and Kundu (2016) Sarvadevabhatla, R. K.; and Kundu, J. 2016.  Enabling my robot to play pictionary: Recurrent neural networks for sketch recognition.  In _ACM MM_ , 247–251.
  * Selvaraju et al. (2017) Selvaraju, R. R.; Cogswell, M.; Das, A.; Vedantam, R.; Parikh, D.; and Batra, D. 2017.  Grad-CAM: Visual Explanations from Deep Networks via Gradient-Based Localization.  In _ICCV_ , 618–626.
  * Shitole et al. (2021) Shitole, V.; Li, F.; Kahng, M.; Tadepalli, P.; and Fern, A. 2021.  One explanation is not enough: structured attention graphs for image classification.  volume 34, 11352–11363.
  * Van der Maaten and Hinton (2008) Van der Maaten, L.; and Hinton, G. 2008.  Visualizing data using t-SNE.  _JMLR_ , 9(11).
  * Van Looveren and Klaise (2021) Van Looveren, A.; and Klaise, J. 2021.  Interpretable counterfactual explanations guided by prototypes.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 650–665.
  * Wang et al. (2019) Wang, Y.; Sun, Y.; Liu, Z.; Sarma, S. E.; Bronstein, M. M.; and Solomon, J. M. 2019\.  Dynamic graph cnn for learning on point clouds.  _ACM TOG_ , 38(5): 1–12.
  * Wu et al. (2018) Wu, X.; Qi, Y.; Liu, J.; and Yang, J. 2018.  Sketchsegnet: A rnn model for labeling sketch strokes.  In _MLSP_ , 1–6.
  * Xu et al. (2022) Xu, P.; Hospedales, T. M.; Yin, Q.; Song, Y.-Z.; Xiang, T.; and Wang, L. 2022.  Deep learning for free-hand sketch: A survey.  _IEEE TPAMI_ , 45(1): 285–312.
  * Xu et al. (2018) Xu, P.; Huang, Y.; Yuan, T.; Pang, K.; Song, Y.-Z.; Xiang, T.; Hospedales, T. M.; Ma, Z.; and Guo, J. 2018.  Sketchmate: Deep hashing for million-scale human sketch retrieval.  In _CVPR_ , 8090–8098.
  * Xu, Joshi, and Bresson (2021) Xu, P.; Joshi, C. K.; and Bresson, X. 2021.  Multigraph transformer for free-hand sketch recognition.  _IEEE TNNLS_ , 33(10): 5150–5161.
  * Yang et al. (2021) Yang, L.; Zhuang, J.; Fu, H.; Wei, X.; Zhou, K.; and Zheng, Y. 2021.  Sketchgnn: Semantic sketch segmentation with graph neural networks.  _ACM TOG_ , 40(3): 1–13.
  * Yu et al. (2017) Yu, Q.; Yang, Y.; Liu, F.; Song, Y.-Z.; Xiang, T.; and Hospedales, T. M. 2017.  Sketch-a-net: A deep neural network that beats humans.  _IJCV_ , 122: 411–425.
  * Yuan and Ji (2020) Yuan, H.; and Ji, S. 2020.  Structpool: Structured graph pooling via conditional random fields.  In _ICLR_.
  * Zhang et al. (2018) Zhang, Q.; Cao, R.; Shi, F.; Wu, Y. N.; and Zhu, S.-C. 2018.  Interpreting CNN knowledge via an explanatory graph.  In _AAAI_ , 4454–4463.
  * Zhang et al. (2019) Zhang, X.; Li, X.; Liu, Y.; and Feng, F. 2019.  A survey on freehand sketch recognition and retrieval.  _IMAVIS_ , 89: 67–87.
  * Zhu et al. (2023) Zhu, G.; Wang, S.; Cheng, Q.; Wu, K.; Li, H.; and Zhang, L. 2023.  Sketch Input Method Editor: A Comprehensive Dataset and Methodology for Systematic Input Recognition.  In _ACM MM_.